/*

 * Compact Elastic Binary Trees - exported functions operating on indirect strings

 *

 * Copyright (C) 2014-2025 Willy Tarreau - w@1wt.eu

 *

 * 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.

 */

#ifndef _CEBIS_TREE_H

#define _CEBIS_TREE_H

#include "cebtree.h"

/* simpler version */

struct ceb_node *cebis_imm_insert(struct ceb_root **root, struct ceb_node *node);

struct ceb_node *cebis_imm_first(struct ceb_root *const *root);

struct ceb_node *cebis_imm_last(struct ceb_root *const *root);

struct ceb_node *cebis_imm_lookup(struct ceb_root *const *root, const void *key);

struct ceb_node *cebis_imm_lookup_le(struct ceb_root *const *root, const void *key);

struct ceb_node *cebis_imm_lookup_lt(struct ceb_root *const *root, const void *key);

struct ceb_node *cebis_imm_lookup_ge(struct ceb_root *const *root, const void *key);

struct ceb_node *cebis_imm_lookup_gt(struct ceb_root *const *root, const void *key);

struct ceb_node *cebis_imm_next_unique(struct ceb_root *const *root, struct ceb_node *node);

struct ceb_node *cebis_imm_prev_unique(struct ceb_root *const *root, struct ceb_node *node);

struct ceb_node *cebis_imm_next_dup(struct ceb_root *const *root, struct ceb_node *node);

struct ceb_node *cebis_imm_prev_dup(struct ceb_root *const *root, struct ceb_node *node);

struct ceb_node *cebis_imm_next(struct ceb_root *const *root, struct ceb_node *node);

struct ceb_node *cebis_imm_prev(struct ceb_root *const *root, struct ceb_node *node);

struct ceb_node *cebis_imm_delete(struct ceb_root **root, struct ceb_node *node);

struct ceb_node *cebis_imm_pick(struct ceb_root **root, const void *key);

struct ceb_node *cebuis_imm_insert(struct ceb_root **root, struct ceb_node *node);

struct ceb_node *cebuis_imm_first(struct ceb_root *const *root);

struct ceb_node *cebuis_imm_last(struct ceb_root *const *root);

struct ceb_node *cebuis_imm_lookup(struct ceb_root *const *root, const void *key);

struct ceb_node *cebuis_imm_lookup_le(struct ceb_root *const *root, const void *key);

struct ceb_node *cebuis_imm_lookup_lt(struct ceb_root *const *root, const void *key);

struct ceb_node *cebuis_imm_lookup_ge(struct ceb_root *const *root, const void *key);

struct ceb_node *cebuis_imm_lookup_gt(struct ceb_root *const *root, const void *key);

struct ceb_node *cebuis_imm_next(struct ceb_root *const *root, struct ceb_node *node);

struct ceb_node *cebuis_imm_prev(struct ceb_root *const *root, struct ceb_node *node);

struct ceb_node *cebuis_imm_delete(struct ceb_root **root, struct ceb_node *node);

struct ceb_node *cebuis_imm_pick(struct ceb_root **root, const void *key);

/* generic dump function */

void cebis_imm_default_dump(struct ceb_root *const *root, const char *label, const void *ctx, int sub);

/* returns the pointer to the indirect char* key, not the pointer itself,

 * or NULL if node is NULL (note that the indirect pointer cannot be NULL

 * if node is non-NULL).

 */

static inline char *cebis_imm_key(const struct ceb_node *node)

{

  return node ? *(char **)_ceb_key_ptr(node, sizeof(struct ceb_node)) : NULL;

}

Unexecuted instantiation: cfgparse.c:cebis_imm_key

Unexecuted instantiation: proxy.c:cebis_imm_key

Unexecuted instantiation: resolvers.c:cebis_imm_key

Unexecuted instantiation: server.c:cebis_imm_key

Unexecuted instantiation: stick_table.c:cebis_imm_key

Unexecuted instantiation: guid.c:cebis_imm_key

/* version taking a key offset */

