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  */
31 dt_pq_t *
dt_pq_init(dtrace_hdl_t * dtp,uint_t size,dt_pq_value_f value_cb,void * cb_arg)32 dt_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 
55 void
dt_pq_fini(dt_pq_t * p)56 dt_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 
64 static uint64_t
dt_pq_getvalue(dt_pq_t * p,uint_t index)65 dt_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 
71 void
dt_pq_insert(dt_pq_t * p,void * item)72 dt_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  */
93 void *
dt_pq_walk(dt_pq_t * p,uint_t * cookie)94 dt_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 
103 void *
dt_pq_pop(dt_pq_t * p)104 dt_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