rbtree-llrb.h

/* ==========================================================================
 * llrb.h - Iterative Left-leaning Red-Black Tree.
 * --------------------------------------------------------------------------
 * Copyright (c) 2011, 2013  William Ahern <william@25thandClement.com>
 *
 * 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.
 * --------------------------------------------------------------------------
 * CREDITS:
 * 	o Algorithm courtesy of Robert Sedgewick, "Left-leaning Red-Black
 * 	  Trees" (September 2008); and Robert Sedgewick and Kevin Wayne,
 * 	  Algorithms (4th ed. 2011).
 *
 * 	  Sedgewick touts the simplicity of the recursive implementation,
 * 	  but at least for the 2-3 tree variant the iterative approach is
 * 	  almost line-for-line identical. The magic of C pointers helps;
 * 	  it'd be uglier with Java.
 *
 * 	  A couple of missing NULL checks were added to Sedgewick's deletion
 * 	  example, and insert was optimized to short-circuit rotations when
 * 	  walking up the tree.
 * 
 * 	o Code implemented in the fashion of Niels Provos' excellent *BSD
 * 	  sys/tree.h pre-processor library.
 *
 * 	  Regarding relative performance, I've refrained from sharing my own
 * 	  benchmarks. Differences in run-time speed were too correlated to
 * 	  compiler options and other external factors.
 *
 * 	  Provos' delete implementation doesn't need to start at the root of
 * 	  the tree. However, RB_REMOVE must be passed the actual node to be
 * 	  removed. LLRB_REMOVE merely requires a key, much like
 * 	  RB_FIND/LLRB_FIND.
 * ==========================================================================
 */
#ifndef LLRB_H
#define LLRB_H

#define LLRB_VENDOR "william@25thandClement.com"
#define LLRB_VERSION 0x20130925

#ifndef LLRB_STATIC
#ifdef __GNUC__
#define LLRB_STATIC __attribute__((__unused__)) static
#else
#define LLRB_STATIC static
#endif
#endif

#define LLRB_HEAD(name, type) \
struct name { struct type *rbh_root; }

#define LLRB_INITIALIZER(root) { 0 }

#define LLRB_INIT(root) do { (root)->rbh_root = 0; } while (0)

#define LLRB_BLACK 0
#define LLRB_RED   1

#define LLRB_ENTRY(type) \
struct { struct type *rbe_left, *rbe_right, *rbe_parent; _Bool rbe_color; }

#define LLRB_LEFT(elm, field) (elm)->field.rbe_left
#define LLRB_RIGHT(elm, field) (elm)->field.rbe_right
#define LLRB_PARENT(elm, field) (elm)->field.rbe_parent
#define LLRB_EDGE(head, elm, field) (((elm) == LLRB_ROOT(head))? &LLRB_ROOT(head) : ((elm) == LLRB_LEFT(LLRB_PARENT((elm), field), field))? &LLRB_LEFT(LLRB_PARENT((elm), field), field) : &LLRB_RIGHT(LLRB_PARENT((elm), field), field))
#define LLRB_COLOR(elm, field) (elm)->field.rbe_color
#define LLRB_ROOT(head) (head)->rbh_root
#define LLRB_EMPTY(head) ((head)->rbh_root == 0)
#define LLRB_ISRED(elm, field) ((elm) && LLRB_COLOR((elm), field) == LLRB_RED)

#define LLRB_PROTOTYPE(name, type, field, cmp) \
	LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
#define LLRB_PROTOTYPE_STATIC(name, type, field, cmp) \
	LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
#define LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
attr struct type *name##_LLRB_INSERT(struct name *, struct type *); \
attr struct type *name##_LLRB_DELETE(struct name *, struct type *); \
attr struct type *name##_LLRB_FIND(struct name *, struct type *); \
attr struct type *name##_LLRB_MIN(struct type *); \
attr struct type *name##_LLRB_MAX(struct type *); \
attr struct type *name##_LLRB_NEXT(struct type *);

#define LLRB_GENERATE(name, type, field, cmp) \
	LLRB_GENERATE_INTERNAL(name, type, field, cmp,)
#define LLRB_GENERATE_STATIC(name, type, field, cmp) \
	LLRB_GENERATE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
