Xenomai  3.1
avl-inner.h
1 /*
2  * Copyright (c) 2015 Gilles Chanteperdrix
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining
5  * a copy of this software and associated documentation files (the
6  * "Software"), to deal in the Software without restriction, including
7  * without limitation the rights to use, copy, modify, merge, publish,
8  * distribute, sublicense, and/or sell copies of the Software, and to
9  * permit persons to whom the Software is furnished to do so, subject to
10  * the following conditions:
11  *
12  * The above copyright notice and this permission notice shall be included
13  * in all copies or substantial portions of the Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
19  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
20  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
21  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22  */
23 #if (!defined(_BOILERPLATE_AVL_INNER_H) && !defined(AVL_PSHARED)) || \
24  (!defined(_BOILERPLATE_AVL_SHARED_INNER_H) && defined(AVL_PSHARED)) /* Yeah, well... */
25 
26 #if !defined(_BOILERPLATE_AVL_H) && !defined(_BOILERPLATE_SHAVL_H)
27 #error "Do not include this file directly. Use <boilerplate/avl.h> or <boilerplate/shavl.h> instead."
28 #endif
29 
30 #include <stddef.h>
31 #include <stdio.h>
32 
33 #ifdef AVL_PSHARED
34 #define __AVL(__decl) shavl_ ## __decl
35 #define __AVLH(__decl) shavlh_ ## __decl
36 #define __AVL_T(__type) sh ## __type
37 #define _BOILERPLATE_AVL_SHARED_INNER_H
38 #else
39 #define __AVL(__decl) avl_ ## __decl
40 #define __AVLH(__decl) avlh_ ## __decl
41 #define __AVL_T(__type) __type
42 #define _BOILERPLATE_AVL_INNER_H
43 #endif
44 
45 struct __AVL_T(avlh) {
46 #define AVLH_APP_BITS 28
47  unsigned int flags: AVLH_APP_BITS;
48  int type: 2;
49  int balance: 2;
50  union {
51  ptrdiff_t offset;
52  struct __AVL_T(avlh) *ptr;
53  } link[3];
54 };
55 
56 struct __AVL_T(avl);
57 
58 /*
59  * Comparison function: should return -1 if left is less than right, 0
60  * if they are equal and 1 if left is greather than right. You can use
61  * the avl_sign function which will convert a difference to -1, 0,
62  * 1. Beware of overflow however. You can also use avl_cmp_sign()
63  * which should not have any such problems.
64  */
65 typedef int __AVL_T(avlh_cmp_t)(const struct __AVL_T(avlh) *const,
66  const struct __AVL_T(avlh) *const);
67 
68 typedef struct __AVL_T(avlh) *
69 __AVL_T(avl_search_t)(const struct __AVL_T(avl) *,
70  const struct __AVL_T(avlh) *, int *, int);
71 
72 typedef int __AVL_T(avlh_prn_t)(char *, size_t,
73  const struct __AVL_T(avlh) *const);
74 
75 struct __AVL_T(avl_searchops) {
76  __AVL_T(avl_search_t) *search;
77  __AVL_T(avlh_cmp_t) *cmp;
78 };
79 
80 struct __AVL_T(avl) {
81  struct __AVL_T(avlh) anchor;
82  union {
83  ptrdiff_t offset;
84  struct __AVL_T(avlh) *ptr;
85  } end[3];
86  unsigned int count;
87  unsigned int height;
88 };
89 
90 #define AVL_LEFT -1
91 #define AVL_UP 0
92 #define AVL_RIGHT 1
93 /* maps AVL_LEFT to AVL_RIGHT and reciprocally. */
94 #define avl_opposite(type) (-(type))
95 /* maps AVL_LEFT and AVL_RIGHT to arrays index (or bit positions). */
96 #define avl_type2index(type) ((type)+1)
97 
98 #define AVL_THR_LEFT (1 << avl_type2index(AVL_LEFT))
99 #define AVL_THR_RIGHT (1 << avl_type2index(AVL_RIGHT))
100 
101 #ifdef AVL_PSHARED
102 
103 static inline struct shavlh *
104 shavlh_link(const struct shavl *const avl,
105  const struct shavlh *const holder, unsigned int dir)
106 {
107  ptrdiff_t offset = holder->link[avl_type2index(dir)].offset;
108  return offset == (ptrdiff_t)-1 ? NULL : (void *)avl + offset;
109 }
110 
111 static inline void
112 shavlh_set_link(struct shavl *const avl, struct shavlh *lhs,
113  int dir, struct shavlh *rhs)
114 {
115  ptrdiff_t offset = rhs ? (void *)rhs - (void *)avl : (ptrdiff_t)-1;
116  lhs->link[avl_type2index(dir)].offset = offset;
117 }
118 
119 static inline
120 struct shavlh *shavl_end(const struct shavl *const avl, int dir)
121 {
122  ptrdiff_t offset = avl->end[avl_type2index(dir)].offset;
123  return offset == (ptrdiff_t)-1 ? NULL : (void *)avl + offset;
124 }
125 
126 static inline void
127 shavl_set_end(struct shavl *const avl, int dir, struct shavlh *holder)
128 {
129  ptrdiff_t offset = holder ? (void *)holder - (void *)avl : (ptrdiff_t)-1;
130  avl->end[avl_type2index(dir)].offset = offset;
131 }
132 
133 #define shavl_count(avl) ((avl)->count)
134 #define shavl_height(avl) ((avl)->height)
135 #define shavl_anchor(avl) (&(avl)->anchor)
136 
137 #define shavlh_up(avl, holder) \
138  shavlh_link((avl), (holder), AVL_UP)
139 #define shavlh_left(avl, holder) \
140  shavlh_link((avl), (holder), AVL_LEFT)
141 #define shavlh_right(avl, holder) \
142  shavlh_link((avl), (holder), AVL_RIGHT)
143 
144 #define shavlh_thr_tst(avl, holder, side) \
145  (shavlh_link(avl, holder, side) == NULL)
146 #define shavlh_child(avl, holder, side) \
147  (shavlh_link((avl),(holder),(side)))
148 #define shavlh_has_child(avl, holder, side) \
149  (!shavlh_thr_tst(avl, holder, side))
150 
151 #define shavl_top(avl) (shavlh_right(avl, shavl_anchor(avl)))
152 #define shavl_head(avl) (shavl_end((avl), AVL_LEFT))
153 #define shavl_tail(avl) (shavl_end((avl), AVL_RIGHT))
154 
155 /*
156  * Search a node in a pshared AVL, return its parent if it could not
157  * be found.
158  */
159 #define DECLARE_SHAVL_SEARCH(__search_fn, __cmp) \
160  struct shavlh *__search_fn(const struct shavl *const avl, \
161  const struct shavlh *const node, \
162  int *const pdelta, int dir) \
163  { \
164  int delta = AVL_RIGHT; \
165  struct shavlh *holder = shavl_top(avl), *next; \
166  \
167  if (holder == NULL) \
168  goto done; \
169  \
170  for (;;) { \
171  delta = __cmp(node, holder); \
172  /* \
173  * Handle duplicates keys here, according to \
174  * "dir", if dir is: \
175  * - AVL_LEFT, the leftmost node is returned, \
176  * - AVL_RIGHT, the rightmost node is returned, \
177  * - 0, the first match is returned. \
178  */ \
179  if (!(delta ?: dir)) \
180  break; \
181  next = shavlh_child(avl, holder, delta ?: dir); \
182  if (next == NULL) \
183  break; \
184  holder = next; \
185  } \
186  \
187  done: \
188  *pdelta = delta; \
189  return holder; \
190  }
191 
192 #else /* !AVL_PSHARED */
193 
194 #define avlh_link(avl, holder, dir) ((holder)->link[avl_type2index(dir)].ptr)
195 
196 #define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)].ptr)
197 
198 static inline void
199 avlh_set_link(struct avl *const avl, struct avlh *lhs, int dir, struct avlh *rhs)
200 {
201  avlh_link(avl, lhs, dir) = rhs;
202 }
203 
204 static inline void
205 avl_set_end(struct avl *const avl, int dir, struct avlh *holder)
206 {
207  avl_end(avl, dir) = holder;
208 }
209 
210 #define avl_count(avl) ((avl)->count)
211 #define avl_height(avl) ((avl)->height)
212 #define avl_anchor(avl) (&(avl)->anchor)
213 
214 #define avlh_up(avl, holder) avlh_link((avl), (holder), AVL_UP)
215 #define avlh_left(avl, holder) avlh_link((avl), (holder), AVL_LEFT)
216 #define avlh_right(avl, holder) avlh_link((avl), (holder), AVL_RIGHT)
217 
218 #define avlh_thr_tst(avl, holder, side) (avlh_link(avl, holder, side) == NULL)
219 #define avlh_child(avl, holder, side) (avlh_link((avl),(holder),(side)))
220 #define avlh_has_child(avl, holder, side) (!avlh_thr_tst(avl, holder, side))
221 
222 #define avl_top(avl) (avlh_right(avl, avl_anchor(avl)))
223 #define avl_head(avl) (avl_end((avl), AVL_LEFT))
224 #define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
225 
226 /*
227  * Search a node in a private AVL, return its parent if it could not
228  * be found.
229  */
230 #define DECLARE_AVL_SEARCH(__search_fn, __cmp) \
231  struct avlh *__search_fn(const struct avl *const avl, \
232  const struct avlh *const node, \
233  int *const pdelta, int dir) \
234  { \
235  int delta = AVL_RIGHT; \
236  struct avlh *holder = avl_top(avl), *next; \
237  \
238  if (holder == NULL) \
239  goto done; \
240  \
241  for (;;) { \
242  delta = __cmp(node, holder); \
243  /* \
244  * Handle duplicates keys here, according to \
245  * "dir", if dir is: \
246  * - AVL_LEFT, the leftmost node is returned, \
247  * - AVL_RIGHT, the rightmost node is returned, \
248  * - 0, the first match is returned. \
249  */ \
250  if (!(delta ?: dir)) \
251  break; \
252  next = avlh_child(avl, holder, delta ?: dir); \
253  if (next == NULL) \
254  break; \
255  holder = next; \
256  } \
257  \
258  done: \
259  *pdelta = delta; \
260  return holder; \
261  }
262 
263 #endif /* !AVL_PSHARED */
264 
265 /*
266  * From "Bit twiddling hacks", returns v < 0 ? -1 : (v > 0 ? 1 : 0)
267  */
268 #define avl_sign(v) \
269  ({ \
270  typeof(v) _v = (v); \
271  ((_v) > 0) - ((_v) < 0); \
272  })
273 
274 /*
275  * Variation on the same theme.
276  */
277 #define avl_cmp_sign(l, r) \
278  ({ \
279  typeof(l) _l = (l); \
280  typeof(r) _r = (r); \
281  (_l > _r) - (_l < _r); \
282  })
283 
284 static inline struct __AVL_T(avlh) *
285 __AVL(search_inner)(const struct __AVL_T(avl) *const avl,
286  const struct __AVL_T(avlh) *n, int *delta,
287  const struct __AVL_T(avl_searchops) *ops)
288 {
289  return ops->search(avl, n, delta, 0);
290 }
291 
292 static inline
293 struct __AVL_T(avlh) *__AVL(gettop)(const struct __AVL_T(avl) *const avl)
294 {
295  return __AVL(top)(avl);
296 }
297 
298 static inline
299 struct __AVL_T(avlh) *__AVL(gethead)(const struct __AVL_T(avl) *const avl)
300 {
301  return __AVL(head)(avl);
302 }
303 
304 static inline
305 struct __AVL_T(avlh) *__AVL(gettail)(const struct __AVL_T(avl) *const avl)
306 {
307  return __AVL(tail)(avl);
308 }
309 
310 static inline
311 unsigned int __AVL(getcount)(const struct __AVL_T(avl) *const avl)
312 {
313  return __AVL(count)(avl);
314 }
315 
316 struct __AVL_T(avlh) *__AVL(inorder)(const struct __AVL_T(avl) *const avl,
317  struct __AVL_T(avlh) *holder,
318  const int dir);
319 
320 struct __AVL_T(avlh) *__AVL(postorder)(const struct __AVL_T(avl) *const avl,
321  struct __AVL_T(avlh) *const holder,
322  const int dir);
323 
324 struct __AVL_T(avlh) *__AVL(preorder)(const struct __AVL_T(avl) *const avl,
325  struct __AVL_T(avlh) *holder,
326  const int dir);
327 
328 static inline struct __AVL_T(avlh) *
329 __AVL(next)(const struct __AVL_T(avl) *const avl,
330  struct __AVL_T(avlh) *const holder)
331 {
332  return __AVL(inorder)(avl, holder, AVL_RIGHT);
333 }
334 
335 static inline struct __AVL_T(avlh) *
336 __AVL(prev)(const struct __AVL_T(avl) *const avl,
337  struct __AVL_T(avlh) *const holder)
338 {
339  return __AVL(inorder)(avl, holder, AVL_LEFT);
340 }
341 
342 static inline struct __AVL_T(avlh) *
343 __AVL(postorder_next)(const struct __AVL_T(avl) *const avl,
344  struct __AVL_T(avlh) *const holder)
345 {
346  return __AVL(postorder)(avl, holder, AVL_RIGHT);
347 }
348 
349 static inline struct __AVL_T(avlh) *
350 __AVL(postorder_prev)(const struct __AVL_T(avl) *const avl,
351  struct __AVL_T(avlh) *const holder)
352 {
353  return __AVL(postorder)(avl, holder, AVL_LEFT);
354 }
355 
356 static inline struct __AVL_T(avlh) *
357 __AVL(preorder_next)(const struct __AVL_T(avl) *const avl,
358  struct __AVL_T(avlh) *const holder)
359 {
360  return __AVL(preorder)(avl, holder, AVL_RIGHT);
361 }
362 
363 static inline struct __AVL_T(avlh) *
364 __AVL(preorder_prev)(const struct __AVL_T(avl) *const avl,
365  struct __AVL_T(avlh) *const holder)
366 {
367  return __AVL(preorder)(avl, holder, AVL_LEFT);
368 }
369 
370 static inline void __AVLH(init)(struct __AVL_T(avlh) *const holder)
371 {
372  holder->balance = 0;
373  holder->type = 0;
374 }
375 
376 static inline struct __AVL_T(avlh) *
377 __AVL(search)(const struct __AVL_T(avl) *const avl,
378  const struct __AVL_T(avlh) *node,
379  const struct __AVL_T(avl_searchops) *ops)
380 {
381  struct __AVL_T(avlh) *holder;
382  int delta;
383 
384  holder = __AVL(search_inner)(avl, node, &delta, ops);
385  if (!delta)
386  return holder;
387 
388  return NULL;
389 }
390 
391 static inline struct __AVL_T(avlh) *
392 __AVL(search_nearest)(const struct __AVL_T(avl) *const avl,
393  const struct __AVL_T(avlh) *node, int dir,
394  const struct __AVL_T(avl_searchops) *ops)
395 {
396  struct __AVL_T(avlh) *holder;
397  int delta;
398 
399  holder = __AVL(search_inner)(avl, node, &delta, ops);
400  if (!holder || delta != dir)
401  return holder;
402 
403  return __AVL(inorder)(avl, holder, dir);
404 }
405 
406 static inline struct __AVL_T(avlh) *
407 __AVL(search_le)(const struct __AVL_T(avl) *const avl,
408  const struct __AVL_T(avlh) *node,
409  const struct __AVL_T(avl_searchops) *ops)
410 {
411  return __AVL(search_nearest)(avl, node, AVL_LEFT, ops);
412 }
413 
414 static inline struct __AVL_T(avlh) *
415 __AVL(search_ge)(const struct __AVL_T(avl) *const avl,
416  const struct __AVL_T(avlh) *node,
417  const struct __AVL_T(avl_searchops) *ops)
418 {
419  return __AVL(search_nearest)(avl, node, AVL_RIGHT, ops);
420 }
421 
422 static inline struct __AVL_T(avlh) *
423 __AVL(search_multi)(const struct __AVL_T(avl) *const avl,
424  const struct __AVL_T(avlh) *node, int dir,
425  const struct __AVL_T(avl_searchops) *ops)
426 {
427  struct __AVL_T(avlh) *holder;
428  int delta;
429 
430  holder = ops->search(avl, node, &delta, dir);
431  if (!delta)
432  return holder;
433 
434  if (!holder)
435  return NULL;
436 
437  return __AVL(inorder)(avl, holder, -dir);
438 }
439 
440 static inline struct __AVL_T(avlh) *
441 __AVL(search_first)(const struct __AVL_T(avl) *const avl,
442  const struct __AVL_T(avlh) *node,
443  const struct __AVL_T(avl_searchops) *ops)
444 {
445  return __AVL(search_multi)(avl, node, AVL_LEFT, ops);
446 }
447 
448 static inline struct __AVL_T(avlh) *
449 __AVL(search_last)(const struct __AVL_T(avl) *const avl,
450  const struct __AVL_T(avlh) *node,
451  const struct __AVL_T(avl_searchops) *ops)
452 {
453  return __AVL(search_multi)(avl, node, AVL_RIGHT, ops);
454 }
455 
456 #ifdef __cplusplus
457 extern "C" {
458 #endif /* __cplusplus */
459 
460 void __AVL(init)(struct __AVL_T(avl) *const avl);
461 
462 void __AVL(destroy)(struct __AVL_T(avl) *const avl);
463 
464 int __AVL(insert)(struct __AVL_T(avl) *const avl,
465  struct __AVL_T(avlh) *const holder,
466  const struct __AVL_T(avl_searchops) *ops);
467 
468 int __AVL(insert_front)(struct __AVL_T(avl) *avl,
469  struct __AVL_T(avlh) *holder,
470  const struct __AVL_T(avl_searchops) *ops);
471 
472 int __AVL(insert_back)(struct __AVL_T(avl) *avl,
473  struct __AVL_T(avlh) *holder,
474  const struct __AVL_T(avl_searchops) *ops);
475 
476 int __AVL(insert_at)(struct __AVL_T(avl) *const avl,
477  struct __AVL_T(avlh) *parent, int dir,
478  struct __AVL_T(avlh) *child);
479 
480 int __AVL(prepend)(struct __AVL_T(avl) *const avl,
481  struct __AVL_T(avlh) *const holder,
482  const struct __AVL_T(avl_searchops) *ops);
483 
484 int __AVL(append)(struct __AVL_T(avl) *const avl,
485  struct __AVL_T(avlh) *const holder,
486  const struct __AVL_T(avl_searchops) *ops);
487 
488 int __AVL(delete)(struct __AVL_T(avl) *const avl,
489  struct __AVL_T(avlh) *node);
490 
491 int __AVL(replace)(struct __AVL_T(avl) *avl,
492  struct __AVL_T(avlh) *oldh,
493  struct __AVL_T(avlh) *newh,
494  const struct __AVL_T(avl_searchops) *ops);
495 
496 struct __AVL_T(avlh) *__AVL(update)(struct __AVL_T(avl) *const avl,
497  struct __AVL_T(avlh) *const holder,
498  const struct __AVL_T(avl_searchops) *ops);
499 
500 struct __AVL_T(avlh) *__AVL(set)(struct __AVL_T(avl) *const avl,
501  struct __AVL_T(avlh) *const holder,
502  const struct __AVL_T(avl_searchops) *ops);
503 
504 void __AVL(clear)(struct __AVL_T(avl) *const avl,
505  void (*destruct)(struct __AVL_T(avlh) *));
506 
507 int __AVL(check)(const struct __AVL_T(avl) *avl,
508  const struct __AVL_T(avl_searchops) *ops);
509 
510 void __AVL(dump)(FILE *file, const struct __AVL_T(avl) *const avl,
511  __AVL_T(avlh_prn_t) *prn, unsigned int indent,
512  unsigned int len);
513 
514 #ifdef __cplusplus
515 }
516 #endif /* __cplusplus */
517 
518 #undef __AVL
519 #undef __AVLH
520 #undef __AVL_T
521 
522 #endif /* !_BOILERPLATE_AVL_INNER_H */