source: trunk/debian/packages/libubox/trunk/avl.c @ 857

Last change on this file since 857 was 857, checked in by amain, 4 years ago

libubox: initial import / part 4

File size: 16.1 KB
Line 
1/*
2 * PacketBB handler library (see RFC 5444)
3 * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
4 * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 *   notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 *   notice, this list of conditions and the following disclaimer in
15 *   the documentation and/or other materials provided with the
16 *   distribution.
17 * * Neither the name of olsr.org, olsrd nor the names of its
18 *   contributors may be used to endorse or promote products derived
19 *   from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *
34 * Visit http://www.olsr.org/git for more information.
35 *
36 * If you find this software useful feel free to make a donation
37 * to the project. For more information see the website or contact
38 * the copyright holders.
39 */
40
41#include <stdbool.h>
42#include <stddef.h>
43#include <stdint.h>
44#include <time.h>
45#include <string.h>
46
47#include "avl.h"
48#include "list.h"
49
50/**
51 * internal type save inline function to calculate the maximum of
52 * to integers without macro implementation.
53 *
54 * @param x first parameter of maximum function
55 * @param y second parameter of maximum function
56 * @return largest integer of both parameters
57 */
58static inline int avl_max(int x, int y) {
59  return x > y ? x : y;
60}
61
62/**
63 * internal type save inline function to calculate the minimum of
64 * to integers without macro implementation.
65 *
66 * @param x first parameter of minimum function
67 * @param y second parameter of minimum function
68 * @return smallest integer of both parameters
69 */
70static inline int avl_min(int x, int y) {
71  return x < y ? x : y;
72}
73
74static struct avl_node *
75avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result);
76static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
77static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
78static void post_insert(struct avl_tree *tree, struct avl_node *node);
79static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node);
80static void avl_remove(struct avl_tree *tree, struct avl_node *node);
81
82/**
83 * Initialize a new avl_tree struct
84 * @param tree pointer to avl-tree
85 * @param comp pointer to comparator for the tree
86 * @param allow_dups true if the tree allows multiple
87 *   elements with the same
88 * @param ptr custom parameter for comparator
89 */
90void
91avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr)
92{
93  INIT_LIST_HEAD(&tree->list_head);
94  tree->root = NULL;
95  tree->count = 0;
96  tree->comp = comp;
97  tree->allow_dups = allow_dups;
98  tree->cmp_ptr = ptr;
99}
100
101static inline struct avl_node *avl_next(struct avl_node *node)
102{
103    return list_entry(node->list.next, struct avl_node, list);
104}
105
106/**
107 * Finds a node in an avl-tree with a certain key
108 * @param tree pointer to avl-tree
109 * @param key pointer to key
110 * @return pointer to avl-node with key, NULL if no node with
111 *    this key exists.
112 */
113struct avl_node *
114avl_find(const struct avl_tree *tree, const void *key)
115{
116  struct avl_node *node;
117  int diff;
118
119  if (tree->root == NULL)
120    return NULL;
121
122  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
123
124  return diff == 0 ? node : NULL;
125}
126
127/**
128 * Finds the last node in an avl-tree with a key less or equal
129 * than the specified key
130 * @param tree pointer to avl-tree
131 * @param key pointer to specified key
132 * @return pointer to avl-node, NULL if no node with
133 *    key less or equal specified key exists.
134 */
135struct avl_node *
136avl_find_lessequal(const struct avl_tree *tree, const void *key) {
137  struct avl_node *node, *next;
138  int diff;
139
140  if (tree->root == NULL)
141    return NULL;
142
143  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
144
145  /* go left as long as key<node.key */
146  while (diff < 0) {
147    if (list_is_first(&node->list, &tree->list_head)) {
148      return NULL;
149    }
150
151    node = (struct avl_node *)node->list.prev;
152    diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
153  }
154
155  /* go right as long as key>=next_node.key */
156  next = node;
157  while (diff >= 0) {
158    node = next;
159    if (list_is_last(&node->list, &tree->list_head)) {
160      break;
161    }
162
163    next = (struct avl_node *)node->list.next;
164    diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
165  }
166  return node;
167}
168
169/**
170 * Finds the first node in an avl-tree with a key greater or equal
171 * than the specified key
172 * @param tree pointer to avl-tree
173 * @param key pointer to specified key
174 * @return pointer to avl-node, NULL if no node with
175 *    key greater or equal specified key exists.
176 */
177struct avl_node *
178avl_find_greaterequal(const struct avl_tree *tree, const void *key) {
179  struct avl_node *node, *next;
180  int diff;
181
182  if (tree->root == NULL)
183    return NULL;
184
185  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
186
187  /* go right as long as key>node.key */
188  while (diff > 0) {
189    if (list_is_last(&node->list, &tree->list_head)) {
190      return NULL;
191    }
192
193    node = (struct avl_node *)node->list.next;
194    diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
195  }
196
197  /* go left as long as key<=next_node.key */
198  next = node;
199  while (diff <= 0) {
200    node = next;
201    if (list_is_first(&node->list, &tree->list_head)) {
202      break;
203    }
204
205    next = (struct avl_node *)node->list.prev;
206    diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
207  }
208  return node;
209}
210
211/**
212 * Inserts an avl_node into a tree
213 * @param tree pointer to tree
214 * @param new pointer to node
215 * @return 0 if node was inserted successfully, -1 if it was not inserted
216 *   because of a key collision
217 */
218int
219avl_insert(struct avl_tree *tree, struct avl_node *new)
220{
221  struct avl_node *node, *next, *last;
222  int diff;
223
224  new->parent = NULL;
225
226  new->left = NULL;
227  new->right = NULL;
228
229  new->balance = 0;
230  new->leader = true;
231
232  if (tree->root == NULL) {
233    list_add(&new->list, &tree->list_head);
234    tree->root = new;
235    tree->count = 1;
236    return 0;
237  }
238
239  node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff);
240
241  last = node;
242
243  while (!list_is_last(&last->list, &tree->list_head)) {
244    next = avl_next(last);
245    if (next->leader) {
246      break;
247    }
248    last = next;
249  }
250
251  diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);
252
253  if (diff == 0) {
254    if (!tree->allow_dups)
255      return -1;
256
257    new->leader = 0;
258
259    avl_insert_after(tree, last, new);
260    return 0;
261  }
262
263  if (node->balance == 1) {
264    avl_insert_before(tree, node, new);
265
266    node->balance = 0;
267    new->parent = node;
268    node->left = new;
269    return 0;
270  }
271
272  if (node->balance == -1) {
273    avl_insert_after(tree, last, new);
274
275    node->balance = 0;
276    new->parent = node;
277    node->right = new;
278    return 0;
279  }
280
281  if (diff < 0) {
282    avl_insert_before(tree, node, new);
283
284    node->balance = -1;
285    new->parent = node;
286    node->left = new;
287    post_insert(tree, node);
288    return 0;
289  }
290
291  avl_insert_after(tree, last, new);
292
293  node->balance = 1;
294  new->parent = node;
295  node->right = new;
296  post_insert(tree, node);
297  return 0;
298}
299
300/**
301 * Remove a node from an avl tree
302 * @param tree pointer to tree
303 * @param node pointer to node
304 */
305void
306avl_delete(struct avl_tree *tree, struct avl_node *node)
307{
308  struct avl_node *next;
309  struct avl_node *parent;
310  struct avl_node *left;
311  struct avl_node *right;
312  if (node->leader) {
313    if (tree->allow_dups
314        && !list_is_last(&node->list, &tree->list_head)
315        && !(next = avl_next(node))->leader) {
316      next->leader = true;
317      next->balance = node->balance;
318
319      parent = node->parent;
320      left = node->left;
321      right = node->right;
322
323      next->parent = parent;
324      next->left = left;
325      next->right = right;
326
327      if (parent == NULL)
328        tree->root = next;
329
330      else {
331        if (node == parent->left)
332          parent->left = next;
333
334        else
335          parent->right = next;
336      }
337
338      if (left != NULL)
339        left->parent = next;
340
341      if (right != NULL)
342        right->parent = next;
343    }
344
345    else
346      avl_delete_worker(tree, node);
347  }
348
349  avl_remove(tree, node);
350}
351
352static struct avl_node *
353avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result)
354{
355  int diff;
356
357  diff = (*comp) (key, node->key, cmp_ptr);
358  *cmp_result = diff;
359
360  if (diff < 0) {
361    if (node->left != NULL)
362      return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
363
364    return node;
365  }
366
367  if (diff > 0) {
368    if (node->right != NULL)
369      return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
370
371    return node;
372  }
373
374  return node;
375}
376
377static void
378avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
379{
380  struct avl_node *left, *parent;
381
382  left = node->left;
383  parent = node->parent;
384
385  left->parent = parent;
386  node->parent = left;
387
388  if (parent == NULL)
389    tree->root = left;
390
391  else {
392    if (parent->left == node)
393      parent->left = left;
394
395    else
396      parent->right = left;
397  }
398
399  node->left = left->right;
400  left->right = node;
401
402  if (node->left != NULL)
403    node->left->parent = node;
404
405  node->balance += 1 - avl_min(left->balance, 0);
406  left->balance += 1 + avl_max(node->balance, 0);
407}
408
409static void
410avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
411{
412  struct avl_node *right, *parent;
413
414  right = node->right;
415  parent = node->parent;
416
417  right->parent = parent;
418  node->parent = right;
419
420  if (parent == NULL)
421    tree->root = right;
422
423  else {
424    if (parent->left == node)
425      parent->left = right;
426
427    else
428      parent->right = right;
429  }
430
431  node->right = right->left;
432  right->left = node;
433
434  if (node->right != NULL)
435    node->right->parent = node;
436
437  node->balance -= 1 + avl_max(right->balance, 0);
438  right->balance -= 1 - avl_min(node->balance, 0);
439}
440
441static void
442post_insert(struct avl_tree *tree, struct avl_node *node)
443{
444  struct avl_node *parent = node->parent;
445
446  if (parent == NULL)
447    return;
448
449  if (node == parent->left) {
450    parent->balance--;
451
452    if (parent->balance == 0)
453      return;
454
455    if (parent->balance == -1) {
456      post_insert(tree, parent);
457      return;
458    }
459
460    if (node->balance == -1) {
461      avl_rotate_right(tree, parent);
462      return;
463    }
464
465    avl_rotate_left(tree, node);
466    avl_rotate_right(tree, node->parent->parent);
467    return;
468  }
469
470  parent->balance++;
471
472  if (parent->balance == 0)
473    return;
474
475  if (parent->balance == 1) {
476    post_insert(tree, parent);
477    return;
478  }
479
480  if (node->balance == 1) {
481    avl_rotate_left(tree, parent);
482    return;
483  }
484
485  avl_rotate_right(tree, node);
486  avl_rotate_left(tree, node->parent->parent);
487}
488
489static void
490avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
491{
492  list_add_tail(&node->list, &pos_node->list);
493  tree->count++;
494}
495
496static void
497avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
498{
499  list_add(&node->list, &pos_node->list);
500  tree->count++;
501}
502
503static void
504avl_remove(struct avl_tree *tree, struct avl_node *node)
505{
506  list_del(&node->list);
507  tree->count--;
508}
509
510static void
511avl_post_delete(struct avl_tree *tree, struct avl_node *node)
512{
513  struct avl_node *parent;
514
515  if ((parent = node->parent) == NULL)
516    return;
517
518  if (node == parent->left) {
519    parent->balance++;
520
521    if (parent->balance == 0) {
522      avl_post_delete(tree, parent);
523      return;
524    }
525
526    if (parent->balance == 1)
527      return;
528
529    if (parent->right->balance == 0) {
530      avl_rotate_left(tree, parent);
531      return;
532    }
533
534    if (parent->right->balance == 1) {
535      avl_rotate_left(tree, parent);
536      avl_post_delete(tree, parent->parent);
537      return;
538    }
539
540    avl_rotate_right(tree, parent->right);
541    avl_rotate_left(tree, parent);
542    avl_post_delete(tree, parent->parent);
543    return;
544  }
545
546  parent->balance--;
547
548  if (parent->balance == 0) {
549    avl_post_delete(tree, parent);
550    return;
551  }
552
553  if (parent->balance == -1)
554    return;
555
556  if (parent->left->balance == 0) {
557    avl_rotate_right(tree, parent);
558    return;
559  }
560
561  if (parent->left->balance == -1) {
562    avl_rotate_right(tree, parent);
563    avl_post_delete(tree, parent->parent);
564    return;
565  }
566
567  avl_rotate_left(tree, parent->left);
568  avl_rotate_right(tree, parent);
569  avl_post_delete(tree, parent->parent);
570}
571
572static struct avl_node *
573avl_local_min(struct avl_node *node)
574{
575  while (node->left != NULL)
576    node = node->left;
577
578  return node;
579}
580
581#if 0
582static struct avl_node *
583avl_local_max(struct avl_node *node)
584{
585  while (node->right != NULL)
586    node = node->right;
587
588  return node;
589}
590#endif
591
592static void
593avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
594{
595  struct avl_node *parent, *min;
596
597  parent = node->parent;
598
599  if (node->left == NULL && node->right == NULL) {
600    if (parent == NULL) {
601      tree->root = NULL;
602      return;
603    }
604
605    if (parent->left == node) {
606      parent->left = NULL;
607      parent->balance++;
608
609      if (parent->balance == 1)
610        return;
611
612      if (parent->balance == 0) {
613        avl_post_delete(tree, parent);
614        return;
615      }
616
617      if (parent->right->balance == 0) {
618        avl_rotate_left(tree, parent);
619        return;
620      }
621
622      if (parent->right->balance == 1) {
623        avl_rotate_left(tree, parent);
624        avl_post_delete(tree, parent->parent);
625        return;
626      }
627
628      avl_rotate_right(tree, parent->right);
629      avl_rotate_left(tree, parent);
630      avl_post_delete(tree, parent->parent);
631      return;
632    }
633
634    if (parent->right == node) {
635      parent->right = NULL;
636      parent->balance--;
637
638      if (parent->balance == -1)
639        return;
640
641      if (parent->balance == 0) {
642        avl_post_delete(tree, parent);
643        return;
644      }
645
646      if (parent->left->balance == 0) {
647        avl_rotate_right(tree, parent);
648        return;
649      }
650
651      if (parent->left->balance == -1) {
652        avl_rotate_right(tree, parent);
653        avl_post_delete(tree, parent->parent);
654        return;
655      }
656
657      avl_rotate_left(tree, parent->left);
658      avl_rotate_right(tree, parent);
659      avl_post_delete(tree, parent->parent);
660      return;
661    }
662  }
663
664  if (node->left == NULL) {
665    if (parent == NULL) {
666      tree->root = node->right;
667      node->right->parent = NULL;
668      return;
669    }
670
671    node->right->parent = parent;
672
673    if (parent->left == node)
674      parent->left = node->right;
675
676    else
677      parent->right = node->right;
678
679    avl_post_delete(tree, node->right);
680    return;
681  }
682
683  if (node->right == NULL) {
684    if (parent == NULL) {
685      tree->root = node->left;
686      node->left->parent = NULL;
687      return;
688    }
689
690    node->left->parent = parent;
691
692    if (parent->left == node)
693      parent->left = node->left;
694
695    else
696      parent->right = node->left;
697
698    avl_post_delete(tree, node->left);
699    return;
700  }
701
702  min = avl_local_min(node->right);
703  avl_delete_worker(tree, min);
704  parent = node->parent;
705
706  min->balance = node->balance;
707  min->parent = parent;
708  min->left = node->left;
709  min->right = node->right;
710
711  if (min->left != NULL)
712    min->left->parent = min;
713
714  if (min->right != NULL)
715    min->right->parent = min;
716
717  if (parent == NULL) {
718    tree->root = min;
719    return;
720  }
721
722  if (parent->left == node) {
723    parent->left = min;
724    return;
725  }
726
727  parent->right = min;
728}
729
730/*
731 * Local Variables:
732 * c-basic-offset: 2
733 * indent-tabs-mode: nil
734 * End:
735 */
Note: See TracBrowser for help on using the repository browser.