xref: /netbsd-src/external/bsd/jemalloc.old/include/jemalloc/internal/ph.h (revision 8e33eff89e26cf71871ead62f0d5063e1313c33a)

/*
 * A Pairing Heap implementation.
 *
 * "The Pairing Heap: A New Form of Self-Adjusting Heap"
 * https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf
 *
 * With auxiliary twopass list, described in a follow on paper.
 *
 * "Pairing Heaps: Experiments and Analysis"
 * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.2988&rep=rep1&type=pdf
 *
 *******************************************************************************
 */

#ifndef PH_H_
#define PH_H_

/* Node structure. */
#define phn(a_type)							\
struct {								\
	a_type	*phn_prev;						\
	a_type	*phn_next;						\
	a_type	*phn_lchild;						\
}

/* Root structure. */
#define ph(a_type)							\
struct {								\
	a_type	*ph_root;						\
}

/* Internal utility macros. */
#define phn_lchild_get(a_type, a_field, a_phn)				\
	(a_phn->a_field.phn_lchild)
#define phn_lchild_set(a_type, a_field, a_phn, a_lchild) do {		\
	a_phn->a_field.phn_lchild = a_lchild;				\
} while (0)

#define phn_next_get(a_type, a_field, a_phn)				\
	(a_phn->a_field.phn_next)
#define phn_prev_set(a_type, a_field, a_phn, a_prev) do {		\
	a_phn->a_field.phn_prev = a_prev;				\
} while (0)

#define phn_prev_get(a_type, a_field, a_phn)				\
	(a_phn->a_field.phn_prev)
#define phn_next_set(a_type, a_field, a_phn, a_next) do {		\
	a_phn->a_field.phn_next = a_next;				\
} while (0)

#define phn_merge_ordered(a_type, a_field, a_phn0, a_phn1, a_cmp) do {	\
	a_type *phn0child;						\
									\
	assert(a_phn0 != NULL);						\
	assert(a_phn1 != NULL);						\
	assert(a_cmp(a_phn0, a_phn1) <= 0);				\
									\
	phn_prev_set(a_type, a_field, a_phn1, a_phn0);			\
	phn0child = phn_lchild_get(a_type, a_field, a_phn0);		\
	phn_next_set(a_type, a_field, a_phn1, phn0child);		\
	if (phn0child != NULL) {					\
		phn_prev_set(a_type, a_field, phn0child, a_phn1);	\
	}								\
	phn_lchild_set(a_type, a_field, a_phn0, a_phn1);		\
} while (0)

#define phn_merge(a_type, a_field, a_phn0, a_phn1, a_cmp, r_phn) do {	\
	if (a_phn0 == NULL) {						\
		r_phn = a_phn1;						\
	} else if (a_phn1 == NULL) {					\
		r_phn = a_phn0;						\
	} else if (a_cmp(a_phn0, a_phn1) < 0) {				\
		phn_merge_ordered(a_type, a_field, a_phn0, a_phn1,	\
		    a_cmp);						\
		r_phn = a_phn0;						\
	} else {							\
		phn_merge_ordered(a_type, a_field, a_phn1, a_phn0,	\
		    a_cmp);						\
		r_phn = a_phn1;						\
	}								\
} while (0)

