diff options
Diffstat (limited to 'cddl/contrib/opensolaris/lib/libdtrace/common/dt_pq.c')
-rw-r--r-- | cddl/contrib/opensolaris/lib/libdtrace/common/dt_pq.c | 157 |
1 files changed, 157 insertions, 0 deletions
diff --git a/cddl/contrib/opensolaris/lib/libdtrace/common/dt_pq.c b/cddl/contrib/opensolaris/lib/libdtrace/common/dt_pq.c new file mode 100644 index 0000000..0cd556a --- /dev/null +++ b/cddl/contrib/opensolaris/lib/libdtrace/common/dt_pq.c @@ -0,0 +1,157 @@ +/* + * CDDL HEADER START + * + * This file and its contents are supplied under the terms of the + * Common Development and Distribution License ("CDDL"), version 1.0. + * You may only use this file in accordance with the terms of version + * 1.0 of the CDDL. + * + * A full copy of the text of the CDDL should have accompanied this + * source. A copy of the CDDL is also available via the Internet at + * http://www.illumos.org/license/CDDL. + * + * CDDL HEADER END + */ + +/* + * Copyright (c) 2012 by Delphix. All rights reserved. + */ + +#include <dtrace.h> +#include <dt_impl.h> +#include <dt_pq.h> +#include <assert.h> + +/* + * Create a new priority queue. + * + * size is the maximum number of items that will be stored in the priority + * queue at one time. + */ +dt_pq_t * +dt_pq_init(dtrace_hdl_t *dtp, uint_t size, dt_pq_value_f value_cb, void *cb_arg) +{ + dt_pq_t *p; + assert(size > 1); + + if ((p = dt_zalloc(dtp, sizeof (dt_pq_t))) == NULL) + return (NULL); + + p->dtpq_items = dt_zalloc(dtp, size * sizeof (p->dtpq_items[0])); + if (p->dtpq_items == NULL) { + dt_free(dtp, p); + return (NULL); + } + + p->dtpq_hdl = dtp; + p->dtpq_size = size; + p->dtpq_last = 1; + p->dtpq_value = value_cb; + p->dtpq_arg = cb_arg; + + return (p); +} + +void +dt_pq_fini(dt_pq_t *p) +{ + dtrace_hdl_t *dtp = p->dtpq_hdl; + + dt_free(dtp, p->dtpq_items); + dt_free(dtp, p); +} + +static uint64_t +dt_pq_getvalue(dt_pq_t *p, uint_t index) +{ + void *item = p->dtpq_items[index]; + return (p->dtpq_value(item, p->dtpq_arg)); +} + +void +dt_pq_insert(dt_pq_t *p, void *item) +{ + uint_t i; + + assert(p->dtpq_last < p->dtpq_size); + + i = p->dtpq_last++; + p->dtpq_items[i] = item; + + while (i > 1 && dt_pq_getvalue(p, i) < dt_pq_getvalue(p, i / 2)) { + void *tmp = p->dtpq_items[i]; + p->dtpq_items[i] = p->dtpq_items[i / 2]; + p->dtpq_items[i / 2] = tmp; + i /= 2; + } +} + +/* + * Return elements from the priority queue. *cookie should be zero when first + * called. Returns NULL when there are no more elements. + */ +void * +dt_pq_walk(dt_pq_t *p, uint_t *cookie) +{ + (*cookie)++; + if (*cookie >= p->dtpq_last) + return (NULL); + + return (p->dtpq_items[*cookie]); +} + +void * +dt_pq_pop(dt_pq_t *p) +{ + uint_t i = 1; + void *ret; + + assert(p->dtpq_last > 0); + + if (p->dtpq_last == 1) + return (NULL); + + ret = p->dtpq_items[1]; + + p->dtpq_last--; + p->dtpq_items[1] = p->dtpq_items[p->dtpq_last]; + p->dtpq_items[p->dtpq_last] = NULL; + + for (;;) { + uint_t lc = i * 2; + uint_t rc = i * 2 + 1; + uint_t c; + uint64_t v; + void *tmp; + + if (lc >= p->dtpq_last) + break; + + if (rc >= p->dtpq_last) { + c = lc; + v = dt_pq_getvalue(p, lc); + } else { + uint64_t lv = dt_pq_getvalue(p, lc); + uint64_t rv = dt_pq_getvalue(p, rc); + + if (lv < rv) { + c = lc; + v = lv; + } else { + c = rc; + v = rv; + } + } + + if (v >= dt_pq_getvalue(p, i)) + break; + + tmp = p->dtpq_items[i]; + p->dtpq_items[i] = p->dtpq_items[c]; + p->dtpq_items[c] = tmp; + + i = c; + } + + return (ret); +} |