diff options
| author | Jason Evans <jasone@canonware.com> | 2017-03-04 06:51:21 (GMT) |
|---|---|---|
| committer | Jason Evans <jasone@canonware.com> | 2017-03-07 18:25:33 (GMT) |
| commit | cc75c35db58f4ce4a27455fe5fe46fe9347d2c45 (patch) | |
| tree | 7549b0ccc33d122d3f18483902ac3aa060a4e745 /include/jemalloc | |
| parent | e201e24904d53897409b1dda451d40c5d2e0dc29 (diff) | |
| download | jemalloc-cc75c35db58f4ce4a27455fe5fe46fe9347d2c45.zip jemalloc-cc75c35db58f4ce4a27455fe5fe46fe9347d2c45.tar.gz jemalloc-cc75c35db58f4ce4a27455fe5fe46fe9347d2c45.tar.bz2 | |
Add any() and remove_any() to ph.
These functions select the easiest-to-remove element in the heap, which
is either the most recently inserted aux list element or the root. If
no calls are made to first() or remove_first(), the behavior (and time
complexity) is the same as for a LIFO queue.
Diffstat (limited to 'include/jemalloc')
| -rw-r--r-- | include/jemalloc/internal/ph.h | 58 |
1 files changed, 54 insertions, 4 deletions
diff --git a/include/jemalloc/internal/ph.h b/include/jemalloc/internal/ph.h index 7e1920c..84d6778 100644 --- a/include/jemalloc/internal/ph.h +++ b/include/jemalloc/internal/ph.h @@ -198,8 +198,10 @@ struct { \ 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); /* @@ -223,6 +225,17 @@ a_prefix##first(a_ph_type *ph) { \ 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))); \ @@ -266,15 +279,52 @@ a_prefix##remove_first(a_ph_type *ph) { \ \ 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; \ \ - /* \ - * 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, \ |