prio_heap.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    1 /*
    2  * Simple insertion-only static-sized priority heap containing
    3  * pointers, based on CLR, chapter 7
    4  */
    5 
    6 #include <linux/slab.h>
    7 #include <linux/prio_heap.h>
    8 
    9 int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask,
   10               int (*gt)(void *, void *))
   11 {
   12         heap->ptrs = kmalloc(size, gfp_mask);
   13         if (!heap->ptrs)
   14                 return -ENOMEM;
   15         heap->size = 0;
   16         heap->max = size / sizeof(void *);
   17         heap->gt = gt;
   18         return 0;
   19 }
   20 
   21 void heap_free(struct ptr_heap *heap)
   22 {
   23         kfree(heap->ptrs);
   24 }
   25 
   26 void *heap_insert(struct ptr_heap *heap, void *p)
   27 {
   28         void *res;
   29         void **ptrs = heap->ptrs;
   30         int pos;
   31 
   32         if (heap->size < heap->max) {
   33                 /* Heap insertion */
   34                 pos = heap->size++;
   35                 while (pos > 0 && heap->gt(p, ptrs[(pos-1)/2])) {
   36                         ptrs[pos] = ptrs[(pos-1)/2];
   37                         pos = (pos-1)/2;
   38                 }
   39                 ptrs[pos] = p;
   40                 return NULL;
   41         }
   42 
   43         /* The heap is full, so something will have to be dropped */
   44 
   45         /* If the new pointer is greater than the current max, drop it */
   46         if (heap->gt(p, ptrs[0]))
   47                 return p;
   48 
   49         /* Replace the current max and heapify */
   50         res = ptrs[0];
   51         ptrs[0] = p;
   52         pos = 0;
   53 
   54         while (1) {
   55                 int left = 2 * pos + 1;
   56                 int right = 2 * pos + 2;
   57                 int largest = pos;
   58                 if (left < heap->size && heap->gt(ptrs[left], p))
   59                         largest = left;
   60                 if (right < heap->size && heap->gt(ptrs[right], ptrs[largest]))
   61                         largest = right;
   62                 if (largest == pos)
   63                         break;
   64                 /* Push p down the heap one level and bump one up */
   65                 ptrs[pos] = ptrs[largest];
   66                 ptrs[largest] = p;
   67                 pos = largest;
   68         }
   69         return res;
   70 }

Cache object: 7a50de46ceeb4517fea3adaefd3a9392

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/lib/prio_heap.c

FreeBSD/Linux Kernel Cross Reference
sys/lib/prio_heap.c