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
hashp(const char * key)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 *
getlist(void)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
dellist(List ** listp)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
removenode(Node * p)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
mergelists(List * dest,List ** src)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 *
getnode(void)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
delnode(Node * p)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
freenode_mem(Node * p)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
freenode(Node * p)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
insert_before(List * list,Node * marker,Node * p)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
addnode(List * list,Node * p)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
addnode_at_front(List * list,Node * p)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 *
findnode(List * list,const char * key)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 *
findnode_fn(List * list,const char * key)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
walklist(List * list,int (* proc)(Node *,void *),void * closure)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
list_isempty(List * list)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
qsort_comp(const void * elem1,const void * elem2)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
sortlist(List * list,int (* comp)(const Node *,const Node *))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
fsortcmp(const Node * p,const Node * q)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 *
nodetypestring(Ntype type)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
printnode(Node * node,void * closure)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
printlist(List * list)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 }
585