4 * This file and its contents are supplied under the terms of the
5 * Common Development and Distribution License ("CDDL"), version 1.0.
6 * You may only use this file in accordance with the terms of version
9 * A full copy of the text of the CDDL should have accompanied this
10 * source. A copy of the CDDL is also available via the Internet at
11 * http://www.illumos.org/license/CDDL.
17 * Copyright (c) 2012 by Delphix. All rights reserved.
26 * Create a new priority queue.
28 * size is the maximum number of items that will be stored in the priority
32 dt_pq_init(dtrace_hdl_t *dtp, uint_t size, dt_pq_value_f value_cb, void *cb_arg)
37 if ((p = dt_zalloc(dtp, sizeof (dt_pq_t))) == NULL)
40 p->dtpq_items = dt_zalloc(dtp, size * sizeof (p->dtpq_items[0]));
41 if (p->dtpq_items == NULL) {
49 p->dtpq_value = value_cb;
56 dt_pq_fini(dt_pq_t *p)
58 dtrace_hdl_t *dtp = p->dtpq_hdl;
60 dt_free(dtp, p->dtpq_items);
65 dt_pq_getvalue(dt_pq_t *p, uint_t index)
67 void *item = p->dtpq_items[index];
68 return (p->dtpq_value(item, p->dtpq_arg));
72 dt_pq_insert(dt_pq_t *p, void *item)
76 assert(p->dtpq_last < p->dtpq_size);
79 p->dtpq_items[i] = item;
81 while (i > 1 && dt_pq_getvalue(p, i) < dt_pq_getvalue(p, i / 2)) {
82 void *tmp = p->dtpq_items[i];
83 p->dtpq_items[i] = p->dtpq_items[i / 2];
84 p->dtpq_items[i / 2] = tmp;
90 * Return elements from the priority queue. *cookie should be zero when first
91 * called. Returns NULL when there are no more elements.
94 dt_pq_walk(dt_pq_t *p, uint_t *cookie)
97 if (*cookie >= p->dtpq_last)
100 return (p->dtpq_items[*cookie]);
104 dt_pq_pop(dt_pq_t *p)
109 assert(p->dtpq_last > 0);
111 if (p->dtpq_last == 1)
114 ret = p->dtpq_items[1];
117 p->dtpq_items[1] = p->dtpq_items[p->dtpq_last];
118 p->dtpq_items[p->dtpq_last] = NULL;
122 uint_t rc = i * 2 + 1;
127 if (lc >= p->dtpq_last)
130 if (rc >= p->dtpq_last) {
132 v = dt_pq_getvalue(p, lc);
134 uint64_t lv = dt_pq_getvalue(p, lc);
135 uint64_t rv = dt_pq_getvalue(p, rc);
146 if (v >= dt_pq_getvalue(p, i))
149 tmp = p->dtpq_items[i];
150 p->dtpq_items[i] = p->dtpq_items[c];
151 p->dtpq_items[c] = tmp;