diff options
author | David Barksdale <amatus.amongus@gmail.com> | 2009-09-23 04:14:06 +0000 |
---|---|---|
committer | David Barksdale <amatus.amongus@gmail.com> | 2009-09-23 04:14:06 +0000 |
commit | 45103b9adc8eb09c21b5eb51e8dead8ddad9eef6 (patch) | |
tree | 91f6d4fee9fbd9c0690be8949fb6a7728ca9c202 /src/util/container_heap.c | |
parent | c04768147bc897cfafb343aeeb02221ecd086795 (diff) | |
download | gnunet-45103b9adc8eb09c21b5eb51e8dead8ddad9eef6.tar.gz gnunet-45103b9adc8eb09c21b5eb51e8dead8ddad9eef6.zip |
Remove use of log2(). FreeBSD doesn't have it and why use floating point when you don't have to?
Diffstat (limited to 'src/util/container_heap.c')
-rw-r--r-- | src/util/container_heap.c | 26 |
1 files changed, 16 insertions, 10 deletions
diff --git a/src/util/container_heap.c b/src/util/container_heap.c index c7afd6f71..96efe9d04 100644 --- a/src/util/container_heap.c +++ b/src/util/container_heap.c | |||
@@ -87,6 +87,17 @@ void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap) | |||
87 | return heap->root->element; | 87 | return heap->root->element; |
88 | } | 88 | } |
89 | 89 | ||
90 | int | ||
91 | next_power_of_2(int v) | ||
92 | { | ||
93 | v |= v >> 1; | ||
94 | v |= v >> 2; | ||
95 | v |= v >> 4; | ||
96 | v |= v >> 8; | ||
97 | v |= v >> 16; | ||
98 | v++; | ||
99 | return v; | ||
100 | } | ||
90 | 101 | ||
91 | void | 102 | void |
92 | internal_print (struct GNUNET_CONTAINER_heap_node *root) | 103 | internal_print (struct GNUNET_CONTAINER_heap_node *root) |
@@ -159,16 +170,14 @@ getNextPos (struct GNUNET_CONTAINER_Heap *root) | |||
159 | struct GNUNET_CONTAINER_heap_node *ret; | 170 | struct GNUNET_CONTAINER_heap_node *ret; |
160 | struct GNUNET_CONTAINER_heap_node *parent; | 171 | struct GNUNET_CONTAINER_heap_node *parent; |
161 | int pos; | 172 | int pos; |
162 | int depth; | ||
163 | int i; | 173 | int i; |
164 | 174 | ||
165 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node)); | 175 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node)); |
166 | pos = root->size + 1; | 176 | pos = root->size + 1; |
167 | depth = (int) log2 (pos); | ||
168 | ret->left_child = NULL; | 177 | ret->left_child = NULL; |
169 | ret->right_child = NULL; | 178 | ret->right_child = NULL; |
170 | 179 | ||
171 | if (depth == 0) | 180 | if (0 == root->size) |
172 | { | 181 | { |
173 | ret->parent = NULL; | 182 | ret->parent = NULL; |
174 | root->root = ret; | 183 | root->root = ret; |
@@ -176,9 +185,9 @@ getNextPos (struct GNUNET_CONTAINER_Heap *root) | |||
176 | else | 185 | else |
177 | { | 186 | { |
178 | parent = root->root; | 187 | parent = root->root; |
179 | for (i = depth; i > 1; i--) | 188 | for (i = next_power_of_2(pos) >> 2; i > 1; i >>= 1) |
180 | { | 189 | { |
181 | if (((pos / (1 << (i - 1))) % 2) == 0) | 190 | if (((pos / i) % 2) == 0) |
182 | parent = parent->left_child; | 191 | parent = parent->left_child; |
183 | else | 192 | else |
184 | parent = parent->right_child; | 193 | parent = parent->right_child; |
@@ -200,11 +209,8 @@ static struct GNUNET_CONTAINER_heap_node * | |||
200 | getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos) | 209 | getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos) |
201 | { | 210 | { |
202 | struct GNUNET_CONTAINER_heap_node *ret; | 211 | struct GNUNET_CONTAINER_heap_node *ret; |
203 | |||
204 | int depth; | ||
205 | int i; | 212 | int i; |
206 | 213 | ||
207 | depth = (int) log2 (pos); | ||
208 | ret = NULL; | 214 | ret = NULL; |
209 | if (pos > root->size) | 215 | if (pos > root->size) |
210 | { | 216 | { |
@@ -213,9 +219,9 @@ getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos) | |||
213 | else | 219 | else |
214 | { | 220 | { |
215 | ret = root->root; | 221 | ret = root->root; |
216 | for (i = depth; i > 0; i--) | 222 | for (i = next_power_of_2(pos) >> 2; i > 0; i >>= 1) |
217 | { | 223 | { |
218 | if (((pos / (1 << (i - 1))) % 2) == 0) | 224 | if (((pos / i) % 2) == 0) |
219 | ret = ret->left_child; | 225 | ret = ret->left_child; |
220 | else | 226 | else |
221 | ret = ret->right_child; | 227 | ret = ret->right_child; |