"Fossies" - the Fresh Open Source Software Archive

Member "ftwin-master/src/napr_heap.h" (15 Feb 2015, 6198 Bytes) of package /linux/privat/ftwin-master.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    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 */