struct ceb_node *cebis_ofs_insert(struct ceb_root **root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebis_ofs_first(struct ceb_root *const *root, ptrdiff_t kofs);

struct ceb_node *cebis_ofs_last(struct ceb_root *const *root, ptrdiff_t kofs);

struct ceb_node *cebis_ofs_lookup(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebis_ofs_lookup_le(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebis_ofs_lookup_lt(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebis_ofs_lookup_ge(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebis_ofs_lookup_gt(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebis_ofs_next_unique(struct ceb_root *const *root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebis_ofs_prev_unique(struct ceb_root *const *root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebis_ofs_next_dup(struct ceb_root *const *root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebis_ofs_prev_dup(struct ceb_root *const *root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebis_ofs_next(struct ceb_root *const *root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebis_ofs_prev(struct ceb_root *const *root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebis_ofs_delete(struct ceb_root **root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebis_ofs_pick(struct ceb_root **root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebuis_ofs_insert(struct ceb_root **root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebuis_ofs_first(struct ceb_root *const *root, ptrdiff_t kofs);

struct ceb_node *cebuis_ofs_last(struct ceb_root *const *root, ptrdiff_t kofs);

struct ceb_node *cebuis_ofs_lookup(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebuis_ofs_lookup_le(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebuis_ofs_lookup_lt(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebuis_ofs_lookup_ge(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebuis_ofs_lookup_gt(struct ceb_root *const *root, ptrdiff_t kofs, const void *key);

struct ceb_node *cebuis_ofs_next(struct ceb_root *const *root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebuis_ofs_prev(struct ceb_root *const *root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebuis_ofs_delete(struct ceb_root **root, ptrdiff_t kofs, struct ceb_node *node);

struct ceb_node *cebuis_ofs_pick(struct ceb_root **root, ptrdiff_t kofs, const void *key);

/* generic dump function taking a key offset */

void cebis_ofs_default_dump(struct ceb_root *const *root, ptrdiff_t kofs, const char *label, const void *ctx, int sub);

/* returns the pointer to the indirect char* key, not the pointer itself,

 * or NULL if node is NULL (note that the indirect pointer cannot be NULL

 * if node is non-NULL).

 */

static inline char *cebis_ofs_key(const struct ceb_node *node, ptrdiff_t kofs)

{

  return node ? *(char **)_ceb_key_ptr(node, kofs) : NULL;

}

Unexecuted instantiation: cfgparse.c:cebis_ofs_key

Unexecuted instantiation: proxy.c:cebis_ofs_key

Unexecuted instantiation: resolvers.c:cebis_ofs_key

Unexecuted instantiation: server.c:cebis_ofs_key

Unexecuted instantiation: stick_table.c:cebis_ofs_key

Unexecuted instantiation: guid.c:cebis_ofs_key

/* insert at root <root>, the item <item_ptr> using node member <nname> and key

 * member <kname>, and returns either the inserted item, or the one that was

 * found there.

 */

#define cebis_item_insert(root, nname, kname, item_ptr) ({        \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebis_ofs_insert(root, _kofs, &(item_ptr)->nname); \

  (typeof(item_ptr))((char *)(_node) - _nofs);          \

})

/* descend root <root>, and return the first item of type <type>, using node

 * member <nname> and key member <kname>, or NULL if the tree is empty.

 */

#define cebis_item_first(root, nname, kname, type) ({          \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebis_ofs_first(root, _kofs);        \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;        \

})

/* descend root <root>, and return the last item of type <type>, using node

 * member <nname> and key member <kname>, or NULL if the tree is empty.

 */

#define cebis_item_last(root, nname, kname, type) ({          \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebis_ofs_last(root, _kofs);       \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the first item of type <type> which contains the

 * key <key>, using node member <nname> and key member <kname>. Returns the

 * pointer to the item, or NULL if not found.

 */

#define cebis_item_lookup(root, nname, kname, key, type) ({        \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebis_ofs_lookup(root, _kofs, key);      \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;        \

})

/* lookup from root <root>, the item of type <type> which contains the last of

 * the greatest keys that are lower than or equal to <key>, using node member

 * <nname> and key member <kname>. Returns the pointer to the item, or NULL if

 * not found.

 */

#define cebis_item_lookup_le(root, nname, kname, key, type) ({        \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebis_ofs_lookup_le(root, _kofs, key);     \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the item of type <type> which contains the last of

 * the greatest keys that are strictly lower than <key>, using node member

 * <nname> and key member <kname>. Returns the pointer to the item, or NULL if

 * not found.

 */

#define cebis_item_lookup_lt(root, nname, kname, key, type) ({        \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebis_ofs_lookup_lt(root, _kofs, key);     \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the item of type <type> which contains the first of

 * the lowest keys key that are greater than or equal to <key>, using node

 * member <nname> and key member <kname>. Returns the pointer to the item, or

 * NULL if not found.

 */

#define cebis_item_lookup_ge(root, nname, kname, key, type) ({        \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebis_ofs_lookup_ge(root, _kofs, key);     \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the item of type <type> which contains the first of

 * the lowest keys that are strictly greater than <key>, using node member

 * <nname> and key member <kname>. Returns the pointer to the item, or NULL if

 * not found.

 */

#define cebis_item_lookup_gt(root, nname, kname, key, type) ({        \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebis_ofs_lookup_gt(root, _kofs, key);     \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the first item after item <item_ptr> that has a

 * strictly greater key, using node member <nname> and key member <kname>, and

 * returns either the found item, or NULL if none exists.

 */

#define cebis_item_next_unique(root, nname, kname, item_ptr) ({       \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebis_ofs_next_unique(root, _kofs, &(item_ptr)->nname);\

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;     \

})

/* lookup from root <root>, the last item before item <item_ptr> that has a

 * strictly lower key, using node member <nname> and key member <kname>, and

 * returns either the found item, or NULL if none exists.

 */

#define cebis_item_prev_unique(root, nname, kname, item_ptr) ({       \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebis_ofs_prev_unique(root, _kofs, &(item_ptr)->nname);\

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;     \

})

/* lookup from root <root>, the first item after item <item_ptr> that has

 * exactly the same key, using node member <nname> and key member <kname>, and

 * returns either the found item, or NULL if none exists.

 */

#define cebis_item_next_dup(root, nname, kname, item_ptr) ({        \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebis_ofs_next_dup(root, _kofs, &(item_ptr)->nname); \

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;      \

})

/* lookup from root <root>, the last item before item <item_ptr> that has

 * exactly the same key, using node member <nname> and key member <kname>, and

 * returns either the found item, or NULL if none exists.

 */

#define cebis_item_prev_dup(root, nname, kname, item_ptr) ({        \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebis_ofs_prev_dup(root, _kofs, &(item_ptr)->nname); \

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;      \

})

/* lookup from root <root>, the first item immediately after item <item_ptr>,

 * using node member <nname> and key member <kname>, and returns either the

 * found item, or NULL if none exists.

 */

#define cebis_item_next(root, nname, kname, item_ptr) ({        \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebis_ofs_next(root, _kofs, &(item_ptr)->nname); \

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;      \

})

/* lookup from root <root>, the last item immediately before item <item_ptr>,

 * using node member <nname> and key member <kname>, and returns either the

 * found item, or NULL if none exists.

 */

#define cebis_item_prev(root, nname, kname, item_ptr) ({        \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebis_ofs_prev(root, _kofs, &(item_ptr)->nname); \

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;     \

})

/* lookup from root <root>, the item <item_ptr> using node member <nname> and

 * key member <kname>, deletes it and returns it. If the item is NULL or absent

 * from the tree, NULL is returned.

 */

#define cebis_item_delete(root, nname, kname, item_ptr) ({       \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  typeof(item_ptr) _item = (item_ptr);            \

  struct ceb_node *_node = cebis_ofs_delete(root, _kofs, _item ? &_item->nname : NULL); \

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;      \

})

/* lookup from root <root>, the first item of type <type> which contains the

 * key <key>, using node member <nname> and key member <kname>, deletes it and

 * returns it. If the key is not found in the tree, NULL is returned.

 */

#define cebis_item_pick(root, nname, kname, key, type) ({       \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebis_ofs_pick(root, _kofs, key);      \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/*** versions using unique keys below ***/

/* insert at root <root>, the item <item_ptr> using node member <nname> and key

 * member <kname>, and returns either the inserted item, or the one that was

 * found there.

 */

#define cebuis_item_insert(root, nname, kname, item_ptr) ({        \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebuis_ofs_insert(root, _kofs, &(item_ptr)->nname);  \

  (typeof(item_ptr))((char *)(_node) - _nofs);          \

})

