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 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 * 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 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 * 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 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 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 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 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 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 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 * 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 * 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 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 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 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 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 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 * 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 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 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