include/wine: Header only implementation of generic redblack binary search tree.

Pauli Nieminen suokkos at gmail.com
Sat Dec 20 11:30:53 CST 2008


This implementation provides easy access to rb-tree which should be used instead of hashmap
if number of entries changes a lot of over time of execution.
It should be simple to write hashtree based on this which uses hash value of the key instead of
key it self. (Which would speed up tree operations a lot if key is long string)

Note: I have also code to test the tree functionality but I don't know where to put
internal test cases.
---
 include/wine/rbtree.h |  647 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 647 insertions(+), 0 deletions(-)
 create mode 100644 include/wine/rbtree.h

diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h
new file mode 100644
index 0000000..8c87d56
--- /dev/null
+++ b/include/wine/rbtree.h
@@ -0,0 +1,647 @@
+/*
+ * red/black binary search tree support
+ *
+ * Copyright (C) 2008 Pauli Nienminen
+ *
+ * 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; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * 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 St, Fifth Floor, Boston, MA 02110-1301, USA
+ */
+
+#ifndef __WINE_MAP_H
+#define __WINE_MAP_H
+
+/**
+ * c++ std::map/std::set style storage using RB-tree
+ * Interface is similar to bsd/sys/tree.h interface
+ * but has some changes that are more c++ style naming.
+ *
+ * Implementation follows "Instruction to algorithms" (SE)
+ * by Cormen, Leiserson, Rivest, Stein and borrows ideas from 
+ * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
+ * by Julienne Walker
+ *
+ * Basic use case includes these steps:
+ *
+ * 1. define node structure to hold data
+ * user defined data has to include key member for storing key data
+ * 	struct map_node_example_t {
+ * 		RB_ENTRY(map_node_example_t) header;
+ * 		size_t key;
+ * 		char text[MAX_LENGTH];
+ *  }
+ *
+ * 2. define helper functions
+ *  BOOL example_less(size_t *a, size_t *b) 
+ *  { return *a < *b; }
+ *
+ * 3. generate specialized code
+ *  RB_GENERATE(exampletree, map_node_example_t, header, example_less)
+ *
+ * 4. create map object
+ *  RB_HEAD(exampletree, map_node_example_t) map; // variable to hold map object
+ *  RB_INIT(&map); // Initialize map object (static initialization also possible)
+ *
+ * 4. Insert/find/erase
+ *  map_node_example_t *node = RB_INSERT(exampletree,map,new_key);
+ *  node->key = new_key;
+ *  strcpy(node->text,new_text);
+ *  node = RB_FIND(exampletree, map,  new_key);
+ * 	RB_ERASE_ITOR(exampletree, map, node);
+ *
+ * 5. Clean up all reserved memory
+ *  RB_ERASE_ALL(exampletree, map);
+ *  
+ * Other usefull interface macros are:
+ * RB_ERASE(treename, map, key)
+ * RB_NEXT(treename, node)
+ * RB_PREV(treename, node)
+ *
+ * RB_INITIALIZER
+ * RB_GENERATE_STATIC
+ * RB_GENERATE_USER
+ * RB_PROTOTYPE
+ * RB_PROTOTYPE_STATIC
+ *
+ * debug:
+ * RB_VERIFY(treename, node)
+ *
+ *  TODO: Make it possible to define user allocator
+ *  	  that would allow large trees to allocate into
+ *  	  sperate heap so memory fragmentation wouldn't
+ *  	  be so large problem.
+ **/
+
+#ifdef INTERFACE_DOCUMENTATION
+/**
+ * Insert new node to map. If key is already in map
+ * don't do anything. (Allocates the data storage)
+ * @param: new is modified to true if no collision with key
+ * @return: node that matches given key after insert
+ **/
+struct map_node_t *map_insert(struct map_t *map, void *key, BOOL *new);
+
+/**
+ * Find node from map that matches the key
+ * @return: NULL if no matching key was found.
+ **/
+struct map_node_t *map_find(struct map_t *map, void *key);
+
+/**
+ * Erase the node from map.
+ **/
+void map_erase_itor(struct map_t *map, map_node_t *node);
+void map_erase(struct map_t *map, void *key);
+
+/**
+ * Erase all nodes in map.
+ **/
+void map_erase_all(struct map_t *map);
+
+/**
+ * Iterate over tree in unspecified order and
+ * apply transform_node to all nodes
+ * This is slow interface because of large
+ * number of function calls.
+ **/
+void map_iterate(struct map_t *map,
+		map_transform_node_t *operation);
+
+/**
+ * used to iterate map inorder
+ **/
+struct map_node_t *map_next(struct map_node_t *node);
+struct map_node_t *map_prev(struct map_node_t *node);
+#endif
+
+#include <wtypes.h>
+#include <wine/debug.h>
+
+WINE_DECLARE_DEBUG_CHANNEL(map);
+
+enum map_color {
+	MAP_RED,
+	MAP_BLACK
+};
+
+enum map_child_dir {
+	MAP_LEFT = 0,
+	MAP_RIGHT = 1
+};
+
+#define RB_HEAD(name, type)				\
+struct name {							\
+	struct type *root;					\
+}
+
+#define RB_INITIALIZER(root)			\
+	{ NULL }
+
+#define RB_INIT(root) do {				\
+	(root)->root = NULL;				\
+} while(0)
+
+
+/**
+ * Internal data used in tree structure
+ **/
+#define RB_ENTRY(type)					\
+struct type##_map_node_header_t {		\
+	struct type *parent;				\
+	struct type *childs[2];				\
+	size_t color;						\
+}
+
+#if 0
+/*
+ * type that map user has to "inherit".
+ **/
+typedef struct map_node_t {
+	 RB_ENTRY(map_node_t) h;
+	 key_type key;
+	/* user defined data */
+} map_node_t;
+#endif
+
+#define RB_LEFT(elm, field)		(elm)->field.childs[0]
+#define RB_RIGHT(elm, field)		(elm)->field.childs[1]
+#define RB_PARENT(elm, field)		(elm)->field.parent
+#define RB_GRANDPARENT(elm, field)	RB_PARENT(RB_PARENT(elm,field),field)
+#define RB_COLOR(elm, field)		(elm)->field.color
+#define RB_ROOT(head)			(head)->root
+#define RB_EMPTY(head)			(RB_ROOT(head) == NULL)
+
+/**
+ * helper macro to rotate nodes
+ **/
+#define RB_ROTATE(type, field, map, node, dir) do {				\
+	struct type *child = node->field.childs[!dir];				\
+	TRACE_(map)("%p, d: %d, c: %p\n", node,dir,child);			\
+	node->field.childs[!dir] = child->field.childs[dir];		\
+	if (node->field.childs[!dir])								\
+		node->field.childs[!dir]->field.parent = node;			\
+	RB_PARENT(child, field) = RB_PARENT(node, field);			\
+																\
+	if (RB_PARENT(node,field) == NULL) {						\
+		RB_ROOT(map) = child;									\
+	} else if (RB_LEFT(RB_PARENT(node,field),field) == node) {	\
+		RB_LEFT(RB_PARENT(node,field),field) = child;			\
+	} else {													\
+		RB_RIGHT(RB_PARENT(node,field),field) = child;			\
+	}															\
+	child->field.childs[dir] = node;							\
+	RB_PARENT(node,field) = child;									\
+} while(0) 														\
+
+#define _map_is_node_red(node, field) (node != NULL && (node)->field.color == MAP_RED)
+
+#define _map_is_node_black(node, field) !_map_is_node_red(node, field)
+
+/* Generates prototypes and inline functions */
+#define	RB_PROTOTYPE(name, type, field, cmp)								\
+	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+
+#define	RB_PROTOTYPE_STATIC(name, type, field, cmp)							\
+	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, inline static)
+
+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)					\
+typedef int (name##_map_transform_node_t)(struct type* node);				\
+attr struct type *name##_map_insert(struct name *map, 						\
+		void *key, BOOL *new); \
+attr struct type *name##_map_find(struct name *map, void *key); 			\
+attr void name##_map_erase_itor(struct name *root, type *node);				\
+attr void name##_map_erase(struct name *root, void *key);					\
+attr void name##_map_erase_all(struct name *map);							\
+attr void name##_map_iterate(struct name *map,								\
+		name##_map_transform_node_t *operation);							\
+attr void name##_map_iterate_limit(struct type *start, struct type *end,	\
+		name##_map_transform_node_t *operation);							\
+attr struct type *name##_map_sucessor(struct type *node);					\
+attr struct type *name##_map_predecessor(struct type *node);				\
+/* */
+
+
+
+/**
+ * macros to expose way to use default operations
+ * for free node and copy node
+ **/
+#define DEFAULT_FREE(name) name##__map_free_node
+#define DEFAULT_COPY_DATA(name) name##__map_copy_data
+#define DEFAULT_COPY_DATA_HEADER(name) name##__map_copy_data_header
+
+#define	RB_GENERATE(name, type, field, less)						\
+	RB_GENERATE_INTERNAL(name, type, field, less, DEFAULT_COPY_DATA(name), DEFAULT_FREE(name),)
+
+#define RB_GENERATE_USER(name, type, field, less, copy, free, attr) 	\
+	RB_GENERATE_INTERNAL(name, type, field, less, copy, free, attr)
+
+#define	RB_GENERATE_STATIC(name, type, field, less)				\
+	RB_GENERATE_INTERNAL(name, type, field, less, DEFAULT_COPY_DATA(name), DEFAULT_FREE(name),static inline)
+
+#define RB_GENERATE_INTERNAL(name, type, field, less, copy, free, attr) \
+																		\
+typedef int (name##_map_transform_node_t)(struct type *node);			\
+																		\
+static inline void name##__map_iterate_child_first(struct type *node,	\
+		name##_map_transform_node_t *operation);						\
+/**																		\
+ * used if no user defined function is provided							\
+ **/																	\
+static inline int name##__map_free_node(struct type *node)				\
+{																		\
+	HeapFree(GetProcessHeap(), 0, node);								\
+	return 0;															\
+}																		\
+																		\
+/* This is more effience than copying data if							\
+ * sizeof(data) >> sizeof(header)										\
+ **/																	\
+static inline void name##__map_copy_data_header(struct type *dst, 		\
+		struct type *src) {												\
+	struct type##_map_node_header_t temp;								\
+	memcpy(&temp, &dst->field, sizeof(temp));							\
+	memcpy(&dst->field, &src->field, sizeof(temp));						\
+	memcpy(&src->field, &temp, sizeof(temp));							\
+}																		\
+																		\
+/**																		\
+ * standard data copy using memcpy										\
+ **/																	\
+static inline void name##__map_copy_data( struct type *dst,				\
+		struct type *src) {												\
+	size_t offset = sizeof(struct type##_map_node_header_t);			\
+	memcpy((BYTE*)dst + offset, (BYTE*)src + offset,					\
+			sizeof(struct type) 										\
+			- sizeof(struct type##_map_node_header_t));					\
+}																		\
+																		\
+static inline struct type *name##__map_create_node(struct type *parent){\
+	struct type *new = 													\
+	HeapAlloc(GetProcessHeap(), 0, sizeof(struct type)); 				\
+	RB_PARENT(new,field) = parent;										\
+	RB_COLOR(new,field) = MAP_RED;										\
+	RB_LEFT(new,field) = 0;												\
+	RB_RIGHT(new,field) = 0;											\
+	TRACE_(map)("create: %p\n", new);									\
+	return new;															\
+}																		\
+																		\
+static inline void name##__map_color_fixup_insert(struct name *map,		\
+		struct type *node) {											\
+																		\
+	/* is_red test also for null pointer */								\
+	while (_map_is_node_red(RB_PARENT(node,field),field)) {				\
+		/* grandparent exists because parent is red 					\
+		 * and rule sayes root is black */								\
+		int dir_grand = RB_RIGHT(RB_GRANDPARENT(node,field),field) 		\
+			== RB_PARENT(node,field);									\
+		struct type *uncle = 											\
+			RB_GRANDPARENT(node,field)->field.childs[!dir_grand];		\
+		/* is_red test also for null pointer */							\
+		if (_map_is_node_red(uncle,field)) {							\
+			TRACE_(map)("case1: %p\n", node);							\
+			/* Color flip because we have currently:					\
+			 * node: red												\
+			 * parent: red												\
+			 * gparent: black											\
+			 * uncle: red												\
+			 **/														\
+			RB_COLOR(RB_PARENT(node,field),field) = MAP_BLACK;			\
+			RB_COLOR(uncle,field) = MAP_BLACK;							\
+			RB_COLOR(RB_GRANDPARENT(node,field),field) = MAP_RED;		\
+			node = RB_GRANDPARENT(node,field);							\
+		} else {														\
+			/* We have to rotate tree to balance it 					\
+			 * Rotations are mirrored if dir_grand is 1 */				\
+			struct type *grandparent;									\
+			if (RB_PARENT(node,field)->field.childs[!dir_grand] 		\
+					== node) {											\
+				TRACE_(map)("case2: %p\n", node);						\
+				/*       G         G									\
+				 *   P      ->   N										\
+				 *     N       P										\
+				 */														\
+				node = RB_PARENT(node,field);							\
+				RB_ROTATE(type, field, map, node, dir_grand);			\
+			}															\
+			/*      G           P										\
+			 *    P     ->   N     G									\
+			 *  N           											\
+			 */															\
+			TRACE_(map)("case3: %p\n", node);							\
+			RB_COLOR(RB_PARENT(node,field),field) = MAP_BLACK;			\
+			RB_COLOR(RB_GRANDPARENT(node,field),field) = MAP_RED;		\
+			grandparent = RB_GRANDPARENT(node,field);					\
+			RB_ROTATE(type, field, map, 								\
+					grandparent, !dir_grand);							\
+		}																\
+	}																	\
+	RB_COLOR(map->root,field) = MAP_BLACK;								\
+}																		\
+																		\
+attr struct type *name##_map_insert(struct name *map, 					\
+		void *key,														\
+		BOOL *new) {													\
+	/* Basic idea:														\
+	 * 1. "normal" BST-insert											\
+	 * 2.  fix RB-violation												\
+	 **/																\
+	struct type *node;													\
+	int dir;															\
+																		\
+	if (new)															\
+		*new = TRUE;													\
+	if (map->root == NULL)												\
+	{																	\
+		map->root = name##__map_create_node(NULL);						\
+		RB_COLOR(map->root,field) = MAP_BLACK; /* root must be black */	\
+		return map->root;												\
+	}																	\
+																		\
+	node = map->root;													\
+	do {																\
+		dir = less(&node->key, key);									\
+		if (dir == 	less(key, &node->key)) {							\
+			if (new)													\
+				*new = FALSE;											\
+			return node;												\
+		}																\
+	} while(node->field.childs[dir] != NULL								\
+		&& (node = node->field.childs[dir]));							\
+	node = node->field.childs[dir] = name##__map_create_node(node);		\
+																		\
+	name##__map_color_fixup_insert(map,node);							\
+	return node;														\
+}																		\
+																		\
+attr struct type *name##_map_find(struct name *map, void *key) {		\
+	struct type *node = map->root;										\
+	int dir;															\
+																		\
+	while (node != NULL ) {												\
+		dir = less(&node->key, key);									\
+		if (dir == 	less(key, &node->key)) {							\
+			break;														\
+		}																\
+		node = node->field.childs[dir];									\
+	}																	\
+	TRACE_(map)("found: %p\n",node);									\
+	return node;														\
+}																		\
+																		\
+/**																		\
+ * Caller has to make sure that right child exists to simplify			\
+ * this code															\
+ **/																	\
+static inline struct type *name##__map_successor_simple(struct type *node) {\
+	node = RB_RIGHT(node,field);										\
+	while (RB_LEFT(node,field) != NULL) {								\
+		node = RB_LEFT(node,field);										\
+	}																	\
+	return node;														\
+}																		\
+																		\
+static inline struct type *name##__map_predecessor_simple(struct type *node) {\
+	node = RB_LEFT(node,field);											\
+	while (RB_RIGHT(node,field) != NULL) {								\
+		node = RB_RIGHT(node,field);									\
+	}																	\
+	return node;														\
+}																		\
+																		\
+attr struct type *name##_map_successor(struct type *node) {				\
+	struct type *parent;												\
+	if (RB_RIGHT(node,field) != NULL)									\
+		return name##__map_successor_simple(node);						\
+	parent = RB_PARENT(node,field);										\
+	while(parent != NULL												\
+		&& node == RB_RIGHT(parent,field)) {							\
+		node = parent;													\
+		parent = RB_PARENT(parent,field);								\
+	}																	\
+	return parent;														\
+}																		\
+																		\
+attr struct type *name##_map_predecessor(struct type *node) {			\
+	struct type *parent;												\
+	if (RB_LEFT(node,field) != NULL)									\
+		return name##__map_successor_simple(node);						\
+	parent = RB_PARENT(node,field);										\
+	while(parent != NULL												\
+		&& node == RB_LEFT(parent,field)) {								\
+		node = parent;													\
+		parent = RB_PARENT(parent,field);								\
+	}																	\
+	return parent;														\
+}																		\
+																		\
+static inline void name##__map_color_fixup_delete(struct name *map, 	\
+									struct type *node,					\
+									int dir) {							\
+	struct type *sibling;												\
+goto skip_dir;															\
+	while (node != map->root											\
+		&& _map_is_node_black(node,field)) {							\
+		dir = RB_RIGHT(RB_PARENT(node,field),field) == node;			\
+skip_dir:																\
+		sibling = RB_PARENT(node,field)->field.childs[!dir];			\
+		if (_map_is_node_red(sibling,field))							\
+		{																\
+			struct type *parent;										\
+			TRACE_(map)("case1: %p, s: %p\n", node, sibling);			\
+			sibling->field.color = MAP_BLACK;							\
+			RB_PARENT(node,field)->field.color = MAP_RED;				\
+			parent = RB_PARENT(node,field);								\
+			RB_ROTATE(type, field, map, parent, dir);					\
+			sibling = RB_PARENT(node,field)->field.childs[!dir];		\
+		}																\
+		if (_map_is_node_black(RB_LEFT(sibling,field),field)			\
+			&& _map_is_node_black(RB_RIGHT(sibling,field),field)) {		\
+			TRACE_(map)("case2: %p, s: %p\n", node,sibling);			\
+			sibling->field.color = MAP_RED;								\
+			node = RB_PARENT(node,field);								\
+		} else {														\
+			struct type *parent;										\
+			if (_map_is_node_black(sibling->field.childs[!dir],field)) {\
+				TRACE_(map)("case3: %p, s: %p\n", node, sibling);		\
+				sibling->field.childs[dir]->field.color = MAP_BLACK;	\
+				sibling->field.color = MAP_RED;							\
+				RB_ROTATE(type, field, map, sibling, !dir);				\
+				sibling = RB_PARENT(node,field)->field.childs[!dir];	\
+			}															\
+			TRACE_(map)("case4: %p, s: %p\n", node,sibling);			\
+			sibling->field.color = RB_PARENT(node,field)->field.color;	\
+			RB_PARENT(node,field)->field.color  = MAP_BLACK;			\
+			if (sibling->field.childs[!dir])							\
+				sibling->field.childs[!dir]->field.color = MAP_BLACK;	\
+			parent = RB_PARENT(node,field);								\
+			RB_ROTATE(type, field, map, parent, dir);					\
+			node = map->root;											\
+		}																\
+	}																	\
+	node->field.color = MAP_BLACK;										\
+}																		\
+																		\
+attr void name##_map_erase_itor(struct name *map, 						\
+		struct type *node) {											\
+	int dir_child, dir_parent;											\
+	struct type *child;													\
+	TRACE_(map)("erase: %p\n", node);									\
+	if (RB_LEFT(node,field) != NULL										\
+		&& RB_RIGHT(node,field) != NULL)								\
+	{																	\
+		/* 2 childs deletion is problem but luckily we can				\
+		 * swap location of successor and simplify deletion code		\
+		 */																\
+		struct type *successor = name##__map_successor_simple(node);	\
+		TRACE_(map)("replace %p with %p\n", node, successor);			\
+		copy(node, successor);											\
+		node = successor;												\
+	}																	\
+																		\
+	dir_child = RB_LEFT(node,field) != NULL;							\
+	child = node->field.childs[dir_child];								\
+																		\
+	if (RB_PARENT(node,field) == NULL) {								\
+		/* deleting root needs special handling */						\
+		if (child != NULL) {											\
+			child->field.color = MAP_BLACK; 							\
+			/* map fix up with simple repaint */						\
+			child->field.parent = NULL;									\
+		}																\
+		map->root = child;												\
+		free(node);														\
+		return;															\
+	}																	\
+																		\
+	dir_parent = RB_RIGHT(RB_PARENT(node,field),field) == node;			\
+	/* Now we have a node selected for deletion							\
+	 * that has only maximum 1 child node and it is not root			\
+	 **/																\
+	if (child != NULL) {												\
+		child->field.parent = RB_PARENT(node,field);					\
+	} 																	\
+	RB_PARENT(node,field)->field.childs[dir_parent] = child;			\
+																		\
+	/* deletion can only cause black violation 							\
+	 * when deleted black node.											\
+	 **/																\
+	if (_map_is_node_black(node,field))									\
+		name##__map_color_fixup_delete(map, 							\
+				node, dir_parent);										\
+																		\
+	free(node);															\
+}																		\
+																		\
+attr void name##_map_erase(struct name *map, void *key) {				\
+	struct type *node = name##_map_find(map, key);						\
+	if (node)															\
+		name##_map_erase_itor(map, node);								\
+}																		\
+																		\
+attr void name##_map_erase_all(struct name *map) {						\
+	while(RB_ROOT(map) != NULL)											\
+		name##_map_erase(map, RB_ROOT(map));							\
+}																		\
+																		\
+static inline void name##__map_iterate_ascenting(struct type *node,		\
+		name##_map_transform_node_t *operation) {						\
+	/* This could be optimized with while loop 							\
+	 * but isn't compiler supposed to do that kind of stuff? :P */		\
+	if (RB_LEFT(node,field) != NULL)									\
+		name##__map_iterate_ascenting(RB_LEFT(node,field), operation);	\
+	operation(node);													\
+	if (RB_RIGHT(node,field) != NULL)									\
+		name##__map_iterate_ascenting(RB_RIGHT(node,field), operation);	\
+}																		\
+																		\
+static inline void name##__map_iterate_child_first(struct type *node,	\
+		name##_map_transform_node_t *operation) {						\
+	if (RB_RIGHT(node,field) != NULL)									\
+		name##__map_iterate_child_first(RB_RIGHT(node,field), operation);\
+	if (RB_LEFT(node,field) != NULL)									\
+		name##__map_iterate_child_first(RB_LEFT(node,field), operation);\
+	operation(node);													\
+}																		\
+																		\
+																		\
+attr void name##_map_iterate(struct name *map,							\
+		name##_map_transform_node_t *operation) {						\
+	if (map->root != NULL)												\
+		name##__map_iterate_ascenting(map->root, operation);			\
+}																		\
+/* debug only function to check RB integrity */							\
+attr int name##_map_verify(struct type *node) {							\
+	if (node == NULL) {													\
+		return 1;														\
+	}																	\
+	/* check red violation with children */								\
+	if (_map_is_node_red(node, field)) {								\
+		if (_map_is_node_red(RB_LEFT(node,field),field)					\
+			|| _map_is_node_red(RB_RIGHT(node,field),field)) {			\
+			printf("Red violation at %p\n", node);						\
+			return 0;													\
+		}																\
+	}																	\
+																		\
+	/* Check BST order */												\
+	if (RB_LEFT(node, field) != NULL									\
+		&& !less(&RB_LEFT(node,field)->key, &node->key)) {				\
+		printf("Left child larger than node %p\n", node);				\
+		return 0;														\
+	}																	\
+	if (RB_RIGHT(node, field) != NULL									\
+		&& !less(&node->key, &RB_RIGHT(node,field)->key)) {				\
+		printf("Right child smaller than node %p\n", node);				\
+		return 0;														\
+	}																	\
+	{																	\
+		int left_height = name##_map_verify(RB_LEFT(node,field));		\
+		int right_height = name##_map_verify(RB_RIGHT(node,field));		\
+		if (left_height == 0											\
+			|| right_height == 0) {										\
+			return 0;													\
+		}																\
+		if (left_height != right_height) {								\
+			printf("Height mismatch in node %p\n", node);				\
+			return 0;													\
+		}																\
+		return left_height + _map_is_node_black(node,field);			\
+	}																	\
+}
+
+
+#define RB_INSERT(name, map, key)		name##_map_insert(map, key, NULL)
+#define RB_ERASE(name, map, key)		name##_map_erase(map, key)
+#define RB_ERASE_ALL(name, map)			name##_map_erase_all(map)
+#define RB_ERASE_ITOR(name, map, node)	name##_map_erase_itor(map, node)
+#define RB_FIND(name, map, key)			name##_map_find(map, key)
+/**
+ * @param n: should be pointer to boolean value
+ **/
+#define RB_INSERT_EX(name, map, key, n) name##_map_insert(map, key, n)
+#define RB_ITERATE(name, map, func)		name##_map_iterate(map, func)
+#define RB_NEXT(name, node)             name##_map_successor(node)
+#define RB_PREV(name, node)             name##_map_predecessor(node)
+
+/**
+ * debug only ... it is very slow operation
+ * because it runs over whole tree so don't call it
+ * in very large trees if you don't have very fast computer.
+ * (This could be optimized using parrelization)
+ **/
+#define RB_VERIFY(name, node)			name##_map_verify(node)
+
+
+#endif
-- 
1.5.6.3




More information about the wine-patches mailing list