2 * Copyright (c) 1992, Brian Berliner and Jeff Polk
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.
7 * Polk's hash list manager. So cool.
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;
20 static void freenode_mem PROTO((Node * p));
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;
41 return (h % HASHSIZE);
45 * create a new list (or get an old one from the cache)
54 if (listcache != NULL)
56 /* get a list from the cache and clear it */
58 listcache = listcache->next;
59 list->next = (List *) NULL;
60 for (i = 0; i < HASHSIZE; i++)
61 list->hasharray[i] = (Node *) NULL;
65 /* make a new list from scratch */
66 list = (List *) xmalloc (sizeof (List));
67 memset ((char *) list, 0, sizeof (List));
71 node->next = node->prev = node;
86 if (*listp == (List *) NULL)
91 /* free each node in the list (except header) */
95 /* free any list-private data, without freeing the actual header */
98 /* free up the header nodes for hash lists (if any) */
99 for (i = 0; i < HASHSIZE; i++)
101 if ((p = (*listp)->hasharray[i]) != (Node *) NULL)
103 /* put the nodes into the cache */
105 p->type = NT_UNKNOWN;
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. */
117 /* put it on the cache */
119 (*listp)->next = listcache;
122 free ((*listp)->list);
125 *listp = (List *) NULL;
129 * get a new list node
136 if (nodecache != (Node *) NULL)
138 /* get one from the cache */
145 p = (Node *) xmalloc (sizeof (Node));
148 /* always make it clean */
149 memset ((char *) p, 0, sizeof (Node));
150 p->type = NT_UNKNOWN;
156 * remove a node from it's list (maybe hash list too) and free it
162 if (p == (Node *) NULL)
165 /* take it out of the list */
166 p->next->prev = p->prev;
167 p->prev->next = p->next;
169 /* if it was hashed, remove it from there too */
170 if (p->hashnext != (Node *) NULL)
172 p->hashnext->hashprev = p->hashprev;
173 p->hashprev->hashnext = p->hashnext;
176 /* free up the storage */
181 * free up the storage associated with a node
187 if (p->delproc != (void (*) ()) NULL)
188 p->delproc (p); /* call the specified delproc */
191 if (p->data != NULL) /* otherwise free() it if necessary */
194 if (p->key != NULL) /* free the key if necessary */
197 /* to be safe, re-initialize these */
198 p->key = p->data = NULL;
199 p->delproc = (void (*) ()) NULL;
203 * free up the storage associated with a node and recycle it
209 /* first free the memory */
212 /* then put it in the cache */
214 p->type = NT_UNKNOWN;
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
227 * return 0 on success
230 insert_before (list, marker, p)
235 if (p->key != NULL) /* hash it too? */
240 hashval = hashp (p->key);
241 if (list->hasharray[hashval] == NULL) /* make a header for list? */
245 list->hasharray[hashval] = q->hashnext = q->hashprev = q;
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)
252 if (strcmp (p->key, q->key) == 0)
255 q = list->hasharray[hashval];
256 p->hashprev = q->hashprev;
258 p->hashprev->hashnext = p;
263 p->prev = marker->prev;
264 marker->prev->next = p;
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
274 * return 0 on success
281 return insert_before (list, list->list, p);
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.
289 addnode_at_front (list, p)
293 return insert_before (list, list->list->next, p);
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
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);
312 assert (key != NULL);
314 head = list->hasharray[hashp (key)];
315 if (head == (Node *) NULL)
317 return ((Node *) NULL);
319 for (p = head->hashnext; p != head; p = p->hashnext)
320 if (strcmp (p->key, key) == 0)
322 return ((Node *) NULL);
326 * Like findnode, but for a filename.
329 findnode_fn (list, key)
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);
341 assert (key != NULL);
343 head = list->hasharray[hashp (key)];
344 if (head == (Node *) NULL)
345 return ((Node *) NULL);
347 for (p = head->hashnext; p != head; p = p->hashnext)
348 if (fncmp (p->key, key) == 0)
350 return ((Node *) NULL);
354 * walk a list with a specific proc
357 walklist (list, proc, closure)
359 int (*proc) PROTO ((Node *, void *));
369 for (p = head->next; p != head; p = p->next)
370 err += proc (p, closure);
378 return list == NULL || list->list->next == list->list;
381 static int (*client_comp) PROTO ((const Node *, const Node *));
382 static int qsort_comp PROTO ((const void *, const void *));
385 qsort_comp (elem1, elem2)
389 Node **node1 = (Node **) elem1;
390 Node **node2 = (Node **) elem2;
391 return client_comp (*node1, *node2);
395 * sort the elements of a list (in place)
398 sortlist (list, comp)
400 int (*comp) PROTO ((const Node *, const Node *));
402 Node *head, *remain, *p, **array;
408 /* save the old first element of the list */
412 /* count the number of nodes in the list */
414 for (p = remain; p != head; p = p->next)
417 /* allocate an array of nodes and populate it */
418 array = (Node **) xmalloc (sizeof(Node *) * n);
420 for (p = remain; p != head; p = p->next)
423 /* sort the array of nodes */
425 qsort (array, n, sizeof(Node *), qsort_comp);
427 /* rebuild the list from beginning to end */
428 head->next = head->prev = head;
429 for (i = 0; i < n; i++)
433 p->prev = head->prev;
438 /* release the array of nodes */
443 * compare two files list node (for sort)
450 return (strcmp (p->key, q->key));
453 /* Debugging functions. Quite useful to call from within gdb. */
455 static char *nodetypestring PROTO ((Ntype));
458 nodetypestring (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");
482 static int printnode PROTO ((Node *, void *));
484 printnode (node, closure)
490 (void) printf("NULL node.\n");
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);
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 *));
513 (void) printf("NULL list.\n");
517 (void) printf("List at %p: list = %p, HASHSIZE = %d, next = %p\n",
518 (void *)list, (void *)list->list, HASHSIZE, (void *)list->next);
520 (void) walklist(list, printnode, NULL);