/*
|
* Copyright (c) 2015 Gilles Chanteperdrix
|
*
|
* Permission is hereby granted, free of charge, to any person obtaining
|
* a copy of this software and associated documentation files (the
|
* "Software"), to deal in the Software without restriction, including
|
* without limitation the rights to use, copy, modify, merge, publish,
|
* distribute, sublicense, and/or sell copies of the Software, and to
|
* permit persons to whom the Software is furnished to do so, subject to
|
* the following conditions:
|
*
|
* The above copyright notice and this permission notice shall be included
|
* in all copies or substantial portions of the Software.
|
*
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
|
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
|
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
|
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
|
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
|
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
*/
|
#if (!defined(_BOILERPLATE_AVL_INNER_H) && !defined(AVL_PSHARED)) || \
|
(!defined(_BOILERPLATE_AVL_SHARED_INNER_H) && defined(AVL_PSHARED)) /* Yeah, well... */
|
|
#if !defined(_BOILERPLATE_AVL_H) && !defined(_BOILERPLATE_SHAVL_H)
|
#error "Do not include this file directly. Use <boilerplate/avl.h> or <boilerplate/shavl.h> instead."
|
#endif
|
|
#include <stddef.h>
|
#include <stdio.h>
|
|
#ifdef AVL_PSHARED
|
#define __AVL(__decl) shavl_ ## __decl
|
#define __AVLH(__decl) shavlh_ ## __decl
|
#define __AVL_T(__type) sh ## __type
|
#define _BOILERPLATE_AVL_SHARED_INNER_H
|
#else
|
#define __AVL(__decl) avl_ ## __decl
|
#define __AVLH(__decl) avlh_ ## __decl
|
#define __AVL_T(__type) __type
|
#define _BOILERPLATE_AVL_INNER_H
|
#endif
|
|
struct __AVL_T(avlh) {
|
#define AVLH_APP_BITS 28
|
unsigned int flags: AVLH_APP_BITS;
|
int type: 2;
|
int balance: 2;
|
union {
|
ptrdiff_t offset;
|
struct __AVL_T(avlh) *ptr;
|
} link[3];
|
};
|
|
struct __AVL_T(avl);
|
|
/*
|
* Comparison function: should return -1 if left is less than right, 0
|
* if they are equal and 1 if left is greather than right. You can use
|
* the avl_sign function which will convert a difference to -1, 0,
|
* 1. Beware of overflow however. You can also use avl_cmp_sign()
|
* which should not have any such problems.
|
*/
|
typedef int __AVL_T(avlh_cmp_t)(const struct __AVL_T(avlh) *const,
|
const struct __AVL_T(avlh) *const);
|
|
typedef struct __AVL_T(avlh) *
|
__AVL_T(avl_search_t)(const struct __AVL_T(avl) *,
|
const struct __AVL_T(avlh) *, int *, int);
|
|
typedef int __AVL_T(avlh_prn_t)(char *, size_t,
|
const struct __AVL_T(avlh) *const);
|
|
struct __AVL_T(avl_searchops) {
|
__AVL_T(avl_search_t) *search;
|
__AVL_T(avlh_cmp_t) *cmp;
|
};
|
|
struct __AVL_T(avl) {
|
struct __AVL_T(avlh) anchor;
|
union {
|
ptrdiff_t offset;
|
struct __AVL_T(avlh) *ptr;
|
} end[3];
|
unsigned int count;
|
unsigned int height;
|
};
|
|
#define AVL_LEFT -1
|
#define AVL_UP 0
|
#define AVL_RIGHT 1
|
/* maps AVL_LEFT to AVL_RIGHT and reciprocally. */
|
#define avl_opposite(type) (-(type))
|
/* maps AVL_LEFT and AVL_RIGHT to arrays index (or bit positions). */
|
#define avl_type2index(type) ((type)+1)
|
|
#define AVL_THR_LEFT (1 << avl_type2index(AVL_LEFT))
|
#define AVL_THR_RIGHT (1 << avl_type2index(AVL_RIGHT))
|
|
#ifdef AVL_PSHARED
|
|
static inline struct shavlh *
|
shavlh_link(const struct shavl *const avl,
|
const struct shavlh *const holder, unsigned int dir)
|
{
|
ptrdiff_t offset = holder->link[avl_type2index(dir)].offset;
|
return offset == (ptrdiff_t)-1 ? NULL : (void *)avl + offset;
|
}
|
|
static inline void
|
shavlh_set_link(struct shavl *const avl, struct shavlh *lhs,
|
int dir, struct shavlh *rhs)
|
{
|
ptrdiff_t offset = rhs ? (void *)rhs - (void *)avl : (ptrdiff_t)-1;
|
lhs->link[avl_type2index(dir)].offset = offset;
|
}
|
|
static inline
|
struct shavlh *shavl_end(const struct shavl *const avl, int dir)
|
{
|
ptrdiff_t offset = avl->end[avl_type2index(dir)].offset;
|
return offset == (ptrdiff_t)-1 ? NULL : (void *)avl + offset;
|
}
|
|
static inline void
|
shavl_set_end(struct shavl *const avl, int dir, struct shavlh *holder)
|
{
|
ptrdiff_t offset = holder ? (void *)holder - (void *)avl : (ptrdiff_t)-1;
|
avl->end[avl_type2index(dir)].offset = offset;
|
}
|
|
#define shavl_count(avl) ((avl)->count)
|
#define shavl_height(avl) ((avl)->height)
|
#define shavl_anchor(avl) (&(avl)->anchor)
|
|
#define shavlh_up(avl, holder) \
|
shavlh_link((avl), (holder), AVL_UP)
|
#define shavlh_left(avl, holder) \
|
shavlh_link((avl), (holder), AVL_LEFT)
|
#define shavlh_right(avl, holder) \
|
shavlh_link((avl), (holder), AVL_RIGHT)
|
|
#define shavlh_thr_tst(avl, holder, side) \
|
(shavlh_link(avl, holder, side) == NULL)
|
#define shavlh_child(avl, holder, side) \
|
(shavlh_link((avl),(holder),(side)))
|
#define shavlh_has_child(avl, holder, side) \
|
(!shavlh_thr_tst(avl, holder, side))
|
|
#define shavl_top(avl) (shavlh_right(avl, shavl_anchor(avl)))
|
#define shavl_head(avl) (shavl_end((avl), AVL_LEFT))
|
#define shavl_tail(avl) (shavl_end((avl), AVL_RIGHT))
|
|
/*
|
* Search a node in a pshared AVL, return its parent if it could not
|
* be found.
|
*/
|
#define DECLARE_SHAVL_SEARCH(__search_fn, __cmp) \
|
struct shavlh *__search_fn(const struct shavl *const avl, \
|
const struct shavlh *const node, \
|
int *const pdelta, int dir) \
|
{ \
|
int delta = AVL_RIGHT; \
|
struct shavlh *holder = shavl_top(avl), *next; \
|
\
|
if (holder == NULL) \
|
goto done; \
|
\
|
for (;;) { \
|
delta = __cmp(node, holder); \
|
/* \
|
* Handle duplicates keys here, according to \
|
* "dir", if dir is: \
|
* - AVL_LEFT, the leftmost node is returned, \
|
* - AVL_RIGHT, the rightmost node is returned, \
|
* - 0, the first match is returned. \
|
*/ \
|
if (!(delta ?: dir)) \
|
break; \
|
next = shavlh_child(avl, holder, delta ?: dir); \
|
if (next == NULL) \
|
break; \
|
holder = next; \
|
} \
|
\
|
done: \
|
*pdelta = delta; \
|
return holder; \
|
}
|
|
#else /* !AVL_PSHARED */
|
|
#define avlh_link(avl, holder, dir) ((holder)->link[avl_type2index(dir)].ptr)
|
|
#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)].ptr)
|
|
static inline void
|
avlh_set_link(struct avl *const avl, struct avlh *lhs, int dir, struct avlh *rhs)
|
{
|
avlh_link(avl, lhs, dir) = rhs;
|
}
|
|
static inline void
|
avl_set_end(struct avl *const avl, int dir, struct avlh *holder)
|
{
|
avl_end(avl, dir) = holder;
|
}
|
|
#define avl_count(avl) ((avl)->count)
|
#define avl_height(avl) ((avl)->height)
|
#define avl_anchor(avl) (&(avl)->anchor)
|
|
#define avlh_up(avl, holder) avlh_link((avl), (holder), AVL_UP)
|
#define avlh_left(avl, holder) avlh_link((avl), (holder), AVL_LEFT)
|
#define avlh_right(avl, holder) avlh_link((avl), (holder), AVL_RIGHT)
|
|
#define avlh_thr_tst(avl, holder, side) (avlh_link(avl, holder, side) == NULL)
|
#define avlh_child(avl, holder, side) (avlh_link((avl),(holder),(side)))
|
#define avlh_has_child(avl, holder, side) (!avlh_thr_tst(avl, holder, side))
|
|
#define avl_top(avl) (avlh_right(avl, avl_anchor(avl)))
|
#define avl_head(avl) (avl_end((avl), AVL_LEFT))
|
#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
|
|
/*
|
* Search a node in a private AVL, return its parent if it could not
|
* be found.
|
*/
|
#define DECLARE_AVL_SEARCH(__search_fn, __cmp) \
|
struct avlh *__search_fn(const struct avl *const avl, \
|
const struct avlh *const node, \
|
int *const pdelta, int dir) \
|
{ \
|
int delta = AVL_RIGHT; \
|
struct avlh *holder = avl_top(avl), *next; \
|
\
|
if (holder == NULL) \
|
goto done; \
|
\
|
for (;;) { \
|
delta = __cmp(node, holder); \
|
/* \
|
* Handle duplicates keys here, according to \
|
* "dir", if dir is: \
|
* - AVL_LEFT, the leftmost node is returned, \
|
* - AVL_RIGHT, the rightmost node is returned, \
|
* - 0, the first match is returned. \
|
*/ \
|
if (!(delta ?: dir)) \
|
break; \
|
next = avlh_child(avl, holder, delta ?: dir); \
|
if (next == NULL) \
|
break; \
|
holder = next; \
|
} \
|
\
|
done: \
|
*pdelta = delta; \
|
return holder; \
|
}
|
|
#endif /* !AVL_PSHARED */
|
|
/*
|
* From "Bit twiddling hacks", returns v < 0 ? -1 : (v > 0 ? 1 : 0)
|
*/
|
#define avl_sign(v) \
|
({ \
|
typeof(v) _v = (v); \
|
((_v) > 0) - ((_v) < 0); \
|
})
|
|
/*
|
* Variation on the same theme.
|
*/
|
#define avl_cmp_sign(l, r) \
|
({ \
|
typeof(l) _l = (l); \
|
typeof(r) _r = (r); \
|
(_l > _r) - (_l < _r); \
|
})
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(search_inner)(const struct __AVL_T(avl) *const avl,
|
const struct __AVL_T(avlh) *n, int *delta,
|
const struct __AVL_T(avl_searchops) *ops)
|
{
|
return ops->search(avl, n, delta, 0);
|
}
|
|
static inline
|
struct __AVL_T(avlh) *__AVL(gettop)(const struct __AVL_T(avl) *const avl)
|
{
|
return __AVL(top)(avl);
|
}
|
|
static inline
|
struct __AVL_T(avlh) *__AVL(gethead)(const struct __AVL_T(avl) *const avl)
|
{
|
return __AVL(head)(avl);
|
}
|
|
static inline
|
struct __AVL_T(avlh) *__AVL(gettail)(const struct __AVL_T(avl) *const avl)
|
{
|
return __AVL(tail)(avl);
|
}
|
|
static inline
|
unsigned int __AVL(getcount)(const struct __AVL_T(avl) *const avl)
|
{
|
return __AVL(count)(avl);
|
}
|
|
struct __AVL_T(avlh) *__AVL(inorder)(const struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *holder,
|
const int dir);
|
|
struct __AVL_T(avlh) *__AVL(postorder)(const struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder,
|
const int dir);
|
|
struct __AVL_T(avlh) *__AVL(preorder)(const struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *holder,
|
const int dir);
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(next)(const struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder)
|
{
|
return __AVL(inorder)(avl, holder, AVL_RIGHT);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(prev)(const struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder)
|
{
|
return __AVL(inorder)(avl, holder, AVL_LEFT);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(postorder_next)(const struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder)
|
{
|
return __AVL(postorder)(avl, holder, AVL_RIGHT);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(postorder_prev)(const struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder)
|
{
|
return __AVL(postorder)(avl, holder, AVL_LEFT);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(preorder_next)(const struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder)
|
{
|
return __AVL(preorder)(avl, holder, AVL_RIGHT);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(preorder_prev)(const struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder)
|
{
|
return __AVL(preorder)(avl, holder, AVL_LEFT);
|
}
|
|
static inline void __AVLH(init)(struct __AVL_T(avlh) *const holder)
|
{
|
holder->balance = 0;
|
holder->type = 0;
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(search)(const struct __AVL_T(avl) *const avl,
|
const struct __AVL_T(avlh) *node,
|
const struct __AVL_T(avl_searchops) *ops)
|
{
|
struct __AVL_T(avlh) *holder;
|
int delta;
|
|
holder = __AVL(search_inner)(avl, node, &delta, ops);
|
if (!delta)
|
return holder;
|
|
return NULL;
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(search_nearest)(const struct __AVL_T(avl) *const avl,
|
const struct __AVL_T(avlh) *node, int dir,
|
const struct __AVL_T(avl_searchops) *ops)
|
{
|
struct __AVL_T(avlh) *holder;
|
int delta;
|
|
holder = __AVL(search_inner)(avl, node, &delta, ops);
|
if (!holder || delta != dir)
|
return holder;
|
|
return __AVL(inorder)(avl, holder, dir);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(search_le)(const struct __AVL_T(avl) *const avl,
|
const struct __AVL_T(avlh) *node,
|
const struct __AVL_T(avl_searchops) *ops)
|
{
|
return __AVL(search_nearest)(avl, node, AVL_LEFT, ops);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(search_ge)(const struct __AVL_T(avl) *const avl,
|
const struct __AVL_T(avlh) *node,
|
const struct __AVL_T(avl_searchops) *ops)
|
{
|
return __AVL(search_nearest)(avl, node, AVL_RIGHT, ops);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(search_multi)(const struct __AVL_T(avl) *const avl,
|
const struct __AVL_T(avlh) *node, int dir,
|
const struct __AVL_T(avl_searchops) *ops)
|
{
|
struct __AVL_T(avlh) *holder;
|
int delta;
|
|
holder = ops->search(avl, node, &delta, dir);
|
if (!delta)
|
return holder;
|
|
if (!holder)
|
return NULL;
|
|
return __AVL(inorder)(avl, holder, -dir);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(search_first)(const struct __AVL_T(avl) *const avl,
|
const struct __AVL_T(avlh) *node,
|
const struct __AVL_T(avl_searchops) *ops)
|
{
|
return __AVL(search_multi)(avl, node, AVL_LEFT, ops);
|
}
|
|
static inline struct __AVL_T(avlh) *
|
__AVL(search_last)(const struct __AVL_T(avl) *const avl,
|
const struct __AVL_T(avlh) *node,
|
const struct __AVL_T(avl_searchops) *ops)
|
{
|
return __AVL(search_multi)(avl, node, AVL_RIGHT, ops);
|
}
|
|
#ifdef __cplusplus
|
extern "C" {
|
#endif /* __cplusplus */
|
|
void __AVL(init)(struct __AVL_T(avl) *const avl);
|
|
void __AVL(destroy)(struct __AVL_T(avl) *const avl);
|
|
int __AVL(insert)(struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder,
|
const struct __AVL_T(avl_searchops) *ops);
|
|
int __AVL(insert_front)(struct __AVL_T(avl) *avl,
|
struct __AVL_T(avlh) *holder,
|
const struct __AVL_T(avl_searchops) *ops);
|
|
int __AVL(insert_back)(struct __AVL_T(avl) *avl,
|
struct __AVL_T(avlh) *holder,
|
const struct __AVL_T(avl_searchops) *ops);
|
|
int __AVL(insert_at)(struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *parent, int dir,
|
struct __AVL_T(avlh) *child);
|
|
int __AVL(prepend)(struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder,
|
const struct __AVL_T(avl_searchops) *ops);
|
|
int __AVL(append)(struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder,
|
const struct __AVL_T(avl_searchops) *ops);
|
|
int __AVL(delete)(struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *node);
|
|
int __AVL(replace)(struct __AVL_T(avl) *avl,
|
struct __AVL_T(avlh) *oldh,
|
struct __AVL_T(avlh) *newh,
|
const struct __AVL_T(avl_searchops) *ops);
|
|
struct __AVL_T(avlh) *__AVL(update)(struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder,
|
const struct __AVL_T(avl_searchops) *ops);
|
|
struct __AVL_T(avlh) *__AVL(set)(struct __AVL_T(avl) *const avl,
|
struct __AVL_T(avlh) *const holder,
|
const struct __AVL_T(avl_searchops) *ops);
|
|
void __AVL(clear)(struct __AVL_T(avl) *const avl,
|
void (*destruct)(struct __AVL_T(avlh) *));
|
|
int __AVL(check)(const struct __AVL_T(avl) *avl,
|
const struct __AVL_T(avl_searchops) *ops);
|
|
void __AVL(dump)(FILE *file, const struct __AVL_T(avl) *const avl,
|
__AVL_T(avlh_prn_t) *prn, unsigned int indent,
|
unsigned int len);
|
|
#ifdef __cplusplus
|
}
|
#endif /* __cplusplus */
|
|
#undef __AVL
|
#undef __AVLH
|
#undef __AVL_T
|
|
#endif /* !_BOILERPLATE_AVL_INNER_H */
|