/* descend root <root>, and return the first item of type <type>, using node

 * member <nname> and key member <kname>, or NULL if the tree is empty.

 */

#define cebuis_item_first(root, nname, kname, type) ({          \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebuis_ofs_first(root, _kofs);       \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* descend root <root>, and return the last item of type <type>, using node

 * member <nname> and key member <kname>, or NULL if the tree is empty.

 */

#define cebuis_item_last(root, nname, kname, type) ({         \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebuis_ofs_last(root, _kofs);        \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the item of type <type> which contains the key

 * <key>, using node member <nname> and key member <kname>. Returns the pointer

 * to the item, or NULL if not found.

 */

#define cebuis_item_lookup(root, nname, kname, key, type) ({        \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebuis_ofs_lookup(root, _kofs, key);     \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;        \

})

/* lookup from root <root>, the item of type <type> which contains the greatest

 * key that is lower than or equal to <key>, using node member <nname> and key

 * member <kname>. Returns the pointer to the item, or NULL if not found.

 */

#define cebuis_item_lookup_le(root, nname, kname, key, type) ({       \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebuis_ofs_lookup_le(root, _kofs, key);    \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the item of type <type> which contains the greatest

 * key that is strictly lower than <key>, using node member <nname> and key

 * member <kname>. Returns the pointer to the item, or NULL if not found.

 */

