1 /*
2 Copyright (C) 1993-2018 Free Software Foundation, Inc.
3 This file is largely based on the GNU C Library and contains:
4
5 * System V style searching functions
6 - Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997.
7 * Hash table management functions
8 - Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1993.
9
10 The GNU C Library is free software; you can redistribute it and/or
11 modify it under the terms of the GNU Lesser General Public
12 License as published by the Free Software Foundation; either
13 version 2.1 of the License, or (at your option) any later version.
14
15 The GNU C Library is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 Lesser General Public License for more details.
19
20 You should have received a copy of the GNU Lesser General Public
21 License along with the GNU C Library; if not, see
22 <http://www.gnu.org/licenses/>.
23 */
24
25 /* Tree search for red/black trees.
26 The algorithm for adding nodes is taken from one of the many "Algorithms"
27 books by Robert Sedgewick, although the implementation differs.
28 The algorithm for deleting nodes can probably be found in a book named
29 "Introduction to Algorithms" by Cormen/Leiserson/Rivest. At least that's
30 the book that my professor took most algorithms from during the "Data
31 Structures" course... Totally public domain. */
32
33 /* Red/black trees are binary trees in which the edges are colored either red
34 or black. They have the following properties:
35 1. The number of black edges on every path from the root to a leaf is
36 constant.
37 2. No two red edges are adjacent.
38 Therefore there is an upper bound on the length of every path, it's
39 O(log n) where n is the number of nodes in the tree. No path can be longer
40 than 1+2*P where P is the length of the shortest path in the tree.
41 Useful for the implementation:
42 3. If one of the children of a node is NULL, then the other one is red
43 (if it exists).
44
45 In the implementation, not the edges are colored, but the nodes. The color
46 interpreted as the color of the edge leading to this node. The color is
47 meaningless for the root node, but we color the root node black for
48 convenience. All added nodes are red initially.
49
50 Adding to a red/black tree is rather easy. The right place is searched
51 with a usual binary tree search. Additionally, whenever a node N is
52 reached that has two red successors, the successors are colored black and
53 the node itself colored red. This moves red edges up the tree where they
54 pose less of a problem once we get to really insert the new node. Changing
55 N's color to red may violate rule 2, however, so rotations may become
56 necessary to restore the invariants. Adding a new red leaf may violate
57 the same rule, so afterwards an additional check is run and the tree
58 possibly rotated.
59
60 Deleting is hairy. There are mainly two nodes involved: the node to be
61 deleted (n1), and another node that is to be unchained from the tree (n2).
62 If n1 has a successor (the node with a smallest key that is larger than
63 n1), then the successor becomes n2 and its contents are copied into n1,
64 otherwise n1 becomes n2.
65 Unchaining a node may violate rule 1: if n2 is black, one subtree is
66 missing one black edge afterwards. The algorithm must try to move this
67 error upwards towards the root, so that the subtree that does not have
68 enough black edges becomes the whole tree. Once that happens, the error
69 has disappeared. It may not be necessary to go all the way up, since it
70 is possible that rotations and recoloring can fix the error before that.
71
72 Although the deletion algorithm must walk upwards through the tree, we
73 do not store parent pointers in the nodes. Instead, delete allocates a
74 small array of parent pointers and fills it while descending the tree.
75 Since we know that the length of a path is O(log n), where n is the number
76 of nodes, this is likely to use less memory. */
77
78 /* Tree rotations look like this:
79 A C
80 / \ / \
81 B C A G
82 / \ / \ --> / \
83 D E F G B F
84 / \
85 D E
86
87 In this case, A has been rotated left. This preserves the ordering of the
88 binary tree. */
89
90 /* includes */
91 #include "pmacct.h"
92 #include "crc32.h"
93
94 /* Possibly "split" a node with two red successors, and/or fix up two red
95 edges in a row. ROOTP is a pointer to the lowest node we visited, PARENTP
96 and GPARENTP pointers to its parent/grandparent. P_R and GP_R contain the
97 comparison values that determined which way was taken in the tree to reach
98 ROOTP. MODE is 1 if we need not do the split, but must check for two red
99 edges between GPARENTP and ROOTP. */
100 static void
pm_maybe_split_for_insert(pm_node * rootp,pm_node * parentp,pm_node * gparentp,int p_r,int gp_r,int mode)101 pm_maybe_split_for_insert (pm_node *rootp, pm_node *parentp, pm_node *gparentp,
102 int p_r, int gp_r, int mode)
103 {
104 pm_node root = DEREFNODEPTR(rootp);
105 pm_node *rp, *lp;
106 pm_node rpn, lpn;
107 rp = RIGHTPTR(root);
108 rpn = RIGHT(root);
109 lp = LEFTPTR(root);
110 lpn = LEFT(root);
111
112 /* See if we have to split this node (both successors red). */
113 if (mode == 1
114 || ((rpn) != NULL && (lpn) != NULL && RED(rpn) && RED(lpn)))
115 {
116 /* This node becomes red, its successors black. */
117 SETRED(root);
118 if (rpn)
119 SETBLACK(rpn);
120 if (lpn)
121 SETBLACK(lpn);
122
123 /* If the parent of this node is also red, we have to do
124 rotations. */
125 if (parentp != NULL && RED(DEREFNODEPTR(parentp)))
126 {
127 pm_node gp = DEREFNODEPTR(gparentp);
128 pm_node p = DEREFNODEPTR(parentp);
129 /* There are two main cases:
130 1. The edge types (left or right) of the two red edges differ.
131 2. Both red edges are of the same type.
132 There exist two symmetries of each case, so there is a total of
133 4 cases. */
134 if ((p_r > 0) != (gp_r > 0))
135 {
136 /* Put the child at the top of the tree, with its parent
137 and grandparent as successors. */
138 SETRED(p);
139 SETRED(gp);
140 SETBLACK(root);
141 if (p_r < 0)
142 {
143 /* Child is left of parent. */
144 SETLEFT(p,rpn);
145 SETNODEPTR(rp,p);
146 SETRIGHT(gp,lpn);
147 SETNODEPTR(lp,gp);
148 }
149 else
150 {
151 /* Child is right of parent. */
152 SETRIGHT(p,lpn);
153 SETNODEPTR(lp,p);
154 SETLEFT(gp,rpn);
155 SETNODEPTR(rp,gp);
156 }
157 SETNODEPTR(gparentp,root);
158 }
159 else
160 {
161 SETNODEPTR(gparentp,p);
162 /* Parent becomes the top of the tree, grandparent and
163 child are its successors. */
164 SETBLACK(p);
165 SETRED(gp);
166 if (p_r < 0)
167 {
168 /* Left edges. */
169 SETLEFT(gp,RIGHT(p));
170 SETRIGHT(p,gp);
171 }
172 else
173 {
174 /* Right edges. */
175 SETRIGHT(gp,LEFT(p));
176 SETLEFT(p,gp);
177 }
178 }
179 }
180 }
181 }
182
183 /* Find or insert datum into search tree.
184 KEY is the key to be located, ROOTP is the address of tree root,
185 COMPAR the ordering function. */
__pm_tsearch(const void * key,void ** vrootp,pm_compar_fn_t compar)186 void * __pm_tsearch (const void *key, void **vrootp, pm_compar_fn_t compar)
187 {
188 pm_node q, root;
189 pm_node *parentp = NULL, *gparentp = NULL;
190 pm_node *rootp = (pm_node *) vrootp;
191 pm_node *nextp;
192 int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler. */
193
194 // static_assert (alignof (max_align_t) > 1, "malloc must return aligned ptrs");
195
196 if (rootp == NULL)
197 return NULL;
198
199 /* This saves some additional tests below. */
200 root = DEREFNODEPTR(rootp);
201 if (root != NULL)
202 SETBLACK(root);
203
204 nextp = rootp;
205 while (DEREFNODEPTR(nextp) != NULL)
206 {
207 root = DEREFNODEPTR(rootp);
208 r = (*compar) (key, root->key);
209 if (r == 0)
210 return root;
211
212 pm_maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0);
213 /* If that did any rotations, parentp and gparentp are now garbage.
214 That doesn't matter, because the values they contain are never
215 used again in that case. */
216
217 nextp = r < 0 ? LEFTPTR(root) : RIGHTPTR(root);
218 if (DEREFNODEPTR(nextp) == NULL)
219 break;
220
221 gparentp = parentp;
222 parentp = rootp;
223 rootp = nextp;
224
225 gp_r = p_r;
226 p_r = r;
227 }
228
229 q = (struct pm_node_t *) malloc (sizeof (struct pm_node_t));
230 if (q != NULL)
231 {
232 /* Make sure the malloc implementation returns naturally aligned
233 memory blocks when expected. Or at least even pointers, so we
234 can use the low bit as red/black flag. Even though we have a
235 static_assert to make sure alignof (max_align_t) > 1 there could
236 be an interposed malloc implementation that might cause havoc by
237 not obeying the malloc contract. */
238 assert (((uintptr_t) q & (uintptr_t) 0x1) == 0);
239 SETNODEPTR(nextp,q); /* link new node to old */
240 q->key = key; /* initialize new node */
241 SETRED(q);
242 SETLEFT(q,NULL);
243 SETRIGHT(q,NULL);
244
245 if (nextp != rootp)
246 /* There may be two red edges in a row now, which we must avoid by
247 rotating the tree. */
248 pm_maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1);
249 }
250
251 return q;
252 }
253
254 /* Find datum in search tree.
255 KEY is the key to be located, ROOTP is the address of tree root,
256 COMPAR the ordering function. */
pm_tfind(const void * key,void ** vrootp,pm_compar_fn_t compar)257 void *pm_tfind (const void *key, void **vrootp, pm_compar_fn_t compar)
258 {
259 pm_node root;
260 pm_node *rootp = (pm_node *) vrootp;
261
262 if (rootp == NULL)
263 return NULL;
264
265 root = DEREFNODEPTR(rootp);
266
267 while (DEREFNODEPTR(rootp) != NULL)
268 {
269 root = DEREFNODEPTR(rootp);
270 int r;
271
272 r = (*compar) (key, root->key);
273 if (r == 0)
274 return root;
275
276 rootp = r < 0 ? LEFTPTR(root) : RIGHTPTR(root);
277 }
278 return NULL;
279 }
280
281 /* Delete node with given key.
282 KEY is the key to be deleted, ROOTP is the address of the root of tree,
283 COMPAR the comparison function. */
pm_tdelete(const void * key,void ** vrootp,pm_compar_fn_t compar)284 void *pm_tdelete (const void *key, void **vrootp, pm_compar_fn_t compar)
285 {
286 pm_node p, q, r, retval;
287 int cmp;
288 pm_node *rootp = (pm_node *) vrootp;
289 pm_node root, unchained;
290 /* Stack of nodes so we remember the parents without recursion. It's
291 _very_ unlikely that there are paths longer than 40 nodes. The tree
292 would need to have around 250.000 nodes. */
293 int stacksize = 40;
294 int sp = 0;
295 pm_node **nodestack = alloca (sizeof (pm_node *) * stacksize);
296
297 if (rootp == NULL)
298 return NULL;
299 p = DEREFNODEPTR(rootp);
300 if (p == NULL)
301 return NULL;
302
303 root = DEREFNODEPTR(rootp);
304 while ((cmp = (*compar) (key, root->key)) != 0)
305 {
306 if (sp == stacksize)
307 {
308 pm_node **newstack;
309 stacksize += 20;
310 newstack = alloca (sizeof (pm_node *) * stacksize);
311 nodestack = memcpy (newstack, nodestack, sp * sizeof (pm_node *));
312 }
313
314 nodestack[sp++] = rootp;
315 p = DEREFNODEPTR(rootp);
316 if (cmp < 0)
317 {
318 rootp = LEFTPTR(p);
319 root = LEFT(p);
320 }
321 else
322 {
323 rootp = RIGHTPTR(p);
324 root = RIGHT(p);
325 }
326 if (root == NULL)
327 return NULL;
328 }
329
330 /* This is bogus if the node to be deleted is the root... this routine
331 really should return an integer with 0 for success, -1 for failure */
332 retval = p;
333
334 /* We don't unchain the node we want to delete. Instead, we overwrite
335 it with its successor and unchain the successor. If there is no
336 successor, we really unchain the node to be deleted. */
337
338 root = DEREFNODEPTR(rootp);
339
340 r = RIGHT(root);
341 q = LEFT(root);
342
343 if (q == NULL || r == NULL)
344 unchained = root;
345 else
346 {
347 pm_node *parentp = rootp, *up = RIGHTPTR(root);
348 pm_node upn;
349 for (;;)
350 {
351 if (sp == stacksize)
352 {
353 pm_node **newstack;
354 stacksize += 20;
355 newstack = alloca (sizeof (pm_node *) * stacksize);
356 nodestack = memcpy (newstack, nodestack, sp * sizeof (pm_node *));
357 }
358 nodestack[sp++] = parentp;
359 parentp = up;
360 upn = DEREFNODEPTR(up);
361 if (LEFT(upn) == NULL)
362 break;
363 up = LEFTPTR(upn);
364 }
365 unchained = DEREFNODEPTR(up);
366 }
367
368 /* We know that either the left or right successor of UNCHAINED is NULL.
369 R becomes the other one, it is chained into the parent of UNCHAINED. */
370 r = LEFT(unchained);
371 if (r == NULL)
372 r = RIGHT(unchained);
373 if (sp == 0)
374 SETNODEPTR(rootp,r);
375 else
376 {
377 q = DEREFNODEPTR(nodestack[sp-1]);
378 if (unchained == RIGHT(q))
379 SETRIGHT(q,r);
380 else
381 SETLEFT(q,r);
382 }
383
384 if (unchained != root)
385 root->key = unchained->key;
386 if (!RED(unchained))
387 {
388 /* Now we lost a black edge, which means that the number of black
389 edges on every path is no longer constant. We must balance the
390 tree. */
391 /* NODESTACK now contains all parents of R. R is likely to be NULL
392 in the first iteration. */
393 /* NULL nodes are considered black throughout - this is necessary for
394 correctness. */
395 while (sp > 0 && (r == NULL || !RED(r)))
396 {
397 pm_node *pp = nodestack[sp - 1];
398 p = DEREFNODEPTR(pp);
399 /* Two symmetric cases. */
400 if (r == LEFT(p))
401 {
402 /* Q is R's brother, P is R's parent. The subtree with root
403 R has one black edge less than the subtree with root Q. */
404 q = RIGHT(p);
405 if (RED(q))
406 {
407 /* If Q is red, we know that P is black. We rotate P left
408 so that Q becomes the top node in the tree, with P below
409 it. P is colored red, Q is colored black.
410 This action does not change the black edge count for any
411 leaf in the tree, but we will be able to recognize one
412 of the following situations, which all require that Q
413 is black. */
414 SETBLACK(q);
415 SETRED(p);
416 /* Left rotate p. */
417 SETRIGHT(p,LEFT(q));
418 SETLEFT(q,p);
419 SETNODEPTR(pp,q);
420 /* Make sure pp is right if the case below tries to use
421 it. */
422 nodestack[sp++] = pp = LEFTPTR(q);
423 q = RIGHT(p);
424 }
425 /* We know that Q can't be NULL here. We also know that Q is
426 black. */
427 if ((LEFT(q) == NULL || !RED(LEFT(q)))
428 && (RIGHT(q) == NULL || !RED(RIGHT(q))))
429 {
430 /* Q has two black successors. We can simply color Q red.
431 The whole subtree with root P is now missing one black
432 edge. Note that this action can temporarily make the
433 tree invalid (if P is red). But we will exit the loop
434 in that case and set P black, which both makes the tree
435 valid and also makes the black edge count come out
436 right. If P is black, we are at least one step closer
437 to the root and we'll try again the next iteration. */
438 SETRED(q);
439 r = p;
440 }
441 else
442 {
443 /* Q is black, one of Q's successors is red. We can
444 repair the tree with one operation and will exit the
445 loop afterwards. */
446 if (RIGHT(q) == NULL || !RED(RIGHT(q)))
447 {
448 /* The left one is red. We perform the same action as
449 in maybe_split_for_insert where two red edges are
450 adjacent but point in different directions:
451 Q's left successor (let's call it Q2) becomes the
452 top of the subtree we are looking at, its parent (Q)
453 and grandparent (P) become its successors. The former
454 successors of Q2 are placed below P and Q.
455 P becomes black, and Q2 gets the color that P had.
456 This changes the black edge count only for node R and
457 its successors. */
458 pm_node q2 = LEFT(q);
459 if (RED(p))
460 SETRED(q2);
461 else
462 SETBLACK(q2);
463 SETRIGHT(p,LEFT(q2));
464 SETLEFT(q,RIGHT(q2));
465 SETRIGHT(q2,q);
466 SETLEFT(q2,p);
467 SETNODEPTR(pp,q2);
468 SETBLACK(p);
469 }
470 else
471 {
472 /* It's the right one. Rotate P left. P becomes black,
473 and Q gets the color that P had. Q's right successor
474 also becomes black. This changes the black edge
475 count only for node R and its successors. */
476 if (RED(p))
477 SETRED(q);
478 else
479 SETBLACK(q);
480 SETBLACK(p);
481
482 SETBLACK(RIGHT(q));
483
484 /* left rotate p */
485 SETRIGHT(p,LEFT(q));
486 SETLEFT(q,p);
487 SETNODEPTR(pp,q);
488 }
489
490 /* We're done. */
491 sp = 1;
492 r = NULL;
493 }
494 }
495 else
496 {
497 /* Comments: see above. */
498 q = LEFT(p);
499 if (RED(q))
500 {
501 SETBLACK(q);
502 SETRED(p);
503 SETLEFT(p,RIGHT(q));
504 SETRIGHT(q,p);
505 SETNODEPTR(pp,q);
506 nodestack[sp++] = pp = RIGHTPTR(q);
507 q = LEFT(p);
508 }
509 if ((RIGHT(q) == NULL || !RED(RIGHT(q)))
510 && (LEFT(q) == NULL || !RED(LEFT(q))))
511 {
512 SETRED(q);
513 r = p;
514 }
515 else
516 {
517 if (LEFT(q) == NULL || !RED(LEFT(q)))
518 {
519 pm_node q2 = RIGHT(q);
520 if (RED(p))
521 SETRED(q2);
522 else
523 SETBLACK(q2);
524 SETLEFT(p,RIGHT(q2));
525 SETRIGHT(q,LEFT(q2));
526 SETLEFT(q2,q);
527 SETRIGHT(q2,p);
528 SETNODEPTR(pp,q2);
529 SETBLACK(p);
530 }
531 else
532 {
533 if (RED(p))
534 SETRED(q);
535 else
536 SETBLACK(q);
537 SETBLACK(p);
538 SETBLACK(LEFT(q));
539 SETLEFT(p,RIGHT(q));
540 SETRIGHT(q,p);
541 SETNODEPTR(pp,q);
542 }
543 sp = 1;
544 r = NULL;
545 }
546 }
547 --sp;
548 }
549 if (r != NULL)
550 SETBLACK(r);
551 }
552
553 free (unchained);
554 return retval;
555 }
556
557 /* Walk the nodes of a tree.
558 ROOT is the root of the tree to be walked, ACTION the function to be
559 called at each node. LEVEL is the level of ROOT in the whole tree.
560 RET, the return level from ACTION, says if continue (TRUE) or break
561 (FALSE), ie. due to budgeted traversal */
pm_trecurse(const void * vroot,pm_action_fn_t action,int level,void * extra)562 static void pm_trecurse (const void *vroot, pm_action_fn_t action, int level, void *extra)
563 {
564 int ret = TRUE;
565 pm_const_node root = (pm_const_node) vroot;
566
567 if (LEFT(root) == NULL && RIGHT(root) == NULL) {
568 ret = (*action) (root, leaf, level, extra);
569 }
570 else {
571 ret = (*action) (root, preorder, level, extra);
572 if (!ret) goto exit_lane;
573
574 if (LEFT(root) != NULL)
575 pm_trecurse (LEFT(root), action, level + 1, extra);
576
577 ret = (*action) (root, postorder, level, extra);
578 if (!ret) goto exit_lane;
579
580 if (RIGHT(root) != NULL)
581 pm_trecurse (RIGHT(root), action, level + 1, extra);
582
583 ret = (*action) (root, endorder, level, extra);
584 if (!ret) goto exit_lane;
585 }
586
587 exit_lane:
588
589 return;
590 }
591
592 /* Walk the nodes of a tree.
593 ROOT is the root of the tree to be walked, ACTION the function to be
594 called at each node. */
pm_twalk(const void * vroot,pm_action_fn_t action,void * extra)595 void pm_twalk (const void *vroot, pm_action_fn_t action, void *extra)
596 {
597 pm_const_node root = (pm_const_node) vroot;
598
599 if (root != NULL && action != NULL)
600 pm_trecurse (root, action, 0, extra);
601 }
602
603 /* The standardized functions miss an important functionality: the
604 tree cannot be removed easily. We provide a function to do this. */
pm_tdestroy_recurse(pm_node root,pm_free_fn_t freefct)605 static void pm_tdestroy_recurse (pm_node root, pm_free_fn_t freefct)
606 {
607 if (LEFT(root) != NULL)
608 pm_tdestroy_recurse (LEFT(root), freefct);
609 if (RIGHT(root) != NULL)
610 pm_tdestroy_recurse (RIGHT(root), freefct);
611 (*freefct) ((void *) root->key);
612 /* Free the node itself. */
613 free (root);
614 }
615
__pm_tdestroy(void * vroot,pm_free_fn_t freefct)616 void __pm_tdestroy (void *vroot, pm_free_fn_t freefct)
617 {
618 pm_node root = (pm_node) vroot;
619
620 if (root != NULL)
621 pm_tdestroy_recurse (root, freefct);
622 }
623
624 /* For the used double hash method the table size has to be a prime. To
625 correct the user given table size we need a prime test. This trivial
626 algorithm is adequate because
627 a) the code is (most probably) called a few times per program run and
628 b) the number is small because the table must fit in the core */
pm_isprime(unsigned int number)629 static int pm_isprime(unsigned int number)
630 {
631 unsigned int div;
632
633 /* no even number will be passed */
634 for (div = 3; div <= number / div; div += 2) {
635 if (number % div == 0) return 0;
636 }
637
638 return 1;
639 }
640
641 /* Before using the hash table we must allocate memory for it.
642 Test for an existing table are done. We allocate one element
643 more as the found prime number says. This is done for more effective
644 indexing as explained in the comment for the hsearch function.
645 The contents of the table is zeroed, especially the field used
646 becomes zero. */
pm_hcreate(size_t nel,struct pm_htable * htab)647 int pm_hcreate(size_t nel, struct pm_htable *htab)
648 {
649 /* Test for correct arguments. */
650 if (htab == NULL) return 0;
651
652 /* There is still another table active. Return with error. */
653 if (htab->table != NULL) return 0;
654
655 /* We need a size of at least 3. Otherwise the hash functions we
656 use will not work. */
657 if (nel < 3) nel = 3;
658
659 /* Change nel to the first prime number in the range [nel, UINT_MAX - 2],
660 The '- 2' means 'nel += 2' cannot overflow. */
661 for (nel |= 1; ; nel += 2) {
662 if (UINT_MAX - 2 < nel) return 0;
663
664 if (pm_isprime (nel)) break;
665 }
666
667 htab->size = nel;
668 htab->filled = 0;
669
670 /* allocate memory and zero out */
671 htab->table = (_pm_HENTRY *) calloc (htab->size + 1, sizeof (_pm_HENTRY));
672 if (htab->table == NULL) return 0;
673
674 /* everything went alright */
675 return 1;
676 }
677
678 /* After using the hash table it has to be destroyed. The used memory can
679 be freed and the local static variable can be marked as not used. */
pm_hdestroy(struct pm_htable * htab)680 void pm_hdestroy(struct pm_htable *htab)
681 {
682 size_t idx;
683
684 /* Test for correct arguments. */
685 if (htab == NULL) return;
686
687 for (idx = 0; idx < htab->size; idx++) __pm_hdelete(&htab->table[idx]);
688
689 /* Free used memory. */
690 free (htab->table);
691
692 /* the sign for an existing table is an value != NULL in htable */
693 htab->table = NULL;
694 }
695
696 /* This is the search function. It uses double hashing with open addressing.
697 The argument item.key has to be a pointer to an zero terminated, most
698 probably strings of chars. The function for generating a number of the
699 strings is simple but fast. It can be replaced by a more complex function
700 like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
701 We use an trick to speed up the lookup. The table is created by hcreate
702 with one more element available. This enables us to use the index zero
703 special. This index will never be used because we store the first hash
704 index in the field used where zero means not used. Every other value
705 means used. The used field can be used as a first fast comparison for
706 equality of the stored and the parameter value. This helps to prevent
707 unnecessary more expensive calls of memcmp. */
pm_hsearch(pm_HENTRY item,pm_ACTION action,pm_HENTRY ** retval,struct pm_htable * htab)708 int pm_hsearch(pm_HENTRY item, pm_ACTION action, pm_HENTRY **retval, struct pm_htable *htab)
709 {
710 unsigned int hval;
711 unsigned int idx;
712
713 /* Compute an value for the given string. Perhaps use a better method. */
714 hval = cache_crc32(item.key, item.keylen);
715
716 /* First hash function: simply take the modul but prevent zero. */
717 idx = hval % htab->size + 1;
718 if (htab->table[idx].used) {
719 /* Further action might be required according to the action value. */
720 if (htab->table[idx].used == hval && item.keylen == htab->table[idx].entry.keylen
721 && (!memcmp(item.key, htab->table[idx].entry.key, item.keylen))) {
722 if (action == DELETE) {
723 __pm_hdelete(&htab->table[idx]);
724 (*retval) = NULL;
725 }
726 else {
727 (*retval) = &htab->table[idx].entry;
728 }
729
730 return 1;
731 }
732
733 /* Second hash function, as suggested in [Knuth] */
734 unsigned int hval2 = 1 + hval % (htab->size - 2);
735 unsigned int first_idx = idx;
736 do {
737 /* Because SIZE is prime this guarantees to step through all available indeces */
738 if (idx <= hval2) idx = htab->size + idx - hval2;
739 else idx -= hval2;
740
741 /* If we visited all entries leave the loop unsuccessfully. */
742 if (idx == first_idx) break;
743
744 /* If entry is found use it. */
745 if (htab->table[idx].used == hval && item.keylen == htab->table[idx].entry.keylen
746 && (!memcmp(item.key, htab->table[idx].entry.key, item.keylen))) {
747 if (action == DELETE) {
748 __pm_hdelete(&htab->table[idx]);
749 (*retval) = NULL;
750 }
751 else {
752 (*retval) = &htab->table[idx].entry;
753 }
754
755 return 1;
756 }
757 }
758 while (htab->table[idx].used);
759 }
760
761 /* An empty bucket has been found. */
762 if (action == INSERT) {
763 /* If table is full and another entry should be entered return with error. */
764 if (htab->filled == htab->size) {
765 *retval = NULL;
766 return ERR;
767 }
768
769 htab->table[idx].used = hval;
770 htab->table[idx].entry = item;
771 ++htab->filled;
772 *retval = &htab->table[idx].entry;
773
774 return 1;
775 }
776
777 *retval = NULL;
778 return 0;
779 }
780
pm_hmove(struct pm_htable * new_htab,struct pm_htable * old_htab,struct pm_htable * saved_htab)781 void pm_hmove(struct pm_htable *new_htab, struct pm_htable *old_htab, struct pm_htable *saved_htab)
782 {
783 memcpy(saved_htab, old_htab, sizeof(struct pm_htable));
784 memcpy(old_htab, new_htab, sizeof(struct pm_htable));
785 }
786
__pm_hdelete(_pm_HENTRY * item)787 void __pm_hdelete(_pm_HENTRY *item)
788 {
789 item->used = 0;
790
791 item->entry.keylen = 0;
792 free(item->entry.key);
793 item->entry.key = NULL;
794
795 if (item->entry.data) {
796 free(item->entry.data);
797 item->entry.data = NULL;
798 }
799 }
800