Home > APR-like heap source code >

An APR like implementation of heap structure

A heap structure is a complete tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. Usually understood to be a binary heap.
For me, its main purpose is to implement a priority queue.
I wrote this to train at using thread and pool mechanisms of the APR library.

Download napr_heap.h

napr_heap.h

Read napr_heap.h

  1. /*
  2.  * Copyright (C) 2007 François Pesce : francois.pesce (at) gmail (dot) com
  3.  *
  4.  * Licensed under the Apache License, Version 2.0 (the "License");
  5.  * you may not use this file except in compliance with the License.
  6.  * You may obtain a copy of the License at
  7.  *
  8.  *      http://www.apache.org/licenses/LICENSE-2.0
  9.  *
  10.  * Unless required by applicable law or agreed to in writing, software
  11.  * distributed under the License is distributed on an "AS IS" BASIS,
  12.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13.  * See the License for the specific language governing permissions and
  14.  * limitations under the License.
  15.  */
  16.  
  17. #ifndef NAPR_HEAP_H
  18. #define NAPR_HEAP_H
  19.  
  20. typedef struct napr_heap_t napr_heap_t;
  21. typedef int (napr_heap_cmp_callback_fn_t) (const void *, const void *);
  22. typedef void (napr_heap_display_callback_fn_t) (const void *);
  23. typedef void (napr_heap_del_callback_fn_t) (void *);
  24.  
  25.  
  26. #ifdef HAVE_APR
  27. #include <apr_pools.h>
  28. /**
  29.  * Return the allocator associated to the heap, thus you can allow elements
  30.  * that will be automatically freed when the heap will be.
  31.  * @param heap The heap you are working with.
  32.  * @return Return a pointer to the allcator of type apr_pool_t.
  33.  */
  34. apr_pool_t *napr_heap_get_allocator(const napr_heap_t *heap);
  35. /* APR_POOL_DECLARE_ACCESSOR(heap); */
  36.  
  37. /**
  38.  * Make a new heap structure, a heap is a structure that is able to return the
  39.  * smallest (or highest, according to the way you compare data) element of its
  40.  * set, in a complexity of O(lg n) the same as the complexity to insert a
  41.  * random element.
  42.  * @param pool The associated pool.
  43.  * @param cmp The function that compare two elements to return the smallest.
  44.  * @return Return a pointer to a newly allocated heap NULL if an error occured.
  45.  */
  46. napr_heap_t *napr_heap_make(apr_pool_t *pool, napr_heap_cmp_callback_fn_t *cmp);
  47.  
  48. /**
  49.  * Re-entrant (Thread safe) version of napr_heap_make.
  50.  * @param pool The associated pool.
  51.  * @param cmp The function that compare two elements to return the smallest.
  52.  * @return Return a pointer to a newly allocated heap NULL if an error occured.
  53.  */
  54. napr_heap_t *napr_heap_make_r(apr_pool_t *pool, napr_heap_cmp_callback_fn_t *cmp);
  55.  
  56. #else /* !HAVE_APR */
  57. /**
  58.  * Make a new heap structure, a heap is a structure that is able to return the
  59.  * smallest (or highest, according to the way you compare data) element of its
  60.  * set, in a complexity of O(lg n) the same as the complexity to insert a
  61.  * random element.
  62.  * @param cmp The function that compare two elements to return the smallest.
  63.  * @param del The function that destroy (de-allocate) an element.
  64.  * @return Return a pointer to a newly allocated heap NULL if an error occured.
  65.  */
  66. napr_heap_t *napr_heap_make(napr_heap_cmp_callback_fn_t *cmp, napr_heap_del_callback_fn_t *del);
  67.  
  68. /**
  69.  * Re-entrant (Thread safe) version of napr_heap_make.
  70.  * @param cmp The function that compare two elements to return the smallest.
  71.  * @param del The function that destroy (de-allocate) an element.
  72.  * @return Return a pointer to a newly allocated heap NULL if an error occured.
  73.  */
  74. napr_heap_t *napr_heap_make_r(napr_heap_cmp_callback_fn_t *cmp, napr_heap_del_callback_fn_t *del);
  75. #endif /* HAVE_APR */
  76.  
  77. /**
  78.  * Deallocate the heap;(NB: if the heap is using apr_pool_t (HAVE_APR macro
  79.  * defined), then it will deallocate elements that have been allocated using
  80.  * the heap allocator, otherwise the function del is used on each element.
  81.  * @param heap The heap you are working with.
  82.  * @return nothing.
  83.  */
  84. void napr_heap_destroy(napr_heap_t *heap);
  85.  
  86. /**
  87.  * Insert an element in the heap.
  88.  * @param heap The heap you are working with.
  89.  * @param datum The datum you want to insert.
  90.  * @return 0 if no error occured, -1 otherwise.
  91.  */
  92. int napr_heap_insert(napr_heap_t *heap, void *datum);
  93.  
  94. /**
  95.  * Extract the highest (or the lowest using cmp function) element in the heap,
  96.  * remove it and return it.
  97.  * @param heap The heap you are working with.
  98.  * @return The highest (or lowest according to cmp function) element of the
  99.  * heap, NULL if the heap is empty.
  100.  */
  101. void *napr_heap_extract(napr_heap_t *heap);
  102.  
  103. /**
  104.  * Get the nth element element in the heap.
  105.  * @param heap The heap you are working with.
  106.  * @param n The index of the tree (take the nth element you encounter in a
  107.  * breadth first traversal of a binary tree)
  108.  * @return A pointer on the nth element of the heap, NULL if there's no
  109.  * such element.
  110.  * @remark if you modify the part of this element that is used in the
  111.  * comparation function, you're doing something really bad!
  112.  */
  113. void *napr_heap_get_nth(const napr_heap_t *heap, unsigned int n);
  114.  
  115. /**
  116.  * Get the nth element (to a const pointer because you can't extract it until
  117.  * it is the highest or the lowest using cmp function) element in the heap.
  118.  * @param heap The heap you are working with.
  119.  * @param datum The adress of the datum you want to set.
  120.  * @param n The index of the tree (take the nth element you encounter in a
  121.  * breadth first traversal of a binary tree)
  122.  * @return 0 if no error occured, -1 otherwise.
  123.  */
  124. unsigned int napr_heap_size(const napr_heap_t *heap);
  125.  
  126. /**
  127.  * Re-entrant (Thread safe) version of napr_heap_insert, heap must have been
  128.  * initialized with napr_heap_make_r.
  129.  * @param heap The heap you are working with.
  130.  * @param datum The datum you want to insert.
  131.  * @return 0 if no error occured, -1 otherwise.
  132.  */
  133. int napr_heap_insert_r(napr_heap_t *heap, void *datum);
  134.  
  135. /**
  136.  * Re-entrant (Thread safe) version of napr_heap_extract, heap must have been
  137.  * initialized with napr_heap_make_r.
  138.  * @param heap The heap you are working with.
  139.  * @return The highest (or lowest according to cmp function) element of the
  140.  * heap, NULL if the heap is empty.
  141.  */
  142. void *napr_heap_extract_r(napr_heap_t *heap);
  143.  
  144. /**
  145.  * Attach a callback to the heap in order to display the data stored.
  146.  * @param heap The heap you are working with.
  147.  * @param display A callback used to display content of a datum.
  148.  */
  149. void napr_heap_set_display_cb(napr_heap_t *heap, napr_heap_display_callback_fn_t display);
  150.  
  151. /**
  152.  * Display the binary tree using the display callback.
  153.  * @param heap The heap you are working with.
  154.  */
  155. void napr_heap_display(const napr_heap_t *heap);
  156. #endif /* NAPR_HEAP_H */
  157.  

