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

   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 #ifndef __XBINHEAP_H
  37 #define __XBINHEAP_H
  38
  39 #include <xtypes/domain.h>
  40 #include <sys/util.h>
  41
  42 typedef uint64_t xbinheapidx;
  43 typedef xbinheapidx xbinheap_handler;
  44 #define NoNode (xbinheapidx)-1
  45 #define XBINHEAP_MAX (uint32_t)(1<<0)
  46 #define XBINHEAP_MIN (uint32_t)(1<<1)
  47
  48 struct xbinheap_node {
  49         xbinheapidx key;
  50         xbinheapidx value;
  51         xbinheapidx h;
  52 };
  53
  54 struct xbinheap {
  55         xbinheapidx size;
  56         xbinheapidx count;
  57         uint32_t flags;
  58         xbinheapidx *indexes;
  59         struct xbinheap_node *nodes;
  60 };
  61
  62 xbinheap_handler xbinheap_insert(struct xbinheap *h, xbinheapidx key,
  63                 xbinheapidx value);
  64 int xbinheap_empty(struct xbinheap *h);
  65 xbinheapidx xbinheap_peak(struct xbinheap *h);
  66 xbinheapidx xbinheap_extract(struct xbinheap *h);
  67 int xbinheap_increasekey(struct xbinheap *h, xbinheap_handler idx,
  68                 xbinheapidx newkey);
  69 int xbinheap_decreasekey(struct xbinheap *h, xbinheap_handler idx,
  70                 xbinheapidx newkey);
  71 xbinheapidx xbinheap_getkey(struct xbinheap *h, xbinheap_handler idx);
  72 int xbinheap_init(struct xbinheap *h, xbinheapidx size, uint32_t flags, void *mem);
  73 void xbinheap_free(struct xbinheap *h);
  74
  75 #endif /* __XBINHEAP_H */