1 /*
2 * avl.h - this file is part of Libtree.
3 * $Id: avl.h 2600 2021-04-25 10:39:54Z soci $
4 *
5 * Copyright (C) 2010 Franck Bui-Huu <fbuihuu@gmail.com>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public License
9 * as published by the Free Software Foundation; version 2 of the
10 * License.
11 *
12 * This library is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 * 02110-1301 USA.
21 */
22 #ifndef AVL_H
23 #define AVL_H
24
25 #include <stddef.h>
26 #include "attributes.h"
27
28 /*
29 * The definition has been stolen from the Linux kernel.
30 */
31 #ifdef __GNUC__
32 # define avltree_container_of(node, type, member) ({ \
33 struct avltree_node *__mptr = (node); \
34 (type *)( (char *)__mptr - offsetof(type,member) );})
35 # define cavltree_container_of(node, type, member) ({ \
36 const struct avltree_node *__mptr = (node); \
37 (const type *)( (const char *)__mptr - offsetof(type,member) );})
38 #else
39 # define avltree_container_of(node, type, member) \
40 ((type *)((char *)(node) - offsetof(type, member)))
41 # define cavltree_container_of(node, type, member) \
42 ((const type *)((const char *)(node) - offsetof(type, member)))
43 #endif /* __GNUC__ */
44
45 /*
46 * AVL tree
47 */
48
49 struct avltree_node {
50 struct avltree_node *left, *right;
51 struct avltree_node *parent;
52 signed char balance; /* balance factor [-2:+2] */
53 };
54
55 typedef FAST_CALL int (*avltree_cmp_fn_t)(const struct avltree_node *, const struct avltree_node *);
56 typedef void (*avltree_free_fn_t)(struct avltree_node *);
57
58 struct avltree {
59 struct avltree_node *root;
60 };
61
avltree_init(struct avltree * tree)62 static inline void avltree_init(struct avltree *tree)
63 {
64 tree->root = NULL;
65 }
66
67 extern FAST_CALL struct avltree_node *avltree_lookup(const struct avltree_node *, const struct avltree *, avltree_cmp_fn_t);
68 extern struct avltree_node *avltree_insert(struct avltree_node *, struct avltree *, avltree_cmp_fn_t);
69 extern void avltree_destroy(struct avltree *, avltree_free_fn_t);
70
71 #endif
72