home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / cvs-1.8.7-src.tgz / tar.out / fsf / cvs / src / hash.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  9KB  |  444 lines
  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 1.4 kit.
  6.  * 
  7.  * Polk's hash list manager.  So cool.
  8.  */
  9.  
  10. #include "cvs.h"
  11. #include <assert.h>
  12.  
  13. /* global caches */
  14. static List *listcache = NULL;
  15. static Node *nodecache = NULL;
  16.  
  17. static void freenode_mem PROTO((Node * p));
  18.  
  19. /* hash function */
  20. static int
  21. hashp (key)
  22.     const char *key;
  23. {
  24.     unsigned int h = 0;
  25.     unsigned int g;
  26.  
  27.     assert(key != NULL);
  28.     
  29.     while (*key != 0)
  30.     {
  31.     unsigned int c = *key++;
  32.     /* The FOLD_FN_CHAR is so that findnode_fn works.  */
  33.     h = (h << 4) + FOLD_FN_CHAR (c);
  34.     if ((g = h & 0xf0000000) != 0)
  35.         h = (h ^ (g >> 24)) ^ g;
  36.     }
  37.  
  38.     return (h % HASHSIZE);
  39. }
  40.  
  41. /*
  42.  * create a new list (or get an old one from the cache)
  43.  */
  44. List *
  45. getlist ()
  46. {
  47.     int i;
  48.     List *list;
  49.     Node *node;
  50.  
  51.     if (listcache != NULL)
  52.     {
  53.     /* get a list from the cache and clear it */
  54.     list = listcache;
  55.     listcache = listcache->next;
  56.     list->next = (List *) NULL;
  57.     for (i = 0; i < HASHSIZE; i++)
  58.         list->hasharray[i] = (Node *) NULL;
  59.     }
  60.     else
  61.     {
  62.     /* make a new list from scratch */
  63.     list = (List *) xmalloc (sizeof (List));
  64.     memset ((char *) list, 0, sizeof (List));
  65.     node = getnode ();
  66.     list->list = node;
  67.     node->type = HEADER;
  68.     node->next = node->prev = node;
  69.     }
  70.     return (list);
  71. }
  72.  
  73. /*
  74.  * free up a list
  75.  */
  76. void
  77. dellist (listp)
  78.     List **listp;
  79. {
  80.     int i;
  81.     Node *p;
  82.  
  83.     if (*listp == (List *) NULL)
  84.     return;
  85.  
  86.     p = (*listp)->list;
  87.  
  88.     /* free each node in the list (except header) */
  89.     while (p->next != p)
  90.     delnode (p->next);
  91.  
  92.     /* free any list-private data, without freeing the actual header */
  93.     freenode_mem (p);
  94.  
  95.     /* free up the header nodes for hash lists (if any) */
  96.     for (i = 0; i < HASHSIZE; i++)
  97.     {
  98.     if ((p = (*listp)->hasharray[i]) != (Node *) NULL)
  99.     {
  100.         /* put the nodes into the cache */
  101.         p->type = UNKNOWN;
  102.         p->next = nodecache;
  103.         nodecache = p;
  104.     }
  105.     }
  106.  
  107.     /* put it on the cache */
  108.     (*listp)->next = listcache;
  109.     listcache = *listp;
  110.     *listp = (List *) NULL;
  111. }
  112.  
  113. /*
  114.  * get a new list node
  115.  */
  116. Node *
  117. getnode ()
  118. {
  119.     Node *p;
  120.  
  121.     if (nodecache != (Node *) NULL)
  122.     {
  123.     /* get one from the cache */
  124.     p = nodecache;
  125.     nodecache = p->next;
  126.     }
  127.     else
  128.     {
  129.     /* make a new one */
  130.     p = (Node *) xmalloc (sizeof (Node));
  131.     }
  132.  
  133.     /* always make it clean */
  134.     memset ((char *) p, 0, sizeof (Node));
  135.     p->type = UNKNOWN;
  136.  
  137.     return (p);
  138. }
  139.  
  140. /*
  141.  * remove a node from it's list (maybe hash list too) and free it
  142.  */
  143. void
  144. delnode (p)
  145.     Node *p;
  146. {
  147.     if (p == (Node *) NULL)
  148.     return;
  149.  
  150.     /* take it out of the list */
  151.     p->next->prev = p->prev;
  152.     p->prev->next = p->next;
  153.  
  154.     /* if it was hashed, remove it from there too */
  155.     if (p->hashnext != (Node *) NULL)
  156.     {
  157.     p->hashnext->hashprev = p->hashprev;
  158.     p->hashprev->hashnext = p->hashnext;
  159.     }
  160.  
  161.     /* free up the storage */
  162.     freenode (p);
  163. }
  164.  
  165. /*
  166.  * free up the storage associated with a node
  167.  */
  168. static void
  169. freenode_mem (p)
  170.     Node *p;
  171. {
  172.     if (p->delproc != (void (*) ()) NULL)
  173.     p->delproc (p);            /* call the specified delproc */
  174.     else
  175.     {
  176.     if (p->data != NULL)        /* otherwise free() it if necessary */
  177.         free (p->data);
  178.     }
  179.     if (p->key != NULL)            /* free the key if necessary */
  180.     free (p->key);
  181.  
  182.     /* to be safe, re-initialize these */
  183.     p->key = p->data = (char *) NULL;
  184.     p->delproc = (void (*) ()) NULL;
  185. }
  186.  
  187. /*
  188.  * free up the storage associated with a node and recycle it
  189.  */
  190. void
  191. freenode (p)
  192.     Node *p;
  193. {
  194.     /* first free the memory */
  195.     freenode_mem (p);
  196.  
  197.     /* then put it in the cache */
  198.     p->type = UNKNOWN;
  199.     p->next = nodecache;
  200.     nodecache = p;
  201. }
  202.  
  203. /*
  204.  * insert item p at end of list "list" (maybe hash it too) if hashing and it
  205.  * already exists, return -1 and don't actually put it in the list
  206.  * 
  207.  * return 0 on success
  208.  */
  209. int
  210. addnode (list, p)
  211.     List *list;
  212.     Node *p;
  213. {
  214.     int hashval;
  215.     Node *q;
  216.  
  217.     if (p->key != NULL)            /* hash it too? */
  218.     {
  219.     hashval = hashp (p->key);
  220.     if (list->hasharray[hashval] == NULL)    /* make a header for list? */
  221.     {
  222.         q = getnode ();
  223.         q->type = HEADER;
  224.         list->hasharray[hashval] = q->hashnext = q->hashprev = q;
  225.     }
  226.  
  227.     /* put it into the hash list if it's not already there */
  228.     for (q = list->hasharray[hashval]->hashnext;
  229.          q != list->hasharray[hashval]; q = q->hashnext)
  230.     {
  231.         if (strcmp (p->key, q->key) == 0)
  232.         return (-1);
  233.     }
  234.     q = list->hasharray[hashval];
  235.     p->hashprev = q->hashprev;
  236.     p->hashnext = q;
  237.     p->hashprev->hashnext = p;
  238.     q->hashprev = p;
  239.     }
  240.  
  241.     /* put it into the regular list */
  242.     p->prev = list->list->prev;
  243.     p->next = list->list;
  244.     list->list->prev->next = p;
  245.     list->list->prev = p;
  246.  
  247.     return (0);
  248. }
  249.  
  250. /* Look up an entry in hash list table and return a pointer to the
  251.    node.  Return NULL if not found.  Abort with a fatal error for
  252.    errors.  */
  253. Node *
  254. findnode (list, key)
  255.     List *list;
  256.     const char *key;
  257. {
  258.     Node *head, *p;
  259.  
  260.     /* This probably should be "assert (list != NULL)" (or if not we
  261.        should document the current behavior), but only if we check all
  262.        the callers to see if any are relying on this behavior.  */
  263.     if ((list == (List *) NULL))
  264.     return ((Node *) NULL);
  265.  
  266.     assert (key != NULL);
  267.  
  268.     head = list->hasharray[hashp (key)];
  269.     if (head == (Node *) NULL)
  270.     /* Not found.  */
  271.     return ((Node *) NULL);
  272.  
  273.     for (p = head->hashnext; p != head; p = p->hashnext)
  274.     if (strcmp (p->key, key) == 0)
  275.         return (p);
  276.     return ((Node *) NULL);
  277. }
  278.  
  279. /*
  280.  * Like findnode, but for a filename.
  281.  */
  282. Node *
  283. findnode_fn (list, key)
  284.     List *list;
  285.     const char *key;
  286. {
  287.     Node *head, *p;
  288.  
  289.     /* This probably should be "assert (list != NULL)" (or if not we
  290.        should document the current behavior), but only if we check all
  291.        the callers to see if any are relying on this behavior.  */
  292.     if (list == (List *) NULL)
  293.     return ((Node *) NULL);
  294.  
  295.     assert (key != NULL);
  296.  
  297.     head = list->hasharray[hashp (key)];
  298.     if (head == (Node *) NULL)
  299.     return ((Node *) NULL);
  300.  
  301.     for (p = head->hashnext; p != head; p = p->hashnext)
  302.     if (fncmp (p->key, key) == 0)
  303.         return (p);
  304.     return ((Node *) NULL);
  305. }
  306.  
  307. /*
  308.  * walk a list with a specific proc
  309.  */
  310. int
  311. walklist (list, proc, closure)
  312.     List *list;
  313.     int (*proc) PROTO ((Node *, void *));
  314.     void *closure;
  315. {
  316.     Node *head, *p;
  317.     int err = 0;
  318.  
  319.     if (list == NULL)
  320.     return (0);
  321.  
  322.     head = list->list;
  323.     for (p = head->next; p != head; p = p->next)
  324.     err += proc (p, closure);
  325.     return (err);
  326. }
  327.  
  328. int
  329. list_isempty (list)
  330.     List *list;
  331. {
  332.     return list == NULL || list->list->next == list->list;
  333. }
  334.  
  335. /*
  336.  * sort the elements of a list (in place)
  337.  */
  338. void
  339. sortlist (list, comp)
  340.     List *list;
  341.     int (*comp) PROTO ((const Node *, const Node *));
  342. {
  343.     Node *head, *remain, *p, *q;
  344.  
  345.     /* save the old first element of the list */
  346.     head = list->list;
  347.     remain = head->next;
  348.  
  349.     /* make the header node into a null list of it's own */
  350.     head->next = head->prev = head;
  351.  
  352.     /* while there are nodes remaining, do insert sort */
  353.     while (remain != head)
  354.     {
  355.     /* take one from the list */
  356.     p = remain;
  357.     remain = remain->next;
  358.  
  359.     /* traverse the sorted list looking for the place to insert it */
  360.     for (q = head->next; q != head; q = q->next)
  361.     {
  362.         if (comp (p, q) < 0)
  363.         {
  364.         /* p comes before q */
  365.         p->next = q;
  366.         p->prev = q->prev;
  367.         p->prev->next = p;
  368.         q->prev = p;
  369.         break;
  370.         }
  371.     }
  372.     if (q == head)
  373.     {
  374.         /* it belongs at the end of the list */
  375.         p->next = head;
  376.         p->prev = head->prev;
  377.         p->prev->next = p;
  378.         head->prev = p;
  379.     }
  380.     }
  381. }
  382.  
  383. /* Debugging functions.  Quite useful to call from within gdb. */
  384.  
  385. char *
  386. nodetypestring (type)
  387.     Ntype type;
  388. {
  389.     switch (type) {
  390.     case UNKNOWN:    return("UNKNOWN");
  391.     case HEADER:    return("HEADER");
  392.     case ENTRIES:    return("ENTRIES");
  393.     case FILES:        return("FILES");
  394.     case LIST:        return("LIST");
  395.     case RCSNODE:    return("RCSNODE");
  396.     case RCSVERS:    return("RCSVERS");
  397.     case DIRS:        return("DIRS");
  398.     case UPDATE:    return("UPDATE");
  399.     case LOCK:        return("LOCK");
  400.     case NDBMNODE:    return("NDBMNODE");
  401.     case FILEATTR:    return("FILEATTR");
  402.     case VARIABLE:    return("VARIABLE");
  403.     case RCSFIELD:    return("RCSFIELD");
  404.     }
  405.  
  406.     return("<trash>");
  407. }
  408.  
  409. static int printnode PROTO ((Node *, void *));
  410. static int
  411. printnode (node, closure)
  412.      Node *node;
  413.      void *closure;
  414. {
  415.     if (node == NULL)
  416.     {
  417.     (void) printf("NULL node.\n");
  418.     return(0);
  419.     }
  420.  
  421.     (void) printf("Node at 0x%p: type = %s, key = 0x%p = \"%s\", data = 0x%p, next = 0x%p, prev = 0x%p\n",
  422.        node, nodetypestring(node->type), node->key, node->key, node->data, node->next, node->prev);
  423.  
  424.     return(0);
  425. }
  426.  
  427. void
  428. printlist (list)
  429.     List *list;
  430. {
  431.     if (list == NULL)
  432.     {
  433.     (void) printf("NULL list.\n");
  434.     return;
  435.     }
  436.  
  437.     (void) printf("List at 0x%p: list = 0x%p, HASHSIZE = %d, next = 0x%p\n",
  438.        list, list->list, HASHSIZE, list->next);
  439.     
  440.     (void) walklist(list, printnode, NULL);
  441.  
  442.     return;
  443. }
  444.