home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / src / linux-headers-2.6.28-15 / include / linux / prio_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  2008-12-24  |  1.8 KB  |  59 lines
  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 */
  59.