Merge branch 'dev'5.0.0

1 files changed, 99 insertions, 53 deletions

diff --git a/include/jemalloc/internal/ph.h b/include/jemalloc/internal/ph.h
index 4f91c33..84d6778 100644
--- a/include/jemalloc/internal/ph.h
+++ b/include/jemalloc/internal/ph.h
@@ -13,10 +13,10 @@
  */
 
 #ifndef PH_H_
-#define	PH_H_
+#define PH_H_
 
 /* Node structure. */
-#define	phn(a_type)							\
+#define phn(a_type)							\
 struct {								\
 	a_type	*phn_prev;						\
 	a_type	*phn_next;						\
@@ -24,31 +24,31 @@ struct {								\
 }
 
 /* Root structure. */
-#define	ph(a_type)							\
+#define ph(a_type)							\
 struct {								\
 	a_type	*ph_root;						\
 }
 
 /* Internal utility macros. */
-#define	phn_lchild_get(a_type, a_field, a_phn)				\
+#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 {		\
+#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)				\
+#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 {		\
+#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)				\
+#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 {		\
+#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 {	\
+#define phn_merge_ordered(a_type, a_field, a_phn0, a_phn1, a_cmp) do {	\
 	a_type *phn0child;						\
 									\
 	assert(a_phn0 != NULL);						\
@@ -58,17 +58,18 @@ struct {								\
 	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)						\
+	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)						\
+#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)					\
+	} else if (a_phn1 == NULL) {					\
 		r_phn = a_phn0;						\
-	else if (a_cmp(a_phn0, a_phn1) < 0) {				\
+	} 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;						\
@@ -79,7 +80,7 @@ struct {								\
 	}								\
 } while (0)
 
-#define	ph_merge_siblings(a_type, a_field, a_phn, a_cmp, r_phn) do {	\
+#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;						\
@@ -95,8 +96,9 @@ struct {								\
 	 */								\
 	if (phn1 != NULL) {						\
 		a_type *phnrest = phn_next_get(a_type, a_field, phn1);	\
-		if (phnrest != NULL)					\
+		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);		\
@@ -150,8 +152,9 @@ struct {								\
 				    NULL);				\
 				phn_merge(a_type, a_field, phn0, phn1,	\
 				    a_cmp, phn0);			\
-				if (head == NULL)			\
+				if (head == NULL) {			\
 					break;				\
+				}					\
 				phn_next_set(a_type, a_field, tail,	\
 				    phn0);				\
 				tail = phn0;				\
@@ -164,7 +167,7 @@ struct {								\
 	r_phn = phn0;							\
 } while (0)
 
-#define	ph_merge_aux(a_type, a_field, a_ph, a_cmp) do {			\
+#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);	\
@@ -177,11 +180,11 @@ struct {								\
 	}								\
 } while (0)
 
-#define	ph_merge_children(a_type, a_field, a_phn, a_cmp, r_phn) do {	\
+#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)						\
+	if (lchild == NULL) {						\
 		r_phn = NULL;						\
-	else {								\
+	} else {							\
 		ph_merge_siblings(a_type, a_field, lchild, a_cmp,	\
 		    r_phn);						\
 	}								\
@@ -191,44 +194,50 @@ struct {								\
  * 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)			\
+#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)	\
+#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)						\
-{									\
-									\
+a_prefix##new(a_ph_type *ph) {						\
 	memset(ph, 0, sizeof(ph(a_type)));				\
 }									\
 a_attr bool								\
-a_prefix##empty(a_ph_type *ph)						\
-{									\
-									\
+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);						\
+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);						\
+	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)				\
-{									\
-									\
+a_prefix##insert(a_ph_type *ph, a_type *phn) {				\
 	memset(&phn->a_field, 0, sizeof(phn(a_type)));			\
 									\
 	/*								\
@@ -239,9 +248,9 @@ a_prefix##insert(a_ph_type *ph, a_type *phn)				\
 	 * constant-time, whereas eager merging would make insert	\
 	 * O(log n).							\
 	 */								\
-	if (ph->ph_root == NULL)					\
+	if (ph->ph_root == NULL) {					\
 		ph->ph_root = phn;					\
-	else {								\
+	} 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) !=	\
@@ -255,12 +264,12 @@ a_prefix##insert(a_ph_type *ph, a_type *phn)				\
 	}								\
 }									\
 a_attr a_type *								\
-a_prefix##remove_first(a_ph_type *ph)					\
-{									\
+a_prefix##remove_first(a_ph_type *ph) {					\
 	a_type *ret;							\
 									\
-	if (ph->ph_root == NULL)					\
-		return (NULL);						\
+	if (ph->ph_root == NULL) {					\
+		return NULL;						\
+	}								\
 	ph_merge_aux(a_type, a_field, ph, a_cmp);			\
 									\
 	ret = ph->ph_root;						\
@@ -268,18 +277,54 @@ a_prefix##remove_first(a_ph_type *ph)					\
 	ph_merge_children(a_type, a_field, ph->ph_root, a_cmp,		\
 	    ph->ph_root);						\
 									\
-	return (ret);							\
+	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_prefix##remove(a_ph_type *ph, a_type *phn) {				\
 	a_type *replace, *parent;					\
 									\
-	/*								\
-	 * We can delete from aux list without merging it, but we need	\
-	 * to merge if we are dealing with the root node.		\
-	 */								\
 	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,	\
@@ -290,8 +335,9 @@ a_prefix##remove(a_ph_type *ph, a_type *phn)				\
 									\
 	/* 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)	\
+		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);	\