#define cebuis_item_lookup_lt(root, nname, kname, key, type) ({       \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebuis_ofs_lookup_lt(root, _kofs, key);    \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the item of type <type> which contains the lowest

 * key key that is greater than or equal to <key>, using node member <nname>

 * and key member <kname>. Returns the pointer to the item, or NULL if not

 * found.

 */

#define cebuis_item_lookup_ge(root, nname, kname, key, type) ({       \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebuis_ofs_lookup_ge(root, _kofs, key);    \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the item of type <type> which contains the lowest

 * key that is strictly greater than <key>, using node member <nname> and key

 * member <kname>. Returns the pointer to the item, or NULL if not found.

 */

#define cebuis_item_lookup_gt(root, nname, kname, key, type) ({       \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebuis_ofs_lookup_gt(root, _kofs, key);    \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

/* lookup from root <root>, the first item immediately after item <item_ptr>,

 * using node member <nname> and key member <kname>, and returns either the

 * found item, or NULL if none exists.

 */

#define cebuis_item_next(root, nname, kname, item_ptr) ({       \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebuis_ofs_next(root, _kofs, &(item_ptr)->nname);  \

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;     \

})

/* lookup from root <root>, the last item immediately before item <item_ptr>,

 * using node member <nname> and key member <kname>, and returns either the

 * found item, or NULL if none exists.

 */

#define cebuis_item_prev(root, nname, kname, item_ptr) ({       \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  struct ceb_node *_node = cebuis_ofs_prev(root, _kofs, &(item_ptr)->nname);  \

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;     \

})

/* lookup from root <root>, the item <item_ptr> using node member <nname> and

 * key member <kname>, deletes it and returns it. If the item is NULL or absent

 * from the tree, NULL is returned.

 */

#define cebuis_item_delete(root, nname, kname, item_ptr) ({        \

  ptrdiff_t _nofs = offsetof(typeof(*(item_ptr)), nname);       \

  ptrdiff_t _kofs = offsetof(typeof(*(item_ptr)), kname) - _nofs;     \

  typeof(item_ptr) _item = (item_ptr);            \

  struct ceb_node *_node = cebuis_ofs_delete(root, _kofs, _item ? &_item->nname : NULL); \

  _node ? (typeof(item_ptr))((char *)(_node) - _nofs) : NULL;      \

})

/* lookup from root <root>, the first item of type <type> which contains the

 * key <key>, using node member <nname> and key member <kname>, deletes it and

 * returns it. If the key is not found in the tree, NULL is returned.

 */

#define cebuis_item_pick(root, nname, kname, key, type) ({        \

  ptrdiff_t _nofs = offsetof(type, nname);          \

  ptrdiff_t _kofs = offsetof(type, kname) - _nofs;        \

  struct ceb_node *_node = cebuis_ofs_pick(root, _kofs, key);     \

  _node ? (type *)((char *)(_node) - _nofs) : NULL;       \

})

#endif /* _CEBIS_TREE_H */