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