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. */
17 static List *listcache = NULL;
18 static Node *nodecache = NULL;
19
20 static void freenode_mem PROTO((Node * p));
21
22 /* hash function */
23 static int
hashp(key)24 hashp (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 */
47 List *
getlist()48 getlist ()
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 */
79 void
dellist(listp)80 dellist (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 */
131 Node *
getnode()132 getnode ()
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 */
158 void
delnode(p)159 delnode (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 */
183 static void
freenode_mem(p)184 freenode_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 */
205 void
freenode(p)206 freenode (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 */
229 int
insert_before(list,marker,p)230 insert_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 */
276 int
addnode(list,p)277 addnode (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 */
288 int
addnode_at_front(list,p)289 addnode_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. */
299 Node *
findnode(list,key)300 findnode (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 */
328 Node *
findnode_fn(list,key)329 findnode_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 */
356 int
walklist(list,proc,closure)357 walklist (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
374 int
list_isempty(list)375 list_isempty (list)
376 List *list;
377 {
378 return list == NULL || list->list->next == list->list;
379 }
380
381 static int (*client_comp) PROTO ((const Node *, const Node *));
382 static int qsort_comp PROTO ((const void *, const void *));
383
384 static int
qsort_comp(elem1,elem2)385 qsort_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 */
397 void
sortlist(list,comp)398 sortlist (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 */
442 int
fsortcmp(p,q)443 fsortcmp (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
452 static char *nodetypestring PROTO ((Ntype));
453
454 static char *
nodetypestring(type)455 nodetypestring (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
479 static int printnode PROTO ((Node *, void *));
480 static int
printnode(node,closure)481 printnode (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. */
500 void printlist PROTO ((List *));
501
502 void
printlist(list)503 printlist (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