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 * 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 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 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 72 dt_pq_insert(dt_pq_t *p, void *item) 73 { 74 uint_t i; 75 76 #if !defined(sun) 77 if (p->dtpq_last >= p->dtpq_size) 78 return; 79 #endif 80 assert(p->dtpq_last < p->dtpq_size); 81 82 i = p->dtpq_last++; 83 p->dtpq_items[i] = item; 84 85 while (i > 1 && dt_pq_getvalue(p, i) < dt_pq_getvalue(p, i / 2)) { 86 void *tmp = p->dtpq_items[i]; 87 p->dtpq_items[i] = p->dtpq_items[i / 2]; 88 p->dtpq_items[i / 2] = tmp; 89 i /= 2; 90 } 91 } 92 93 /* 94 * Return elements from the priority queue. *cookie should be zero when first 95 * called. Returns NULL when there are no more elements. 96 */ 97 void * 98 dt_pq_walk(dt_pq_t *p, uint_t *cookie) 99 { 100 (*cookie)++; 101 if (*cookie >= p->dtpq_last) 102 return (NULL); 103 104 return (p->dtpq_items[*cookie]); 105 } 106 107 void * 108 dt_pq_pop(dt_pq_t *p) 109 { 110 uint_t i = 1; 111 void *ret; 112 113 assert(p->dtpq_last > 0); 114 115 if (p->dtpq_last == 1) 116 return (NULL); 117 118 ret = p->dtpq_items[1]; 119 120 p->dtpq_last--; 121 p->dtpq_items[1] = p->dtpq_items[p->dtpq_last]; 122 p->dtpq_items[p->dtpq_last] = NULL; 123 124 for (;;) { 125 uint_t lc = i * 2; 126 uint_t rc = i * 2 + 1; 127 uint_t c; 128 uint64_t v; 129 void *tmp; 130 131 if (lc >= p->dtpq_last) 132 break; 133 134 if (rc >= p->dtpq_last) { 135 c = lc; 136 v = dt_pq_getvalue(p, lc); 137 } else { 138 uint64_t lv = dt_pq_getvalue(p, lc); 139 uint64_t rv = dt_pq_getvalue(p, rc); 140 141 if (lv < rv) { 142 c = lc; 143 v = lv; 144 } else { 145 c = rc; 146 v = rv; 147 } 148 } 149 150 if (v >= dt_pq_getvalue(p, i)) 151 break; 152 153 tmp = p->dtpq_items[i]; 154 p->dtpq_items[i] = p->dtpq_items[c]; 155 p->dtpq_items[c] = tmp; 156 157 i = c; 158 } 159 160 return (ret); 161 } 162