lib/prio_heap/prio_heap.h

   1 /*
   2  * LICENSING: this file is copied from the Linux kernel. We should therefore
   3  * assume a GPLv2 license for the code that comes from the Linux mainline.
   4  */
   5
   6 #ifndef _LINUX_PRIO_HEAP_H
   7 #define _LINUX_PRIO_HEAP_H
   8
   9 /*
  10  * Static-sized priority heap containing pointers. Based on CLR, chapter 7.
  11  */
  12
  13 #include <linux/gfp.h>
  14
  15 /**
  16  * struct ptr_heap - simple static-sized priority heap
  17  * @ptrs - pointer to data area
  18  * @max - max number of elements that can be stored in @ptrs
  19  * @size - current number of valid elements in @ptrs (in the range 0..@size-1
  20  * @gt: comparison operator, which should implement "greater than"
  21  */
  22 struct ptr_heap {
  23         void **ptrs;
  24         int max;
  25         int size;
  26         int (*gt)(void *, void *);
  27 };
  28
  29 /**
  30  * heap_maximum - return the largest element in the heap
  31  * @heap: the heap to be operated on
  32  *
  33  * Returns the largest element in the heap, without performing any modification
  34  * to the heap structure. Returns NULL if the heap is empty.
  35  */
  36 static inline void *heap_maximum(const struct ptr_heap *heap)
  37 {
  38         return heap->size ? heap->ptrs[0] : NULL;
  39 }
  40
  41 /**
  42  * heap_init - initialize an empty heap with a given memory size
  43  * @heap: the heap structure to be initialized
  44  * @size: amount of memory to use in bytes
  45  * @gfp_mask: mask to pass to kmalloc()
  46  * @gt: comparison operator, which should implement "greater than"
  47  */
  48 extern int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask,
  49                      int (*gt)(void *, void *));
  50
  51 /**
  52  * heap_free - release a heap's storage
  53  * @heap: the heap structure whose data should be released
  54  */
  55 void heap_free(struct ptr_heap *heap);
  56
  57 /**
  58  * heap_insert - insert a value into the heap and return any overflowed value
  59  * @heap: the heap to be operated on
  60  * @p: the pointer to be inserted
  61  *
  62  * Attempts to insert the given value into the priority heap. If the
  63  * heap is full prior to the insertion, then the resulting heap will
  64  * consist of the smallest @max elements of the original heap and the
  65  * new element; the greatest element will be removed from the heap and
  66  * returned. Note that the returned element will be the new element
  67  * (i.e. no change to the heap) if the new element is greater than all
  68  * elements currently in the heap.
  69  */
  70 extern void *heap_insert(struct ptr_heap *heap, void *p);
  71
  72 /**
  73  * heap_remove - remove the largest element from the heap
  74  * @heap: the heap to be operated on
  75  *
  76  * Returns the largest element in the heap. It removes this element from the
  77  * heap. Returns NULL if the heap is empty.
  78  */
  79 extern void *heap_remove(struct ptr_heap *heap);
  80
  81 /**
  82  * heap_cherrypick - remove a given element from the heap
  83  * @heap: the heap to be operated on
  84  * @p: the element
  85  *
  86  * Remove the given element from the heap. Return the element if present, else
  87  * return NULL. This algorithm has a complexity of O(n), which is higher than
  88  * O(log(n)) provided by the rest of this API.
  89  */
  90 extern void *heap_cherrypick(struct ptr_heap *heap, void *p);
  91
  92 /**
  93  * heap_replace_max - replace the the largest element from the heap
  94  * @heap: the heap to be operated on
  95  * @p: the pointer to be inserted as topmost element replacement
  96  *
  97  * Returns the largest element in the heap. It removes this element from the
  98  * heap. The heap is rebalanced only once after the insertion. Returns NULL if
  99  * the heap is empty.
 100  *
 101  * This is the equivalent of calling heap_remove() and then heap_insert(), but
 102  * it only rebalances the heap once.
 103  */
 104 extern void *heap_replace_max(struct ptr_heap *heap, void *p);
 105
 106 #endif /* _LINUX_PRIO_HEAP_H */