diff options
Diffstat (limited to 'usr.sbin/unbound/util/rbtree.h')
| -rw-r--r-- | usr.sbin/unbound/util/rbtree.h | 78 |
1 files changed, 39 insertions, 39 deletions
diff --git a/usr.sbin/unbound/util/rbtree.h b/usr.sbin/unbound/util/rbtree.h index 879804dd860..dfcf09ac6a8 100644 --- a/usr.sbin/unbound/util/rbtree.h +++ b/usr.sbin/unbound/util/rbtree.h @@ -21,16 +21,16 @@ * specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED - * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED + * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * */ @@ -45,40 +45,40 @@ /** * This structure must be the first member of the data structure in - * the rbtree. This allows easy casting between an rbnode_t and the + * the rbtree. This allows easy casting between an rbnode_type and the * user data (poor man's inheritance). */ -typedef struct rbnode_t rbnode_t; +typedef struct rbnode_type rbnode_type; /** - * The rbnode_t struct definition. + * The rbnode_type struct definition. */ -struct rbnode_t { +struct rbnode_type { /** parent in rbtree, RBTREE_NULL for root */ - rbnode_t *parent; + rbnode_type *parent; /** left node (smaller items) */ - rbnode_t *left; + rbnode_type *left; /** right node (larger items) */ - rbnode_t *right; + rbnode_type *right; /** pointer to sorting key */ - const void *key; + const void *key; /** colour of this node */ - uint8_t color; + uint8_t color; }; /** The nullpointer, points to empty node */ #define RBTREE_NULL &rbtree_null_node /** the global empty node */ -extern rbnode_t rbtree_null_node; +extern rbnode_type rbtree_null_node; /** An entire red black tree */ -typedef struct rbtree_t rbtree_t; +typedef struct rbtree_type rbtree_type; /** definition for tree struct */ -struct rbtree_t { +struct rbtree_type { /** The root of the red-black tree */ - rbnode_t *root; + rbnode_type *root; /** The number of the nodes in the tree */ - size_t count; + size_t count; /** * Key compare function. <0,0,>0 like strcmp. @@ -92,14 +92,14 @@ struct rbtree_t { * @param cmpf: compare function (like strcmp) takes pointers to two keys. * @return: new tree, empty. */ -rbtree_t *rbtree_create(int (*cmpf)(const void *, const void *)); +rbtree_type *rbtree_create(int (*cmpf)(const void *, const void *)); /** * Init a new tree (malloced by caller) with given key compare function. * @param rbtree: uninitialised memory for new tree, returned empty. * @param cmpf: compare function (like strcmp) takes pointers to two keys. */ -void rbtree_init(rbtree_t *rbtree, int (*cmpf)(const void *, const void *)); +void rbtree_init(rbtree_type *rbtree, int (*cmpf)(const void *, const void *)); /** * Insert data into the tree. @@ -107,7 +107,7 @@ void rbtree_init(rbtree_t *rbtree, int (*cmpf)(const void *, const void *)); * @param data: element to insert. * @return: data ptr or NULL if key already present. */ -rbnode_t *rbtree_insert(rbtree_t *rbtree, rbnode_t *data); +rbnode_type *rbtree_insert(rbtree_type *rbtree, rbnode_type *data); /** * Delete element from tree. @@ -116,7 +116,7 @@ rbnode_t *rbtree_insert(rbtree_t *rbtree, rbnode_t *data); * @return: node that is now unlinked from the tree. User to delete it. * returns 0 if node not present */ -rbnode_t *rbtree_delete(rbtree_t *rbtree, const void *key); +rbnode_type *rbtree_delete(rbtree_type *rbtree, const void *key); /** * Find key in tree. Returns NULL if not found. @@ -124,7 +124,7 @@ rbnode_t *rbtree_delete(rbtree_t *rbtree, const void *key); * @param key: key that must match. * @return: node that fits or NULL. */ -rbnode_t *rbtree_search(rbtree_t *rbtree, const void *key); +rbnode_type *rbtree_search(rbtree_type *rbtree, const void *key); /** * Find, but match does not have to be exact. @@ -135,45 +135,45 @@ rbnode_t *rbtree_search(rbtree_t *rbtree, const void *key); * @return: true if exact match in result. Else result points to <= element, * or NULL if key is smaller than the smallest key. */ -int rbtree_find_less_equal(rbtree_t *rbtree, const void *key, - rbnode_t **result); +int rbtree_find_less_equal(rbtree_type *rbtree, const void *key, + rbnode_type **result); /** * Returns first (smallest) node in the tree * @param rbtree: tree * @return: smallest element or NULL if tree empty. */ -rbnode_t *rbtree_first(rbtree_t *rbtree); +rbnode_type *rbtree_first(rbtree_type *rbtree); /** * Returns last (largest) node in the tree * @param rbtree: tree * @return: largest element or NULL if tree empty. */ -rbnode_t *rbtree_last(rbtree_t *rbtree); +rbnode_type *rbtree_last(rbtree_type *rbtree); /** * Returns next larger node in the tree * @param rbtree: tree * @return: next larger element or NULL if no larger in tree. */ -rbnode_t *rbtree_next(rbnode_t *rbtree); +rbnode_type *rbtree_next(rbnode_type *rbtree); /** * Returns previous smaller node in the tree * @param rbtree: tree * @return: previous smaller element or NULL if no previous in tree. */ -rbnode_t *rbtree_previous(rbnode_t *rbtree); +rbnode_type *rbtree_previous(rbnode_type *rbtree); /** - * Call with node=variable of struct* with rbnode_t as first element. + * Call with node=variable of struct* with rbnode_type as first element. * with type is the type of a pointer to that struct. */ #define RBTREE_FOR(node, type, rbtree) \ for(node=(type)rbtree_first(rbtree); \ - (rbnode_t*)node != RBTREE_NULL; \ - node = (type)rbtree_next((rbnode_t*)node)) + (rbnode_type*)node != RBTREE_NULL; \ + node = (type)rbtree_next((rbnode_type*)node)) /** * Call function for all elements in the redblack tree, such that @@ -186,7 +186,7 @@ rbnode_t *rbtree_previous(rbnode_t *rbtree); * The function must not alter the rbtree. * @param arg: user argument. */ -void traverse_postorder(rbtree_t* tree, void (*func)(rbnode_t*, void*), +void traverse_postorder(rbtree_type* tree, void (*func)(rbnode_type*, void*), void* arg); #endif /* UTIL_RBTREE_H_ */ |