Blame jemalloc/include/jemalloc/internal/ph.h

Packit 345191
/*
Packit 345191
 * A Pairing Heap implementation.
Packit 345191
 *
Packit 345191
 * "The Pairing Heap: A New Form of Self-Adjusting Heap"
Packit 345191
 * https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf
Packit 345191
 *
Packit 345191
 * With auxiliary twopass list, described in a follow on paper.
Packit 345191
 *
Packit 345191
 * "Pairing Heaps: Experiments and Analysis"
Packit 345191
 * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.2988&rep=rep1&type=pdf
Packit 345191
 *
Packit 345191
 *******************************************************************************
Packit 345191
 */
Packit 345191
Packit 345191
#ifndef PH_H_
Packit 345191
#define PH_H_
Packit 345191
Packit 345191
/* Node structure. */
Packit 345191
#define phn(a_type)							\
Packit 345191
struct {								\
Packit 345191
	a_type	*phn_prev;						\
Packit 345191
	a_type	*phn_next;						\
Packit 345191
	a_type	*phn_lchild;						\
Packit 345191
}
Packit 345191
Packit 345191
/* Root structure. */
Packit 345191
#define ph(a_type)							\
Packit 345191
struct {								\
Packit 345191
	a_type	*ph_root;						\
Packit 345191
}
Packit 345191
Packit 345191
/* Internal utility macros. */
Packit 345191
#define phn_lchild_get(a_type, a_field, a_phn)				\
Packit 345191
	(a_phn->a_field.phn_lchild)
Packit 345191
#define phn_lchild_set(a_type, a_field, a_phn, a_lchild) do {		\
Packit 345191
	a_phn->a_field.phn_lchild = a_lchild;				\
Packit 345191
} while (0)
Packit 345191
Packit 345191
#define phn_next_get(a_type, a_field, a_phn)				\
Packit 345191
	(a_phn->a_field.phn_next)
Packit 345191
#define phn_prev_set(a_type, a_field, a_phn, a_prev) do {		\
Packit 345191
	a_phn->a_field.phn_prev = a_prev;				\
Packit 345191
} while (0)
Packit 345191
Packit 345191
#define phn_prev_get(a_type, a_field, a_phn)				\
Packit 345191
	(a_phn->a_field.phn_prev)
Packit 345191
#define phn_next_set(a_type, a_field, a_phn, a_next) do {		\
Packit 345191
	a_phn->a_field.phn_next = a_next;				\
Packit 345191
} while (0)
Packit 345191
Packit 345191
#define phn_merge_ordered(a_type, a_field, a_phn0, a_phn1, a_cmp) do {	\
Packit 345191
	a_type *phn0child;						\
Packit 345191
									\
Packit 345191
	assert(a_phn0 != NULL);						\
Packit 345191
	assert(a_phn1 != NULL);						\
Packit 345191
	assert(a_cmp(a_phn0, a_phn1) <= 0);				\
Packit 345191
									\
Packit 345191
	phn_prev_set(a_type, a_field, a_phn1, a_phn0);			\
Packit 345191
	phn0child = phn_lchild_get(a_type, a_field, a_phn0);		\
Packit 345191
	phn_next_set(a_type, a_field, a_phn1, phn0child);		\
Packit 345191
	if (phn0child != NULL) {					\
Packit 345191
		phn_prev_set(a_type, a_field, phn0child, a_phn1);	\
Packit 345191
	}								\
Packit 345191
	phn_lchild_set(a_type, a_field, a_phn0, a_phn1);		\
Packit 345191
} while (0)
Packit 345191
Packit 345191
#define phn_merge(a_type, a_field, a_phn0, a_phn1, a_cmp, r_phn) do {	\
Packit 345191
	if (a_phn0 == NULL) {						\
Packit 345191
		r_phn = a_phn1;						\
Packit 345191
	} else if (a_phn1 == NULL) {					\
Packit 345191
		r_phn = a_phn0;						\
Packit 345191
	} else if (a_cmp(a_phn0, a_phn1) < 0) {				\
Packit 345191
		phn_merge_ordered(a_type, a_field, a_phn0, a_phn1,	\
Packit 345191
		    a_cmp);						\
Packit 345191
		r_phn = a_phn0;						\
Packit 345191
	} else {							\
Packit 345191
		phn_merge_ordered(a_type, a_field, a_phn1, a_phn0,	\
Packit 345191
		    a_cmp);						\
Packit 345191
		r_phn = a_phn1;						\
Packit 345191
	}								\
