source/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         int i;
 197
 198         /* if we have no destination, return an error */
 199         if (dest == NULL)
 200                 return False;
 201
 202         /* if the src handle is NULL, then copy 0x00 to
 203            the dest handle  */
 204         if (src == NULL)
 205         {
 206                 /* if POLICY_HND internals ever changes,
 207                    this will need to be fixed */
 208                 memset (dest->data, 0, POLICY_HND_SIZE);
 209                 return True;
 210         }
 211
 212         /* copy the src handle to the dest */
 213         for (i=0; i<POLICY_HND_SIZE; i++)
 214                 dest->data[i] = src->data[i];
 215
 216         return True;
 217 }
 218
 219 /***************************************************************
 220  Return True if the to RPC_HND_NODEs are eqivalent in value.
 221  Return False if they are not.  Since a POLICY_HND is really
 222  a UUID, two RPC_HND_NODES are considered to be the same if the
 223  POLICY_HND value matches.
 224
 225  No ordering betweeen the two is attempted.
 226  **************************************************************/
 227 BOOL compare_rpc_hnd_node(const RPC_HND_NODE *x,
 228                           const RPC_HND_NODE *y)
 229 {
 230         /* only compare valid nodes */
 231         if (x==NULL || y==NULL)
 232                 return FALSE;
 233
 234         /* if the POLICY_HND field(s) are ever changed, this
 235            will need to be updated.  Probably should be a set of
 236           support function for dealing with POLICY_HND */
 237         return (memcmp(x->hnd.data, y->hnd.data, POLICY_HND_SIZE) == 0);
 238 }
 239
 240 /***************************************************************
 241  associate a POLICY_HND with a cli_connection
 242  **************************************************************/
 243 BOOL RpcHndList_set_connection(const POLICY_HND *hnd,
 244                                struct cli_connection *con)
 245 {
 246
 247         RPC_HND_NODE    *node = NULL;
 248
 249         /* initialize the list if necessary */
 250         if (!hnds.initialized)
 251                 generic_list_init(&hnds);
 252
 253         /* allocate a node to insert */
 254         if ((node=(RPC_HND_NODE*)malloc(sizeof(RPC_HND_NODE))) == NULL)
 255         {
 256                 DEBUG(0, ("ERROR: Unable to allocate memory for an RPC_HND_NODE!\n"));
 257                 return False;
 258         }
 259
 260         /* fill in the RPC_HND_NODE */
 261         copy_policy_hnd (&node->hnd, hnd);
 262         node->cli = con;
 263
 264         /* insert the node into the list:
 265                 The 3rd parameter is set to 0 since we don't care
 266                 anything about the type field */
 267         return (generic_list_insert(&hnds, (void*)node, 0));
 268 }
 269
 270 /************************************************************************
 271  delete a POLICY_HND (and associated cli_connection) from the list
 272  ***********************************************************************/
 273 BOOL RpcHndList_del_connection(const POLICY_HND *hnd)
 274 {
 275         RPC_HND_NODE    node, *located;
 276
 277         /* return NULL if the list has not been initialized */
 278         if (!hnds.initialized)
 279                 return False;
 280
 281         /* fill in the RPC_HND_NODE */
 282         copy_policy_hnd (&node.hnd, hnd);
 283         node.cli = NULL;
 284
 285         /* search for the POLICY_HND */
 286         located = (RPC_HND_NODE*)generic_list_remove(&hnds, &node,
 287                   (BOOL(*)(const void*, const void*))compare_rpc_hnd_node);
 288         if (located == NULL)
 289                 return False;
 290
 291         /* delete the information */
 292         cli_connection_free(located->cli);
 293         free(located);
 294         return True;
 295 }
 296
 297 /************************************************************************
 298  search for a POLICY_HND and return a pointer to the associated
 299  cli_connection struct in the list
 300  **********************************************************************/
 301 struct cli_connection* RpcHndList_get_connection(const POLICY_HND *hnd)
 302 {
 303         RPC_HND_NODE    node, *located;
 304
 305         /* return NULL if the list has not been initialized */
 306         if (!hnds.initialized)
 307                 return NULL;
 308
 309         /* fill in the RPC_HND_NODE */
 310         copy_policy_hnd (&node.hnd, hnd);
 311         node.cli = NULL;
 312
 313         /* search for the POLICY_HND */
 314         located = (RPC_HND_NODE*)generic_list_locate(&hnds, &node,
 315                   (BOOL(*)(const void*, const void*))compare_rpc_hnd_node);
 316         if (located  == NULL)
 317                 return NULL;
 318         else
 319                 return located->cli;
 320 }
 321