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 source distribution.
6 *
7 * Polk's hash list manager.  So cool.
8 */
9
10#include "cvs.h"
11#include <assert.h>
12
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.  */
17static List *listcache = NULL;
18static Node *nodecache = NULL;
19
20static void freenode_mem PROTO((Node * p));
21
22/* hash function */
23static int
24hashp (key)
25    const char *key;
26{
27    unsigned int h = 0;
28    unsigned int g;
29
30    assert(key != NULL);
31
32    while (*key != 0)
33    {
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;
39    }
40
41    return (h % HASHSIZE);
42}
43
44/*
45 * create a new list (or get an old one from the cache)
46 */
47List *
48getlist ()
49{
50    int i;
51    List *list;
52    Node *node;
53
54    if (listcache != NULL)
55    {
56	/* get a list from the cache and clear it */
57	list = listcache;
58	listcache = listcache->next;
59	list->next = (List *) NULL;
60	for (i = 0; i < HASHSIZE; i++)
61	    list->hasharray[i] = (Node *) NULL;
62    }
63    else
64    {
65	/* make a new list from scratch */
66	list = (List *) xmalloc (sizeof (List));
67	memset ((char *) list, 0, sizeof (List));
68	node = getnode ();
69	list->list = node;
70	node->type = HEADER;
71	node->next = node->prev = node;
72    }
73    return (list);
74}
75
76/*
77 * free up a list
78 */
79void
80dellist (listp)
81    List **listp;
82{
83    int i;
84    Node *p;
85
86    if (*listp == (List *) NULL)
87	return;
88
89    p = (*listp)->list;
90
91    /* free each node in the list (except header) */
92    while (p->next != p)
93	delnode (p->next);
94
95    /* free any list-private data, without freeing the actual header */
96    freenode_mem (p);
97
98    /* free up the header nodes for hash lists (if any) */
99    for (i = 0; i < HASHSIZE; i++)
100    {
101	if ((p = (*listp)->hasharray[i]) != (Node *) NULL)
102	{
103	    /* put the nodes into the cache */
104#ifndef NOCACHE
105	    p->type = NT_UNKNOWN;
106	    p->next = nodecache;
107	    nodecache = p;
108#else
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.  */
112	    free (p);
113#endif
114	}
115    }
116
117    /* put it on the cache */
118#ifndef NOCACHE
119    (*listp)->next = listcache;
120    listcache = *listp;
121#else
122    free ((*listp)->list);
123    free (*listp);
124#endif
125    *listp = (List *) NULL;
126}
127
128/*
129 * get a new list node
130 */
131Node *
132getnode ()
133{
134    Node *p;
135
136    if (nodecache != (Node *) NULL)
137    {
138	/* get one from the cache */
139	p = nodecache;
140	nodecache = p->next;
141    }
142    else
143    {
144	/* make a new one */
145	p = (Node *) xmalloc (sizeof (Node));
146    }
147
148    /* always make it clean */
149    memset ((char *) p, 0, sizeof (Node));
150    p->type = NT_UNKNOWN;
151
152    return (p);
153}
154
155/*
156 * remove a node from it's list (maybe hash list too) and free it
157 */
158void
159delnode (p)
160    Node *p;
161{
162    if (p == (Node *) NULL)
163	return;
164
165    /* take it out of the list */
166    p->next->prev = p->prev;
167    p->prev->next = p->next;
168
169    /* if it was hashed, remove it from there too */
170    if (p->hashnext != (Node *) NULL)
171    {
172	p->hashnext->hashprev = p->hashprev;
173	p->hashprev->hashnext = p->hashnext;
174    }
175
176    /* free up the storage */
177    freenode (p);
178}
179
180/*
181 * free up the storage associated with a node
182 */
183static void
184freenode_mem (p)
185    Node *p;
186{
187    if (p->delproc != (void (*) ()) NULL)
188	p->delproc (p);			/* call the specified delproc */
189    else
190    {
191	if (p->data != NULL)		/* otherwise free() it if necessary */
192	    free (p->data);
193    }
194    if (p->key != NULL)			/* free the key if necessary */
195	free (p->key);
196
197    /* to be safe, re-initialize these */
198    p->key = p->data = (char *) NULL;
199    p->delproc = (void (*) ()) NULL;
200}
201
202/*
203 * free up the storage associated with a node and recycle it
204 */
205void
206freenode (p)
207    Node *p;
208{
209    /* first free the memory */
210    freenode_mem (p);
211
212    /* then put it in the cache */
213#ifndef NOCACHE
214    p->type = NT_UNKNOWN;
215    p->next = nodecache;
216    nodecache = p;
217#else
218    free (p);
219#endif
220}
221
222/*
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
225 * parameter.
226 *
227 * return 0 on success
228 */
229int
230insert_before (list, marker, p)
231    List *list;
232    Node *marker;
233    Node *p;
234{
235    if (p->key != NULL)			/* hash it too? */
236    {
237	int hashval;
238	Node *q;
239
240	hashval = hashp (p->key);
241	if (list->hasharray[hashval] == NULL)	/* make a header for list? */
242	{
243	    q = getnode ();
244	    q->type = HEADER;
245	    list->hasharray[hashval] = q->hashnext = q->hashprev = q;
246	}
247
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)
251	{
252	    if (strcmp (p->key, q->key) == 0)
253		return (-1);
254	}
255	q = list->hasharray[hashval];
256	p->hashprev = q->hashprev;
257	p->hashnext = q;
258	p->hashprev->hashnext = p;
259	q->hashprev = p;
260    }
261
262    p->next = marker;
263    p->prev = marker->prev;
264    marker->prev->next = p;
265    marker->prev = p;
266
267    return (0);
268}
269
270/*
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
273 *
274 * return 0 on success
275 */
276int
277addnode (list, p)
278    List *list;
279    Node *p;
280{
281  return insert_before (list, list->list, p);
282}
283
284/*
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.
287 */
288int
289addnode_at_front (list, p)
290    List *list;
291    Node *p;
292{
293  return insert_before (list, list->list->next, p);
294}
295
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
298   errors.  */
299Node *
300findnode (list, key)
301    List *list;
302    const char *key;
303{
304    Node *head, *p;
305
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);
311
312    assert (key != NULL);
313
314    head = list->hasharray[hashp (key)];
315    if (head == (Node *) NULL)
316	/* Not found.  */
317	return ((Node *) NULL);
318
319    for (p = head->hashnext; p != head; p = p->hashnext)
320	if (strcmp (p->key, key) == 0)
321	    return (p);
322    return ((Node *) NULL);
323}
324
325/*
326 * Like findnode, but for a filename.
327 */
328Node *
329findnode_fn (list, key)
330    List *list;
331    const char *key;
332{
333    Node *head, *p;
334
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);
340
341    assert (key != NULL);
342
343    head = list->hasharray[hashp (key)];
344    if (head == (Node *) NULL)
345	return ((Node *) NULL);
346
347    for (p = head->hashnext; p != head; p = p->hashnext)
348	if (fncmp (p->key, key) == 0)
349	    return (p);
350    return ((Node *) NULL);
351}
352
353/*
354 * walk a list with a specific proc
355 */
356int
357walklist (list, proc, closure)
358    List *list;
359    int (*proc) PROTO ((Node *, void *));
360    void *closure;
361{
362    Node *head, *p;
363    int err = 0;
364
365    if (list == NULL)
366	return (0);
367
368    head = list->list;
369    for (p = head->next; p != head; p = p->next)
370	err += proc (p, closure);
371    return (err);
372}
373
374int
375list_isempty (list)
376    List *list;
377{
378    return list == NULL || list->list->next == list->list;
379}
380
381static int (*client_comp) PROTO ((const Node *, const Node *));
382static int qsort_comp PROTO ((const void *, const void *));
383
384static int
385qsort_comp (elem1, elem2)
386    const void *elem1;
387    const void *elem2;
388{
389    Node **node1 = (Node **) elem1;
390    Node **node2 = (Node **) elem2;
391    return client_comp (*node1, *node2);
392}
393
394/*
395 * sort the elements of a list (in place)
396 */
397void
398sortlist (list, comp)
399    List *list;
400    int (*comp) PROTO ((const Node *, const Node *));
401{
402    Node *head, *remain, *p, **array;
403    int i, n;
404
405    /* save the old first element of the list */
406    head = list->list;
407    remain = head->next;
408
409    /* count the number of nodes in the list */
410    n = 0;
411    for (p = remain; p != head; p = p->next)
412	n++;
413
414    /* allocate an array of nodes and populate it */
415    array = (Node **) xmalloc (sizeof(Node *) * n);
416    i = 0;
417    for (p = remain; p != head; p = p->next)
418	array[i++] = p;
419
420    /* sort the array of nodes */
421    client_comp = comp;
422    qsort (array, n, sizeof(Node *), qsort_comp);
423
424    /* rebuild the list from beginning to end */
425    head->next = head->prev = head;
426    for (i = 0; i < n; i++)
427    {
428	p = array[i];
429	p->next = head;
430	p->prev = head->prev;
431	p->prev->next = p;
432	head->prev = p;
433    }
434
435    /* release the array of nodes */
436    free (array);
437}
438
439/*
440 * compare two files list node (for sort)
441 */
442int
443fsortcmp (p, q)
444    const Node *p;
445    const Node *q;
446{
447    return (strcmp (p->key, q->key));
448}
449
450/* Debugging functions.  Quite useful to call from within gdb. */
451
452static char *nodetypestring PROTO ((Ntype));
453
454static char *
455nodetypestring (type)
456    Ntype type;
457{
458    switch (type) {
459    case NT_UNKNOWN:	return("UNKNOWN");
460    case HEADER:	return("HEADER");
461    case ENTRIES:	return("ENTRIES");
462    case FILES:		return("FILES");
463    case LIST:		return("LIST");
464    case RCSNODE:	return("RCSNODE");
465    case RCSVERS:	return("RCSVERS");
466    case DIRS:		return("DIRS");
467    case UPDATE:	return("UPDATE");
468    case LOCK:		return("LOCK");
469    case NDBMNODE:	return("NDBMNODE");
470    case FILEATTR:	return("FILEATTR");
471    case VARIABLE:	return("VARIABLE");
472    case RCSFIELD:	return("RCSFIELD");
473    case RCSCMPFLD:	return("RCSCMPFLD");
474    }
475
476    return("<trash>");
477}
478
479static int printnode PROTO ((Node *, void *));
480static int
481printnode (node, closure)
482     Node *node;
483     void *closure;
484{
485    if (node == NULL)
486    {
487	(void) printf("NULL node.\n");
488	return(0);
489    }
490
491    (void) printf("Node at 0x%p: type = %s, key = 0x%p = \"%s\", data = 0x%p, next = 0x%p, prev = 0x%p\n",
492	   node, nodetypestring(node->type), node->key, node->key, node->data, node->next, node->prev);
493
494    return(0);
495}
496
497/* This is global, not static, so that its name is unique and to avoid
498   compiler warnings about it not being used.  But it is not used by CVS;
499   it exists so one can call it from a debugger.  */
500void printlist PROTO ((List *));
501
502void
503printlist (list)
504    List *list;
505{
506    if (list == NULL)
507    {
508	(void) printf("NULL list.\n");
509	return;
510    }
511
512    (void) printf("List at 0x%p: list = 0x%p, HASHSIZE = %d, next = 0x%p\n",
513	   list, list->list, HASHSIZE, list->next);
514
515    (void) walklist(list, printnode, NULL);
516
517    return;
518}
519