1 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
\r
2 * This file is part of clib library
\r
3 * Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )
\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
12 * The above copyright notice and this permission notice shall be included in
\r
13 * all copies or substantial portions of the Software.
\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
22 ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/
\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
31 pvt_clib_heap_leftchild( int pos ) {
\r
32 return 2 * pos + 1;
\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
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
50 pvt_clib_heap_siftdown_max( struct clib_heap *pHeap, int pos ) {
\r
52 struct clib_array *pArray = pHeap->pHeapPtr;
\r
53 int n = pArray->no_of_elements;
\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
61 if ( pvt_clib_heap_compare( pArray, pos, j ) == 1 ||
\r
62 pvt_clib_heap_compare( pArray, pos, j ) == 0) return;
\r
64 swap_element_clib_array(pArray, pos, j);
\r
70 pvt_clib_heap_siftdown_min( struct clib_heap *pHeap, int pos ) {
\r
72 struct clib_array *pArray = pHeap->pHeapPtr;
\r
73 int n = pArray->no_of_elements;
\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
81 if ( pvt_clib_heap_compare( pArray, pos, j ) == -1 ||
\r
82 pvt_clib_heap_compare( pArray, pos, j ) == 0) return;
\r
84 swap_element_clib_array(pArray, pos, j);
\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
100 delete_clib_heap( struct clib_heap *pHeap) {
\r
101 delete_clib_array ( pHeap->pHeapPtr );
\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
111 build_max_clib_heap ( struct clib_heap *pHeap ) {
\r
113 for ( i = (pHeap->pHeapPtr->no_of_elements / 2 ) - 1; i >= 0; i--) {
\r
114 pvt_clib_heap_siftdown_max(pHeap, i);
\r
118 extract_max_clib_heap( struct clib_heap *pHeap) {
\r
120 swap_element_clib_array(pHeap->pHeapPtr,
\r
122 pHeap->pHeapPtr->no_of_elements - 1);
\r
124 back_clib_array( pHeap->pHeapPtr, &elem);
\r
125 remove_clib_array ( pHeap->pHeapPtr, pHeap->pHeapPtr->no_of_elements - 1 );
\r
127 if (pHeap->pHeapPtr->no_of_elements != 0) {
\r
128 pvt_clib_heap_siftdown_max(pHeap, 0);
\r
135 build_min_clib_heap ( struct clib_heap *pHeap ) {
\r
137 for ( i = (pHeap->pHeapPtr->no_of_elements / 2 ) - 1; i >= 0; i--) {
\r
138 pvt_clib_heap_siftdown_min(pHeap, i);
\r
143 extract_min_clib_heap( struct clib_heap *pHeap) {
\r
145 swap_element_clib_array(pHeap->pHeapPtr,
\r
147 pHeap->pHeapPtr->no_of_elements - 1);
\r
149 back_clib_array( pHeap->pHeapPtr, &elem);
\r
150 remove_clib_array ( pHeap->pHeapPtr, pHeap->pHeapPtr->no_of_elements - 1 );
\r
152 if (pHeap->pHeapPtr->no_of_elements != 0) {
\r
153 pvt_clib_heap_siftdown_min(pHeap, 0);
\r
158 empty_clib_heap ( struct clib_heap *pHeap) {
\r
159 if ( pHeap == ( struct clib_heap*)0 )
\r
162 return pHeap->pHeapPtr->no_of_elements == 0 ? clib_true : clib_false;
\r
166 void for_each_clib_heap ( struct clib_heap *pHeap, void (*fn)(void*)) {
\r
167 int size = size_clib_array ( pHeap->pHeapPtr );
\r
169 for ( i = 0; i < size; i++ ) {
\r
171 element_at_clib_array ( pHeap->pHeapPtr, i , &elem);
\r