File Manager

003 File Manager

Current Path: /usr/src/contrib/unbound/util

📁 ..
📄 alloc.c(18.06 KB)
📄 alloc.h(8.23 KB)
📄 as112.c(4.16 KB)
📄 as112.h(2.22 KB)
📄 config_file.c(77.33 KB)
📄 config_file.h(40.38 KB)
📄 configlexer.lex(26.89 KB)
📄 configparser.y(101.23 KB)
📄 configyyrename.h(2.22 KB)
📁 data
📄 edns.c(5.04 KB)
📄 edns.h(3.86 KB)
📄 fptr_wlist.c(19.07 KB)
📄 fptr_wlist.h(12.78 KB)
📄 iana_ports.inc(31.81 KB)
📄 locks.c(7.88 KB)
📄 locks.h(12.53 KB)
📄 log.c(16.31 KB)
📄 log.h(7.5 KB)
📄 mini_event.c(9.73 KB)
📄 mini_event.h(6.51 KB)
📄 module.c(7.14 KB)
📄 module.h(31.35 KB)
📄 net_help.c(42.81 KB)
📄 net_help.h(16.12 KB)
📄 netevent.c(114.68 KB)
📄 netevent.h(33.92 KB)
📄 random.c(6.23 KB)
📄 random.h(2.98 KB)
📄 rbtree.c(16.08 KB)
📄 rbtree.h(6.23 KB)
📄 regional.c(6.24 KB)
📄 regional.h(5.37 KB)
📄 rtt.c(3.53 KB)
📄 rtt.h(3.57 KB)
📁 shm_side
📁 storage
📄 tcp_conn_limit.c(4.91 KB)
📄 tcp_conn_limit.h(3.88 KB)
📄 timehist.c(6.06 KB)
📄 timehist.h(3.81 KB)
📄 tube.c(17.71 KB)
📄 tube.h(8.4 KB)
📄 ub_event.c(11.67 KB)
📄 ub_event.h(5.07 KB)
📄 ub_event_pluggable.c(17.61 KB)
📄 winsock_event.c(21.16 KB)
📄 winsock_event.h(10.19 KB)

Editing: rbtree.h

/*
 * rbtree.h -- generic red-black tree
 *
 * Copyright (c) 2001-2007, NLnet Labs. All rights reserved.
 * 
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * 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 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.
 *
 */

/**
 * \file
 * Red black tree. Implementation taken from NSD 3.0.5, adjusted for use
 * in unbound (memory allocation, logging and so on).
 */

#ifndef UTIL_RBTREE_H_
#define	UTIL_RBTREE_H_

/**
 * This structure must be the first member of the data structure in
 * the rbtree.  This allows easy casting between an rbnode_type and the
 * user data (poor man's inheritance).
 */
typedef struct rbnode_type rbnode_type;
/**
 * The rbnode_type struct definition.
 */
struct rbnode_type {
	/** parent in rbtree, RBTREE_NULL for root */
	rbnode_type   *parent;
	/** left node (smaller items) */
	rbnode_type   *left;
	/** right node (larger items) */
	rbnode_type   *right;
	/** pointer to sorting key */
	const void    *key;
	/** colour of this node */
	uint8_t	       color;
};

/** The nullpointer, points to empty node */
#define	RBTREE_NULL &rbtree_null_node
/** the global empty node */
extern	rbnode_type	rbtree_null_node;

/** An entire red black tree */
typedef struct rbtree_type rbtree_type;
/** definition for tree struct */
struct rbtree_type {
	/** The root of the red-black tree */
	rbnode_type    *root;

/** The number of the nodes in the tree */
	size_t          count;

/** 
	 * Key compare function. <0,0,>0 like strcmp. 
	 * Return 0 on two NULL ptrs. 
	 */
	int (*cmp) (const void *, const void *);
};

/** 
 * Create new tree (malloced) with given key compare function. 
 * @param cmpf: compare function (like strcmp) takes pointers to two keys.
 * @return: new tree, empty.
 */
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_type *rbtree, int (*cmpf)(const void *, const void *));

/** 
 * Insert data into the tree. 
 * @param rbtree: tree to insert to.
 * @param data: element to insert. 
 * @return: data ptr or NULL if key already present. 
 */
rbnode_type *rbtree_insert(rbtree_type *rbtree, rbnode_type *data);

/**
 * Delete element from tree.
 * @param rbtree: tree to delete from.
 * @param key: key of item to delete.
 * @return: node that is now unlinked from the tree. User to delete it. 
 * returns 0 if node not present 
 */
rbnode_type *rbtree_delete(rbtree_type *rbtree, const void *key);

/**
 * Find key in tree. Returns NULL if not found.
 * @param rbtree: tree to find in.
 * @param key: key that must match.
 * @return: node that fits or NULL.
 */
rbnode_type *rbtree_search(rbtree_type *rbtree, const void *key);

/**
 * Find, but match does not have to be exact.
 * @param rbtree: tree to find in.
 * @param key: key to find position of.
 * @param result: set to the exact node if present, otherwise to element that
 *   precedes the position of key in the tree. NULL if no smaller element.
 * @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_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_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_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_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_type *rbtree_previous(rbnode_type *rbtree);

/**
 * 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_type*)node != RBTREE_NULL; \
		node = (type)rbtree_next((rbnode_type*)node))

/**
 * Call function for all elements in the redblack tree, such that
 * leaf elements are called before parent elements. So that all
 * elements can be safely free()d.
 * Note that your function must not remove the nodes from the tree.
 * Since that may trigger rebalances of the rbtree.
 * @param tree: the tree
 * @param func: function called with element and user arg.
 * 	The function must not alter the rbtree.
 * @param arg: user argument.
 */
void traverse_postorder(rbtree_type* tree, void (*func)(rbnode_type*, void*),
	void* arg);

#endif /* UTIL_RBTREE_H_ */

003 File Manager

Editing: rbtree.h

Upload File

Create Folder