Packit 345191
} while (0)
Packit 345191
Packit 345191
#define ph_merge_siblings(a_type, a_field, a_phn, a_cmp, r_phn) do {	\
Packit 345191
	a_type *head = NULL;						\
Packit 345191
	a_type *tail = NULL;						\
Packit 345191
	a_type *phn0 = a_phn;						\
Packit 345191
	a_type *phn1 = phn_next_get(a_type, a_field, phn0);		\
Packit 345191
									\
Packit 345191
	/*								\
Packit 345191
	 * Multipass merge, wherein the first two elements of a FIFO	\
Packit 345191
	 * are repeatedly merged, and each result is appended to the	\
Packit 345191
	 * singly linked FIFO, until the FIFO contains only a single	\
Packit 345191
	 * element.  We start with a sibling list but no reference to	\
Packit 345191
	 * its tail, so we do a single pass over the sibling list to	\
Packit 345191
	 * populate the FIFO.						\
Packit 345191
	 */								\
Packit 345191
	if (phn1 != NULL) {						\
Packit 345191
		a_type *phnrest = phn_next_get(a_type, a_field, phn1);	\
Packit 345191
		if (phnrest != NULL) {					\
Packit 345191
			phn_prev_set(a_type, a_field, phnrest, NULL);	\
Packit 345191
		}							\
Packit 345191
		phn_prev_set(a_type, a_field, phn0, NULL);		\
Packit 345191
		phn_next_set(a_type, a_field, phn0, NULL);		\
Packit 345191
		phn_prev_set(a_type, a_field, phn1, NULL);		\
Packit 345191
		phn_next_set(a_type, a_field, phn1, NULL);		\
Packit 345191
		phn_merge(a_type, a_field, phn0, phn1, a_cmp, phn0);	\
Packit 345191
		head = tail = phn0;					\
Packit 345191
		phn0 = phnrest;						\
Packit 345191
		while (phn0 != NULL) {					\
Packit 345191
			phn1 = phn_next_get(a_type, a_field, phn0);	\
Packit 345191
			if (phn1 != NULL) {				\
Packit 345191
				phnrest = phn_next_get(a_type, a_field,	\
Packit 345191
				    phn1);				\
Packit 345191
				if (phnrest != NULL) {			\
Packit 345191
					phn_prev_set(a_type, a_field,	\
Packit 345191
					    phnrest, NULL);		\
Packit 345191
				}					\
Packit 345191
				phn_prev_set(a_type, a_field, phn0,	\
Packit 345191
				    NULL);				\
Packit 345191
				phn_next_set(a_type, a_field, phn0,	\
Packit 345191
				    NULL);				\
Packit 345191
				phn_prev_set(a_type, a_field, phn1,	\
Packit 345191
				    NULL);				\
Packit 345191
				phn_next_set(a_type, a_field, phn1,	\
Packit 345191
				    NULL);				\
Packit 345191
				phn_merge(a_type, a_field, phn0, phn1,	\
Packit 345191
				    a_cmp, phn0);			\
Packit 345191
				phn_next_set(a_type, a_field, tail,	\
Packit 345191
				    phn0);				\
Packit 345191
				tail = phn0;				\
Packit 345191
				phn0 = phnrest;				\
Packit 345191
			} else {					\
Packit 345191
				phn_next_set(a_type, a_field, tail,	\
Packit 345191
				    phn0);				\
Packit 345191
				tail = phn0;				\
Packit 345191
				phn0 = NULL;				\
Packit 345191
			}						\
Packit 345191
		}							\
Packit 345191
		phn0 = head;						\
Packit 345191
		phn1 = phn_next_get(a_type, a_field, phn0);		\
Packit 345191
		if (phn1 != NULL) {					\
Packit 345191
			while (true) {					\
Packit 345191
				head = phn_next_get(a_type, a_field,	\
Packit 345191
				    phn1);				\
Packit 345191
				assert(phn_prev_get(a_type, a_field,	\
Packit 345191
				    phn0) == NULL);			\
Packit 345191
				phn_next_set(a_type, a_field, phn0,	\
Packit 345191
				    NULL);				\
Packit 345191
				assert(phn_prev_get(a_type, a_field,	\
Packit 345191
				    phn1) == NULL);			\
Packit 345191
				phn_next_set(a_type, a_field, phn1,	\
Packit 345191
				    NULL);				\
Packit 345191
				phn_merge(a_type, a_field, phn0, phn1,	\
Packit 345191
				    a_cmp, phn0);			\
Packit 345191
				if (head == NULL) {			\
Packit 345191
					break;				\
Packit 345191
				}					\
Packit 345191
				phn_next_set(a_type, a_field, tail,	\
Packit 345191
				    phn0);				\
Packit 345191
				tail = phn0;				\
Packit 345191
				phn0 = head;				\
Packit 345191
				phn1 = phn_next_get(a_type, a_field,	\
Packit 345191
				    phn0);				\
Packit 345191
			}						\
Packit 345191
		}							\
Packit 345191
	}								\
