[thirdparty/git.git] / vcs-svn / trp.h

/*
 * C macro implementation of treaps.
 *
 * Usage:
 *   #include <stdint.h>
 *   #include "trp.h"
 *   trp_gen(...)
 *
 * Licensed under a two-clause BSD-style license.
 * See LICENSE for details.
 */

#ifndef TRP_H_
#define TRP_H_

#define MAYBE_UNUSED __attribute__((__unused__))

/* Node structure. */
struct trp_node {
	uint32_t trpn_left;
	uint32_t trpn_right;
};

/* Root structure. */
struct trp_root {
	uint32_t trp_root;
};

/* Pointer/Offset conversion. */
#define trpn_pointer(a_base, a_offset) (a_base##_pointer(a_offset))
#define trpn_offset(a_base, a_pointer) (a_base##_offset(a_pointer))
#define trpn_modify(a_base, a_offset) \
	do { \
		if ((a_offset) < a_base##_pool.committed) { \
			uint32_t old_offset = (a_offset);\
			(a_offset) = a_base##_alloc(1); \
			*trpn_pointer(a_base, a_offset) = \
				*trpn_pointer(a_base, old_offset); \
		} \
	} while (0)

/* Left accessors. */
#define trp_left_get(a_base, a_field, a_node) \
	(trpn_pointer(a_base, a_node)->a_field.trpn_left)
#define trp_left_set(a_base, a_field, a_node, a_left) \
	do { \
		trpn_modify(a_base, a_node); \
		trp_left_get(a_base, a_field, a_node) = (a_left); \
	} while (0)

/* Right accessors. */
#define trp_right_get(a_base, a_field, a_node) \
	(trpn_pointer(a_base, a_node)->a_field.trpn_right)
#define trp_right_set(a_base, a_field, a_node, a_right) \
	do { \
		trpn_modify(a_base, a_node); \
		trp_right_get(a_base, a_field, a_node) = (a_right); \
	} while (0)

/*
 * Fibonacci hash function.
 * The multiplier is the nearest prime to (2^32 times (√5 - 1)/2).
 * See Knuth §6.4: volume 3, 3rd ed, p518.
 */
#define trpn_hash(a_node) (uint32_t) (2654435761u * (a_node))

/* Priority accessors. */
#define trp_prio_get(a_node) trpn_hash(a_node)

/* Node initializer. */
#define trp_node_new(a_base, a_field, a_node) \
	do { \
		trp_left_set(a_base, a_field, (a_node), ~0); \
		trp_right_set(a_base, a_field, (a_node), ~0); \
	} while (0)

/* Internal utility macros. */
#define trpn_first(a_base, a_field, a_root, r_node) \
	do { \
		(r_node) = (a_root); \
		if ((r_node) == ~0) \
			return NULL; \
		while (~trp_left_get(a_base, a_field, (r_node))) \
			(r_node) = trp_left_get(a_base, a_field, (r_node)); \
	} while (0)

#define trpn_rotate_left(a_base, a_field, a_node, r_node) \
	do { \
		(r_node) = trp_right_get(a_base, a_field, (a_node)); \
		trp_right_set(a_base, a_field, (a_node), \
			trp_left_get(a_base, a_field, (r_node))); \
		trp_left_set(a_base, a_field, (r_node), (a_node)); \
	} while (0)

#define trpn_rotate_right(a_base, a_field, a_node, r_node) \
	do { \
		(r_node) = trp_left_get(a_base, a_field, (a_node)); \
		trp_left_set(a_base, a_field, (a_node), \
			trp_right_get(a_base, a_field, (r_node))); \
		trp_right_set(a_base, a_field, (r_node), (a_node)); \
	} while (0)