#define LLRB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
static inline void name##_LLRB_ROTL(struct type **pivot) { \
	struct type *a = *pivot; \
	struct type *b = LLRB_RIGHT(a, field); \
	if ((LLRB_RIGHT(a, field) = LLRB_LEFT(b, field))) \
		LLRB_PARENT(LLRB_RIGHT(a, field), field) = a; \
	LLRB_LEFT(b, field) = a; \
	LLRB_COLOR(b, field) = LLRB_COLOR(a, field); \
	LLRB_COLOR(a, field) = LLRB_RED; \
	LLRB_PARENT(b, field) = LLRB_PARENT(a, field); \
	LLRB_PARENT(a, field) = b; \
	*pivot = b; \
} \
static inline void name##_LLRB_ROTR(struct type **pivot) { \
	struct type *b = *pivot; \
	struct type *a = LLRB_LEFT(b, field); \
	if ((LLRB_LEFT(b, field) = LLRB_RIGHT(a, field))) \
		LLRB_PARENT(LLRB_LEFT(b, field), field) = b; \
	LLRB_RIGHT(a, field) = b; \
	LLRB_COLOR(a, field) = LLRB_COLOR(b, field); \
	LLRB_COLOR(b, field) = LLRB_RED; \
	LLRB_PARENT(a, field) = LLRB_PARENT(b, field); \
	LLRB_PARENT(b, field) = a; \
	*pivot = a; \
} \
static inline void name##_LLRB_FLIP(struct type *root) { \
	LLRB_COLOR(root, field) = !LLRB_COLOR(root, field); \
	LLRB_COLOR(LLRB_LEFT(root, field), field) = !LLRB_COLOR(LLRB_LEFT(root, field), field); \
	LLRB_COLOR(LLRB_RIGHT(root, field), field) = !LLRB_COLOR(LLRB_RIGHT(root, field), field); \
} \
static inline void name##_LLRB_FIXUP(struct type **root) { \
	if (LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field)) \
		name##_LLRB_ROTL(root); \
	if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
		name##_LLRB_ROTR(root); \
	if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_RIGHT(*root, field), field)) \
		name##_LLRB_FLIP(*root); \
} \
attr struct type *name##_LLRB_INSERT(struct name *head, struct type *elm) { \
	struct type **root = &LLRB_ROOT(head); \
	struct type *parent = 0; \
	while (*root) { \
		int comp = (cmp)((elm), (*root)); \
		parent = *root; \
		if (comp < 0) \
			root = &LLRB_LEFT(*root, field); \
		else if (comp > 0) \
			root = &LLRB_RIGHT(*root, field); \
		else \
			return *root; \
	} \
	LLRB_LEFT((elm), field) = 0; \
	LLRB_RIGHT((elm), field) = 0; \
	LLRB_COLOR((elm), field) = LLRB_RED; \
	LLRB_PARENT((elm), field) = parent; \
	*root = (elm); \
	while (parent && (LLRB_ISRED(LLRB_LEFT(parent, field), field) || LLRB_ISRED(LLRB_RIGHT(parent, field), field))) { \
		root = LLRB_EDGE(head, parent, field); \
		parent = LLRB_PARENT(parent, field); \
		name##_LLRB_FIXUP(root); \
	} \
	LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
	return 0; \
} \
static inline void name##_LLRB_MOVL(struct type **pivot) { \
	name##_LLRB_FLIP(*pivot); \
	if (LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*pivot, field), field), field)) { \
		name##_LLRB_ROTR(&LLRB_RIGHT(*pivot, field)); \
		name##_LLRB_ROTL(pivot); \
		name##_LLRB_FLIP(*pivot); \
	} \
} \
static inline void name##_LLRB_MOVR(struct type **pivot) { \
	name##_LLRB_FLIP(*pivot); \
	if (LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) { \
		name##_LLRB_ROTR(pivot); \
		name##_LLRB_FLIP(*pivot); \
	} \
} \
static inline struct type *name##_DELETEMIN(struct name *head, struct type **root) { \
	struct type **pivot = root, *deleted, *parent; \
	while (LLRB_LEFT(*pivot, field)) { \
		if (!LLRB_ISRED(LLRB_LEFT(*pivot, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) \
			name##_LLRB_MOVL(pivot); \
		pivot = &LLRB_LEFT(*pivot, field); \
	} \
	deleted = *pivot; \
	parent = LLRB_PARENT(*pivot, field); \
	*pivot = 0; \
	while (root != pivot) { \
		pivot = LLRB_EDGE(head, parent, field); \
		parent = LLRB_PARENT(parent, field); \
		name##_LLRB_FIXUP(pivot); \
	} \
	return deleted; \
} \
attr struct type *name##_LLRB_DELETE(struct name *head, struct type *elm) { \
	struct type **root = &LLRB_ROOT(head), *parent = 0, *deleted = 0; \
	int comp; \
	while (*root) { \
		parent = LLRB_PARENT(*root, field); \
		comp = (cmp)(elm, *root); \
		if (comp < 0) { \
			if (LLRB_LEFT(*root, field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
				name##_LLRB_MOVL(root); \
			root = &LLRB_LEFT(*root, field); \
		} else { \
			if (LLRB_ISRED(LLRB_LEFT(*root, field), field)) { \
				name##_LLRB_ROTR(root); \
				comp = (cmp)(elm, *root); \
			} \
			if (!comp && !LLRB_RIGHT(*root, field)) { \
				deleted = *root; \
				*root = 0; \
				break; \
			} \
			if (LLRB_RIGHT(*root, field) && !LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*root, field), field), field)) { \
				name##_LLRB_MOVR(root); \
				comp = (cmp)(elm, *root); \
			} \
			if (!comp) { \
				struct type *orphan = name##_DELETEMIN(head, &LLRB_RIGHT(*root, field)); \
				LLRB_COLOR(orphan, field) = LLRB_COLOR(*root, field); \
				LLRB_PARENT(orphan, field) = LLRB_PARENT(*root, field); \
				if ((LLRB_RIGHT(orphan, field) = LLRB_RIGHT(*root, field))) \
					LLRB_PARENT(LLRB_RIGHT(orphan, field), field) = orphan; \
				if ((LLRB_LEFT(orphan, field) = LLRB_LEFT(*root, field))) \
					LLRB_PARENT(LLRB_LEFT(orphan, field), field) = orphan; \
				deleted = *root; \
				*root = orphan; \
				parent = *root; \
				break; \
			} else \
				root = &LLRB_RIGHT(*root, field); \
		} \
	} \
	while (parent) { \
		root = LLRB_EDGE(head, parent, field); \
		parent = LLRB_PARENT(parent, field); \
		name##_LLRB_FIXUP(root); \
	} \
	if (LLRB_ROOT(head)) \
		LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
	return deleted; \
} \
attr struct type *name##_LLRB_FIND(struct name *head, struct type *key) { \
	struct type *elm = LLRB_ROOT(head); \
	while (elm) { \
		int comp = (cmp)(key, elm); \
		if (comp < 0) \
			elm = LLRB_LEFT(elm, field); \
		else if (comp > 0) \
			elm = LLRB_RIGHT(elm, field); \
		else \
			return elm; \
	} \
	return 0; \
} \
attr struct type *name##_LLRB_MIN(struct type *elm) { \
	while (elm && LLRB_LEFT(elm, field)) \
		elm = LLRB_LEFT(elm, field); \
	return elm; \
} \
attr struct type *name##_LLRB_MAX(struct type *elm) { \
	while (elm && LLRB_RIGHT(elm, field)) \
		elm = LLRB_RIGHT(elm, field); \
	return elm; \
} \
attr struct type *name##_LLRB_NEXT(struct type *elm) { \
	if (LLRB_RIGHT(elm, field)) { \
		return name##_LLRB_MIN(LLRB_RIGHT(elm, field)); \
	} else if (LLRB_PARENT(elm, field)) { \
		if (elm == LLRB_LEFT(LLRB_PARENT(elm, field), field)) \
			return LLRB_PARENT(elm, field); \
		while (LLRB_PARENT(elm, field) && elm == LLRB_RIGHT(LLRB_PARENT(elm, field), field)) \
			elm = LLRB_PARENT(elm, field); \
		return LLRB_PARENT(elm, field); \
	} else return 0; \
}

#define LLRB_INSERT(name, head, elm) name##_LLRB_INSERT((head), (elm))
#define LLRB_DELETE(name, head, elm) name##_LLRB_DELETE((head), (elm))
#define LLRB_REMOVE(name, head, elm) name##_LLRB_DELETE((head), (elm))
#define LLRB_FIND(name, head, elm) name##_LLRB_FIND((head), (elm))
#define LLRB_MIN(name, head) name##_LLRB_MIN(LLRB_ROOT((head)))
#define LLRB_MAX(name, head) name##_LLRB_MAX(LLRB_ROOT((head)))
#define LLRB_NEXT(name, head, elm) name##_LLRB_NEXT((elm))

#define LLRB_FOREACH(elm, name, head) \
for ((elm) = LLRB_MIN(name, head); (elm); (elm) = name##_LLRB_NEXT((elm)))

#endif /* LLRB_H */