Packit 345191
	r_phn = phn0;							\
Packit 345191
} while (0)
Packit 345191
Packit 345191
#define ph_merge_aux(a_type, a_field, a_ph, a_cmp) do {			\
Packit 345191
	a_type *phn = phn_next_get(a_type, a_field, a_ph->ph_root);	\
Packit 345191
	if (phn != NULL) {						\
Packit 345191
		phn_prev_set(a_type, a_field, a_ph->ph_root, NULL);	\
Packit 345191
		phn_next_set(a_type, a_field, a_ph->ph_root, NULL);	\
Packit 345191
		phn_prev_set(a_type, a_field, phn, NULL);		\
Packit 345191
		ph_merge_siblings(a_type, a_field, phn, a_cmp, phn);	\
Packit 345191
		assert(phn_next_get(a_type, a_field, phn) == NULL);	\
Packit 345191
		phn_merge(a_type, a_field, a_ph->ph_root, phn, a_cmp,	\
Packit 345191
		    a_ph->ph_root);					\
Packit 345191
	}								\
Packit 345191
} while (0)
Packit 345191
Packit 345191
#define ph_merge_children(a_type, a_field, a_phn, a_cmp, r_phn) do {	\
Packit 345191
	a_type *lchild = phn_lchild_get(a_type, a_field, a_phn);	\
Packit 345191
	if (lchild == NULL) {						\
Packit 345191
		r_phn = NULL;						\
Packit 345191
	} else {							\
Packit 345191
		ph_merge_siblings(a_type, a_field, lchild, a_cmp,	\
Packit 345191
		    r_phn);						\
Packit 345191
	}								\
Packit 345191
} while (0)
Packit 345191
Packit 345191
/*
Packit 345191
 * The ph_proto() macro generates function prototypes that correspond to the
Packit 345191
 * functions generated by an equivalently parameterized call to ph_gen().
Packit 345191
 */
Packit 345191
#define ph_proto(a_attr, a_prefix, a_ph_type, a_type)			\
Packit 345191
a_attr void	a_prefix##new(a_ph_type *ph);				\
Packit 345191
a_attr bool	a_prefix##empty(a_ph_type *ph);				\
Packit 345191
a_attr a_type	*a_prefix##first(a_ph_type *ph);			\
Packit 345191
a_attr a_type	*a_prefix##any(a_ph_type *ph);				\
Packit 345191
a_attr void	a_prefix##insert(a_ph_type *ph, a_type *phn);		\
Packit 345191
a_attr a_type	*a_prefix##remove_first(a_ph_type *ph);			\
Packit 345191
a_attr a_type	*a_prefix##remove_any(a_ph_type *ph);			\
Packit 345191
a_attr void	a_prefix##remove(a_ph_type *ph, a_type *phn);
Packit 345191
Packit 345191
/*
Packit 345191
 * The ph_gen() macro generates a type-specific pairing heap implementation,
Packit 345191
 * based on the above cpp macros.
Packit 345191
 */
Packit 345191
#define ph_gen(a_attr, a_prefix, a_ph_type, a_type, a_field, a_cmp)	\
Packit 345191
a_attr void								\
Packit 345191
a_prefix##new(a_ph_type *ph) {						\
Packit 345191
	memset(ph, 0, sizeof(ph(a_type)));				\
Packit 345191
}									\
Packit 345191
a_attr bool								\
Packit 345191
a_prefix##empty(a_ph_type *ph) {					\
Packit 345191
	return (ph->ph_root == NULL);					\
Packit 345191
}									\
Packit 345191
a_attr a_type *								\
Packit 345191
a_prefix##first(a_ph_type *ph) {					\
Packit 345191
	if (ph->ph_root == NULL) {					\
Packit 345191
		return NULL;						\
Packit 345191
	}								\
Packit 345191
	ph_merge_aux(a_type, a_field, ph, a_cmp);			\
Packit 345191
	return ph->ph_root;						\
Packit 345191
}									\
Packit 345191
a_attr a_type *								\
Packit 345191
a_prefix##any(a_ph_type *ph) {						\
Packit 345191
	if (ph->ph_root == NULL) {					\
Packit 345191
		return NULL;						\
Packit 345191
	}								\
