code.grnet.gr Git - archipelago/blob - xseg/xtypes/xbinheap.c

   1 /*
   2  * Copyright 2013 GRNET S.A. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or
   5  * without modification, are permitted provided that the following
   6  * conditions are met:
   7  *
   8  *   1. Redistributions of source code must retain the above
   9  *      copyright notice, this list of conditions and the following
  10  *      disclaimer.
  11  *   2. Redistributions in binary form must reproduce the above
  12  *      copyright notice, this list of conditions and the following
  13  *      disclaimer in the documentation and/or other materials
  14  *      provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS
  17  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  23  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  24  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  26  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27  * POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * The views and conclusions contained in the software and
  30  * documentation are those of the authors and should not be
  31  * interpreted as representing official policies, either expressed
  32  * or implied, of GRNET S.A.
  33  */
  34
  35
  36 #include <xtypes/xbinheap.h>
  37
  38 //TODO, container aware. use xptr
  39 //add resize capability
  40 //add custom compare functions
  41
  42 #define SWAP(_a_, _b_)                          \
  43         do {                                    \
  44                 typeof(_a_) __temp__ = _a_;     \
  45                 _a_ = _b_;                      \
  46                 _b_ = __temp__ ;                \
  47         } while (0)
  48
  49 static inline void swap_nodes(struct xbinheap *h, xbinheapidx a, xbinheapidx b)
  50 {
  51         xbinheapidx h1, h2;
  52         h1 = h->nodes[a].h;
  53         h2 = h->nodes[b].h;
  54         //XSEGLOG("Swaping %llu, %llu", a, b);
  55         SWAP(h->nodes[a].key, h->nodes[b].key);
  56         SWAP(h->nodes[a].value, h->nodes[b].value);
  57         SWAP(h->nodes[a].h, h->nodes[b].h);
  58         SWAP(h->indexes[h1], h->indexes[h2]);
  59         //XSEGLOG("Index[%llu]: %llu, Index[%llu]: %lli", a, h->indexes[a], b, h->indexes[b]);
  60 }
  61
  62 static inline int isMaxHeap(struct xbinheap *h)
  63 {
  64         return (h->flags & XBINHEAP_MAX);
  65 }
  66
  67 static int heapify_up(struct xbinheap *h, xbinheapidx i)
  68 {
  69         xbinheapidx parent;
  70         struct xbinheap_node *n, *pn;
  71         int cmp;
  72         if (!i)
  73                 return 0;
  74         parent = (i-1)/2;
  75         n = &h->nodes[i];
  76         pn = &h->nodes[parent];
  77         //XSEGLOG("i: %llu, p: %llu, count: %lu", n->key, pn->key, h->count);
  78         if (isMaxHeap(h)){
  79                 cmp = pn->key < n->key;
  80         } else {
  81                 cmp = pn->key > n->key;
  82         }
  83         if (cmp){
  84                 swap_nodes(h, i, parent);
  85                 return heapify_up(h, parent);
  86         }
  87         return 0;
  88 }
  89
  90 static int heapify_down(struct xbinheap *h, xbinheapidx i)
  91 {
  92         xbinheapidx left, right, largest;
  93         struct xbinheap_node *n, *ln, *rn, *largest_n;
  94         left = 2*i + 1;
  95         right = 2*i + 1 + 1;
  96         largest = i;
  97         n = &h->nodes[i];
  98         ln = &h->nodes[left];
  99         rn = &h->nodes[right];
 100         largest_n = &h->nodes[largest];
 101         if (isMaxHeap(h)){
 102         //      XSEGLOG("l: %llu, r: %llu, p: %llu, count: %lu", ln->key, rn->key, largest_n->key, h->count);
 103                 if (left < h->count && (ln->key > largest_n->key)){
 104                         largest = left;
 105                         largest_n = &h->nodes[largest];
 106                 }
 107                 if (right < h->count && (rn->key > largest_n->key)){
 108                         largest = right;
 109                         largest_n = &h->nodes[largest];
 110                 }
 111                 if (largest != i){
 112                         swap_nodes(h, i, largest);
 113                         return heapify_down(h, largest);
 114                 }
 115         } else {
 116                 if (left < h->count && ln->key < largest_n->key){
 117                         largest = left;
 118                         largest_n = &h->nodes[largest];
 119                 }
 120                 if (right < h->count && rn->key < largest_n->key){
 121                         largest = right;
 122                         largest_n = &h->nodes[largest];
 123                 }
 124                 if (largest != i){
 125                         swap_nodes(h, i, largest);
 126                         return heapify_down(h, largest);
 127                 }
 128         }
 129         return 0;
 130 }
 131
 132 xbinheap_handler xbinheap_insert(struct xbinheap *h, xbinheapidx key,
 133                 xbinheapidx value)
 134 {
 135         xbinheap_handler ret;
 136         if (h->count + 1 > h->size)
 137                 return NoNode;
 138         ret = h->nodes[h->count].h;
 139         h->nodes[h->count].key = key;
 140         h->nodes[h->count].value = value;
 141         //h->indexes[h->count] = h->count;
 142         heapify_up(h, h->count);
 143         h->count++;
 144         return ret;
 145 }
 146
 147 int xbinheap_empty(struct xbinheap *h)
 148 {
 149         return (h->count == 0);
 150 }
 151
 152 /* peek min or max */
 153 xbinheapidx xbinheap_peak(struct xbinheap *h)
 154 {
 155         if (xbinheap_empty(h))
 156                 return NoNode;
 157         return h->nodes[0].value;
 158 }
 159
 160 /* extract min or max */
 161 xbinheapidx xbinheap_extract(struct xbinheap *h)
 162 {
 163         xbinheapidx ret = h->nodes[0].value;
 164         if (xbinheap_empty(h))
 165                 return NoNode;
 166         h->count--;
 167         swap_nodes(h, 0, h->count);
 168         heapify_down(h, 0);
 169         return ret;
 170 }
 171
 172 int xbinheap_increasekey(struct xbinheap *h, xbinheap_handler idx,
 173                 xbinheapidx newkey)
 174 {
 175         int r;
 176         xbinheapidx i = h->indexes[idx];
 177         struct xbinheap_node *hn = &h->nodes[i];
 178         //XSEGLOG("h: %llu, index: %llu, key: %llu, newkey:%llu",
 179         //              idx, i, hn->key, newkey);
 180         //assert newkey > hn->key
 181         hn->key = newkey;
 182         if (isMaxHeap(h)){
 183                 r = heapify_up(h, i);
 184         } else {
 185                 r = heapify_down(h, i);
 186         }
 187         return r;
 188 }
 189
 190 xbinheapidx xbinheap_getkey(struct xbinheap *h, xbinheap_handler idx)
 191 {
 192         xbinheapidx i = h->indexes[idx];
 193         if (i > h->count)
 194                 return NoNode;
 195         return h->nodes[i].key;
 196 }
 197
 198 int xbinheap_init(struct xbinheap *h, xbinheapidx size, uint32_t flags, void *mem)
 199 {
 200         xbinheapidx i;
 201         if (!mem){
 202                 h->indexes = xtypes_malloc(sizeof(xbinheapidx) * size);
 203                 h->nodes = xtypes_malloc(sizeof(struct xbinheap_node) * size);
 204                 if (!h->indexes || !h->nodes){
 205                         xtypes_free(h->indexes);
 206                         xtypes_free(h->nodes);
 207                         return -1;
 208                 }
 209         } else {
 210                 h->indexes = mem;
 211                 h->nodes = (void *)((unsigned long)mem + sizeof(xbinheapidx) * size);
 212         }
 213         for (i = 0; i < size; i++) {
 214                 h->nodes[i].h = i;
 215                 h->indexes[i] = i;
 216         }
 217         h->flags = flags;
 218         h->size = size;
 219         h->count = 0;
 220         return 0;
 221 }
 222
 223 void xbinheap_free(struct xbinheap *h)
 224 {
 225         xtypes_free(h->indexes);
 226         xtypes_free(h->nodes);
 227 }
 228
 229
 230 int xbinheap_decreasekey(struct xbinheap *h, xbinheap_handler idx,
 231                 xbinheapidx newkey)
 232 {
 233         int r;
 234         xbinheapidx i = h->indexes[idx];
 235         struct xbinheap_node *hn = &h->nodes[i];
 236         //XSEGLOG("h: %llu, index: %llu, key: %llu, newkey:%llu",
 237         //              idx, i, hn->key, newkey);
 238         //assert newkey > hn->key
 239         hn->key = newkey;
 240         if (isMaxHeap(h)){
 241                 r = heapify_down(h, i);
 242         } else {
 243                 r = heapify_up(h, i);
 244         }
 245         return r;
 246 }
 247
 248 #ifdef __KERNEL__
 249 #include <linux/module.h>
 250 #include <xtypes/xbinheap_exports.h>
 251 #endif