#define trp_gen(a_attr, a_pre, a_type, a_field, a_base, a_cmp) \
a_attr a_type MAYBE_UNUSED *a_pre##first(struct trp_root *treap) \
{ \
	uint32_t ret; \
	trpn_first(a_base, a_field, treap->trp_root, ret); \
	return trpn_pointer(a_base, ret); \
} \
a_attr a_type MAYBE_UNUSED *a_pre##next(struct trp_root *treap, a_type *node) \
{ \
	uint32_t ret; \
	uint32_t offset = trpn_offset(a_base, node); \
	if (~trp_right_get(a_base, a_field, offset)) { \
		trpn_first(a_base, a_field, \
			trp_right_get(a_base, a_field, offset), ret); \
	} else { \
		uint32_t tnode = treap->trp_root; \
		ret = ~0; \
		while (1) { \
			int cmp = (a_cmp)(trpn_pointer(a_base, offset), \
				trpn_pointer(a_base, tnode)); \
			if (cmp < 0) { \
				ret = tnode; \
				tnode = trp_left_get(a_base, a_field, tnode); \
			} else if (cmp > 0) { \
				tnode = trp_right_get(a_base, a_field, tnode); \
			} else { \
				break; \
			} \
		} \
	} \
	return trpn_pointer(a_base, ret); \
} \
a_attr a_type MAYBE_UNUSED *a_pre##search(struct trp_root *treap, a_type *key) \
{ \
	int cmp; \
	uint32_t ret = treap->trp_root; \
	while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \
		if (cmp < 0) { \
			ret = trp_left_get(a_base, a_field, ret); \
		} else { \
			ret = trp_right_get(a_base, a_field, ret); \
		} \
	} \
	return trpn_pointer(a_base, ret); \
} \
a_attr a_type MAYBE_UNUSED *a_pre##nsearch(struct trp_root *treap, a_type *key) \
{ \
	int cmp; \
	uint32_t ret = treap->trp_root; \
	while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \
		if (cmp < 0) { \
			if (!~trp_left_get(a_base, a_field, ret)) \
				break; \
			ret = trp_left_get(a_base, a_field, ret); \
		} else { \
			ret = trp_right_get(a_base, a_field, ret); \
		} \
	} \
	return trpn_pointer(a_base, ret); \
} \
a_attr uint32_t MAYBE_UNUSED a_pre##insert_recurse(uint32_t cur_node, uint32_t ins_node) \
{ \
	if (cur_node == ~0) { \
		return ins_node; \
	} else { \
		uint32_t ret; \
		int cmp = (a_cmp)(trpn_pointer(a_base, ins_node), \
					trpn_pointer(a_base, cur_node)); \
		if (cmp < 0) { \
			uint32_t left = a_pre##insert_recurse( \
				trp_left_get(a_base, a_field, cur_node), ins_node); \
			trp_left_set(a_base, a_field, cur_node, left); \
			if (trp_prio_get(left) < trp_prio_get(cur_node)) \
				trpn_rotate_right(a_base, a_field, cur_node, ret); \
			else \
				ret = cur_node; \
		} else { \
			uint32_t right = a_pre##insert_recurse( \
				trp_right_get(a_base, a_field, cur_node), ins_node); \
			trp_right_set(a_base, a_field, cur_node, right); \
			if (trp_prio_get(right) < trp_prio_get(cur_node)) \
				trpn_rotate_left(a_base, a_field, cur_node, ret); \
			else \
				ret = cur_node; \
		} \
		return ret; \
	} \
} \
a_attr a_type *MAYBE_UNUSED a_pre##insert(struct trp_root *treap, a_type *node) \
{ \
	uint32_t offset = trpn_offset(a_base, node); \
	trp_node_new(a_base, a_field, offset); \
	treap->trp_root = a_pre##insert_recurse(treap->trp_root, offset); \
	return trpn_pointer(a_base, offset); \
} \
a_attr uint32_t MAYBE_UNUSED a_pre##remove_recurse(uint32_t cur_node, uint32_t rem_node) \
{ \
	int cmp = a_cmp(trpn_pointer(a_base, rem_node), \
			trpn_pointer(a_base, cur_node)); \
	if (cmp == 0) { \
		uint32_t ret; \
		uint32_t left = trp_left_get(a_base, a_field, cur_node); \
		uint32_t right = trp_right_get(a_base, a_field, cur_node); \
		if (left == ~0) { \
			if (right == ~0) \
				return ~0; \
		} else if (right == ~0 || trp_prio_get(left) < trp_prio_get(right)) { \
			trpn_rotate_right(a_base, a_field, cur_node, ret); \
			right = a_pre##remove_recurse(cur_node, rem_node); \
			trp_right_set(a_base, a_field, ret, right); \
			return ret; \
		} \
		trpn_rotate_left(a_base, a_field, cur_node, ret); \
		left = a_pre##remove_recurse(cur_node, rem_node); \
		trp_left_set(a_base, a_field, ret, left); \
		return ret; \
	} else if (cmp < 0) { \
		uint32_t left = a_pre##remove_recurse( \
			trp_left_get(a_base, a_field, cur_node), rem_node); \
		trp_left_set(a_base, a_field, cur_node, left); \
		return cur_node; \
	} else { \
		uint32_t right = a_pre##remove_recurse( \
			trp_right_get(a_base, a_field, cur_node), rem_node); \
		trp_right_set(a_base, a_field, cur_node, right); \
		return cur_node; \
	} \
} \
a_attr void MAYBE_UNUSED a_pre##remove(struct trp_root *treap, a_type *node) \
{ \
	treap->trp_root = a_pre##remove_recurse(treap->trp_root, \
		trpn_offset(a_base, node)); \
} \

