source3/lib/util_list.c

   1 /*
   2    Unix SMB/Netbios implementation.
   3    Version 1.9.
   4    Samba utility functions
   5    Copyright (C) Andrew Tridgell                   1992-1999
   6    Copyright (C) Gerald Carter <jerry@samba.org>   2000
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21 */
  22
  23 /****************************************************************
  24  In order to make use of the GENERIC_LIST data structure, you
  25  should create wrapper functions around:
  26
  27         BOOL    generic_list_insert()
  28         void*   generic_list_remove()
  29         void*   generic_list_locate()
  30
  31  The reason this is necessary is that the GENERIC_LIST uses a
  32  void pointer to store your data structure.  This means that
  33  you get no type checking and can create a hetergenous list.
  34  However, you will need to have some way to determine the type
  35  of your data.  If you are using a homogenous list, then
  36  wrapper functions are the easiest way.  If you are creating
  37  a hetergenous list, then you will need to use the type field
  38  for your arbitrary identifiers.
  39
  40  TODO:
  41  If neccessary, you can add a few generic_list_*() to do things
  42  like grab from the front (to implement a FIFO queue) or from
  43  the tail (to implement a FILO stack)
  44  ****************************************************************/
  45
  46 #include "includes.h"
  47
  48
  49 /*
  50  * list variables
  51  */
  52 static GENERIC_LIST hnds;
  53
  54
  55 /****************************************************************
  56  Initialize the list.  This doesn't do much currently.  Just make
  57  sure that you call it so we can determine wether the list is
  58  empty or not.
  59  ****************************************************************/
  60 static void generic_list_init(GENERIC_LIST *l)
  61 {
  62
  63         l->head         = NULL;
  64         l->tail         = NULL;
  65         l->length       = 0;
  66         l->initialized  = True;
  67
  68         return;
  69 }
  70
  71
  72 /*****************************************************************
  73  Insert some data into the list (appended to the end of the list)
  74  *****************************************************************/
  75 static BOOL generic_list_insert(GENERIC_LIST *l,
  76                                 void *item, uint8 type)
  77 {
  78         /* check for an emtpy list first */
  79         if (l->length == 0)
  80         {
  81                 if ((l->head = malloc(sizeof(struct _list_node))) == NULL)
  82                 {
  83                         DEBUG(0, ("ERROR: out of memory!  Cannot allocate a list node!\n"));
  84                         return False;
  85                 }
  86                 l->head->data = item;
  87                 l->head->type = type;
  88                 l->head->next = NULL;
  89                 l->length++;
  90                 l->tail = l->head;
  91         }
  92
  93         /* we already have an existing list */
  94         else
  95         {
  96                 if ((l->tail->next = malloc(sizeof(struct _list_node))) == NULL)
  97                 {
  98                         DEBUG(0, ("ERROR: out of memory!  Cannot allocate a list node!\n"));
  99                         return False;
 100                 }
 101                 l->tail = l->tail->next;
 102                 l->tail->next = NULL;
 103                 l->tail->data = item;
 104                 l->tail->type = type;
 105                 l->length++;
 106         }
 107
 108         /* return the list pointer in case this was the first node */
 109         return True;
 110 }
 111
 112 /****************************************************************
 113  In order to locate an item in the list we need a pointer to
 114  a compare function for the data items.
 115
 116  We will return the actual pointer to the item in the list.  Not
 117  a copy of the item.
 118  ****************************************************************/
 119 static void* generic_list_locate (GENERIC_LIST *l, void *search,
 120                                   BOOL(*cmp)(const void*,const void*))
 121 {
 122         struct _list_node *item;
 123
 124         /* loop through the list in linear order */
 125         item = l->head;
 126         while (item != NULL)
 127         {
 128                 if (cmp(search, item->data))
 129                         return item->data;
 130                 else
 131                 {
 132                         item = item->next;
 133                 }
 134         }
 135
 136         return NULL;
 137 }
 138
 139
 140 /***************************************************************
 141  In order to remove a node from the list, we will need a pointer
 142  to a compare function.  The function will return a pointer to
 143  data in the removed node.
 144
 145  **WARNING** It is the responsibility of the caller to save
 146  the pointer and destroy the data.
 147  ***************************************************************/
 148  static void* generic_list_remove(GENERIC_LIST *l, void *search,
 149                                 BOOL(*cmp)(const void*,const void*))
 150 {
 151         struct _list_node       *item, *tag;
 152         void                    *data_ptr;
 153
 154         /* loop through the list in linear order */
 155         tag = NULL;
 156         item = l->head;
 157         while (item != NULL)
 158         {
 159                 /* did we find it?  If so remove the node */
 160                 if (cmp(search, item->data))
 161                 {
 162                         /* found, so remove the node */
 163
 164                         /* remove the first item in the list */
 165                         if (item == l->head)
 166                                 l->head = item->next;
 167                         /* remove from the middle or the end */
 168                         else
 169                                 tag->next = item->next;
 170
 171                         /* check to see if we need to update the tail */
 172                         if (l->tail == item)
 173                                 l->tail = tag;
 174
 175                         l->length--;
 176                         data_ptr = item->data;
 177                         free(item);
 178                         return data_ptr;
 179                 }
 180                 /* increment to the nbext node in the list */
 181                 else
 182                 {
 183                         tag = item;
 184                         item = item->next;
 185                 }
 186         }
 187
 188         return NULL;
 189 }
 190
 191 /**************************************************************
 192  copy a POLICY_HND
 193  *************************************************************/
 194 BOOL copy_policy_hnd (POLICY_HND *dest, const POLICY_HND *src)
 195 {
 196         /* if we have no destination, return an error */
 197         if (dest == NULL)
 198                 return False;
 199
 200         /* if the src handle is NULL, then copy 0x00 to
 201            the dest handle  */
 202         if (src == NULL)
 203         {
 204                 /* if POLICY_HND internals ever changes,
 205                    this will need to be fixed */
 206                 ZERO_STRUCTP(dest);
 207                 return True;
 208         }
 209
 210         *dest = *src;
 211         return True;
 212 }
 213
 214 /* -------------------------------------------------------------
 215         Functions to implement the RpcHandle list
 216  -------------------------------------------------------------- */
 217
 218
 219
 220 /***************************************************************
 221  Return True if the to RPC_HND_NODEs are eqivalent in value.
 222  Return False if they are not.  Since a POLICY_HND is really
 223  a UUID, two RPC_HND_NODES are considered to be the same if the
 224  POLICY_HND value matches.
 225
 226  No ordering betweeen the two is attempted.
 227  **************************************************************/
 228 BOOL compare_rpc_hnd_node(const RPC_HND_NODE *x,
 229                           const RPC_HND_NODE *y)
 230 {
 231         /* only compare valid nodes */
 232         if (x==NULL || y==NULL)
 233                 return FALSE;
 234
 235         /* if the POLICY_HND field(s) are ever changed, this
 236            will need to be updated.  Probably should be a set of
 237           support function for dealing with POLICY_HND */
 238         return (memcmp(&x->hnd, &y->hnd, sizeof(POLICY_HND)) == 0);
 239 }
 240
 241 /***************************************************************
 242  associate a POLICY_HND with a cli_connection
 243  **************************************************************/
 244 BOOL RpcHndList_set_connection(const POLICY_HND *hnd,
 245                                struct cli_connection *con)
 246 {
 247
 248         RPC_HND_NODE    *node = NULL;
 249
 250         /* initialize the list if necessary */
 251         if (!hnds.initialized)
 252                 generic_list_init(&hnds);
 253
 254         /* allocate a node to insert */
 255         if ((node=(RPC_HND_NODE*)malloc(sizeof(RPC_HND_NODE))) == NULL)
 256         {
 257                 DEBUG(0, ("ERROR: Unable to allocate memory for an RPC_HND_NODE!\n"));
 258                 return False;
 259         }
 260
 261         /* fill in the RPC_HND_NODE */
 262         copy_policy_hnd (&node->hnd, hnd);
 263         node->cli = con;
 264
 265         /* insert the node into the list:
 266                 The 3rd parameter is set to 0 since we don't care
 267                 anything about the type field */
 268         return (generic_list_insert(&hnds, (void*)node, 0));
 269 }
 270
 271 /************************************************************************
 272  delete a POLICY_HND (and associated cli_connection) from the list
 273  ***********************************************************************/
 274 BOOL RpcHndList_del_connection(const POLICY_HND *hnd)
 275 {
 276         RPC_HND_NODE    node, *located;
 277
 278         /* return NULL if the list has not been initialized */
 279         if (!hnds.initialized)
 280                 return False;
 281
 282         /* fill in the RPC_HND_NODE */
 283         copy_policy_hnd (&node.hnd, hnd);
 284         node.cli = NULL;
 285
 286         /* search for the POLICY_HND */
 287         located = (RPC_HND_NODE*)generic_list_remove(&hnds, &node,
 288                   (BOOL(*)(const void*, const void*))compare_rpc_hnd_node);
 289         if (located == NULL)
 290                 return False;
 291
 292         /* delete the information */
 293         cli_connection_free(located->cli);
 294         free(located);
 295         return True;
 296 }
 297
 298 /************************************************************************
 299  search for a POLICY_HND and return a pointer to the associated
 300  cli_connection struct in the list
 301  **********************************************************************/
 302 struct cli_connection* RpcHndList_get_connection(const POLICY_HND *hnd)
 303 {
 304         RPC_HND_NODE    node, *located;
 305
 306         /* return NULL if the list has not been initialized */
 307         if (!hnds.initialized)
 308                 return NULL;
 309
 310         /* fill in the RPC_HND_NODE */
 311         copy_policy_hnd (&node.hnd, hnd);
 312         node.cli = NULL;
 313
 314         /* search for the POLICY_HND */
 315         located = (RPC_HND_NODE*)generic_list_locate(&hnds, &node,
 316                   (BOOL(*)(const void*, const void*))compare_rpc_hnd_node);
 317         if (located  == NULL)
 318                 return NULL;
 319         else
 320                 return located->cli;
 321 }
 322
 323