Download napr_heap.c

napr_heap.c

Read napr_heap.c

  1. /*
  2.  * Copyright (C) 2007 François Pesce : francois.pesce (at) gmail (dot) com
  3.  *
  4.  * Licensed under the Apache License, Version 2.0 (the "License");
  5.  * you may not use this file except in compliance with the License.
  6.  * You may obtain a copy of the License at
  7.  *
  8.  *      http://www.apache.org/licenses/LICENSE-2.0
  9.  *
  10.  * Unless required by applicable law or agreed to in writing, software
  11.  * distributed under the License is distributed on an "AS IS" BASIS,
  12.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13.  * See the License for the specific language governing permissions and
  14.  * limitations under the License.
  15.  */
  16.  
  17. #ifndef HAVE_APR
  18. #include <stdlib.h>
  19. #include <pthread.h>
  20. #else
  21. #include <apr_thread_mutex.h>
  22. #endif
  23. #include <string.h>
  24.  
  25. #include "napr_heap.h"
  26.  
  27. #define INITIAL_MAX 256
  28. #define NAPR_HEAP_PARENT(position) (((position) - 1) >> 1)
  29. #define NAPR_HEAP_LEFT(position)   (((position) << 1) + 1)
  30. #define NAPR_HEAP_RIGHT(position)  (((position) + 1) << 1)
  31.  
  32. struct napr_heap_t
  33. {
  34. #ifdef HAVE_APR
  35.     apr_pool_t *pool;
  36.     apr_thread_mutex_t *mutex;
  37. #else
  38.     pthread_mutex_t mutex;
  39. #endif
  40.     void **tree;
  41.     napr_heap_cmp_callback_fn_t *cmp;
  42.     napr_heap_display_callback_fn_t *display;
  43. #ifndef HAVE_APR                /* !HAVE_APR */
  44.     /* Then we may specify a function to deallocate data */
  45.     napr_heap_del_callback_fn_t *del;
  46. #endif
  47.     unsigned int count, max;
  48.     int mutex_set;              /* true (i.e. 1) if napr_heap_make_r has been
  49.                                    called instead of non-reentrant function */
  50. };
  51.  
  52. #ifdef HAVE_APR
  53. /* APR_POOL_IMPLEMENT_ACCESSOR(heap); */
  54. apr_pool_t *napr_heap_get_allocator(const napr_heap_t *heap)
  55. {
  56.     return heap->pool;
  57. }
  58. #endif
  59.  
  60. napr_heap_t *napr_heap_make(
  61. #ifdef HAVE_APR
  62.                                apr_pool_t *pool,
  63. #endif
  64.                                napr_heap_cmp_callback_fn_t *cmp
  65. #ifndef HAVE_APR                /* !HAVE_APR */
  66.                                , napr_heap_del_callback_fn_t *del
  67. #endif
  68.     )
  69. {
  70.     napr_heap_t *heap = NULL;;
  71. #ifdef HAVE_APR
  72.     apr_pool_t *local_pool;
  73.  
  74.     if (APR_SUCCESS == (apr_pool_create(&local_pool, pool))) {
  75.         heap = apr_palloc(local_pool, sizeof(napr_heap_t));
  76.         heap->pool = local_pool;
  77.         heap->tree = apr_pcalloc(local_pool, sizeof(void *) * INITIAL_MAX);
  78.     }
  79. #else /* !HAVE_APR */
  80.     if (NULL != (heap = malloc(sizeof(napr_heap_t)))) {
  81.         heap->del = del;
  82.         if (NULL == (heap->tree = calloc(INITIAL_MAX, sizeof(void *)))) {
  83.             free(heap);
  84.             heap = NULL;
  85.         }
  86.     }
  87. #endif
  88.     if (NULL != heap) {
  89.         heap->max = INITIAL_MAX;
  90.         heap->count = 0;
  91.         heap->cmp = cmp;
  92.         heap->mutex_set = 0;
  93. #ifdef HAVE_APR
  94.         heap->mutex = NULL;
  95. #else
  96.         memset(&(heap->mutex), 0, sizeof(pthread_mutex_t));
  97. #endif
  98.     }
  99.  
  100.     return heap;
  101. }
  102.  
  103. void napr_heap_destroy(napr_heap_t *heap)
  104. {
  105. #ifdef HAVE_APR
  106.     apr_pool_destroy(heap->pool);
  107. #else /* !HAVE_APR */
  108.     if (NULL != heap) {
  109.         if (NULL != heap->del && NULL != heap->tree) {
  110.             unsigned int i;
  111.             for (i = 0; i < heap->count; i++) {
  112.                 heap->del(heap->tree[i]);
  113.             }
  114.         }
  115.         free(heap->tree);
  116.         free(heap);
  117.     }
  118. #endif
  119. }
  120.  
  121. int napr_heap_insert(napr_heap_t *heap, void *datum)
  122. {
  123.     void **tmp;
  124.     unsigned int ipos, ppos;
  125.  
  126.     if (heap->max <= heap->count) {
  127.         /*
  128.          * reallocation by power of 2:
  129.          */
  130.         unsigned int new_max;
  131.  
  132.         for (new_max = 1; new_max <= heap->max; new_max *= 2);
  133.  
  134. #ifdef HAVE_APR
  135.         tmp = apr_palloc(heap->pool, new_max * sizeof(void *));
  136. #else
  137.         tmp = realloc(heap->tree, new_max * sizeof(void *));
  138. #endif
  139.         if (NULL != tmp) {
  140. #ifdef HAVE_APR
  141.             memcpy(tmp, (heap->tree), (heap->count) * sizeof(void *));
  142. #endif
  143.             memset((tmp + (heap->count)), 0, (new_max - (heap->count + 1)) * sizeof(void *));
  144.             heap->tree = tmp;
  145.             heap->max = new_max;
  146.         }
  147.         else {
  148.             heap->tree = NULL;
  149.             return -1;
  150.         }
  151.     }
  152.  
  153.     /*
  154.      * insertion of the datum after the last one of the tree...
  155.      */
  156.     heap->tree[heap->count] = datum;
  157.  
  158.     ipos = heap->count;
  159.     ppos = NAPR_HEAP_PARENT(ipos);
  160.  
  161.     while (ipos > 0 && (heap->cmp(heap->tree[ppos], heap->tree[ipos]) < 0)) {
  162.         /*
  163.          * Swap the value ...
  164.          */
  165.         tmp = heap->tree[ppos];
  166.         heap->tree[ppos] = heap->tree[ipos];
  167.         heap->tree[ipos] = tmp;
  168.  
  169.         ipos = ppos;
  170.         ppos = NAPR_HEAP_PARENT(ipos);
  171.     }
  172.  
  173.     heap->count++;
  174.  
  175.     return 0;
  176. }
  177.  
  178. void *napr_heap_extract(napr_heap_t *heap)
  179. {
  180.     void *ret = NULL, *tmp;
  181.     unsigned int ipos, rpos, lpos, mpos;
  182.  
  183.     if ((0 != heap->count) && (NULL != heap->tree)) {
  184.         /* keep the value to return */
  185.         ret = heap->tree[0];
  186.         /* It works for count == 1 too (just think about it) */
  187.         heap->tree[0] = heap->tree[heap->count - 1];
  188.         heap->tree[heap->count - 1] = NULL;
  189.         heap->count--;
  190.         ipos = 0;
  191.  
  192.         while (1) {
  193.             lpos = NAPR_HEAP_LEFT(ipos);
  194.             rpos = NAPR_HEAP_RIGHT(ipos);
  195.  
  196.             if (lpos < heap->count) {
  197.                 if (heap->cmp(heap->tree[lpos], heap->tree[ipos]) > 0) {
  198.                     mpos = lpos;
  199.                 }
  200.                 else {
  201.                     mpos = ipos;
  202.                 }
  203.                 if ((rpos < heap->count) && (heap->cmp(heap->tree[rpos], heap->tree[mpos])) > 0) {
  204.                     mpos = rpos;
  205.                 }
  206.             }
  207.             else {
  208.                 mpos = ipos;
  209.             }
  210.  
  211.             if (mpos != ipos) {
  212.                 /*
  213.                  * Swap the choosen children with the current node
  214.                  */
  215.                 tmp = heap->tree[mpos];
  216.                 heap->tree[mpos] = heap->tree[ipos];
  217.                 heap->tree[ipos] = tmp;
  218.                 ipos = mpos;
  219.             }
  220.             else {
  221.                 break;
  222.             }
  223.         }
  224.     }
  225.  
  226.     return ret;
  227. }
  228.  
  229. void *napr_heap_get_nth(const napr_heap_t *heap, unsigned int n)
  230. {
  231.     if ((n < heap->count) && (NULL != heap->tree))
  232.         return heap->tree[n];
  233.     else
  234.         return NULL;
  235. }
  236.  
  237. unsigned int napr_heap_size(const napr_heap_t *heap)
  238. {
  239.     return heap->count;
  240. }
  241.  
  242. /*
  243.  * Reentrant versions of previous functions.
  244.  */
  245. napr_heap_t *napr_heap_make_r(
  246. #ifdef HAVE_APR
  247.                                  apr_pool_t *pool,
  248. #endif
  249.                                  napr_heap_cmp_callback_fn_t *cmp
  250. #ifndef HAVE_APR                /* !HAVE_APR */
  251.                                  , napr_heap_del_callback_fn_t *del
  252. #endif
  253.     )
  254. {
  255.     napr_heap_t *heap;
  256.  
  257.     if (NULL != (heap = napr_heap_make(
  258. #ifdef HAVE_APR
  259.                                           pool,
  260. #endif
  261.                                           cmp
  262. #ifndef HAVE_APR                /* !HAVE_APR */
  263.                                           , del
  264. #endif
  265.                  ))) {
  266. #ifdef HAVE_APR
  267.         if (APR_SUCCESS != apr_thread_mutex_create(&(heap->mutex), APR_THREAD_MUTEX_DEFAULT, pool))
  268.             heap = NULL;
  269. #else
  270.         if (0 > pthread_mutex_init(&(heap->mutex), NULL)) {
  271.             free(heap->tree);
  272.             free(heap);
  273.             heap = NULL;
  274.         }
  275. #endif
  276.     }
  277.     heap->mutex_set = 1;
  278.  
  279.     return heap;
  280. }
  281.  
  282. int napr_heap_insert_r(napr_heap_t *heap, void *datum)
  283. {
  284.     int rc;
  285.  
  286.     if (1 == heap->mutex_set) {
  287. #ifdef HAVE_APR
  288.         if (APR_SUCCESS == (rc = apr_thread_mutex_lock(heap->mutex))) {
  289.             if (0 == (rc = napr_heap_insert(heap, datum)))
  290.                 rc = apr_thread_mutex_unlock(heap->mutex);
  291.         }
  292. #else
  293.         if (0 == (rc = pthread_mutex_lock(&heap->mutex))) {
  294.             if (0 == (rc = napr_heap_insert(heap, datum)))
  295.                 rc = pthread_mutex_unlock(&heap->mutex);
  296.         }
  297. #endif
  298.     }
  299.     else
  300.         rc = -1;
  301.  
  302.     return rc;
  303. }
  304.  
  305. void *napr_heap_extract_r(napr_heap_t *heap)
  306. {
  307.     void *result;
  308.  
  309.     result = NULL;
  310.     if (1 == heap->mutex_set) {
  311. #ifdef HAVE_APR
  312.         if (APR_SUCCESS == apr_thread_mutex_lock(heap->mutex)) {
  313.             if (NULL != (result = napr_heap_extract(heap)))
  314.                 if (APR_SUCCESS != apr_thread_mutex_unlock(heap->mutex)) {
  315.                     result = NULL;
  316.                 }
  317.         }
  318. #else
  319.         if (0 == pthread_mutex_lock(&heap->mutex)) {
  320.             if (NULL != (result = napr_heap_extract(heap)))
  321.                 if (0 != pthread_mutex_unlock(&heap->mutex))
  322.                     result = NULL;
  323.         }
  324. #endif
  325.     }
  326.  
  327.     return result;
  328. }
  329.  
  330. void napr_heap_set_display_cb(napr_heap_t *heap, napr_heap_display_callback_fn_t display)
  331. {
  332.     heap->display = display;
  333. }
  334.  
  335. void napr_heap_display(const napr_heap_t *heap)
  336. {
  337.     unsigned int i;
  338.  
  339.     for (i = 0; i < heap->count; i++) {
  340.         if (((i - 1) % 2) == 0) {
  341.             printf("\n");
  342.         }
  343.         printf("%u:", i);
  344.         heap->display(heap->tree[i]);
  345.         printf("\t");
  346.     }
  347.     printf("\n");
  348.     fflush(stdout);
  349. }
  350.