--- /dev/null
+/** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **\r
+ * This file is part of clib library\r
+ * Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )\r
+ *\r
+ * Permission is hereby granted, free of charge, to any person obtaining a copy\r
+ * of this software and associated documentation files (the "Software"), to deal\r
+ * in the Software without restriction, including without limitation the rights\r
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
+ * copies of the Software, and to permit persons to whom the Software is\r
+ * furnished to do so, subject to the following conditions:\r
+ * \r
+ * The above copyright notice and this permission notice shall be included in\r
+ * all copies or substantial portions of the Software.\r
+ * \r
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN\r
+ * THE SOFTWARE.\r
+ ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/\r
+#include "c_lib.h"\r
+\r
+static int\r
+pvt_clib_heap_isLeaf( int pos , struct clib_heap *pHeap) { \r
+ return ( pos >= (pHeap->pHeapPtr->no_of_elements/2)) && ( pos < pHeap->pHeapPtr->no_of_elements );\r
+}\r
+\r
+static int \r
+pvt_clib_heap_leftchild( int pos ) {\r
+ return 2 * pos + 1; \r
+}\r
+\r
+static int\r
+pvt_clib_heap_compare(struct clib_array *pArray, int lIndex , int rIndex) {\r
+ void *left = (void*)0;\r
+ void *right = (void*)0;\r
+ int compare_result = 0;\r
+ clib_error rc = 0;\r
+ rc = element_at_clib_array ( pArray, lIndex , &left);\r
+ rc = element_at_clib_array ( pArray, rIndex , &right);\r
+ compare_result = pArray->compare_fn ( left, right );\r
+ if ( left ) free ( left );\r
+ if ( right ) free ( right );\r
+ return compare_result;\r
+}\r
+\r
+static void\r
+pvt_clib_heap_siftdown_max( struct clib_heap *pHeap, int pos ) {\r
+\r
+ struct clib_array *pArray = pHeap->pHeapPtr;\r
+ int n = pArray->no_of_elements;\r
+\r
+ while ( !pvt_clib_heap_isLeaf(pos, pHeap) ) {\r
+ int j = pvt_clib_heap_leftchild( pos );\r
+ if ( ( j < ( n - 1) ) && \r
+ (pvt_clib_heap_compare( pArray, j, j+1) == -1)) {\r
+ j++;\r
+ }\r
+ if ( pvt_clib_heap_compare( pArray, pos, j ) == 1 || \r
+ pvt_clib_heap_compare( pArray, pos, j ) == 0) return;\r
+\r
+ swap_element_clib_array(pArray, pos, j);\r
+ pos = j;\r
+ }\r
+}\r
+\r
+static void\r
+pvt_clib_heap_siftdown_min( struct clib_heap *pHeap, int pos ) {\r
+\r
+ struct clib_array *pArray = pHeap->pHeapPtr;\r
+ int n = pArray->no_of_elements;\r
+\r
+ while ( !pvt_clib_heap_isLeaf(pos, pHeap) ) {\r
+ int j = pvt_clib_heap_leftchild( pos );\r
+ if ( ( j < ( n - 1) ) && \r
+ (pvt_clib_heap_compare( pArray, j, j+1) == 1)) {\r
+ j++;\r
+ }\r
+ if ( pvt_clib_heap_compare( pArray, pos, j ) == -1 || \r
+ pvt_clib_heap_compare( pArray, pos, j ) == 0) return;\r
+\r
+ swap_element_clib_array(pArray, pos, j);\r
+ pos = j;\r
+ }\r
+}\r
+\r
+struct clib_heap *\r
+new_clib_heap( int default_size, clib_compare fn_c, clib_destroy fn_d ) {\r
+ struct clib_heap *pHeap = ( struct clib_heap *) malloc ( sizeof ( struct clib_heap ));\r
+ pHeap->pHeapPtr = new_clib_array ( default_size, fn_c, fn_d);\r
+ pHeap->heap_left = 0;\r
+ pHeap->heap_parent = 0;\r
+ pHeap->heap_right = 0;\r
+ return pHeap;\r
+}\r
+\r
+void \r
+delete_clib_heap( struct clib_heap *pHeap) {\r
+ delete_clib_array ( pHeap->pHeapPtr );\r
+ free ( pHeap );\r
+}\r
+\r
+void \r
+insert_clib_heap ( struct clib_heap *pHeap, void *elem, size_t elem_size) {\r
+ push_back_clib_array ( pHeap->pHeapPtr, elem, elem_size);\r
+}\r
+\r
+void\r
+build_max_clib_heap ( struct clib_heap *pHeap ) {\r
+ int i = 0;\r
+ for ( i = (pHeap->pHeapPtr->no_of_elements / 2 ) - 1; i >= 0; i--) {\r
+ pvt_clib_heap_siftdown_max(pHeap, i);\r
+ }\r
+}\r
+void *\r
+extract_max_clib_heap( struct clib_heap *pHeap) {\r
+ void *elem;\r
+ swap_element_clib_array(pHeap->pHeapPtr, \r
+ 0,\r
+ pHeap->pHeapPtr->no_of_elements - 1);\r
+\r
+ back_clib_array( pHeap->pHeapPtr, &elem);\r
+ remove_clib_array ( pHeap->pHeapPtr, pHeap->pHeapPtr->no_of_elements - 1 );\r
+\r
+ if (pHeap->pHeapPtr->no_of_elements != 0) {\r
+ pvt_clib_heap_siftdown_max(pHeap, 0);\r
+ }\r
+\r
+ return elem;\r
+}\r
+\r
+void\r
+build_min_clib_heap ( struct clib_heap *pHeap ) {\r
+ int i = 0;\r
+ for ( i = (pHeap->pHeapPtr->no_of_elements / 2 ) - 1; i >= 0; i--) {\r
+ pvt_clib_heap_siftdown_min(pHeap, i);\r
+ }\r
+}\r
+\r
+void *\r
+extract_min_clib_heap( struct clib_heap *pHeap) {\r
+ void *elem;\r
+ swap_element_clib_array(pHeap->pHeapPtr, \r
+ 0,\r
+ pHeap->pHeapPtr->no_of_elements - 1);\r
+\r
+ back_clib_array( pHeap->pHeapPtr, &elem);\r
+ remove_clib_array ( pHeap->pHeapPtr, pHeap->pHeapPtr->no_of_elements - 1 );\r
+\r
+ if (pHeap->pHeapPtr->no_of_elements != 0) {\r
+ pvt_clib_heap_siftdown_min(pHeap, 0);\r
+ }\r
+ return elem;\r
+}\r
+clib_bool \r
+empty_clib_heap ( struct clib_heap *pHeap) {\r
+ if ( pHeap == ( struct clib_heap*)0 )\r
+ return clib_true;\r
+\r
+ return pHeap->pHeapPtr->no_of_elements == 0 ? clib_true : clib_false;\r
+}\r
+\r
+\r
+void for_each_clib_heap ( struct clib_heap *pHeap, void (*fn)(void*)) {\r
+ int size = size_clib_array ( pHeap->pHeapPtr );\r
+ int i = 0;\r
+ for ( i = 0; i < size; i++ ) {\r
+ void *elem;\r
+ element_at_clib_array ( pHeap->pHeapPtr, i , &elem);\r
+ (fn)(elem);\r
+ free ( elem );\r
+ }\r
+}\r
projects / ccan / blobdiff