include/linux/prio_heap.h

   1 #ifndef _LINUX_PRIO_HEAP_H
   2 #define _LINUX_PRIO_HEAP_H
   3
   4 /*
   5  * Simple insertion-only static-sized priority heap containing
   6  * pointers, based on CLR, chapter 7
   7  */
   8
   9 #include <linux/gfp.h>
  10
  11 /**
  12  * struct ptr_heap - simple static-sized priority heap
  13  * @ptrs - pointer to data area
  14  * @max - max number of elements that can be stored in @ptrs
  15  * @size - current number of valid elements in @ptrs (in the range 0..@size-1
  16  * @gt: comparison operator, which should implement "greater than"
  17  */
  18 struct ptr_heap {
  19         void **ptrs;
  20         int max;
  21         int size;
  22         int (*gt)(void *, void *);
  23 };
  24
  25 /**
  26  * heap_init - initialize an empty heap with a given memory size
  27  * @heap: the heap structure to be initialized
  28  * @size: amount of memory to use in bytes
  29  * @gfp_mask: mask to pass to kmalloc()
  30  * @gt: comparison operator, which should implement "greater than"
  31  */
  32 extern int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask,
  33                      int (*gt)(void *, void *));
  34
  35 /**
  36  * heap_free - release a heap's storage
  37  * @heap: the heap structure whose data should be released
  38  */
  39 void heap_free(struct ptr_heap *heap);
  40
  41 /**
  42  * heap_insert - insert a value into the heap and return any overflowed value
  43  * @heap: the heap to be operated on
  44  * @p: the pointer to be inserted
  45  *
  46  * Attempts to insert the given value into the priority heap. If the
  47  * heap is full prior to the insertion, then the resulting heap will
  48  * consist of the smallest @max elements of the original heap and the
  49  * new element; the greatest element will be removed from the heap and
  50  * returned. Note that the returned element will be the new element
  51  * (i.e. no change to the heap) if the new element is greater than all
  52  * elements currently in the heap.
  53  */
  54 extern void *heap_insert(struct ptr_heap *heap, void *p);
  55
  56
  57
  58 #endif /* _LINUX_PRIO_HEAP_H */