Home | History | Annotate | Line # | Download | only in common 
      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 	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 *
     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 *
    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