1/*
2 * CDDL HEADER START
3 *
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
7 * 1.0 of the CDDL.
8 *
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.
12 *
13 * CDDL HEADER END
14 */
15
16/*
17 * Copyright (c) 2012 by Delphix. All rights reserved.
18 */
19
20#include <dtrace.h>
21#include <dt_impl.h>
22#include <dt_pq.h>
23#include <assert.h>
24
25/*
26 * Create a new priority queue.
27 *
28 * size is the maximum number of items that will be stored in the priority
29 * queue at one time.
30 */
31dt_pq_t *
32dt_pq_init(dtrace_hdl_t *dtp, uint_t size, dt_pq_value_f value_cb, void *cb_arg)
33{
34	dt_pq_t *p;
35	assert(size > 1);
36
37	if ((p = dt_zalloc(dtp, sizeof (dt_pq_t))) == NULL)
38		return (NULL);
39
40	p->dtpq_items = dt_zalloc(dtp, size * sizeof (p->dtpq_items[0]));
41	if (p->dtpq_items == NULL) {
42		dt_free(dtp, p);
43		return (NULL);
44	}
45
46	p->dtpq_hdl = dtp;
47	p->dtpq_size = size;
48	p->dtpq_last = 1;
49	p->dtpq_value = value_cb;
50	p->dtpq_arg = cb_arg;
51
52	return (p);
53}
54
55void
56dt_pq_fini(dt_pq_t *p)
57{
58	dtrace_hdl_t *dtp = p->dtpq_hdl;
59
60	dt_free(dtp, p->dtpq_items);
61	dt_free(dtp, p);
62}
63
64static uint64_t
65dt_pq_getvalue(dt_pq_t *p, uint_t index)
66{
67	void *item = p->dtpq_items[index];
68	return (p->dtpq_value(item, p->dtpq_arg));
69}
70
71void
72dt_pq_insert(dt_pq_t *p, void *item)
73{
74	uint_t i;
75
76	assert(p->dtpq_last < p->dtpq_size);
77
78	i = p->dtpq_last++;
79	p->dtpq_items[i] = item;
80
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;
85		i /= 2;
86	}
87}
88
89/*
90 * Return elements from the priority queue.  *cookie should be zero when first
91 * called.  Returns NULL when there are no more elements.
92 */
93void *
94dt_pq_walk(dt_pq_t *p, uint_t *cookie)
95{
96	(*cookie)++;
97	if (*cookie >= p->dtpq_last)
98		return (NULL);
99
100	return (p->dtpq_items[*cookie]);
101}
102
103void *
104dt_pq_pop(dt_pq_t *p)
105{
106	uint_t i = 1;
107	void *ret;
108
109	assert(p->dtpq_last > 0);
110
111	if (p->dtpq_last == 1)
112		return (NULL);
113
114	ret = p->dtpq_items[1];
115
116	p->dtpq_last--;
117	p->dtpq_items[1] = p->dtpq_items[p->dtpq_last];
118	p->dtpq_items[p->dtpq_last] = NULL;
119
120	for (;;) {
121		uint_t lc = i * 2;
122		uint_t rc = i * 2 + 1;
123		uint_t c;
124		uint64_t v;
125		void *tmp;
126
127		if (lc >= p->dtpq_last)
128			break;
129
130		if (rc >= p->dtpq_last) {
131			c = lc;
132			v = dt_pq_getvalue(p, lc);
133		} else {
134			uint64_t lv = dt_pq_getvalue(p, lc);
135			uint64_t rv = dt_pq_getvalue(p, rc);
136
137			if (lv < rv) {
138				c = lc;
139				v = lv;
140			} else {
141				c = rc;
142				v = rv;
143			}
144		}
145
146		if (v >= dt_pq_getvalue(p, i))
147			break;
148
149		tmp = p->dtpq_items[i];
150		p->dtpq_items[i] = p->dtpq_items[c];
151		p->dtpq_items[c] = tmp;
152
153		i = c;
154	}
155
156	return (ret);
157}
158