usr/src/lib/libdtrace/common/dt_pq.c

   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 }