Packit 345191
	a_type *aux = phn_next_get(a_type, a_field, ph->ph_root);	\
Packit 345191
	if (aux != NULL) {						\
Packit 345191
		return aux;						\
Packit 345191
	}								\
Packit 345191
	return ph->ph_root;						\
Packit 345191
}									\
Packit 345191
a_attr void								\
Packit 345191
a_prefix##insert(a_ph_type *ph, a_type *phn) {				\
Packit 345191
	memset(&phn->a_field, 0, sizeof(phn(a_type)));			\
Packit 345191
									\
Packit 345191
	/*								\
Packit 345191
	 * Treat the root as an aux list during insertion, and lazily	\
Packit 345191
	 * merge during a_prefix##remove_first().  For elements that	\
Packit 345191
	 * are inserted, then removed via a_prefix##remove() before the	\
Packit 345191
	 * aux list is ever processed, this makes insert/remove		\
Packit 345191
	 * constant-time, whereas eager merging would make insert	\
Packit 345191
	 * O(log n).							\
Packit 345191
	 */								\
Packit 345191
	if (ph->ph_root == NULL) {					\
Packit 345191
		ph->ph_root = phn;					\
Packit 345191
	} else {							\
Packit 345191
		phn_next_set(a_type, a_field, phn, phn_next_get(a_type,	\
Packit 345191
		    a_field, ph->ph_root));				\
Packit 345191
		if (phn_next_get(a_type, a_field, ph->ph_root) !=	\
Packit 345191
		    NULL) {						\
Packit 345191
			phn_prev_set(a_type, a_field,			\
Packit 345191
			    phn_next_get(a_type, a_field, ph->ph_root),	\
Packit 345191
			    phn);					\
Packit 345191
		}							\
Packit 345191
		phn_prev_set(a_type, a_field, phn, ph->ph_root);	\
Packit 345191
		phn_next_set(a_type, a_field, ph->ph_root, phn);	\
Packit 345191
	}								\
Packit 345191
}									\
Packit 345191
a_attr a_type *								\
Packit 345191
a_prefix##remove_first(a_ph_type *ph) {					\
Packit 345191
	a_type *ret;							\
Packit 345191
									\
Packit 345191
	if (ph->ph_root == NULL) {					\
Packit 345191
		return NULL;						\
Packit 345191
	}								\
Packit 345191
	ph_merge_aux(a_type, a_field, ph, a_cmp);			\
Packit 345191
									\
Packit 345191
	ret = ph->ph_root;						\
Packit 345191
									\
Packit 345191
	ph_merge_children(a_type, a_field, ph->ph_root, a_cmp,		\
Packit 345191
	    ph->ph_root);						\
Packit 345191
									\
Packit 345191
	return ret;							\
Packit 345191
}									\
Packit 345191
a_attr a_type *								\
Packit 345191
a_prefix##remove_any(a_ph_type *ph) {					\
Packit 345191
	/*								\
Packit 345191
	 * Remove the most recently inserted aux list element, or the	\
Packit 345191
	 * root if the aux list is empty.  This has the effect of	\
Packit 345191
	 * behaving as a LIFO (and insertion/removal is therefore	\
Packit 345191
	 * constant-time) if a_prefix##[remove_]first() are never	\
Packit 345191
	 * called.							\
Packit 345191
	 */								\
Packit 345191
	if (ph->ph_root == NULL) {					\
Packit 345191
		return NULL;						\
Packit 345191
	}								\
Packit 345191
	a_type *ret = phn_next_get(a_type, a_field, ph->ph_root);	\
Packit 345191
	if (ret != NULL) {						\
Packit 345191
		a_type *aux = phn_next_get(a_type, a_field, ret);	\
Packit 345191
		phn_next_set(a_type, a_field, ph->ph_root, aux);	\
Packit 345191
		if (aux != NULL) {					\
Packit 345191
			phn_prev_set(a_type, a_field, aux,		\
Packit 345191
			    ph->ph_root);				\
Packit 345191
		}							\
Packit 345191
		return ret;						\
Packit 345191
	}								\
Packit 345191
	ret = ph->ph_root;						\
Packit 345191
	ph_merge_children(a_type, a_field, ph->ph_root, a_cmp,		\
Packit 345191
	    ph->ph_root);						\
Packit 345191
	return ret;							\
Packit 345191
}									\
Packit 345191
a_attr void								\
Packit 345191
a_prefix##remove(a_ph_type *ph, a_type *phn) {				\
Packit 345191
	a_type *replace, *parent;					\
Packit 345191
									\
