diff options
Diffstat (limited to 'include/jemalloc/internal/ph.h')
| -rw-r--r-- | include/jemalloc/internal/ph.h | 152 |
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); \ |