Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 713 lines (571 sloc) 14.346 kb
a68f41b @alobbs Merges the Front-Line Cache branch.
alobbs authored
1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
2
3 /* Cherokee
4 *
5 * Authors:
6 * Alvaro Lopez Ortega <alvaro@alobbs.com>
7 *
8 * Copyright (C) 2001-2011 Alvaro Lopez Ortega
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of version 2 of the GNU General Public
12 * License as published by the Free Software Foundation.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
22 * 02110-1301, USA.
23 */
24
25 #include "common-internal.h"
26 #include "avl_generic.h"
27
28 #define MAX_HEIGHT 45
29
30
31 static cherokee_avl_generic_node_t *node_first (cherokee_avl_generic_t *avl);
32 static cherokee_avl_generic_node_t *node_prev (cherokee_avl_generic_node_t *node);
33 static cherokee_avl_generic_node_t *node_next (cherokee_avl_generic_node_t *node);
34 static ret_t node_free (cherokee_avl_generic_node_t *node, cherokee_avl_generic_t *avl);
35 static cint_t node_height (cherokee_avl_generic_node_t *node);
36
37
38 /* AVL Tree Node
39 */
40
41 ret_t
42 cherokee_avl_generic_node_init (cherokee_avl_generic_node_t *node)
43 {
44 node->balance = 0;
45 node->left = NULL;
46 node->right = NULL;
47 node->left_child = false;
48 node->right_child = false;
49 node->value = NULL;
50
51 return ret_ok;
52 }
53
54
55 /* AVL Tree
56 */
57
58 ret_t
59 cherokee_avl_generic_init (cherokee_avl_generic_t *avl)
60 {
61 avl->root = NULL;
62
63 avl->node_mrproper = NULL;
64 avl->node_cmp = NULL;
65 avl->node_is_empty = NULL;
66
67 return ret_ok;
68 }
69
70
71 /* Util
72 */
73
74 static ret_t
75 node_free (cherokee_avl_generic_node_t *node,
76 cherokee_avl_generic_t *avl)
77 {
78 avl->node_mrproper (node);
79 free (node);
80 return ret_ok;
81 }
82
83
84 static cherokee_avl_generic_node_t *
85 node_first (cherokee_avl_generic_t *avl)
86 {
87 cherokee_avl_generic_node_t *tmp;
88
89 if (!avl->root)
90 return NULL;
91
92 tmp = avl->root;
93
94 while (tmp->left_child)
95 tmp = tmp->left;
96
97 return tmp;
98 }
99
100 static cherokee_avl_generic_node_t *
101 node_next (cherokee_avl_generic_node_t *node)
102 {
103 cherokee_avl_generic_node_t *tmp = node->right;
104
105 if (node->right_child)
106 while (tmp->left_child)
107 tmp = tmp->left;
108 return tmp;
109 }
110
111 static cherokee_avl_generic_node_t *
112 node_prev (cherokee_avl_generic_node_t *node)
113 {
114 cherokee_avl_generic_node_t *tmp = node->left;
115
116 if (node->left_child)
117 while (tmp->right_child)
118 tmp = tmp->right;
119 return tmp;
120 }
121
122
123 static cherokee_avl_generic_node_t *
124 node_rotate_left (cherokee_avl_generic_node_t *node)
125 {
126 cherokee_avl_generic_node_t *right;
127 cint_t a_bal;
128 cint_t b_bal;
129
130 right = node->right;
131
132 if (right->left_child)
133 node->right = right->left;
134 else {
135 node->right_child = FALSE;
136 node->right = right;
137 right->left_child = TRUE;
138 }
139 right->left = node;
140
141 a_bal = node->balance;
142 b_bal = right->balance;
143
144 if (b_bal <= 0) {
145 if (a_bal >= 1)
146 right->balance = b_bal - 1;
147 else
148 right->balance = a_bal + b_bal - 2;
149 node->balance = a_bal - 1;
150 } else {
151 if (a_bal <= b_bal)
152 right->balance = a_bal - 2;
153 else
154 right->balance = b_bal - 1;
155 node->balance = a_bal - b_bal - 1;
156 }
157
158 return right;
159 }
160
161 static cherokee_avl_generic_node_t *
162 node_rotate_right (cherokee_avl_generic_node_t *node)
163 {
164 cherokee_avl_generic_node_t *left;
165 cint_t a_bal;
166 cint_t b_bal;
167
168 left = node->left;
169
170 if (left->right_child)
171 node->left = left->right;
172 else {
173 node->left_child = FALSE;
174 node->left = left;
175 left->right_child = TRUE;
176 }
177 left->right = node;
178
179 a_bal = node->balance;
180 b_bal = left->balance;
181
182 if (b_bal <= 0) {
183 if (b_bal > a_bal)
184 left->balance = b_bal + 1;
185 else
186 left->balance = a_bal + 2;
187 node->balance = a_bal - b_bal + 1;
188 } else {
189 if (a_bal <= -1)
190 left->balance = b_bal + 1;
191 else
192 left->balance = a_bal + b_bal + 2;
193 node->balance = a_bal + 1;
194 }
195
196 return left;
197 }
198
199
200 static cherokee_avl_generic_node_t *
201 node_balance (cherokee_avl_generic_node_t *node)
202 {
203 if (node->balance < -1) {
204 if (node->left->balance > 0)
205 node->left = node_rotate_left (node->left);
206 node = node_rotate_right (node);
207
208 } else if (node->balance > 1) {
209 if (node->right->balance < 0)
210 node->right = node_rotate_right (node->right);
211 node = node_rotate_left (node);
212 }
213
214 return node;
215 }
216
217
218 static ret_t
219 node_add (cherokee_avl_generic_t *avl, cherokee_avl_generic_node_t *child)
220 {
221 short re;
222 cherokee_boolean_t is_left;
223 cherokee_avl_generic_node_t *path[MAX_HEIGHT];
224 cherokee_avl_generic_node_t *node = avl->root;
225 cherokee_avl_generic_node_t *parent = NULL;
226 cint_t idx = 1;
227
228 path[0] = NULL;
229
230 /* If the tree is empty..
231 */
232 if (unlikely (avl->root == NULL)) {
233 avl->root = child;
234 return ret_ok;
235 }
236
237 /* Insert the node
238 */
239 while (true) {
240 re = avl->node_cmp (child, node, avl);
241
242 if (re < 0) {
243 /* Insert it on the left */
244 if (node->left_child) {
245 path[idx++] = node;
246 node = node->left;
247 } else {
248 child->left = node->left;
249 child->right = node;
250 node->left = child;
251 node->left_child = true;
252 node->balance -= 1;
253 break;
254 }
255
256 } else if (re > 0) {
257 /* Insert it on the left */
258 if (node->right_child) {
259 path[idx++] = node;
260 node = node->right;
261 } else {
262 child->right = node->right;
263 child->left = node;
264 node->right = child;
265 node->right_child = true;
266 node->balance += 1;
267 break;
268 }
269
270 } else {
271 node_free (child, avl);
272 return ret_error;
273 }
274 }
275
276 /* Rebalance the tree
277 */
278 while (true) {
279 parent = path[--idx];
280 is_left = (parent && (parent->left == node));
281
282 if ((node->balance < -1) ||
283 (node->balance > 1))
284 {
285 node = node_balance (node);
286 if (parent == NULL)
287 avl->root = node;
288 else if (is_left)
289 parent->left = node;
290 else
291 parent->right = node;
292 }
293
294 if ((node->balance == 0) || (parent == NULL))
295 break;
296
297 if (is_left)
298 parent->balance -= 1;
299 else
300 parent->balance += 1;
301
302 node = parent;
303 }
304
305 return ret_ok;
306 }
307
308
309 static cint_t
310 node_height (cherokee_avl_generic_node_t *node)
311 {
312 cint_t left_height;
313 cint_t right_height;
314
315 if (node) {
316 left_height = 0;
317 right_height = 0;
318
319 if (node->left_child)
320 left_height = node_height (node->left);
321
322 if (node->right_child)
323 right_height = node_height (node->right);
324
325 return MAX (left_height, right_height) + 1;
326 }
327 return 0;
328 }
329
330
331 static ret_t
332 node_check (cherokee_avl_generic_node_t *node)
333 {
334 cint_t left_height;
335 cint_t right_height;
336 cint_t balance;
337 cherokee_avl_generic_node_t *tmp;
338
339 if (node == NULL)
340 return ret_ok;
341
342 if (node->left_child) {
343 tmp = node_prev (node);
344 if (tmp->right != node) {
345 LOG_ERROR_S (CHEROKEE_ERROR_AVL_PREVIOUS);
346 return ret_error;
347 }
348 }
349
350 if (node->right_child) {
351 tmp = node_next (node);
352 if (tmp->left != node) {
353 LOG_ERROR_S (CHEROKEE_ERROR_AVL_NEXT);
354 return ret_error;
355 }
356 }
357
358 left_height = 0;
359 right_height = 0;
360
361 if (node->left_child)
362 left_height = node_height (node->left);
363 if (node->right_child)
364 right_height = node_height (node->right);
365
366 balance = right_height - left_height;
367 if (balance != node->balance) {
368 LOG_ERROR_S (CHEROKEE_ERROR_AVL_BALANCE);
369 return ret_error;
370 }
371
372 if (node->left_child)
373 node_check (node->left);
374 if (node->right_child)
375 node_check (node->right);
376
377 return ret_ok;
378 }
379
380
381 ret_t
382 cherokee_avl_generic_add (cherokee_avl_generic_t *avl, cherokee_avl_generic_node_t *key, void *value)
383 {
384 ret_t ret;
385
386 if (unlikely (avl->node_is_empty (key)))
387 return ret_error;
388
389 /* Store the node value
390 */
391 key->value = value;
392
393 /* Add th node to the tree
394 */
395 ret = node_add (avl, key);
396 if (unlikely (ret != ret_ok)) {
397 return ret;
398 }
399
400 return ret_ok;
401 }
402
403
404 ret_t
405 cherokee_avl_generic_del (cherokee_avl_generic_t *avl, cherokee_avl_generic_node_t *key, void **value)
406 {
407 short re;
408 cherokee_boolean_t is_left;
409 cherokee_avl_generic_node_t *path[MAX_HEIGHT];
410 cherokee_avl_generic_node_t *parent;
411 cherokee_avl_generic_node_t *pbalance;
412 cherokee_avl_generic_node_t *node = avl->root;
413 cint_t idx = 1;
414
415 if (unlikely (avl->node_is_empty (key)))
416 return ret_error;
417
418 if (avl->root == NULL)
419 return ret_not_found;
420
421 path[0] = NULL;
422
423 while (true) {
424 re = avl->node_cmp (key, node, avl);
425 if (re == 0) {
426 if (value)
427 *value = node->value;
428 break;
429 } else if (re < 0) {
430 if (!node->left_child)
431 return ret_not_found;
432 path[idx++] = node;
433 node = node->left;
434 } else {
435 if (!node->right_child)
436 return ret_not_found;
437 path[idx++] = node;
438 node = node->right;
439 }
440 }
441
442 pbalance = path[idx-1];
443 parent = pbalance;
444 idx -= 1;
445 is_left = (parent && (node == parent->left));
446
447 if (!node->left_child) {
448 if (!node->right_child) {
449 if (!parent)
450 avl->root = NULL;
451 else if (is_left) {
452 parent->left_child = false;
453 parent->left = node->left;
454 parent->balance += 1;
455 } else {
456 parent->right_child = false;
457 parent->right = node->right;
458 parent->balance -= 1;
459 }
460
461 } else { /* right child */
462 cherokee_avl_generic_node_t *tmp = node_next (node);
463 tmp->left = node->left;
464
465 if (!parent)
466 avl->root = node->right;
467 else if (is_left) {
468 parent->left = node->right;
469 parent->balance += 1;
470 } else {
471 parent->right = node->right;
472 parent->balance -= 1;
473 }
474 }
475
476 } else { /* left child */
477 if (!node->right_child) {
478 cherokee_avl_generic_node_t *tmp = node_prev(node);
479 tmp->right = node->right;
480
481 if (parent == NULL)
482 avl->root = node->left;
483 else if (is_left) {
484 parent->left = node->left;
485 parent->balance += 1;
486 } else {
487 parent->right = node->left;
488 parent->balance -= 1;
489 }
490 } else { /* both children */
491 cherokee_avl_generic_node_t *prev = node->left;
492 cherokee_avl_generic_node_t *next = node->right;
493 cherokee_avl_generic_node_t *nextp = node;
494 cint_t old_idx = idx + 1;
495 idx++;
496
497 /* find the immediately next node (and its parent) */
498 while (next->left_child) {
499 path[++idx] = nextp = next;
500 next = next->left;
501 }
502
503 path[old_idx] = next;
504 pbalance = path[idx];
505
506 /* remove 'next' from the tree */
507 if (nextp != node) {
508 if (next->right_child)
509 nextp->left = next->right;
510 else
511 nextp->left_child = FALSE;
512
513 nextp->balance += 1;
514 next->right_child = TRUE;
515 next->right = node->right;
516
517 } else {
518 node->balance -= 1;
519 }
520
521 /* set the prev to point to the right place */
522 while (prev->right_child)
523 prev = prev->right;
524 prev->right = next;
525
526 /* prepare 'next' to replace 'node' */
527 next->left_child = TRUE;
528 next->left = node->left;
529 next->balance = node->balance;
530
531 if (!parent)
532 avl->root = next;
533 else if (is_left)
534 parent->left = next;
535 else
536 parent->right = next;
537 }
538 }
539
540 /* restore balance */
541 if (pbalance) {
542 while (true) {
543 cherokee_avl_generic_node_t *bparent = path[--idx];
544 is_left = (bparent && (pbalance == bparent->left));
545
546 if(pbalance->balance < -1 || pbalance->balance > 1) {
547 pbalance = node_balance (pbalance);
548 if (!bparent)
549 avl->root = pbalance;
550 else if (is_left)
551 bparent->left = pbalance;
552 else
553 bparent->right = pbalance;
554 }
555
556 if (pbalance->balance != 0 || !bparent)
557 break;
558
559 if (is_left)
560 bparent->balance += 1;
561 else
562 bparent->balance -= 1;
563
564 pbalance = bparent;
565 }
566 }
567
568 node_free (node, avl);
569 return ret_ok;
570 }
571
572
573 ret_t
574 cherokee_avl_generic_get (cherokee_avl_generic_t *avl, cherokee_avl_generic_node_t *key, void **value)
575 {
576 short re;
577 cherokee_avl_generic_node_t *node;
578
579 if (unlikely (avl->node_is_empty (key)))
580 return ret_error;
581
582 node = avl->root;
583 if (!node)
584 return ret_not_found;
585
586 while (true) {
587 re = avl->node_cmp (key, node, avl);
588 if (re == 0) {
589 if (value)
590 *value = node->value;
591 return ret_ok;
592
593 } else if (re < 0) {
594 if (!node->left_child)
595 return ret_not_found;
596 node = node->left;
597
598 } else {
599 if (!node->right_child)
600 return ret_not_found;
601 node = node->right;
602 }
603 }
604
605 SHOULDNT_HAPPEN;
606 return ret_error;
607 }
608
609
610 ret_t
611 cherokee_avl_check (cherokee_avl_generic_t *avl)
612 {
613 return node_check (avl->root);
614 }
615
616
617 ret_t
618 cherokee_avl_generic_while (cherokee_avl_generic_t *avl,
619 cherokee_avl_generic_while_func_t func,
620 void *param,
621 cherokee_avl_generic_node_t **key,
622 void **value)
623 {
624 ret_t ret;
625 cherokee_avl_generic_node_t *node = avl->root;
626
627 if (avl->root == NULL) {
628 return ret_ok;
629 }
630
631 node = node_first (avl);
632 while (node) {
633 if (key)
634 *key = node;
635 if (value)
636 *value = node->value;
637
638 ret = func (node, node->value, param);
639 if (ret != ret_ok) return ret;
640
641 node = node_next (node);
642 }
643
644 return ret_ok;
645 }
646
647
648 static ret_t
649 func_len_each (cherokee_avl_generic_node_t *key, void *value, void *param)
650 {
651 UNUSED(key);
652 UNUSED(value);
653
654 *((size_t *)param) += 1;
655 return ret_ok;
656 }
657
658
659 ret_t
660 cherokee_avl_len (cherokee_avl_generic_t *avl, size_t *len)
661 {
662 *len = 0;
663 return cherokee_avl_generic_while (avl, func_len_each, len, NULL, NULL);
664 }
665
666
667 ret_t
668 cherokee_avl_mrproper (cherokee_avl_generic_t *avl,
669 cherokee_func_free_t free_func)
670 {
671 cherokee_avl_generic_node_t *node;
672 cherokee_avl_generic_node_t *next;
673
674 if (unlikely (avl == NULL))
675 return ret_ok;
676
677 node = node_first (avl);
678
679 while (node) {
680 next = node_next (node);
681
682 /* Node content */
683 if (free_func) {
684 free_func (node->value);
685 }
686
687 /* Node itself */
688 node_free (node, avl);
689
690 node = next;
691 }
692
693 return ret_ok;
694 }
695
696 ret_t
697 cherokee_avl_free (cherokee_avl_generic_t *avl,
698 cherokee_func_free_t free_func)
699 {
700 ret_t ret;
701 ret = cherokee_avl_mrproper (avl, free_func);
702
703 free (avl);
704 return ret;
705 }
706
707
708 int
709 cherokee_avl_is_empty (cherokee_avl_generic_t *avl)
710 {
711 return (avl->root == NULL);
712 }
Something went wrong with that request. Please try again.