1    	/*
2    	 * libtree.h - this file is part of Libtree.
3    	 *
4    	 * Copyright (C) 2010-2014 Franck Bui-Huu <fbuihuu@gmail.com>
5    	 *
6    	 * This file is part of libtree which is free software; you can
7    	 * redistribute it and/or modify it under the terms of the GNU Lesser
8    	 * General Public License as published by the Free Software
9    	 * Foundation; either version 2.1 of the License, or (at your option)
10   	 * any later version.
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.
15   	 *
16   	 * See the LICENSE file for license rights and limitations.
17   	 */
18   	#ifndef _LIBTREE_H
19   	#define _LIBTREE_H
20   	
21   	#include <stdint.h>
22   	#include <stddef.h>
23   	
24   	/*
25   	 * The definition has been stolen from the Linux kernel.
26   	 */
27   	#ifdef __GNUC__
28   	#define bstree_container_of(node, type, member) ({			\
29   		const struct bstree_node *__mptr = (node);			\
30   		(type *)( (char *)__mptr - offsetof(type,member) );})
31   	#define rbtree_container_of(node, type, member) ({			\
32   		const struct rbtree_node *__mptr = (node);			\
33   		(type *)( (char *)__mptr - offsetof(type,member) );})
34   	#define avltree_container_of(node, type, member) ({			\
35   		const struct avltree_node *__mptr = (node);			\
36   		(type *)( (char *)__mptr - offsetof(type,member) );})
37   	#define splaytree_container_of(node, type, member) ({			\
38   		const struct splaytree_node *__mptr = (node);			\
39   		(type *)( (char *)__mptr - offsetof(type,member) );})
40   	#else
41   	#define bstree_container_of(node, type, member)			\
42   		((type *)((char *)(node) - offsetof(type, member)))
43   	#define rbtree_container_of(node, type, member)			\
44   		((type *)((char *)(node) - offsetof(type, member)))
45   	#define avltree_container_of(node, type, member)			\
46   		((type *)((char *)(node) - offsetof(type, member)))
47   	#define splaytree_container_of(node, type, member)			\
48   		((type *)((char *)(node) - offsetof(type, member)))
49   	#endif				/* __GNUC__ */
50   	
51   	/*
52   	 * Threaded binary search tree
53   	 */
54   	#ifdef UINTPTR_MAX
55   	
56   	struct bstree_node {
57   		uintptr_t left, right;
58   	} __attribute__ ((aligned(2)));
59   	
60   	#else
61   	
62   	struct bstree_node {
63   		struct bstree_node *left, *right;
64   		unsigned left_is_thread:1;
65   		unsigned right_is_thread:1;
66   	};
67   	
68   	#endif				/* UINTPTR_MAX */
69   	
70   	typedef int (*bstree_cmp_fn_t) (const struct bstree_node *,
71   					const struct bstree_node *);
72   	
73   	struct bstree {
74   		struct bstree_node *root;
75   		bstree_cmp_fn_t cmp_fn;
76   		struct bstree_node *first, *last;
77   		uint64_t reserved[4];
78   	};
79   	
80   	struct bstree_node *bstree_first(const struct bstree *tree);
81   	struct bstree_node *bstree_last(const struct bstree *tree);
82   	struct bstree_node *bstree_next(const struct bstree_node *node);
83   	struct bstree_node *bstree_prev(const struct bstree_node *node);
84   	
85   	struct bstree_node *bstree_lookup(const struct bstree_node *key,
86   					  const struct bstree *tree);
87   	struct bstree_node *bstree_insert(struct bstree_node *node,
88   					  struct bstree *tree);
89   	void bstree_remove(struct bstree_node *node, struct bstree *tree);
90   	void bstree_replace(struct bstree_node *old, struct bstree_node *newe,
91   			    struct bstree *tree);
92   	int bstree_init(struct bstree *tree, bstree_cmp_fn_t cmp, unsigned long flags);
93   	
94   	/*
95   	 * Red-black tree
96   	 */
97   	enum rb_color {
98   		RB_BLACK,
99   		RB_RED,
100  	};
101  	
102  	#ifdef UINTPTR_MAX
103  	
104  	struct rbtree_node {
105  		struct rbtree_node *left, *right;
106  		uintptr_t parent;
(1) Event alignment_reduction_ignored: a reduction in alignment without the "packed" attribute is ignored
(2) Event caretline: ^
107  	} __attribute__ ((aligned(2)));
108  	
109  	#else
110  	
111  	struct rbtree_node {
112  		struct rbtree_node *left, *right;
113  		struct rbtree_node *parent;
114  		enum rb_color color;
115  	};
116  	
117  	#endif				/* UINTPTR_MAX */
118  	
119  	typedef int (*rbtree_cmp_fn_t) (const struct rbtree_node *,
120  					const struct rbtree_node *);
121  	
122  	struct rbtree {
123  		struct rbtree_node *root;
124  		rbtree_cmp_fn_t cmp_fn;
125  		struct rbtree_node *first, *last;
126  		uint64_t reserved[4];
127  	};
128  	
129  	struct rbtree_node *rbtree_first(const struct rbtree *tree);
130  	struct rbtree_node *rbtree_last(const struct rbtree *tree);
131  	struct rbtree_node *rbtree_next(const struct rbtree_node *node);
132  	struct rbtree_node *rbtree_prev(const struct rbtree_node *node);
133  	
134  	struct rbtree_node *rbtree_lookup(const struct rbtree_node *key,
135  					  const struct rbtree *tree);
136  	struct rbtree_node *rbtree_insert(struct rbtree_node *node,
137  					  struct rbtree *tree);
138  	void rbtree_remove(struct rbtree_node *node, struct rbtree *tree);
139  	void rbtree_replace(struct rbtree_node *old, struct rbtree_node *newe,
140  			    struct rbtree *tree);
141  	int rbtree_init(struct rbtree *tree, rbtree_cmp_fn_t cmp, unsigned long flags);
142  	
143  	/*
144  	 * AVL tree
145  	 */
146  	#if defined UINTPTR_MAX && UINTPTR_MAX == UINT64_MAX
147  	
148  	struct avltree_node {
149  		struct avltree_node *left, *right;
150  		uintptr_t parent;	/* balance factor [0:4] */
151  	} __attribute__ ((aligned(8)));
152  	
153  	static inline signed int get_balance(struct avltree_node *node)
154  	{
155  		return (int)(node->parent & 7) - 2;
156  	}
157  	
158  	#else
159  	
160  	struct avltree_node {
161  		struct avltree_node *left, *right;
162  		struct avltree_node *parent;
163  		signed balance:3;	/* balance factor [-2:+2] */
164  	};
165  	
166  	static inline signed int get_balance(struct avltree_node *node)
167  	{
168  		return node->balance;
169  	}
170  	
171  	#endif
172  	
173  	typedef int (*avltree_cmp_fn_t) (const struct avltree_node *,
174  					 const struct avltree_node *);
175  	
176  	struct avltree {
177  		struct avltree_node *root;
178  		avltree_cmp_fn_t cmp_fn;
179  		int height;
180  		struct avltree_node *first, *last;
181  		uint64_t size;
182  	#if 0
183  		uint64_t reserved[4];
184  	#endif
185  	};
186  	
187  	/**
188  	 * @brief Perform a lookup in an AVL tree, returning useful bits for
189  	 * subsequent inser.
190  	 *
191  	 * 'pparent', 'unbalanced' and 'is_left' are only used for
192  	 * insertions. Normally GCC will notice this and get rid of them for
193  	 * lookups.
194  	 *
195  	 * @param[in]     key         Key to look for
196  	 * @param[in]     tree        AVL tree to look in
197  	 * @param[in,out] pparent     Parent of key
198  	 * @param[in,out] unbalanced  Unbalanced parent
199  	 * @param[in,out] is_left     True if key would be to left of parent
200  	 * @param[in]     cmp_fn      Comparison function to use
201  	 *
202  	 * @returns The node found if any
203  	 */
204  	static inline
205  	struct avltree_node *avltree_do_lookup(const struct avltree_node *key,
206  					       const struct avltree *tree,
207  					       struct avltree_node **pparent,
208  					       struct avltree_node **unbalanced,
209  					       int *is_left,
210  					       avltree_cmp_fn_t cmp_fn)
211  	{
212  		struct avltree_node *node = tree->root;
213  		int res = 0;
214  	
215  		*pparent = NULL;
216  		*unbalanced = node;
217  		*is_left = 0;
218  	
219  		while (node) {
220  			if (get_balance(node) != 0)
221  				*unbalanced = node;
222  	
223  			res = cmp_fn(node, key);
224  			if (res == 0)
225  				return node;
226  			*pparent = node;
227  			*is_left = res > 0;
228  			if (*is_left)
229  				node = node->left;
230  			else
231  				node = node->right;
232  		}
233  		return NULL;
234  	}
235  	
236  	static inline
237  	struct avltree_node *avltree_inline_lookup(const struct avltree_node *key,
238  						   const struct avltree *tree,
239  						   avltree_cmp_fn_t cmp_fn)
240  	{
241  		struct avltree_node *parent, *unbalanced;
242  		int is_left;
243  	
244  		return avltree_do_lookup(key, tree, &parent, &unbalanced, &is_left,
245  					 cmp_fn);
246  	}
247  	
248  	static inline
249  	struct avltree_node *avltree_lookup(const struct avltree_node *key,
250  					    const struct avltree *tree)
251  	{
252  		return avltree_inline_lookup(key, tree, tree->cmp_fn);
253  	}
254  	
255  	void avltree_do_insert(struct avltree_node *node,
256  			       struct avltree *tree,
257  			       struct avltree_node *parent,
258  			       struct avltree_node *unbalanced,
259  			       int is_left);
260  	
261  	static inline
262  	struct avltree_node *avltree_inline_insert(struct avltree_node *node,
263  						   struct avltree *tree,
264  						   avltree_cmp_fn_t cmp_fn)
265  	{
266  		struct avltree_node *found, *parent, *unbalanced;
267  		int is_left;
268  	
269  		found = avltree_do_lookup(node, tree, &parent, &unbalanced, &is_left,
270  					  cmp_fn);
271  	
272  		if (found)
273  			return found;
274  	
275  		avltree_do_insert(node, tree, parent, unbalanced, is_left);
276  	
277  		return NULL;
278  	}
279  	
280  	static inline
281  	struct avltree_node *avltree_insert(struct avltree_node *node,
282  					    struct avltree *tree)
283  	{
284  		return avltree_inline_insert(node, tree, tree->cmp_fn);
285  	}
286  	
287  	static inline
288  	struct avltree_node *avltree_first(const struct avltree *tree)
289  	{
290  		return tree->first;
291  	}
292  	
293  	static inline
294  	struct avltree_node *avltree_last(const struct avltree *tree)
295  	{
296  		return tree->last;
297  	}
298  	
299  	struct avltree_node *avltree_next(const struct avltree_node *node);
300  	struct avltree_node *avltree_prev(const struct avltree_node *node);
301  	uint64_t avltree_size(const struct avltree *tree);
302  	struct avltree_node *avltree_inf(const struct avltree_node *key,
303  					 const struct avltree *tree);
304  	struct avltree_node *avltree_sup(const struct avltree_node *key,
305  					 const struct avltree *tree);
306  	void avltree_remove(struct avltree_node *node, struct avltree *tree);
307  	void avltree_replace(struct avltree_node *old, struct avltree_node *newe,
308  			     struct avltree *tree);
309  	int avltree_init(struct avltree *tree, avltree_cmp_fn_t cmp,
310  			 unsigned long flags);
311  	
312  	/*
313  	 * Splay tree
314  	 */
315  	#ifdef UINTPTR_MAX
316  	
317  	struct splaytree_node {
318  		uintptr_t left, right;
319  	} __attribute__ ((aligned(2)));
320  	
321  	#else
322  	
323  	struct splaytree_node {
324  		struct splaytree_node *left, *right;
325  		unsigned left_is_thread:1;
326  		unsigned right_is_thread:1;
327  	};
328  	
329  	#endif
330  	
331  	typedef int (*splaytree_cmp_fn_t) (const struct splaytree_node *,
332  					   const struct splaytree_node *);
333  	
334  	struct splaytree {
335  		struct splaytree_node *root;
336  		struct splaytree_node *first, *last;
337  		splaytree_cmp_fn_t cmp_fn;
338  		uint64_t reserved[4];
339  	};
340  	
341  	struct splaytree_node *splaytree_first(const struct splaytree *tree);
342  	struct splaytree_node *splaytree_last(const struct splaytree *tree);
343  	struct splaytree_node *splaytree_next(const struct splaytree_node *node);
344  	struct splaytree_node *splaytree_prev(const struct splaytree_node *node);
345  	
346  	struct splaytree_node *splaytree_lookup(const struct splaytree_node *key,
347  						struct splaytree *tree);
348  	struct splaytree_node *splaytree_insert(struct splaytree_node *node,
349  						struct splaytree *tree);
350  	void splaytree_remove(struct splaytree_node *node, struct splaytree *tree);
351  	void splaytree_replace(struct splaytree_node *old, struct splaytree_node *newe,
352  			       struct splaytree *tree);
353  	int splaytree_init(struct splaytree *tree, splaytree_cmp_fn_t cmp,
354  			   unsigned long flags);
355  	
356  	#endif				/* _LIBTREE_H */
357