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