#define ph_merge_siblings(a_type, a_field, a_phn, a_cmp, r_phn) do {	\
	a_type *head = NULL;						\
	a_type *tail = NULL;						\
	a_type *phn0 = a_phn;						\
	a_type *phn1 = phn_next_get(a_type, a_field, phn0);		\
									\
	/*								\
	 * Multipass merge, wherein the first two elements of a FIFO	\
	 * are repeatedly merged, and each result is appended to the	\
	 * singly linked FIFO, until the FIFO contains only a single	\
	 * element.  We start with a sibling list but no reference to	\
	 * its tail, so we do a single pass over the sibling list to	\
	 * populate the FIFO.						\
	 */								\
	if (phn1 != NULL) {						\
		a_type *phnrest = phn_next_get(a_type, a_field, phn1);	\
		if (phnrest != NULL) {					\
			phn_prev_set(a_type, a_field, phnrest, NULL);	\
		}							\
		phn_prev_set(a_type, a_field, phn0, NULL);		\
		phn_next_set(a_type, a_field, phn0, NULL);		\
		phn_prev_set(a_type, a_field, phn1, NULL);		\
		phn_next_set(a_type, a_field, phn1, NULL);		\
		phn_merge(a_type, a_field, phn0, phn1, a_cmp, phn0);	\
		head = tail = phn0;					\
		phn0 = phnrest;						\
		while (phn0 != NULL) {					\
			phn1 = phn_next_get(a_type, a_field, phn0);	\
			if (phn1 != NULL) {				\
				phnrest = phn_next_get(a_type, a_field,	\
				    phn1);				\
				if (phnrest != NULL) {			\
					phn_prev_set(a_type, a_field,	\
					    phnrest, NULL);		\
				}					\
				phn_prev_set(a_type, a_field, phn0,	\
				    NULL);				\
				phn_next_set(a_type, a_field, phn0,	\
				    NULL);				\
				phn_prev_set(a_type, a_field, phn1,	\
				    NULL);				\
				phn_next_set(a_type, a_field, phn1,	\
				    NULL);				\
				phn_merge(a_type, a_field, phn0, phn1,	\
				    a_cmp, phn0);			\
				phn_next_set(a_type, a_field, tail,	\
				    phn0);				\
				tail = phn0;				\
				phn0 = phnrest;				\
			} else {					\
				phn_next_set(a_type, a_field, tail,	\
				    phn0);				\
				tail = phn0;				\
				phn0 = NULL;				\
			}						\
		}							\
		phn0 = head;						\
		phn1 = phn_next_get(a_type, a_field, phn0);		\
		if (phn1 != NULL) {					\
			while (true) {					\
				head = phn_next_get(a_type, a_field,	\
				    phn1);				\
				assert(phn_prev_get(a_type, a_field,	\
				    phn0) == NULL);			\
				phn_next_set(a_type, a_field, phn0,	\
				    NULL);				\
				assert(phn_prev_get(a_type, a_field,	\
				    phn1) == NULL);			\
				phn_next_set(a_type, a_field, phn1,	\
				    NULL);				\
				phn_merge(a_type, a_field, phn0, phn1,	\
				    a_cmp, phn0);			\
				if (head == NULL) {			\
					break;				\
				}					\
				phn_next_set(a_type, a_field, tail,	\
				    phn0);				\
				tail = phn0;				\
				phn0 = head;				\
				phn1 = phn_next_get(a_type, a_field,	\
				    phn0);				\
			}						\
		}							\
	}								\
	r_phn = phn0;							\
} while (0)

#define ph_merge_aux(a_type, a_field, a_ph, a_cmp) do {			\
	a_type *_phn = phn_next_get(a_type, a_field, a_ph->ph_root);	\
	if (_phn != NULL) {						\
		phn_prev_set(a_type, a_field, a_ph->ph_root, NULL);	\
		phn_next_set(a_type, a_field, a_ph->ph_root, NULL);	\
		phn_prev_set(a_type, a_field, _phn, NULL);		\
		ph_merge_siblings(a_type, a_field, _phn, a_cmp, _phn);	\
		assert(phn_next_get(a_type, a_field, _phn) == NULL);	\
		phn_merge(a_type, a_field, a_ph->ph_root, _phn, a_cmp,	\
		    a_ph->ph_root);					\
	}								\
} while (0)

#define ph_merge_children(a_type, a_field, a_phn, a_cmp, r_phn) do {	\
	a_type *lchild = phn_lchild_get(a_type, a_field, a_phn);	\
	if (lchild == NULL) {						\
		r_phn = NULL;						\
	} else {							\
		ph_merge_siblings(a_type, a_field, lchild, a_cmp,	\
		    r_phn);						\
	}								\
} while (0)

/*
 * The ph_proto() macro generates function prototypes that correspond to the
 * functions generated by an equivalently parameterized call to ph_gen().
 */