#endif
Commit	Line	Data
951f3164 JE	1	/*
	2	* C macro implementation of treaps.
	3	*
	4	* Usage:
	5	* #include <stdint.h>
	6	* #include "trp.h"
	7	* trp_gen(...)
	8	*
	9	* Licensed under a two-clause BSD-style license.
	10	* See LICENSE for details.
	11	*/
	12
	13	#ifndef TRP_H_
	14	#define TRP_H_
	15
	16	#define MAYBE_UNUSED __attribute__((__unused__))
	17
	18	/* Node structure. */
	19	struct trp_node {
	20	uint32_t trpn_left;
	21	uint32_t trpn_right;
	22	};
	23
	24	/* Root structure. */
	25	struct trp_root {
	26	uint32_t trp_root;
	27	};
	28
	29	/* Pointer/Offset conversion. */
	30	#define trpn_pointer(a_base, a_offset) (a_base##_pointer(a_offset))
	31	#define trpn_offset(a_base, a_pointer) (a_base##_offset(a_pointer))
	32	#define trpn_modify(a_base, a_offset) \
	33	do { \
	34	if ((a_offset) < a_base##_pool.committed) { \
	35	uint32_t old_offset = (a_offset);\
	36	(a_offset) = a_base##_alloc(1); \
	37	*trpn_pointer(a_base, a_offset) = \
	38	*trpn_pointer(a_base, old_offset); \
	39	} \
6ad263ce	40	} while (0)
951f3164 JE	41
	42	/* Left accessors. */
	43	#define trp_left_get(a_base, a_field, a_node) \
	44	(trpn_pointer(a_base, a_node)->a_field.trpn_left)
	45	#define trp_left_set(a_base, a_field, a_node, a_left) \
	46	do { \
	47	trpn_modify(a_base, a_node); \
	48	trp_left_get(a_base, a_field, a_node) = (a_left); \
6ad263ce	49	} while (0)
951f3164 JE	50
	51	/* Right accessors. */
	52	#define trp_right_get(a_base, a_field, a_node) \
	53	(trpn_pointer(a_base, a_node)->a_field.trpn_right)
	54	#define trp_right_set(a_base, a_field, a_node, a_right) \
	55	do { \
	56	trpn_modify(a_base, a_node); \
	57	trp_right_get(a_base, a_field, a_node) = (a_right); \
6ad263ce	58	} while (0)
951f3164 JE	59
	60	/*
	61	* Fibonacci hash function.
	62	* The multiplier is the nearest prime to (2^32 times (√5 - 1)/2).
	63	* See Knuth §6.4: volume 3, 3rd ed, p518.
	64	*/
	65	#define trpn_hash(a_node) (uint32_t) (2654435761u * (a_node))
	66
	67	/* Priority accessors. */
	68	#define trp_prio_get(a_node) trpn_hash(a_node)
	69
	70	/* Node initializer. */
	71	#define trp_node_new(a_base, a_field, a_node) \
	72	do { \
	73	trp_left_set(a_base, a_field, (a_node), ~0); \
	74	trp_right_set(a_base, a_field, (a_node), ~0); \
6ad263ce	75	} while (0)
951f3164 JE	76
	77	/* Internal utility macros. */
	78	#define trpn_first(a_base, a_field, a_root, r_node) \
	79	do { \
	80	(r_node) = (a_root); \
	81	if ((r_node) == ~0) \
	82	return NULL; \
	83	while (~trp_left_get(a_base, a_field, (r_node))) \
	84	(r_node) = trp_left_get(a_base, a_field, (r_node)); \
	85	} while (0)
	86
	87	#define trpn_rotate_left(a_base, a_field, a_node, r_node) \
	88	do { \
	89	(r_node) = trp_right_get(a_base, a_field, (a_node)); \
	90	trp_right_set(a_base, a_field, (a_node), \
	91	trp_left_get(a_base, a_field, (r_node))); \
	92	trp_left_set(a_base, a_field, (r_node), (a_node)); \
6ad263ce	93	} while (0)
951f3164 JE	94
	95	#define trpn_rotate_right(a_base, a_field, a_node, r_node) \
	96	do { \
	97	(r_node) = trp_left_get(a_base, a_field, (a_node)); \
	98	trp_left_set(a_base, a_field, (a_node), \
	99	trp_right_get(a_base, a_field, (r_node))); \
	100	trp_right_set(a_base, a_field, (r_node), (a_node)); \
6ad263ce	101	} while (0)
951f3164 JE	102
	103	#define trp_gen(a_attr, a_pre, a_type, a_field, a_base, a_cmp) \
	104	a_attr a_type MAYBE_UNUSED a_pre##first(struct trp_root treap) \
	105	{ \
	106	uint32_t ret; \
	107	trpn_first(a_base, a_field, treap->trp_root, ret); \
	108	return trpn_pointer(a_base, ret); \
	109	} \
	110	a_attr a_type MAYBE_UNUSED a_pre##next(struct trp_root treap, a_type *node) \
	111	{ \
	112	uint32_t ret; \
	113	uint32_t offset = trpn_offset(a_base, node); \
	114	if (~trp_right_get(a_base, a_field, offset)) { \
	115	trpn_first(a_base, a_field, \
	116	trp_right_get(a_base, a_field, offset), ret); \
	117	} else { \
	118	uint32_t tnode = treap->trp_root; \
	119	ret = ~0; \
	120	while (1) { \
	121	int cmp = (a_cmp)(trpn_pointer(a_base, offset), \
	122	trpn_pointer(a_base, tnode)); \
	123	if (cmp < 0) { \
	124	ret = tnode; \
	125	tnode = trp_left_get(a_base, a_field, tnode); \
	126	} else if (cmp > 0) { \
	127	tnode = trp_right_get(a_base, a_field, tnode); \
	128	} else { \
	129	break; \
	130	} \
	131	} \
	132	} \
	133	return trpn_pointer(a_base, ret); \
	134	} \
	135	a_attr a_type MAYBE_UNUSED a_pre##search(struct trp_root treap, a_type *key) \
	136	{ \
	137	int cmp; \
	138	uint32_t ret = treap->trp_root; \
6ad263ce	139	while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \
951f3164 JE	140	if (cmp < 0) { \
	141	ret = trp_left_get(a_base, a_field, ret); \
	142	} else { \
	143	ret = trp_right_get(a_base, a_field, ret); \
	144	} \
	145	} \
	146	return trpn_pointer(a_base, ret); \
	147	} \
	148	a_attr a_type MAYBE_UNUSED a_pre##nsearch(struct trp_root treap, a_type *key) \
	149	{ \
	150	int cmp; \
	151	uint32_t ret = treap->trp_root; \
6ad263ce	152	while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \
951f3164 JE	153	if (cmp < 0) { \
	154	if (!~trp_left_get(a_base, a_field, ret)) \
	155	break; \
	156	ret = trp_left_get(a_base, a_field, ret); \
	157	} else { \
	158	ret = trp_right_get(a_base, a_field, ret); \
	159	} \
	160	} \
	161	return trpn_pointer(a_base, ret); \
	162	} \
	163	a_attr uint32_t MAYBE_UNUSED a_pre##insert_recurse(uint32_t cur_node, uint32_t ins_node) \
	164	{ \
	165	if (cur_node == ~0) { \
6ad263ce	166	return ins_node; \
951f3164 JE	167	} else { \
	168	uint32_t ret; \
	169	int cmp = (a_cmp)(trpn_pointer(a_base, ins_node), \
	170	trpn_pointer(a_base, cur_node)); \
	171	if (cmp < 0) { \
	172	uint32_t left = a_pre##insert_recurse( \
	173	trp_left_get(a_base, a_field, cur_node), ins_node); \
	174	trp_left_set(a_base, a_field, cur_node, left); \
	175	if (trp_prio_get(left) < trp_prio_get(cur_node)) \
	176	trpn_rotate_right(a_base, a_field, cur_node, ret); \
	177	else \
	178	ret = cur_node; \
	179	} else { \
	180	uint32_t right = a_pre##insert_recurse( \
	181	trp_right_get(a_base, a_field, cur_node), ins_node); \
	182	trp_right_set(a_base, a_field, cur_node, right); \
	183	if (trp_prio_get(right) < trp_prio_get(cur_node)) \
	184	trpn_rotate_left(a_base, a_field, cur_node, ret); \
	185	else \
	186	ret = cur_node; \
	187	} \
