2 * Copyright (C) 1986-2005 The Free Software Foundation, Inc.
4 * Portions Copyright (C) 1998-2005 Derek Price, Ximbiot <http://ximbiot.com>,
7 * Portions Copyright (C) 1992, Brian Berliner and Jeff Polk
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.
12 * Polk's hash list manager. So cool.
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;
25 static void freenode_mem PROTO((Node * p));
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;
46 return (h % HASHSIZE);
50 * create a new list (or get an old one from the cache)
59 if (listcache != NULL)
61 /* get a list from the cache and clear it */
63 listcache = listcache->next;
64 list->next = (List *) NULL;
65 for (i = 0; i < HASHSIZE; i++)
66 list->hasharray[i] = (Node *) NULL;
70 /* make a new list from scratch */
71 list = (List *) xmalloc (sizeof (List));
72 memset ((char *) list, 0, sizeof (List));
76 node->next = node->prev = node;
91 if (*listp == (List *) NULL)
96 /* free each node in the list (except header) */
100 /* free any list-private data, without freeing the actual header */
103 /* free up the header nodes for hash lists (if any) */
104 for (i = 0; i < HASHSIZE; i++)
106 if ((p = (*listp)->hasharray[i]) != (Node *) NULL)
108 /* put the nodes into the cache */
110 p->type = NT_UNKNOWN;
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. */
122 /* put it on the cache */
124 (*listp)->next = listcache;
127 free ((*listp)->list);
130 *listp = (List *) NULL;
134 * get a new list node
141 if (nodecache != (Node *) NULL)
143 /* get one from the cache */
150 p = (Node *) xmalloc (sizeof (Node));
153 /* always make it clean */
154 memset ((char *) p, 0, sizeof (Node));
155 p->type = NT_UNKNOWN;
161 * remove a node from it's list (maybe hash list too) and free it
167 if (p == (Node *) NULL)
170 /* take it out of the list */
171 p->next->prev = p->prev;
172 p->prev->next = p->next;
174 /* if it was hashed, remove it from there too */
175 if (p->hashnext != (Node *) NULL)
177 p->hashnext->hashprev = p->hashprev;
178 p->hashprev->hashnext = p->hashnext;
181 /* free up the storage */
186 * free up the storage associated with a node
192 if (p->delproc != (void (*) ()) NULL)
193 p->delproc (p); /* call the specified delproc */
196 if (p->data != NULL) /* otherwise free() it if necessary */
199 if (p->key != NULL) /* free the key if necessary */
202 /* to be safe, re-initialize these */
203 p->key = p->data = NULL;
204 p->delproc = (void (*) ()) NULL;
208 * free up the storage associated with a node and recycle it
214 /* first free the memory */
217 /* then put it in the cache */
219 p->type = NT_UNKNOWN;
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
232 * return 0 on success
235 insert_before (list, marker, p)
240 if (p->key != NULL) /* hash it too? */
245 hashval = hashp (p->key);
246 if (list->hasharray[hashval] == NULL) /* make a header for list? */
250 list->hasharray[hashval] = q->hashnext = q->hashprev = q;
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)
257 if (strcmp (p->key, q->key) == 0)
260 q = list->hasharray[hashval];
261 p->hashprev = q->hashprev;
263 p->hashprev->hashnext = p;
268 p->prev = marker->prev;
269 marker->prev->next = p;
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
279 * return 0 on success
286 return insert_before (list, list->list, p);
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.
294 addnode_at_front (list, p)
298 return insert_before (list, list->list->next, p);
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
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);
317 assert (key != NULL);
319 head = list->hasharray[hashp (key)];
320 if (head == (Node *) NULL)
322 return ((Node *) NULL);
324 for (p = head->hashnext; p != head; p = p->hashnext)
325 if (strcmp (p->key, key) == 0)
327 return ((Node *) NULL);
331 * Like findnode, but for a filename.
334 findnode_fn (list, key)
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);
346 assert (key != NULL);
348 head = list->hasharray[hashp (key)];
349 if (head == (Node *) NULL)
350 return ((Node *) NULL);
352 for (p = head->hashnext; p != head; p = p->hashnext)
353 if (fncmp (p->key, key) == 0)
355 return ((Node *) NULL);
359 * walk a list with a specific proc
362 walklist (list, proc, closure)
364 int (*proc) PROTO ((Node *, void *));
374 for (p = head->next; p != head; p = p->next)
375 err += proc (p, closure);
383 return list == NULL || list->list->next == list->list;
386 static int (*client_comp) PROTO ((const Node *, const Node *));
387 static int qsort_comp PROTO ((const void *, const void *));
390 qsort_comp (elem1, elem2)
394 Node **node1 = (Node **) elem1;
395 Node **node2 = (Node **) elem2;
396 return client_comp (*node1, *node2);
400 * sort the elements of a list (in place)
403 sortlist (list, comp)
405 int (*comp) PROTO ((const Node *, const Node *));
407 Node *head, *remain, *p, **array;
413 /* save the old first element of the list */
417 /* count the number of nodes in the list */
419 for (p = remain; p != head; p = p->next)
422 /* allocate an array of nodes and populate it */
423 array = (Node **) xmalloc (sizeof(Node *) * n);
425 for (p = remain; p != head; p = p->next)
428 /* sort the array of nodes */
430 qsort (array, n, sizeof(Node *), qsort_comp);
432 /* rebuild the list from beginning to end */
433 head->next = head->prev = head;
434 for (i = 0; i < n; i++)
438 p->prev = head->prev;
443 /* release the array of nodes */
448 * compare two files list node (for sort)
455 return (strcmp (p->key, q->key));
458 /* Debugging functions. Quite useful to call from within gdb. */
460 static char *nodetypestring PROTO ((Ntype));
463 nodetypestring (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");
487 static int printnode PROTO ((Node *, void *));
489 printnode (node, closure)
495 (void) printf("NULL node.\n");
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);
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 *));
518 (void) printf("NULL list.\n");
522 (void) printf("List at %p: list = %p, HASHSIZE = %d, next = %p\n",
523 (void *)list, (void *)list->list, HASHSIZE, (void *)list->next);
525 (void) walklist(list, printnode, NULL);