Line data Source code
1 : /**
2 : * @file napr_heap.c
3 : * @brief Implementation of the generic binary heap.
4 : * @ingroup DataStructures
5 : */
6 : /*
7 : * Copyright (C) 2007 François Pesce : francois.pesce (at) gmail (dot) com
8 : *
9 : * Licensed under the Apache License, Version 2.0 (the "License");
10 : * you may not use this file except in compliance with the License.
11 : * You may obtain a copy of the License at
12 : *
13 : * http://www.apache.org/licenses/LICENSE-2.0
14 : *
15 : * Unless required by applicable law or agreed to in writing, software
16 : * distributed under the License is distributed on an "AS IS" BASIS,
17 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 : * See the License for the specific language governing permissions and
19 : * limitations under the License.
20 : */
21 :
22 : #include <apr_thread_mutex.h>
23 : #include <string.h>
24 :
25 : #include "debug.h"
26 : #include "napr_heap.h"
27 :
28 : #define INITIAL_MAX 256
29 : #define NAPR_HEAP_PARENT(position) (((position) - 1) >> 1)
30 : #define NAPR_HEAP_LEFT(position) (((position) << 1) + 1)
31 : #define NAPR_HEAP_RIGHT(position) (((position) + 1) << 1)
32 :
33 : struct napr_heap_t
34 : {
35 : apr_pool_t *pool;
36 : apr_thread_mutex_t *mutex;
37 : void **tree;
38 : napr_heap_cmp_callback_fn_t *cmp;
39 : unsigned int count, max;
40 : int mutex_set; /* true (i.e. 1) if napr_heap_make_r has been
41 : called instead of non-reentrant function */
42 : };
43 :
44 : #ifdef HAVE_APR
45 : /* APR_POOL_IMPLEMENT_ACCESSOR(heap); */
46 : #endif
47 :
48 35 : napr_heap_t *napr_heap_make(apr_pool_t *pool, napr_heap_cmp_callback_fn_t *cmp)
49 : {
50 35 : napr_heap_t *heap = NULL;
51 : apr_pool_t *local_pool;
52 :
53 35 : if (APR_SUCCESS == (apr_pool_create(&local_pool, pool))) {
54 35 : heap = apr_palloc(local_pool, sizeof(napr_heap_t));
55 35 : heap->pool = local_pool;
56 35 : heap->tree = (void **) apr_pcalloc(local_pool, sizeof(void *) * INITIAL_MAX);
57 : }
58 :
59 35 : if (NULL != heap) {
60 35 : heap->max = INITIAL_MAX;
61 35 : heap->count = 0;
62 35 : heap->cmp = cmp;
63 35 : heap->mutex_set = 0;
64 35 : heap->mutex = NULL;
65 : }
66 :
67 35 : return heap;
68 : }
69 :
70 221 : int napr_heap_insert(napr_heap_t *heap, void *datum)
71 : {
72 : void **tmp;
73 : unsigned int ipos, ppos;
74 :
75 221 : if (heap->max <= heap->count) {
76 : /*
77 : * reallocation by power of 2:
78 : */
79 : unsigned int new_max;
80 :
81 0 : for (new_max = 1; new_max <= heap->max; new_max *= 2);
82 :
83 0 : tmp = apr_palloc(heap->pool, new_max * sizeof(void *));
84 0 : if (NULL != tmp) {
85 0 : memcpy(tmp, (heap->tree), (heap->count) * sizeof(void *));
86 0 : memset((tmp + (heap->count)), 0, (new_max - (heap->count + 1)) * sizeof(void *));
87 0 : heap->tree = tmp;
88 0 : heap->max = new_max;
89 : }
90 : else {
91 0 : heap->tree = NULL;
92 0 : DEBUG_ERR("allocation failed");
93 0 : return -1;
94 : }
95 : }
96 :
97 : /*
98 : * insertion of the datum after the last one of the tree...
99 : */
100 221 : heap->tree[heap->count] = datum;
101 :
102 221 : ipos = heap->count;
103 221 : ppos = NAPR_HEAP_PARENT(ipos);
104 :
105 356 : while (ipos > 0 && (heap->cmp(heap->tree[ppos], heap->tree[ipos]) < 0)) {
106 : /*
107 : * Swap the value ...
108 : */
109 135 : tmp = heap->tree[ppos];
110 135 : heap->tree[ppos] = heap->tree[ipos];
111 135 : heap->tree[ipos] = tmp;
112 :
113 135 : ipos = ppos;
114 135 : ppos = NAPR_HEAP_PARENT(ipos);
115 : }
116 :
117 221 : heap->count++;
118 :
119 221 : return 0;
120 : }
121 :
122 256 : void *napr_heap_extract(napr_heap_t *heap)
123 : {
124 256 : void *ret = NULL, *tmp;
125 : unsigned int ipos, rpos, lpos, mpos;
126 :
127 256 : if ((0 != heap->count) && (NULL != heap->tree)) {
128 : /* keep the value to return */
129 221 : ret = heap->tree[0];
130 : /* It works for count == 1 too (just think about it) */
131 221 : heap->tree[0] = heap->tree[heap->count - 1];
132 221 : heap->tree[heap->count - 1] = NULL;
133 221 : heap->count--;
134 221 : ipos = 0;
135 :
136 : while (1) {
137 620 : lpos = NAPR_HEAP_LEFT(ipos);
138 620 : rpos = NAPR_HEAP_RIGHT(ipos);
139 :
140 620 : if (lpos < heap->count) {
141 462 : if (heap->cmp(heap->tree[lpos], heap->tree[ipos]) > 0) {
142 368 : mpos = lpos;
143 : }
144 : else {
145 94 : mpos = ipos;
146 : }
147 462 : if ((rpos < heap->count) && (heap->cmp(heap->tree[rpos], heap->tree[mpos])) > 0) {
148 182 : mpos = rpos;
149 : }
150 : }
151 : else {
152 158 : mpos = ipos;
153 : }
154 :
155 620 : if (mpos != ipos) {
156 : /*
157 : * Swap the choosen children with the current node
158 : */
159 399 : tmp = heap->tree[mpos];
160 399 : heap->tree[mpos] = heap->tree[ipos];
161 399 : heap->tree[ipos] = tmp;
162 399 : ipos = mpos;
163 : }
164 : else {
165 221 : break;
166 : }
167 : }
168 : }
169 :
170 256 : return ret;
171 : }
172 :
173 0 : void *napr_heap_get_nth(const napr_heap_t *heap, unsigned int n)
174 : {
175 0 : if ((n < heap->count) && (NULL != heap->tree))
176 0 : return heap->tree[n];
177 : else
178 0 : return NULL;
179 : }
180 :
181 17 : unsigned int napr_heap_size(const napr_heap_t *heap)
182 : {
183 17 : return heap->count;
184 : }
185 :
186 : /*
187 : * Reentrant versions of previous functions.
188 : */
189 1 : napr_heap_t *napr_heap_make_r(apr_pool_t *pool, napr_heap_cmp_callback_fn_t *cmp)
190 : {
191 : napr_heap_t *heap;
192 :
193 1 : if (NULL != (heap = napr_heap_make(pool, cmp))) {
194 1 : if (APR_SUCCESS != apr_thread_mutex_create(&(heap->mutex), APR_THREAD_MUTEX_DEFAULT, pool))
195 0 : heap = NULL;
196 : }
197 :
198 1 : if (NULL != heap)
199 1 : heap->mutex_set = 1;
200 :
201 1 : return heap;
202 : }
203 :
204 5 : int napr_heap_insert_r(napr_heap_t *heap, void *datum)
205 : {
206 : int rc;
207 :
208 5 : if (1 == heap->mutex_set) {
209 5 : if (APR_SUCCESS == (rc = apr_thread_mutex_lock(heap->mutex))) {
210 5 : if (0 == (rc = napr_heap_insert(heap, datum)))
211 5 : rc = apr_thread_mutex_unlock(heap->mutex);
212 : }
213 : else {
214 0 : DEBUG_ERR("locking failed");
215 : }
216 : }
217 : else
218 0 : rc = -1;
219 :
220 5 : return rc;
221 : }
|
