/* * Elastic Binary Trees - types * Version 6.0.6 * (C) 2002-2011 - Willy Tarreau * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation, version 2.1 * exclusively. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #ifndef _EBTREE_T_H #define _EBTREE_T_H #include /* * generic types for ebtree */ /* Number of bits per node, and number of leaves per node */ #define EB_NODE_BITS 1 #define EB_NODE_BRANCHES (1 << EB_NODE_BITS) #define EB_NODE_BRANCH_MASK (EB_NODE_BRANCHES - 1) /* Be careful not to tweak those values. The walking code is optimized for NULL * detection on the assumption that the following values are intact. */ #define EB_LEFT 0 #define EB_RGHT 1 #define EB_LEAF 0 #define EB_NODE 1 /* Tags to set in root->b[EB_RGHT] : * - EB_NORMAL is a normal tree which stores duplicate keys. * - EB_UNIQUE is a tree which stores unique keys. */ #define EB_NORMAL 0 #define EB_UNIQUE 1 /* This is the same as an eb_node pointer, except that the lower bit embeds * a tag. See eb_dotag()/eb_untag()/eb_gettag(). This tag has two meanings : * - 0=left, 1=right to designate the parent's branch for leaf_p/node_p * - 0=link, 1=leaf to designate the branch's type for branch[] */ typedef void eb_troot_t; /* The eb_root connects the node which contains it, to two nodes below it, one * of which may be the same node. At the top of the tree, we use an eb_root * too, which always has its right branch NULL (+/1 low-order bits). */ struct eb_root { eb_troot_t *b[EB_NODE_BRANCHES]; /* left and right branches */ }; /* The eb_node contains the two parts, one for the leaf, which always exists, * and one for the node, which remains unused in the very first node inserted * into the tree. This structure is 20 bytes per node on 32-bit machines. Do * not change the order, benchmarks have shown that it's optimal this way. * Note: be careful about this struct's alignment if it gets included into * another struct and some atomic ops are expected on the keys or the node. */ struct eb_node { struct eb_root branches; /* branches, must be at the beginning */ eb_troot_t *node_p; /* link node's parent */ eb_troot_t *leaf_p; /* leaf node's parent */ short int bit; /* link's bit position. */ short unsigned int pfx; /* data prefix length, always related to leaf */ } __attribute__((packed)); /* The root of a tree is an eb_root initialized with both pointers NULL. * During its life, only the left pointer will change. The right one will * always remain NULL, which is the way we detect it. */ #define EB_ROOT \ (struct eb_root) { \ .b = {[0] = NULL, [1] = NULL }, \ } #define EB_ROOT_UNIQUE \ (struct eb_root) { \ .b = {[0] = NULL, [1] = (void *)1 }, \ } #define EB_TREE_HEAD(name) \ struct eb_root name = EB_ROOT /* * types for eb32tree */ #define EB32_ROOT EB_ROOT #define EB32_TREE_HEAD EB_TREE_HEAD /* These types may sometimes already be defined */ typedef unsigned int u32; typedef signed int s32; /* This structure carries a node, a leaf, and a key. It must start with the * eb_node so that it can be cast into an eb_node. We could also have put some * sort of transparent union here to reduce the indirection level, but the fact * is, the end user is not meant to manipulate internals, so this is pointless. */ struct eb32_node { struct eb_node node; /* the tree node, must be at the beginning */ MAYBE_ALIGN(sizeof(u32)); u32 key; } ALIGNED(sizeof(void*)); /* This structure carries a node, a leaf, a scope, and a key. It must start * with the eb_node so that it can be cast into an eb_node. We could also * have put some sort of transparent union here to reduce the indirection * level, but the fact is, the end user is not meant to manipulate internals, * so this is pointless. * In case sizeof(void*)>=sizeof(long), we know there will be some padding after * the leaf if it's unaligned. In this case we force the alignment on void* so * that we prefer to have the padding before for more efficient accesses. */ struct eb32sc_node { struct eb_node node; /* the tree node, must be at the beginning */ MAYBE_ALIGN(sizeof(u32)); u32 key; ALWAYS_ALIGN(sizeof(void*)); unsigned long node_s; /* visibility of this node's branches */ unsigned long leaf_s; /* visibility of this node's leaf */ } ALIGNED(sizeof(void*)); /* * types for eb64tree */ #define EB64_ROOT EB_ROOT #define EB64_TREE_HEAD EB_TREE_HEAD /* These types may sometimes already be defined */ typedef unsigned long long u64; typedef signed long long s64; /* This structure carries a node, a leaf, and a key. It must start with the * eb_node so that it can be cast into an eb_node. We could also have put some * sort of transparent union here to reduce the indirection level, but the fact * is, the end user is not meant to manipulate internals, so this is pointless. * In case sizeof(void*)>=sizeof(u64), we know there will be some padding after * the key if it's unaligned. In this case we force the alignment on void* so * that we prefer to have the padding before for more efficient accesses. */ struct eb64_node { struct eb_node node; /* the tree node, must be at the beginning */ MAYBE_ALIGN(sizeof(u64)); ALWAYS_ALIGN(sizeof(void*)); u64 key; } ALIGNED(sizeof(void*)); #define EBPT_ROOT EB_ROOT #define EBPT_TREE_HEAD EB_TREE_HEAD /* on *almost* all platforms, a pointer can be cast into a size_t which is unsigned */ #ifndef PTR_INT_TYPE #define PTR_INT_TYPE size_t #endif /* * types for ebpttree */ typedef PTR_INT_TYPE ptr_t; /* This structure carries a node, a leaf, and a key. It must start with the * eb_node so that it can be cast into an eb_node. We could also have put some * sort of transparent union here to reduce the indirection level, but the fact * is, the end user is not meant to manipulate internals, so this is pointless. * Internally, it is automatically cast as an eb32_node or eb64_node. * We always align the key since the struct itself will be padded to the same * size anyway. */ struct ebpt_node { struct eb_node node; /* the tree node, must be at the beginning */ ALWAYS_ALIGN(sizeof(void*)); void *key; } ALIGNED(sizeof(void*)); /* * types for ebmbtree */ #define EBMB_ROOT EB_ROOT #define EBMB_TREE_HEAD EB_TREE_HEAD /* This structure carries a node, a leaf, and a key. It must start with the * eb_node so that it can be cast into an eb_node. We could also have put some * sort of transparent union here to reduce the indirection level, but the fact * is, the end user is not meant to manipulate internals, so this is pointless. * The 'node.bit' value here works differently from scalar types, as it contains * the number of identical bits between the two branches. * Note that we take a great care of making sure the key is located exactly at * the end of the struct even if that involves holes before it, so that it * always aliases any external key a user would append after. This is why the * key uses the same alignment as the struct. */ struct ebmb_node { struct eb_node node; /* the tree node, must be at the beginning */ ALWAYS_ALIGN(sizeof(void*)); unsigned char key[0]; /* the key, its size depends on the application */ } ALIGNED(sizeof(void*)); #endif /* _EB_TREE_T_H */