mem: add memends_str() helper for symmetry
[ccan] / 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