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 #include <sys/cdefs.h>
15 __RCSID("$NetBSD: hash.c,v 1.2 2016/05/17 14:00:09 christos Exp $");
16
17 #include "cvs.h"
18
19 /* Global caches. The idea is that we maintain a linked list of "free"d
20 nodes or lists, and get new items from there. It has been suggested
21 to use an obstack instead, but off the top of my head, I'm not sure
22 that would gain enough to be worth worrying about. */
23 static List *listcache = NULL;
24 static Node *nodecache = NULL;
25
26 static void freenode_mem (Node * p);
27
28 /* hash function */
29 static int
hashp(const char * key)30 hashp (const char *key)
31 {
32 unsigned int h = 0;
33 unsigned int g;
34
35 assert(key != NULL);
36
37 while (*key != 0)
38 {
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;
44 }
45
46 return h % HASHSIZE;
47 }
48
49
50
51 /*
52 * create a new list (or get an old one from the cache)
53 */
54 List *
getlist(void)55 getlist (void)
56 {
57 int i;
58 List *list;
59 Node *node;
60
61 if (listcache != NULL)
62 {
63 /* get a list from the cache and clear it */
64 list = listcache;
65 listcache = listcache->next;
66 list->next = NULL;
67 for (i = 0; i < HASHSIZE; i++)
68 list->hasharray[i] = NULL;
69 }
70 else
71 {
72 /* make a new list from scratch */
73 list = xmalloc (sizeof (List));
74 memset (list, 0, sizeof (List));
75 node = getnode ();
76 list->list = node;
77 node->type = HEADER;
78 node->next = node->prev = node;
79 }
80 return list;
81 }
82
83
84
85 /*
86 * Free up a list. For accessing globals which might be accessed via interrupt
87 * handlers, it can be assumed that the first action of this function will be
88 * to set the *listp to NULL.
89 */
90 void
dellist(List ** listp)91 dellist (List **listp)
92 {
93 int i;
94 Node *p;
95 List *tmp;
96
97 if (*listp == NULL)
98 return;
99
100 tmp = *listp;
101 *listp = NULL;
102
103 p = tmp->list;
104
105 /* free each node in the list (except header) */
106 while (p->next != p)
107 delnode (p->next);
108
109 /* free any list-private data, without freeing the actual header */
110 freenode_mem (p);
111
112 /* free up the header nodes for hash lists (if any) */
113 for (i = 0; i < HASHSIZE; i++)
114 {
115 if ((p = tmp->hasharray[i]) != NULL)
116 {
117 /* put the nodes into the cache */
118 #ifndef NOCACHE
119 p->type = NT_UNKNOWN;
120 p->next = nodecache;
121 nodecache = p;
122 #else
123 /* If NOCACHE is defined we turn off the cache. This can make
124 it easier to tools to determine where items were allocated
125 and freed, for tracking down memory leaks and the like. */
126 free (p);
127 #endif
128 }
129 }
130
131 /* put it on the cache */
132 #ifndef NOCACHE
133 tmp->next = listcache;
134 listcache = tmp;
135 #else
136 free (tmp->list);
137 free (tmp);
138 #endif
139 }
140
141
142
143 /*
144 * remove a node from it's list (maybe hash list too)
145 */
146 void
removenode(Node * p)147 removenode (Node *p)
148 {
149 if (!p) return;
150
151 /* take it out of the list */
152 p->next->prev = p->prev;
153 p->prev->next = p->next;
154
155 /* if it was hashed, remove it from there too */
156 if (p->hashnext)
157 {
158 p->hashnext->hashprev = p->hashprev;
159 p->hashprev->hashnext = p->hashnext;
160 }
161 }
162
163
164
165 void
mergelists(List * dest,List ** src)166 mergelists (List *dest, List **src)
167 {
168 Node *head, *p, *n;
169
170 head = (*src)->list;
171 for (p = head->next; p != head; p = n)
172 {
173 n = p->next;
174 removenode (p);
175 addnode (dest, p);
176 }
177 dellist (src);
178 }
179
180
181
182 /*
183 * get a new list node
184 */
185 Node *
getnode(void)186 getnode (void)
187 {
188 Node *p;
189
190 if (nodecache != NULL)
191 {
192 /* get one from the cache */
193 p = nodecache;
194 nodecache = p->next;
195 }
196 else
197 {
198 /* make a new one */
199 p = xmalloc (sizeof (Node));
200 }
201
202 /* always make it clean */
203 memset (p, 0, sizeof (Node));
204 p->type = NT_UNKNOWN;
205
206 return p;
207 }
208
209
210
211 /*
212 * remove a node from it's list (maybe hash list too) and free it
213 */
214 void
delnode(Node * p)215 delnode (Node *p)
216 {
217 if (!p) return;
218 /* remove it */
219 removenode (p);
220 /* free up the storage */
221 freenode (p);
222 }
223
224
225
226 /*
227 * free up the storage associated with a node
228 */
229 static void
freenode_mem(Node * p)230 freenode_mem (Node *p)
231 {
232 if (p->delproc != NULL)
233 p->delproc (p); /* call the specified delproc */
234 else
235 {
236 if (p->data != NULL) /* otherwise free() it if necessary */
237 free (p->data);
238 }
239 if (p->key != NULL) /* free the key if necessary */
240 free (p->key);
241
242 /* to be safe, re-initialize these */
243 p->key = p->data = NULL;
244 p->delproc = NULL;
245 }
246
247
248
249 /*
250 * free up the storage associated with a node and recycle it
251 */
252 void
freenode(Node * p)253 freenode (Node *p)
254 {
255 /* first free the memory */
256 freenode_mem (p);
257
258 /* then put it in the cache */
259 #ifndef NOCACHE
260 p->type = NT_UNKNOWN;
261 p->next = nodecache;
262 nodecache = p;
263 #else
264 free (p);
265 #endif
266 }
267
268
269
270 /*
271 * Link item P into list LIST before item MARKER. If P->KEY is non-NULL and
272 * that key is already in the hash table, return -1 without modifying any
273 * parameter.
274 *
275 * return 0 on success
276 */
277 int
insert_before(List * list,Node * marker,Node * p)278 insert_before (List *list, Node *marker, Node *p)
279 {
280 if (p->key != NULL) /* hash it too? */
281 {
282 int hashval;
283 Node *q;
284
285 hashval = hashp (p->key);
286 if (list->hasharray[hashval] == NULL) /* make a header for list? */
287 {
288 q = getnode ();
289 q->type = HEADER;
290 list->hasharray[hashval] = q->hashnext = q->hashprev = q;
291 }
292
293 /* put it into the hash list if it's not already there */
294 for (q = list->hasharray[hashval]->hashnext;
295 q != list->hasharray[hashval]; q = q->hashnext)
296 {
297 if (strcmp (p->key, q->key) == 0)
298 return -1;
299 }
300 q = list->hasharray[hashval];
301 p->hashprev = q->hashprev;
302 p->hashnext = q;
303 p->hashprev->hashnext = p;
304 q->hashprev = p;
305 }
306
307 p->next = marker;
308 p->prev = marker->prev;
309 marker->prev->next = p;
310 marker->prev = p;
311
312 return 0;
313 }
314
315
316
317 /*
318 * insert item p at end of list "list" (maybe hash it too) if hashing and it
319 * already exists, return -1 and don't actually put it in the list
320 *
321 * return 0 on success
322 */
323 int
addnode(List * list,Node * p)324 addnode (List *list, Node *p)
325 {
326 return insert_before (list, list->list, p);
327 }
328
329
330
331 /*
332 * Like addnode, but insert p at the front of `list'. This bogosity is
333 * necessary to preserve last-to-first output order for some RCS functions.
334 */
335 int
addnode_at_front(List * list,Node * p)336 addnode_at_front (List *list, Node *p)
337 {
338 return insert_before (list, list->list->next, p);
339 }
340
341
342
343 /* Look up an entry in hash list table and return a pointer to the
344 * node. Return NULL if not found or if list is NULL. Abort with a fatal
345 * error for errors.
346 */
347 Node *
findnode(List * list,const char * key)348 findnode (List *list, const char *key)
349 {
350 Node *head, *p;
351
352 if ((list == NULL))
353 return NULL;
354
355 assert (key != NULL);
356
357 head = list->hasharray[hashp (key)];
358 if (head == NULL)
359 /* Not found. */
360 return NULL;
361
362 for (p = head->hashnext; p != head; p = p->hashnext)
363 if (strcmp (p->key, key) == 0)
364 return p;
365 return NULL;
366 }
367
368
369
370 /*
371 * Like findnode, but for a filename.
372 */
373 Node *
findnode_fn(List * list,const char * key)374 findnode_fn (List *list, const char *key)
375 {
376 Node *head, *p;
377
378 /* This probably should be "assert (list != NULL)" (or if not we
379 should document the current behavior), but only if we check all
380 the callers to see if any are relying on this behavior. */
381 if (list == NULL)
382 return NULL;
383
384 assert (key != NULL);
385
386 head = list->hasharray[hashp (key)];
387 if (head == NULL)
388 return NULL;
389
390 for (p = head->hashnext; p != head; p = p->hashnext)
391 if (fncmp (p->key, key) == 0)
392 return p;
393 return NULL;
394 }
395
396
397
398 /*
399 * walk a list with a specific proc
400 */
401 int
walklist(List * list,int (* proc)(Node *,void *),void * closure)402 walklist (List *list, int (*proc) (Node *, void *), void *closure)
403 {
404 Node *head, *p;
405 int err = 0;
406
407 #ifdef HAVE_PRINTF_PTR
408 TRACE (TRACE_FLOW, "walklist ( list=%p, proc=%p, closure=%p )",
409 (void *)list, (void *)proc, (void *)closure);
410 #else
411 TRACE (TRACE_FLOW, "walklist ( list=%lx, proc=%lx, closure=%lx )",
412 (unsigned long)list,(unsigned long) proc,
413 (unsigned long)closure);
414 #endif
415
416 if (list == NULL)
417 return 0;
418
419 head = list->list;
420 for (p = head->next; p != head; p = p->next)
421 err += proc (p, closure);
422 return err;
423 }
424
425
426
427 int
list_isempty(List * list)428 list_isempty (List *list)
429 {
430 return list == NULL || list->list->next == list->list;
431 }
432
433
434
435 static int (*client_comp) (const Node *, const Node *);
436
437 static int
qsort_comp(const void * elem1,const void * elem2)438 qsort_comp (const void *elem1, const void *elem2)
439 {
440 Node **node1 = (Node **) elem1;
441 Node **node2 = (Node **) elem2;
442 return client_comp (*node1, *node2);
443 }
444
445
446
447 /*
448 * sort the elements of a list (in place)
449 */
450 void
sortlist(List * list,int (* comp)(const Node *,const Node *))451 sortlist (List *list, int (*comp) (const Node *, const Node *))
452 {
453 Node *head, *remain, *p, **array;
454 int i, n;
455
456 if (list == NULL)
457 return;
458
459 /* save the old first element of the list */
460 head = list->list;
461 remain = head->next;
462
463 /* count the number of nodes in the list */
464 n = 0;
465 for (p = remain; p != head; p = p->next)
466 n++;
467
468 /* allocate an array of nodes and populate it */
469 array = xnmalloc (n, sizeof (Node *));
470 i = 0;
471 for (p = remain; p != head; p = p->next)
472 array[i++] = p;
473
474 /* sort the array of nodes */
475 client_comp = comp;
476 qsort (array, n, sizeof(Node *), qsort_comp);
477
478 /* rebuild the list from beginning to end */
479 head->next = head->prev = head;
480 for (i = 0; i < n; i++)
481 {
482 p = array[i];
483 p->next = head;
484 p->prev = head->prev;
485 p->prev->next = p;
486 head->prev = p;
487 }
488
489 /* release the array of nodes */
490 free (array);
491 }
492
493
494
495 /*
496 * compare two files list node (for sort)
497 */
498 int
fsortcmp(const Node * p,const Node * q)499 fsortcmp (const Node *p, const Node *q)
500 {
501 return strcmp (p->key, q->key);
502 }
503
504
505
506 /* Debugging functions. Quite useful to call from within gdb. */
507
508
509 static char *
nodetypestring(Ntype type)510 nodetypestring (Ntype type)
511 {
512 switch (type) {
513 case NT_UNKNOWN: return "UNKNOWN";
514 case HEADER: return "HEADER";
515 case ENTRIES: return "ENTRIES";
516 case FILES: return "FILES";
517 case LIST: return "LIST";
518 case RCSNODE: return "RCSNODE";
519 case RCSVERS: return "RCSVERS";
520 case DIRS: return "DIRS";
521 case UPDATE: return "UPDATE";
522 case LOCK: return "LOCK";
523 case NDBMNODE: return "NDBMNODE";
524 case FILEATTR: return "FILEATTR";
525 case VARIABLE: return "VARIABLE";
526 case RCSFIELD: return "RCSFIELD";
527 case RCSCMPFLD: return "RCSCMPFLD";
528 }
529
530 return "<trash>";
531 }
532
533
534
535 static int
printnode(Node * node,void * closure)536 printnode (Node *node, void *closure)
537 {
538 if (node == NULL)
539 {
540 (void) printf("NULL node.\n");
541 return 0;
542 }
543
544 #ifdef HAVE_PRINTF_PTR
545 (void) printf("Node at %p: type = %s, key = %p = \"%s\", data = %p, next = %p, prev = %p\n",
546 (void *) node, nodetypestring(node->type),
547 (void *) node->key, node->key, node->data,
548 (void *) node->next, (void *) node->prev);
549 #else
550 (void) printf("Node at 0x%lx: type = %s, key = 0x%lx = \"%s\", data = 0x%lx, next = 0x%lx, prev = 0x%lx\n",
551 (unsigned long) node, nodetypestring(node->type),
552 (unsigned long) node->key, node->key, (unsigned long) node->data,
553 (unsigned long) node->next, (unsigned long) node->prev);
554 #endif
555
556 return 0;
557 }
558
559
560
561 /* This is global, not static, so that its name is unique and to avoid
562 compiler warnings about it not being used. But it is not used by CVS;
563 it exists so one can call it from a debugger. */
564
565 void
printlist(List * list)566 printlist (List *list)
567 {
568 if (list == NULL)
569 {
570 (void) printf("NULL list.\n");
571 return;
572 }
573
574 #ifdef HAVE_PRINTF_PTR
575 (void) printf("List at %p: list = %p, HASHSIZE = %d, next = %p\n",
576 (void *) list, (void *) list->list, HASHSIZE, (void *) list->next);
577 #else
578 (void) printf("List at 0x%lx: list = 0x%lx, HASHSIZE = %d, next = 0x%lx\n",
579 (unsigned long) list, (unsigned long) list->list, HASHSIZE,
580 (unsigned long) list->next);
581 #endif
582
583 (void) walklist(list, printnode, NULL);
584
585 return;
586 }
587