git.ozlabs.org Git - ccan/blob - junkcode/dongre.avinash@gmail.com-clibutils/src/c_heap.c

   1 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **\r
   2  *  This file is part of clib library\r
   3  *  Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )\r
   4  *\r
   5  *  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   6  *  of this software and associated documentation files (the "Software"), to deal\r
   7  *  in the Software without restriction, including without limitation the rights\r
   8  *  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   9  *  copies of the Software, and to permit persons to whom the Software is\r
  10  *  furnished to do so, subject to the following conditions:\r
  11  * \r
  12  *  The above copyright notice and this permission notice shall be included in\r
  13  *  all copies or substantial portions of the Software.\r
  14  * \r
  15  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  16  *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  17  *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  18  *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  19  *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  20  *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN\r
  21  *  THE SOFTWARE.\r
  22  ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/\r
  23 #include "c_lib.h"\r
  24 \r
  25 static int\r
  26 pvt_clib_heap_isLeaf( int pos , struct clib_heap *pHeap) { \r
  27         return ( pos >= (pHeap->pHeapPtr->no_of_elements/2)) && ( pos < pHeap->pHeapPtr->no_of_elements );\r
  28 }\r
  29 \r
  30 static int \r
  31 pvt_clib_heap_leftchild( int pos ) {\r
  32       return 2 * pos + 1;            \r
  33 }\r
  34 \r
  35 static int\r
  36 pvt_clib_heap_compare(struct clib_array *pArray, int lIndex , int rIndex) {\r
  37         void *left         =  (void*)0;\r
  38         void *right        = (void*)0;\r
  39         int compare_result = 0;\r
  40         clib_error rc      = 0;\r
  41         rc = element_at_clib_array ( pArray, lIndex , &left);\r
  42         rc = element_at_clib_array ( pArray, rIndex , &right);\r
  43         compare_result =  pArray->compare_fn ( left, right );\r
  44         if ( left ) free ( left );\r
  45         if ( right ) free ( right );\r
  46         return compare_result;\r
  47 }\r
  48 \r
  49 static void\r
  50 pvt_clib_heap_siftdown_max( struct clib_heap *pHeap, int pos ) {\r
  51 \r
  52         struct clib_array *pArray = pHeap->pHeapPtr;\r
  53         int n = pArray->no_of_elements;\r
  54 \r
  55         while ( !pvt_clib_heap_isLeaf(pos, pHeap) ) {\r
  56                 int j = pvt_clib_heap_leftchild( pos );\r
  57                 if ( ( j < ( n - 1) )  &&  \r
  58                         (pvt_clib_heap_compare( pArray, j, j+1) == -1)) {\r
  59                         j++;\r
  60                 }\r
  61                 if ( pvt_clib_heap_compare( pArray, pos, j ) == 1 || \r
  62                          pvt_clib_heap_compare( pArray, pos, j ) == 0) return;\r
  63 \r
  64                 swap_element_clib_array(pArray, pos, j);\r
  65                 pos = j;\r
  66         }\r
  67 }\r
  68 \r
  69 static void\r
  70 pvt_clib_heap_siftdown_min( struct clib_heap *pHeap, int pos ) {\r
  71 \r
  72         struct clib_array *pArray = pHeap->pHeapPtr;\r
  73         int n = pArray->no_of_elements;\r
  74 \r
  75         while ( !pvt_clib_heap_isLeaf(pos, pHeap) ) {\r
  76                 int j = pvt_clib_heap_leftchild( pos );\r
  77                 if ( ( j < ( n - 1) )  &&  \r
  78                         (pvt_clib_heap_compare( pArray, j, j+1) == 1)) {\r
  79                         j++;\r
  80                 }\r
  81                 if ( pvt_clib_heap_compare( pArray, pos, j ) == -1 || \r
  82                          pvt_clib_heap_compare( pArray, pos, j ) == 0) return;\r
  83 \r
  84                 swap_element_clib_array(pArray, pos, j);\r
  85                 pos = j;\r
  86         }\r
  87 }\r
  88 \r
  89 struct clib_heap *\r
  90 new_clib_heap( int default_size, clib_compare fn_c, clib_destroy fn_d ) {\r
  91         struct clib_heap *pHeap = ( struct clib_heap *) malloc ( sizeof ( struct clib_heap ));\r
  92         pHeap->pHeapPtr =  new_clib_array ( default_size, fn_c, fn_d);\r
  93         pHeap->heap_left = 0;\r
  94         pHeap->heap_parent = 0;\r
  95         pHeap->heap_right = 0;\r
  96         return pHeap;\r
  97 }\r
  98 \r
  99 void \r
 100 delete_clib_heap( struct clib_heap *pHeap) {\r
 101         delete_clib_array ( pHeap->pHeapPtr );\r
 102         free ( pHeap );\r
 103 }\r
 104 \r
 105 void \r
 106 insert_clib_heap ( struct clib_heap *pHeap, void *elem, size_t elem_size) {\r
 107         push_back_clib_array ( pHeap->pHeapPtr, elem, elem_size);\r
 108 }\r
 109 \r
 110 void\r
 111 build_max_clib_heap ( struct clib_heap *pHeap ) {\r
 112         int i = 0;\r
 113         for (  i = (pHeap->pHeapPtr->no_of_elements / 2 ) - 1; i >= 0; i--) {\r
 114                 pvt_clib_heap_siftdown_max(pHeap, i);\r
 115         }\r
 116 }\r
 117 void *\r
 118 extract_max_clib_heap( struct clib_heap *pHeap) {\r
 119         void *elem;\r
 120         swap_element_clib_array(pHeap->pHeapPtr, \r
 121                                     0,\r
 122                                                         pHeap->pHeapPtr->no_of_elements - 1);\r
 123 \r
 124         back_clib_array( pHeap->pHeapPtr, &elem);\r
 125         remove_clib_array ( pHeap->pHeapPtr, pHeap->pHeapPtr->no_of_elements - 1 );\r
 126 \r
 127         if (pHeap->pHeapPtr->no_of_elements != 0) {\r
 128                 pvt_clib_heap_siftdown_max(pHeap, 0);\r
 129         }\r
 130 \r
 131         return elem;\r
 132 }\r
 133 \r
 134 void\r
 135 build_min_clib_heap ( struct clib_heap *pHeap ) {\r
 136         int i = 0;\r
 137         for (  i = (pHeap->pHeapPtr->no_of_elements / 2 ) - 1; i >= 0; i--) {\r
 138                 pvt_clib_heap_siftdown_min(pHeap, i);\r
 139         }\r
 140 }\r
 141 \r
 142 void *\r
 143 extract_min_clib_heap( struct clib_heap *pHeap) {\r
 144         void *elem;\r
 145         swap_element_clib_array(pHeap->pHeapPtr, \r
 146                                     0,\r
 147                                                         pHeap->pHeapPtr->no_of_elements - 1);\r
 148 \r
 149         back_clib_array( pHeap->pHeapPtr, &elem);\r
 150         remove_clib_array ( pHeap->pHeapPtr, pHeap->pHeapPtr->no_of_elements - 1 );\r
 151 \r
 152         if (pHeap->pHeapPtr->no_of_elements != 0) {\r
 153                 pvt_clib_heap_siftdown_min(pHeap, 0);\r
 154         }\r
 155         return elem;\r
 156 }\r
 157 clib_bool      \r
 158 empty_clib_heap ( struct clib_heap *pHeap) {\r
 159         if ( pHeap == ( struct clib_heap*)0 )\r
 160                 return clib_true;\r
 161 \r
 162         return pHeap->pHeapPtr->no_of_elements == 0 ? clib_true : clib_false;\r
 163 }\r
 164 \r
 165 \r
 166 void for_each_clib_heap ( struct clib_heap *pHeap, void (*fn)(void*)) {\r
 167         int size = size_clib_array ( pHeap->pHeapPtr );\r
 168         int i = 0;\r
 169         for ( i = 0; i < size; i++ ) {\r
 170                 void *elem;\r
 171                 element_at_clib_array ( pHeap->pHeapPtr, i , &elem);\r
 172                 (fn)(elem);\r
 173                 free ( elem );\r
 174         }\r
 175 }\r