mostly revert commit 700c1c04445f4ff11cdb7256df2be57db55abbf6
[alioth/cvs.git] / 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 }