contrib/cvs/src/hash.c

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