#define ph_proto(a_attr, a_prefix, a_ph_type, a_type)			\
a_attr void	a_prefix##new(a_ph_type *ph);				\
a_attr bool	a_prefix##empty(a_ph_type *ph);				\
a_attr a_type	*a_prefix##first(a_ph_type *ph);			\
a_attr a_type	*a_prefix##any(a_ph_type *ph);				\
a_attr void	a_prefix##insert(a_ph_type *ph, a_type *phn);		\
a_attr a_type	*a_prefix##remove_first(a_ph_type *ph);			\
a_attr a_type	*a_prefix##remove_any(a_ph_type *ph);			\
a_attr void	a_prefix##remove(a_ph_type *ph, a_type *phn);

/*
 * The ph_gen() macro generates a type-specific pairing heap implementation,
 * based on the above cpp macros.
 */
#define ph_gen(a_attr, a_prefix, a_ph_type, a_type, a_field, a_cmp)	\
a_attr void								\
a_prefix##new(a_ph_type *ph) {						\
	memset(ph, 0, sizeof(ph(a_type)));				\
}									\
a_attr bool								\
a_prefix##empty(a_ph_type *ph) {					\
	return (ph->ph_root == NULL);					\
}									\
a_attr a_type *								\
a_prefix##first(a_ph_type *ph) {					\
	if (ph->ph_root == NULL) {					\
		return NULL;						\
	}								\
	ph_merge_aux(a_type, a_field, ph, a_cmp);			\
	return ph->ph_root;						\
}									\
a_attr a_type *								\
a_prefix##any(a_ph_type *ph) {						\
	if (ph->ph_root == NULL) {					\
		return NULL;						\
	}								\
	a_type *aux = phn_next_get(a_type, a_field, ph->ph_root);	\
	if (aux != NULL) {						\
		return aux;						\
	}								\
	return ph->ph_root;						\
}									\
a_attr void								\
a_prefix##insert(a_ph_type *ph, a_type *phn) {				\
	memset(&phn->a_field, 0, sizeof(phn(a_type)));			\
									\
	/*								\
	 * Treat the root as an aux list during insertion, and lazily	\
	 * merge during a_prefix##remove_first().  For elements that	\
	 * are inserted, then removed via a_prefix##remove() before the	\
	 * aux list is ever processed, this makes insert/remove		\
	 * constant-time, whereas eager merging would make insert	\
	 * O(log n).							\
	 */								\
	if (ph->ph_root == NULL) {					\
		ph->ph_root = phn;					\
	} else {							\
		phn_next_set(a_type, a_field, phn, phn_next_get(a_type,	\
		    a_field, ph->ph_root));				\
		if (phn_next_get(a_type, a_field, ph->ph_root) !=	\
		    NULL) {						\
			phn_prev_set(a_type, a_field,			\
			    phn_next_get(a_type, a_field, ph->ph_root),	\
			    phn);					\
		}							\
		phn_prev_set(a_type, a_field, phn, ph->ph_root);	\
		phn_next_set(a_type, a_field, ph->ph_root, phn);	\
	}								\
}									\
a_attr a_type *								\
a_prefix##remove_first(a_ph_type *ph) {					\
	a_type *ret;							\
									\
	if (ph->ph_root == NULL) {					\
		return NULL;						\
	}								\
	ph_merge_aux(a_type, a_field, ph, a_cmp);			\
									\
	ret = ph->ph_root;						\
									\
	ph_merge_children(a_type, a_field, ph->ph_root, a_cmp,		\
	    ph->ph_root);						\
									\
	return ret;							\
}									\
a_attr a_type *								\
a_prefix##remove_any(a_ph_type *ph) {					\
	/*								\
	 * Remove the most recently inserted aux list element, or the	\
	 * root if the aux list is empty.  This has the effect of	\
	 * behaving as a LIFO (and insertion/removal is therefore	\
	 * constant-time) if a_prefix##[remove_]first() are never	\
	 * called.							\
	 */								\
	if (ph->ph_root == NULL) {					\
		return NULL;						\
	}								\
	a_type *ret = phn_next_get(a_type, a_field, ph->ph_root);	\
	if (ret != NULL) {						\
		a_type *aux = phn_next_get(a_type, a_field, ret);	\
		phn_next_set(a_type, a_field, ph->ph_root, aux);	\
		if (aux != NULL) {					\
			phn_prev_set(a_type, a_field, aux,		\
			    ph->ph_root);				\
		}							\
		return ret;						\
	}								\
	ret = ph->ph_root;						\
	ph_merge_children(a_type, a_field, ph->ph_root, a_cmp,		\
	    ph->ph_root);						\
	return ret;							\
}									\
a_attr void								\
a_prefix##remove(a_ph_type *ph, a_type *phn) {				\
	a_type *replace, *parent;					\
									\
	if (ph->ph_root == phn) {					\
		/*							\
		 * We can delete from aux list without merging it, but	\
		 * we need to merge if we are dealing with the root	\
		 * node and it has children.				\
		 */							\
		if (phn_lchild_get(a_type, a_field, phn) == NULL) {	\
			ph->ph_root = phn_next_get(a_type, a_field,	\
			    phn);					\
			if (ph->ph_root != NULL) {			\
				phn_prev_set(a_type, a_field,		\
				    ph->ph_root, NULL);			\
			}						\
			return;						\
		}							\
		ph_merge_aux(a_type, a_field, ph, a_cmp);		\
		if (ph->ph_root == phn) {				\
			ph_merge_children(a_type, a_field, ph->ph_root,	\
			    a_cmp, ph->ph_root);			\
			return;						\
		}							\
	}								\
									\
	/* Get parent (if phn is leftmost child) before mutating. */	\
	if ((parent = phn_prev_get(a_type, a_field, phn)) != NULL) {	\
		if (phn_lchild_get(a_type, a_field, parent) != phn) {	\
			parent = NULL;					\
		}							\
	}								\
	/* Find a possible replacement node, and link to parent. */	\
	ph_merge_children(a_type, a_field, phn, a_cmp, replace);	\
	/* Set next/prev for sibling linked list. */			\
	if (replace != NULL) {						\
		if (parent != NULL) {					\
			phn_prev_set(a_type, a_field, replace, parent);	\
			phn_lchild_set(a_type, a_field, parent,		\
			    replace);					\
		} else {						\
			phn_prev_set(a_type, a_field, replace,		\
			    phn_prev_get(a_type, a_field, phn));	\
			if (phn_prev_get(a_type, a_field, phn) !=	\
			    NULL) {					\
				phn_next_set(a_type, a_field,		\
				    phn_prev_get(a_type, a_field, phn),	\
				    replace);				\
			}						\
		}							\
		phn_next_set(a_type, a_field, replace,			\
		    phn_next_get(a_type, a_field, phn));		\
		if (phn_next_get(a_type, a_field, phn) != NULL) {	\
			phn_prev_set(a_type, a_field,			\
			    phn_next_get(a_type, a_field, phn),		\
			    replace);					\
		}							\
	} else {							\
		if (parent != NULL) {					\
			a_type *next = phn_next_get(a_type, a_field,	\
			    phn);					\
			phn_lchild_set(a_type, a_field, parent, next);	\
			if (next != NULL) {				\
				phn_prev_set(a_type, a_field, next,	\
				    parent);				\
			}						\
		} else {						\
			assert(phn_prev_get(a_type, a_field, phn) !=	\
			    NULL);					\
			phn_next_set(a_type, a_field,			\
			    phn_prev_get(a_type, a_field, phn),		\
			    phn_next_get(a_type, a_field, phn));	\
		}							\
		if (phn_next_get(a_type, a_field, phn) != NULL) {	\
			phn_prev_set(a_type, a_field,			\
			    phn_next_get(a_type, a_field, phn),		\
			    phn_prev_get(a_type, a_field, phn));	\
		}							\
	}								\
}

#endif /* PH_H_ */