6ad263ce	188	return ret; \
951f3164 JE	189	} \
951f3164 JE	190	} \
97a5e345	191	a_attr a_type MAYBE_UNUSED a_pre##insert(struct trp_root treap, a_type *node) \
951f3164 JE	192	{ \
	193	uint32_t offset = trpn_offset(a_base, node); \
	194	trp_node_new(a_base, a_field, offset); \
	195	treap->trp_root = a_pre##insert_recurse(treap->trp_root, offset); \
97a5e345	196	return trpn_pointer(a_base, offset); \
951f3164 JE	197	} \
	198	a_attr uint32_t MAYBE_UNUSED a_pre##remove_recurse(uint32_t cur_node, uint32_t rem_node) \
	199	{ \
	200	int cmp = a_cmp(trpn_pointer(a_base, rem_node), \
	201	trpn_pointer(a_base, cur_node)); \
	202	if (cmp == 0) { \
	203	uint32_t ret; \
	204	uint32_t left = trp_left_get(a_base, a_field, cur_node); \
	205	uint32_t right = trp_right_get(a_base, a_field, cur_node); \
	206	if (left == ~0) { \
	207	if (right == ~0) \
6ad263ce	208	return ~0; \
951f3164 JE	209	} else if (right == ~0 \|\| trp_prio_get(left) < trp_prio_get(right)) { \
	210	trpn_rotate_right(a_base, a_field, cur_node, ret); \
	211	right = a_pre##remove_recurse(cur_node, rem_node); \
	212	trp_right_set(a_base, a_field, ret, right); \
6ad263ce	213	return ret; \
951f3164 JE	214	} \
	215	trpn_rotate_left(a_base, a_field, cur_node, ret); \
	216	left = a_pre##remove_recurse(cur_node, rem_node); \
	217	trp_left_set(a_base, a_field, ret, left); \
6ad263ce	218	return ret; \
951f3164 JE	219	} else if (cmp < 0) { \
	220	uint32_t left = a_pre##remove_recurse( \
	221	trp_left_get(a_base, a_field, cur_node), rem_node); \
	222	trp_left_set(a_base, a_field, cur_node, left); \
6ad263ce	223	return cur_node; \
951f3164 JE	224	} else { \
	225	uint32_t right = a_pre##remove_recurse( \
	226	trp_right_get(a_base, a_field, cur_node), rem_node); \
	227	trp_right_set(a_base, a_field, cur_node, right); \
6ad263ce	228	return cur_node; \
951f3164 JE	229	} \
	230	} \
	231	a_attr void MAYBE_UNUSED a_pre##remove(struct trp_root treap, a_type node) \
	232	{ \
	233	treap->trp_root = a_pre##remove_recurse(treap->trp_root, \
	234	trpn_offset(a_base, node)); \
	235	} \
	236
	237	#endif