Packit 345191
	if (ph->ph_root == phn) {					\
Packit 345191
		/*							\
Packit 345191
		 * We can delete from aux list without merging it, but	\
Packit 345191
		 * we need to merge if we are dealing with the root	\
Packit 345191
		 * node and it has children.				\
Packit 345191
		 */							\
Packit 345191
		if (phn_lchild_get(a_type, a_field, phn) == NULL) {	\
Packit 345191
			ph->ph_root = phn_next_get(a_type, a_field,	\
Packit 345191
			    phn);					\
Packit 345191
			if (ph->ph_root != NULL) {			\
Packit 345191
				phn_prev_set(a_type, a_field,		\
Packit 345191
				    ph->ph_root, NULL);			\
Packit 345191
			}						\
Packit 345191
			return;						\
Packit 345191
		}							\
Packit 345191
		ph_merge_aux(a_type, a_field, ph, a_cmp);		\
Packit 345191
		if (ph->ph_root == phn) {				\
Packit 345191
			ph_merge_children(a_type, a_field, ph->ph_root,	\
Packit 345191
			    a_cmp, ph->ph_root);			\
Packit 345191
			return;						\
Packit 345191
		}							\
Packit 345191
	}								\
Packit 345191
									\
Packit 345191
	/* Get parent (if phn is leftmost child) before mutating. */	\
Packit 345191
	if ((parent = phn_prev_get(a_type, a_field, phn)) != NULL) {	\
Packit 345191
		if (phn_lchild_get(a_type, a_field, parent) != phn) {	\
Packit 345191
			parent = NULL;					\
Packit 345191
		}							\
Packit 345191
	}								\
Packit 345191
	/* Find a possible replacement node, and link to parent. */	\
Packit 345191
	ph_merge_children(a_type, a_field, phn, a_cmp, replace);	\
Packit 345191
	/* Set next/prev for sibling linked list. */			\
Packit 345191
	if (replace != NULL) {						\
Packit 345191
		if (parent != NULL) {					\
Packit 345191
			phn_prev_set(a_type, a_field, replace, parent);	\
Packit 345191
			phn_lchild_set(a_type, a_field, parent,		\
Packit 345191
			    replace);					\
Packit 345191
		} else {						\
Packit 345191
			phn_prev_set(a_type, a_field, replace,		\
Packit 345191
			    phn_prev_get(a_type, a_field, phn));	\
Packit 345191
			if (phn_prev_get(a_type, a_field, phn) !=	\
Packit 345191
			    NULL) {					\
Packit 345191
				phn_next_set(a_type, a_field,		\
Packit 345191
				    phn_prev_get(a_type, a_field, phn),	\
Packit 345191
				    replace);				\
Packit 345191
			}						\
Packit 345191
		}							\
Packit 345191
		phn_next_set(a_type, a_field, replace,			\
Packit 345191
		    phn_next_get(a_type, a_field, phn));		\
Packit 345191
		if (phn_next_get(a_type, a_field, phn) != NULL) {	\
Packit 345191
			phn_prev_set(a_type, a_field,			\
Packit 345191
			    phn_next_get(a_type, a_field, phn),		\
Packit 345191
			    replace);					\
Packit 345191
		}							\
Packit 345191
	} else {							\
Packit 345191
		if (parent != NULL) {					\
Packit 345191
			a_type *next = phn_next_get(a_type, a_field,	\
Packit 345191
			    phn);					\
Packit 345191
			phn_lchild_set(a_type, a_field, parent, next);	\
Packit 345191
			if (next != NULL) {				\
Packit 345191
				phn_prev_set(a_type, a_field, next,	\
Packit 345191
				    parent);				\
Packit 345191
			}						\
Packit 345191
		} else {						\
Packit 345191
			assert(phn_prev_get(a_type, a_field, phn) !=	\
Packit 345191
			    NULL);					\
Packit 345191
			phn_next_set(a_type, a_field,			\
Packit 345191
			    phn_prev_get(a_type, a_field, phn),		\
Packit 345191
			    phn_next_get(a_type, a_field, phn));	\
Packit 345191
		}							\
Packit 345191
		if (phn_next_get(a_type, a_field, phn) != NULL) {	\
Packit 345191
			phn_prev_set(a_type, a_field,			\
Packit 345191
			    phn_next_get(a_type, a_field, phn),		\
Packit 345191
			    phn_prev_get(a_type, a_field, phn));	\
Packit 345191
		}							\
Packit 345191
	}								\
Packit 345191
}
Packit 345191
Packit 345191
#endif /* PH_H_ */