contrib/cvs/src/hash.c

   1 /*
   2  * Copyright (c) 1992, Brian Berliner and Jeff Polk
   3  *
   4  * You may distribute under the terms of the GNU General Public License as
   5  * specified in the README file that comes with the CVS source distribution.
   6  *
   7  * Polk's hash list manager.  So cool.
   8  */
   9
  10 #include "cvs.h"
  11 #include <assert.h>
  12
  13 /* Global caches.  The idea is that we maintain a linked list of "free"d
  14    nodes or lists, and get new items from there.  It has been suggested
  15    to use an obstack instead, but off the top of my head, I'm not sure
  16    that would gain enough to be worth worrying about.  */
  17 static List *listcache = NULL;
  18 static Node *nodecache = NULL;
  19
  20 static void freenode_mem PROTO((Node * p));
  21
  22 /* hash function */
  23 static int
  24 hashp (key)
  25     const char *key;
  26 {
  27     unsigned int h = 0;
  28     unsigned int g;
  29
  30     assert(key != NULL);
  31
  32     while (*key != 0)
  33     {
  34         unsigned int c = *key++;
  35         /* The FOLD_FN_CHAR is so that findnode_fn works.  */
  36         h = (h << 4) + FOLD_FN_CHAR (c);
  37         if ((g = h & 0xf0000000) != 0)
  38             h = (h ^ (g >> 24)) ^ g;
  39     }
  40
  41     return (h % HASHSIZE);
  42 }
  43
  44 /*
  45  * create a new list (or get an old one from the cache)
  46  */
  47 List *
  48 getlist ()
  49 {
  50     int i;
  51     List *list;
  52     Node *node;
  53
  54     if (listcache != NULL)
  55     {
  56         /* get a list from the cache and clear it */
  57         list = listcache;
  58         listcache = listcache->next;
  59         list->next = (List *) NULL;
  60         for (i = 0; i < HASHSIZE; i++)
  61             list->hasharray[i] = (Node *) NULL;
  62     }
  63     else
  64     {
  65         /* make a new list from scratch */
  66         list = (List *) xmalloc (sizeof (List));
  67         memset ((char *) list, 0, sizeof (List));
  68         node = getnode ();
  69         list->list = node;
  70         node->type = HEADER;
  71         node->next = node->prev = node;
  72     }
  73     return (list);
  74 }
  75
  76 /*
  77  * free up a list
  78  */
  79 void
  80 dellist (listp)
  81     List **listp;
  82 {
  83     int i;
  84     Node *p;
  85
  86     if (*listp == (List *) NULL)
  87         return;
  88
  89     p = (*listp)->list;
  90
  91     /* free each node in the list (except header) */
  92     while (p->next != p)
  93         delnode (p->next);
  94
  95     /* free any list-private data, without freeing the actual header */
  96     freenode_mem (p);
  97
  98     /* free up the header nodes for hash lists (if any) */
  99     for (i = 0; i < HASHSIZE; i++)
 100     {
 101         if ((p = (*listp)->hasharray[i]) != (Node *) NULL)
 102         {
 103             /* put the nodes into the cache */
 104 #ifndef NOCACHE
 105             p->type = NT_UNKNOWN;
 106             p->next = nodecache;
 107             nodecache = p;
 108 #else
 109             /* If NOCACHE is defined we turn off the cache.  This can make
 110                it easier to tools to determine where items were allocated
 111                and freed, for tracking down memory leaks and the like.  */
 112             free (p);
 113 #endif
 114         }
 115     }
 116
 117     /* put it on the cache */
 118 #ifndef NOCACHE
 119     (*listp)->next = listcache;
 120     listcache = *listp;
 121 #else
 122     free ((*listp)->list);
 123     free (*listp);
 124 #endif
 125     *listp = (List *) NULL;
 126 }
 127
 128 /*
 129  * get a new list node
 130  */
 131 Node *
 132 getnode ()
 133 {
 134     Node *p;
 135
 136     if (nodecache != (Node *) NULL)
 137     {
 138         /* get one from the cache */
 139         p = nodecache;
 140         nodecache = p->next;
 141     }
 142     else
 143     {
 144         /* make a new one */
 145         p = (Node *) xmalloc (sizeof (Node));
 146     }
 147
 148     /* always make it clean */
 149     memset ((char *) p, 0, sizeof (Node));
 150     p->type = NT_UNKNOWN;
 151
 152     return (p);
 153 }
 154
 155 /*
 156  * remove a node from it's list (maybe hash list too) and free it
 157  */
 158 void
 159 delnode (p)
 160     Node *p;
 161 {
 162     if (p == (Node *) NULL)
 163         return;
 164
 165     /* take it out of the list */
 166     p->next->prev = p->prev;
 167     p->prev->next = p->next;
 168
 169     /* if it was hashed, remove it from there too */
 170     if (p->hashnext != (Node *) NULL)
 171     {
 172         p->hashnext->hashprev = p->hashprev;
 173         p->hashprev->hashnext = p->hashnext;
 174     }
 175
 176     /* free up the storage */
 177     freenode (p);
 178 }
 179
 180 /*
 181  * free up the storage associated with a node
 182  */
 183 static void
 184 freenode_mem (p)
 185     Node *p;
 186 {
 187     if (p->delproc != (void (*) ()) NULL)
 188         p->delproc (p);                 /* call the specified delproc */
 189     else
 190     {
 191         if (p->data != NULL)            /* otherwise free() it if necessary */
 192             free (p->data);
 193     }
 194     if (p->key != NULL)                 /* free the key if necessary */
 195         free (p->key);
 196
 197     /* to be safe, re-initialize these */
 198     p->key = p->data = NULL;
 199     p->delproc = (void (*) ()) NULL;
 200 }
 201
 202 /*
 203  * free up the storage associated with a node and recycle it
 204  */
 205 void
 206 freenode (p)
 207     Node *p;
 208 {
 209     /* first free the memory */
 210     freenode_mem (p);
 211
 212     /* then put it in the cache */
 213 #ifndef NOCACHE
 214     p->type = NT_UNKNOWN;
 215     p->next = nodecache;
 216     nodecache = p;
 217 #else
 218     free (p);
 219 #endif
 220 }
 221
 222 /*
 223  * Link item P into list LIST before item MARKER.  If P->KEY is non-NULL and
 224  * that key is already in the hash table, return -1 without modifying any
 225  * parameter.
 226  *
 227  * return 0 on success
 228  */
 229 int
 230 insert_before (list, marker, p)
 231     List *list;
 232     Node *marker;
 233     Node *p;
 234 {
 235     if (p->key != NULL)                 /* hash it too? */
 236     {
 237         int hashval;
 238         Node *q;
 239
 240         hashval = hashp (p->key);
 241         if (list->hasharray[hashval] == NULL)   /* make a header for list? */
 242         {
 243             q = getnode ();
 244             q->type = HEADER;
 245             list->hasharray[hashval] = q->hashnext = q->hashprev = q;
 246         }
 247
 248         /* put it into the hash list if it's not already there */
 249         for (q = list->hasharray[hashval]->hashnext;
 250              q != list->hasharray[hashval]; q = q->hashnext)
 251         {
 252             if (strcmp (p->key, q->key) == 0)
 253                 return (-1);
 254         }
 255         q = list->hasharray[hashval];
 256         p->hashprev = q->hashprev;
 257         p->hashnext = q;
 258         p->hashprev->hashnext = p;
 259         q->hashprev = p;
 260     }
 261
 262     p->next = marker;
 263     p->prev = marker->prev;
 264     marker->prev->next = p;
 265     marker->prev = p;
 266
 267     return (0);
 268 }
 269
 270 /*
 271  * insert item p at end of list "list" (maybe hash it too) if hashing and it
 272  * already exists, return -1 and don't actually put it in the list
 273  *
 274  * return 0 on success
 275  */
 276 int
 277 addnode (list, p)
 278     List *list;
 279     Node *p;
 280 {
 281   return insert_before (list, list->list, p);
 282 }
 283
 284 /*
 285  * Like addnode, but insert p at the front of `list'.  This bogosity is
 286  * necessary to preserve last-to-first output order for some RCS functions.
 287  */
 288 int
 289 addnode_at_front (list, p)
 290     List *list;
 291     Node *p;
 292 {
 293   return insert_before (list, list->list->next, p);
 294 }
 295
 296 /* Look up an entry in hash list table and return a pointer to the
 297    node.  Return NULL if not found.  Abort with a fatal error for
 298    errors.  */
 299 Node *
 300 findnode (list, key)
 301     List *list;
 302     const char *key;
 303 {
 304     Node *head, *p;
 305
 306     /* This probably should be "assert (list != NULL)" (or if not we
 307        should document the current behavior), but only if we check all
 308        the callers to see if any are relying on this behavior.  */
 309     if ((list == (List *) NULL))
 310         return ((Node *) NULL);
 311
 312     assert (key != NULL);
 313
 314     head = list->hasharray[hashp (key)];
 315     if (head == (Node *) NULL)
 316         /* Not found.  */
 317         return ((Node *) NULL);
 318
 319     for (p = head->hashnext; p != head; p = p->hashnext)
 320         if (strcmp (p->key, key) == 0)
 321             return (p);
 322     return ((Node *) NULL);
 323 }
 324
 325 /*
 326  * Like findnode, but for a filename.
 327  */
 328 Node *
 329 findnode_fn (list, key)
 330     List *list;
 331     const char *key;
 332 {
 333     Node *head, *p;
 334
 335     /* This probably should be "assert (list != NULL)" (or if not we
 336        should document the current behavior), but only if we check all
 337        the callers to see if any are relying on this behavior.  */
 338     if (list == (List *) NULL)
 339         return ((Node *) NULL);
 340
 341     assert (key != NULL);
 342
 343     head = list->hasharray[hashp (key)];
 344     if (head == (Node *) NULL)
 345         return ((Node *) NULL);
 346
 347     for (p = head->hashnext; p != head; p = p->hashnext)
 348         if (fncmp (p->key, key) == 0)
 349             return (p);
 350     return ((Node *) NULL);
 351 }
 352
 353 /*
 354  * walk a list with a specific proc
 355  */
 356 int
 357 walklist (list, proc, closure)
 358     List *list;
 359     int (*proc) PROTO ((Node *, void *));
 360     void *closure;
 361 {
 362     Node *head, *p;
 363     int err = 0;
 364
 365     if (list == NULL)
 366         return (0);
 367
 368     head = list->list;
 369     for (p = head->next; p != head; p = p->next)
 370         err += proc (p, closure);
 371     return (err);
 372 }
 373
 374 int
 375 list_isempty (list)
 376     List *list;
 377 {
 378     return list == NULL || list->list->next == list->list;
 379 }
 380
 381 static int (*client_comp) PROTO ((const Node *, const Node *));
 382 static int qsort_comp PROTO ((const void *, const void *));
 383
 384 static int
 385 qsort_comp (elem1, elem2)
 386     const void *elem1;
 387     const void *elem2;
 388 {
 389     Node **node1 = (Node **) elem1;
 390     Node **node2 = (Node **) elem2;
 391     return client_comp (*node1, *node2);
 392 }
 393
 394 /*
 395  * sort the elements of a list (in place)
 396  */
 397 void
 398 sortlist (list, comp)
 399     List *list;
 400     int (*comp) PROTO ((const Node *, const Node *));
 401 {
 402     Node *head, *remain, *p, **array;
 403     int i, n;
 404
 405     if (list == NULL)
 406         return;
 407
 408     /* save the old first element of the list */
 409     head = list->list;
 410     remain = head->next;
 411
 412     /* count the number of nodes in the list */
 413     n = 0;
 414     for (p = remain; p != head; p = p->next)
 415         n++;
 416
 417     /* allocate an array of nodes and populate it */
 418     array = (Node **) xmalloc (sizeof(Node *) * n);
 419     i = 0;
 420     for (p = remain; p != head; p = p->next)
 421         array[i++] = p;
 422
 423     /* sort the array of nodes */
 424     client_comp = comp;
 425     qsort (array, n, sizeof(Node *), qsort_comp);
 426
 427     /* rebuild the list from beginning to end */
 428     head->next = head->prev = head;
 429     for (i = 0; i < n; i++)
 430     {
 431         p = array[i];
 432         p->next = head;
 433         p->prev = head->prev;
 434         p->prev->next = p;
 435         head->prev = p;
 436     }
 437
 438     /* release the array of nodes */
 439     free (array);
 440 }
 441
 442 /*
 443  * compare two files list node (for sort)
 444  */
 445 int
 446 fsortcmp (p, q)
 447     const Node *p;
 448     const Node *q;
 449 {
 450     return (strcmp (p->key, q->key));
 451 }
 452
 453 /* Debugging functions.  Quite useful to call from within gdb. */
 454
 455 static char *nodetypestring PROTO ((Ntype));
 456
 457 static char *
 458 nodetypestring (type)
 459     Ntype type;
 460 {
 461     switch (type) {
 462     case NT_UNKNOWN:    return("UNKNOWN");
 463     case HEADER:        return("HEADER");
 464     case ENTRIES:       return("ENTRIES");
 465     case FILES:         return("FILES");
 466     case LIST:          return("LIST");
 467     case RCSNODE:       return("RCSNODE");
 468     case RCSVERS:       return("RCSVERS");
 469     case DIRS:          return("DIRS");
 470     case UPDATE:        return("UPDATE");
 471     case LOCK:          return("LOCK");
 472     case NDBMNODE:      return("NDBMNODE");
 473     case FILEATTR:      return("FILEATTR");
 474     case VARIABLE:      return("VARIABLE");
 475     case RCSFIELD:      return("RCSFIELD");
 476     case RCSCMPFLD:     return("RCSCMPFLD");
 477     }
 478
 479     return("<trash>");
 480 }
 481
 482 static int printnode PROTO ((Node *, void *));
 483 static int
 484 printnode (node, closure)
 485      Node *node;
 486      void *closure;
 487 {
 488     if (node == NULL)
 489     {
 490         (void) printf("NULL node.\n");
 491         return(0);
 492     }
 493
 494     (void) printf("Node at %p: type = %s, key = %p = \"%s\", data = %p, next = %p, prev = %p\n",
 495            (void *)node, nodetypestring(node->type),
 496            (void *)node->key, node->key, node->data,
 497            (void *)node->next, (void *)node->prev);
 498
 499     return(0);
 500 }
 501
 502 /* This is global, not static, so that its name is unique and to avoid
 503    compiler warnings about it not being used.  But it is not used by CVS;
 504    it exists so one can call it from a debugger.  */
 505 void printlist PROTO ((List *));
 506
 507 void
 508 printlist (list)
 509     List *list;
 510 {
 511     if (list == NULL)
 512     {
 513         (void) printf("NULL list.\n");
 514         return;
 515     }
 516
 517     (void) printf("List at %p: list = %p, HASHSIZE = %d, next = %p\n",
 518            (void *)list, (void *)list->list, HASHSIZE, (void *)list->next);
 519
 520     (void) walklist(list, printnode, NULL);
 521
 522     return;
 523 }