]>
Commit | Line | Data |
---|---|---|
ad19eafb | 1 | |
2 | /* | |
262a0e14 | 3 | * $Id$ |
ad19eafb | 4 | * |
5 | * AUTHOR: John Dilley, Hewlett Packard | |
6 | * | |
2b6662ba | 7 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
ad19eafb | 8 | * ---------------------------------------------------------- |
9 | * | |
2b6662ba | 10 | * Squid is the result of efforts by numerous individuals from |
11 | * the Internet community; see the CONTRIBUTORS file for full | |
12 | * details. Many organizations have provided support for Squid's | |
13 | * development; see the SPONSORS file for full details. Squid is | |
14 | * Copyrighted (C) 2001 by the Regents of the University of | |
15 | * California; see the COPYRIGHT file for full details. Squid | |
16 | * incorporates software developed and/or copyrighted by other | |
17 | * sources; see the CREDITS file for full details. | |
ad19eafb | 18 | * |
19 | * This program is free software; you can redistribute it and/or modify | |
20 | * it under the terms of the GNU General Public License as published by | |
21 | * the Free Software Foundation; either version 2 of the License, or | |
22 | * (at your option) any later version. | |
26ac0430 | 23 | * |
ad19eafb | 24 | * This program is distributed in the hope that it will be useful, |
25 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
26 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
27 | * GNU General Public License for more details. | |
26ac0430 | 28 | * |
ad19eafb | 29 | * You should have received a copy of the GNU General Public License |
30 | * along with this program; if not, write to the Free Software | |
31 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. | |
32 | * | |
33 | */ | |
34 | ||
35 | /**************************************************************************** | |
36 | * Heap implementation | |
9bc73deb | 37 | * Copyright (C) 1999 by Hewlett Packard |
ad19eafb | 38 | ****************************************************************************/ |
39 | ||
40 | #include "config.h" | |
2d72d4fd | 41 | #include "heap.h" |
ad19eafb | 42 | |
43 | #if HAVE_STDLIB_H | |
44 | #include <stdlib.h> | |
45 | #endif | |
46 | #if HAVE_ASSERT_H | |
47 | #include <assert.h> | |
48 | #endif | |
49 | #if HAVE_STRING_H | |
50 | #include <string.h> | |
51 | #endif | |
52 | #if HAVE_STDIO_H | |
53 | #include <stdio.h> | |
54 | #endif | |
55 | ||
56 | #include "heap.h" | |
7e3ce7b9 | 57 | #include "util.h" |
ad19eafb | 58 | |
59 | /* | |
60 | * Hacks for non-synchronized heap implementation. | |
61 | */ | |
62 | #define mutex_lock(m) (void)0 | |
63 | #define mutex_unlock(m) (void)0 | |
64 | #define mutex_trylock(m) (void)0 | |
65 | #define mutex_init(m) ((m)=123456) | |
66 | ||
26ac0430 | 67 | /* |
ad19eafb | 68 | * Private function prototypes. |
69 | */ | |
70 | static void _heap_ify_up(heap * hp, heap_node * elm); | |
71 | static void _heap_ify_down(heap * hp, heap_node * elm); | |
72 | static int _heap_should_grow(heap * hp); | |
73 | static void _heap_grow(heap * hp); | |
74 | static void _heap_swap_element(heap * hp, heap_node * elm1, heap_node * elm2); | |
75 | static int _heap_node_exist(heap * hp, int id); | |
76 | ||
77 | #ifdef HEAP_DEBUG | |
78 | void _heap_print_tree(heap * hp, heap_node * node); | |
79 | #endif /* HEAP_DEBUG */ | |
80 | ||
81 | #define Left(x) (2 * (x) + 1) | |
82 | #define Right(x) (2 * (x) + 2) | |
83 | #define Parent(x) ((int)((x)-1)/2) | |
84 | ||
85 | #define Threshold 10000 | |
86 | #define NormalRate 2 | |
87 | #define SlowRate 1.5 | |
88 | #define MinSize 32 | |
89 | ||
90 | /**************************************************************************** | |
91 | * Public functions | |
92 | ****************************************************************************/ | |
93 | ||
94 | /* | |
95 | * Return a newly created heap. INITSIZE is the initial size of the heap. | |
96 | */ | |
97 | heap * | |
98 | new_heap(int initSize, heap_key_func gen_key) | |
99 | { | |
7e3ce7b9 | 100 | heap *hp = xmalloc(sizeof(*hp)); |
ad19eafb | 101 | assert(hp != NULL); |
102 | ||
9bc73deb | 103 | if (initSize <= 0) |
26ac0430 | 104 | initSize = MinSize; |
7e3ce7b9 | 105 | hp->nodes = xcalloc(initSize, sizeof(heap_node *)); |
ad19eafb | 106 | assert(hp->nodes != NULL); |
107 | ||
ad19eafb | 108 | hp->size = initSize; |
109 | hp->last = 0; | |
110 | hp->gen_key = gen_key; | |
111 | hp->age = 0; | |
112 | ||
113 | return hp; | |
114 | } | |
115 | ||
116 | ||
117 | /* | |
118 | * Free memory used by a heap. Does not free the metadata pointed to by the | |
119 | * heap nodes, only the heap's internal memory. | |
120 | */ | |
121 | void | |
122 | delete_heap(heap * hp) | |
123 | { | |
124 | int i; | |
137a13ea | 125 | assert(hp != NULL); |
ad19eafb | 126 | for (i = 0; i < hp->last; i++) { |
26ac0430 | 127 | xfree(hp->nodes[i]); |
ad19eafb | 128 | } |
7e3ce7b9 | 129 | xfree(hp->nodes); |
130 | xfree(hp); | |
ad19eafb | 131 | } |
132 | ||
133 | /* | |
7e3ce7b9 | 134 | * Insert DAT based on KY into HP maintaining the heap property. |
135 | * Return the newly inserted heap node. The fields of ELM other | |
136 | * than ID are never changed until ELM is deleted from HP, i.e. | |
137 | * caller can assume that the heap node always exist at the same | |
138 | * place in memory unless heap_delete or heap_extractmin is called | |
139 | * on that node. This function exposes the heap's internal data | |
140 | * structure to the caller. This is required in order to do O(lgN) | |
141 | * deletion. | |
ad19eafb | 142 | */ |
143 | heap_node * | |
144 | heap_insert(heap * hp, void *dat) | |
145 | { | |
7e3ce7b9 | 146 | heap_node *elm = xmalloc(sizeof(*elm)); |
ad19eafb | 147 | |
148 | elm->key = heap_gen_key(hp, dat); | |
149 | elm->data = dat; | |
150 | ||
151 | if (_heap_should_grow(hp)) | |
26ac0430 | 152 | _heap_grow(hp); |
ad19eafb | 153 | |
154 | hp->nodes[hp->last] = elm; | |
155 | elm->id = hp->last; | |
156 | hp->last += 1; | |
157 | ||
158 | _heap_ify_up(hp, elm); | |
159 | ||
160 | return elm; | |
161 | } | |
162 | ||
163 | ||
164 | /* | |
165 | * Delete ELM while maintaining the heap property. ELM may be modified. | |
166 | * Assumes that ELM is not NULL and frees it. Returns the data pointed to | |
167 | * in, which the caller must free if necessary. | |
168 | */ | |
169 | heap_t | |
170 | heap_delete(heap * hp, heap_node * elm) | |
171 | { | |
172 | heap_node *lastNode; | |
173 | heap_t data = elm->data; | |
174 | ||
175 | assert(_heap_node_exist(hp, hp->last - 1)); | |
176 | ||
177 | lastNode = hp->nodes[hp->last - 1]; | |
178 | _heap_swap_element(hp, lastNode, elm); | |
179 | heap_extractlast(hp); | |
180 | ||
7e3ce7b9 | 181 | if (elm == lastNode) { |
26ac0430 AJ |
182 | /* |
183 | * lastNode just got freed, so don't access it in the next | |
184 | * block. | |
185 | */ | |
186 | (void) 0; | |
7e3ce7b9 | 187 | } else if (hp->last > 0) { |
26ac0430 AJ |
188 | if (lastNode->key < hp->nodes[Parent(lastNode->id)]->key) |
189 | _heap_ify_up(hp, lastNode); /* COOL! */ | |
190 | _heap_ify_down(hp, lastNode); | |
ad19eafb | 191 | } |
192 | return data; | |
193 | } | |
194 | ||
26ac0430 | 195 | /* |
ad19eafb | 196 | * Delete the last element (leaf) out of the heap. Does not require a |
197 | * heapify operation. | |
198 | */ | |
199 | ||
200 | #ifndef heap_gen_key | |
201 | /* | |
202 | * Function to generate keys. See macro definition in heap.h. | |
203 | */ | |
204 | heap_key | |
205 | heap_gen_key(heap * hp, heap_t dat) | |
206 | { | |
207 | return hp->gen_key(dat, hp->age); | |
208 | } | |
209 | #endif /* heap_gen_key */ | |
210 | ||
211 | ||
26ac0430 | 212 | /* |
ad19eafb | 213 | * Returns the data of the node with the largest KEY value and removes that |
214 | * node from the heap. Returns NULL if the heap was empty. | |
215 | */ | |
216 | heap_t | |
217 | heap_extractmin(heap * hp) | |
218 | { | |
219 | heap_t data; | |
220 | ||
221 | if (hp->last <= 0) | |
26ac0430 | 222 | return NULL; |
ad19eafb | 223 | |
224 | mutex_lock(hp->lock); | |
225 | ||
226 | data = hp->nodes[0]->data; | |
227 | heap_delete(hp, hp->nodes[0]); /* Delete the root */ | |
228 | ||
229 | mutex_unlock(hp->lock); | |
230 | ||
231 | return data; | |
232 | } | |
233 | ||
234 | ||
26ac0430 | 235 | /* |
ad19eafb | 236 | * Remove the last node in HP. Frees the heap internal structure and |
237 | * returns the data pointes to by the last node. | |
238 | */ | |
239 | heap_t | |
240 | heap_extractlast(heap * hp) | |
241 | { | |
242 | heap_t data; | |
243 | assert(_heap_node_exist(hp, hp->last - 1)); | |
244 | hp->last -= 1; | |
245 | data = hp->nodes[hp->last]->data; | |
7e3ce7b9 | 246 | xfree(hp->nodes[hp->last]); |
ad19eafb | 247 | return data; |
248 | } | |
249 | ||
250 | ||
26ac0430 | 251 | /* |
ad19eafb | 252 | * The semantics of this routine is the same as the followings: |
253 | * heap_delete(hp, elm); | |
254 | * heap_insert(hp, dat); | |
255 | * Returns the old data object from elm (the one being replaced). The | |
256 | * caller must free this as necessary. | |
257 | */ | |
258 | heap_t | |
259 | heap_update(heap * hp, heap_node * elm, void *dat) | |
260 | { | |
261 | heap_t old = elm->data; | |
262 | heap_key ky = heap_gen_key(hp, dat); | |
263 | ||
264 | elm->key = ky; | |
265 | elm->data = dat; | |
266 | ||
267 | if (elm->key < hp->nodes[Parent(elm->id)]->key) | |
26ac0430 | 268 | _heap_ify_up(hp, elm); |
ad19eafb | 269 | _heap_ify_down(hp, elm); |
270 | ||
271 | return old; | |
272 | } | |
273 | ||
274 | ||
26ac0430 | 275 | /* |
ad19eafb | 276 | * A pointer to the root node's DATA. |
277 | */ | |
278 | void * | |
279 | heap_peepmin(heap * hp) | |
280 | { | |
281 | assert(_heap_node_exist(hp, 0)); | |
282 | return hp->nodes[0]->data; | |
283 | } | |
284 | ||
285 | ||
26ac0430 | 286 | /* |
ad19eafb | 287 | * The KEY of the root node. |
288 | */ | |
289 | heap_key | |
290 | heap_peepminkey(heap * hp) | |
291 | { | |
292 | assert(_heap_node_exist(hp, 0)); | |
293 | return hp->nodes[0]->key; | |
294 | } | |
295 | ||
296 | ||
26ac0430 | 297 | /* |
ad19eafb | 298 | * Same as heap_peep except that this return the KEY of the node. |
299 | * Only meant for iteration. | |
300 | */ | |
301 | heap_key | |
302 | heap_peepkey(heap * hp, int n) | |
303 | { | |
304 | assert(_heap_node_exist(hp, n)); | |
305 | return hp->nodes[n]->key; | |
306 | } | |
307 | ||
308 | ||
26ac0430 | 309 | /* |
ad19eafb | 310 | * A pointer to Nth node's DATA. The caller can iterate through HP by |
311 | * calling this routine. eg. Caller can execute the following code: | |
312 | * for(i = 0; i < heap_nodes(hp); i++) | |
313 | * data = heap_peep(hp, i); | |
314 | */ | |
315 | void * | |
316 | heap_peep(heap * hp, int n) | |
317 | { | |
318 | void *data; | |
319 | assert(_heap_node_exist(hp, n)); | |
320 | data = hp->nodes[n]->data; | |
321 | return data; | |
322 | } | |
323 | ||
324 | ||
325 | #ifndef heap_nodes | |
26ac0430 | 326 | /* |
ad19eafb | 327 | * Current number of nodes in HP. |
328 | */ | |
329 | int | |
330 | heap_nodes(heap * hp) | |
331 | { | |
332 | return hp->last; | |
333 | } | |
334 | #endif /* heap_nodes */ | |
335 | ||
336 | ||
337 | #ifndef heap_empty | |
26ac0430 | 338 | /* |
ad19eafb | 339 | * Determine if the heap is empty. Returns 1 if HP has no elements and 0 |
340 | * otherwise. | |
341 | */ | |
342 | int | |
343 | heap_empty(heap * hp) | |
344 | { | |
345 | return (hp->last <= 0) ? 1 : 0; | |
346 | } | |
347 | #endif /* heap_empty */ | |
348 | ||
349 | /****************** Private Functions *******************/ | |
350 | ||
26ac0430 | 351 | /* |
ad19eafb | 352 | * Maintain the heap order property (parent is smaller than children) which |
353 | * may only be violated at ELM downwards. Assumes caller has locked the heap. | |
354 | */ | |
355 | static void | |
356 | _heap_ify_down(heap * hp, heap_node * elm) | |
357 | { | |
358 | heap_node *kid; | |
359 | int left = 0, right = 0; | |
360 | int true = 1; | |
361 | while (true) { | |
26ac0430 AJ |
362 | left = Left(elm->id); |
363 | right = Right(elm->id); | |
364 | if (!_heap_node_exist(hp, left)) { | |
365 | /* At the bottom of the heap (no child). */ | |
366 | ||
367 | assert(!_heap_node_exist(hp, right)); | |
368 | break; | |
369 | } else if (!_heap_node_exist(hp, right)) | |
370 | /* Only left child exists. */ | |
371 | ||
372 | kid = hp->nodes[left]; | |
373 | else { | |
374 | if (hp->nodes[right]->key < hp->nodes[left]->key) | |
375 | kid = hp->nodes[right]; | |
376 | else | |
377 | kid = hp->nodes[left]; | |
378 | } | |
379 | if (elm->key <= kid->key) | |
380 | break; | |
381 | _heap_swap_element(hp, kid, elm); | |
ad19eafb | 382 | } |
383 | } | |
384 | ||
385 | ||
26ac0430 | 386 | /* |
ad19eafb | 387 | * Maintain the heap property above ELM. Caller has locked the heap. |
388 | */ | |
389 | static void | |
390 | _heap_ify_up(heap * hp, heap_node * elm) | |
391 | { | |
392 | heap_node *parentNode; | |
393 | while (elm->id > 0) { | |
26ac0430 AJ |
394 | parentNode = hp->nodes[Parent(elm->id)]; |
395 | if (parentNode->key <= elm->key) | |
396 | break; | |
397 | _heap_swap_element(hp, parentNode, elm); /* Demote the parent. */ | |
ad19eafb | 398 | } |
399 | } | |
400 | ||
401 | ||
26ac0430 | 402 | /* |
ad19eafb | 403 | * Swap the position of ELM1 and ELM2 in heap structure. Their IDs are also |
26ac0430 | 404 | * swapped. |
ad19eafb | 405 | */ |
406 | static void | |
407 | _heap_swap_element(heap * hp, heap_node * elm1, heap_node * elm2) | |
408 | { | |
409 | int elm1Id = elm1->id; | |
410 | elm1->id = elm2->id; | |
411 | elm2->id = elm1Id; | |
412 | hp->nodes[elm1->id] = elm1; | |
413 | hp->nodes[elm2->id] = elm2; | |
414 | } | |
415 | ||
416 | ||
417 | ||
418 | #ifdef NOTDEF | |
26ac0430 | 419 | /* |
ad19eafb | 420 | * Copy KEY and DATA fields of SRC to DEST. ID field is NOT copied. |
421 | */ | |
422 | static void | |
423 | _heap_copy_element(heap_node * src, heap_node * dest) | |
424 | { | |
425 | dest->key = src->key; | |
426 | dest->data = src->data; | |
427 | } | |
428 | ||
429 | #endif /* NOTDEF */ | |
430 | ||
431 | ||
26ac0430 | 432 | /* |
ad19eafb | 433 | * True if HP needs to be grown in size. |
434 | */ | |
435 | static int | |
436 | _heap_should_grow(heap * hp) | |
437 | { | |
438 | if (hp->size <= hp->last) | |
26ac0430 | 439 | return 1; |
ad19eafb | 440 | return 0; |
441 | } | |
442 | ||
443 | ||
26ac0430 | 444 | /* |
ad19eafb | 445 | * Grow HP. |
446 | */ | |
447 | static void | |
448 | _heap_grow(heap * hp) | |
449 | { | |
450 | int newSize; | |
451 | ||
452 | if (hp->size > Threshold) | |
26ac0430 | 453 | newSize = hp->size * SlowRate; |
ad19eafb | 454 | else |
26ac0430 | 455 | newSize = hp->size * NormalRate; |
ad19eafb | 456 | |
7e3ce7b9 | 457 | hp->nodes = xrealloc(hp->nodes, newSize * sizeof(heap_node *)); |
44e08383 | 458 | #if COMMENTED_OUT |
459 | for (i = 0; i < hp->size; i++) | |
26ac0430 | 460 | newNodes[i] = hp->nodes[i]; |
7e3ce7b9 | 461 | xfree(hp->nodes); |
44e08383 | 462 | hp->nodes = newNodes; |
463 | #endif | |
ad19eafb | 464 | hp->size = newSize; |
465 | } | |
466 | ||
467 | ||
26ac0430 | 468 | /* |
ad19eafb | 469 | * True if a node with ID exists in HP. |
470 | */ | |
471 | static int | |
472 | _heap_node_exist(heap * hp, int id) | |
473 | { | |
474 | if ((id >= hp->last) || (id < 0) || (hp->nodes[id] == NULL)) | |
26ac0430 | 475 | return 0; |
ad19eafb | 476 | return 1; |
477 | } | |
478 | ||
479 | /**************************************************************************** | |
480 | * Printing and debug functions | |
481 | ****************************************************************************/ | |
482 | ||
26ac0430 AJ |
483 | /* |
484 | * Print the heap in element order, id..last. | |
ad19eafb | 485 | */ |
2d72d4fd | 486 | static void |
ad19eafb | 487 | heap_print_inorder(heap * hp, int id) |
488 | { | |
489 | while (id < hp->last) { | |
26ac0430 AJ |
490 | printf("%d\tKey = %.04f\n", id, hp->nodes[id]->key); |
491 | id++; | |
ad19eafb | 492 | } |
493 | } | |
494 | ||
495 | /* | |
496 | * Returns 1 if HP maintians the heap property and 0 otherwise. | |
497 | */ | |
498 | int | |
499 | verify_heap_property(heap * hp) | |
500 | { | |
501 | int i = 0; | |
502 | int correct = 1; | |
503 | for (i = 0; i < hp->last / 2; i++) { | |
26ac0430 AJ |
504 | correct = 1; |
505 | if (_heap_node_exist(hp, Left(i))) | |
506 | if (hp->nodes[i]->key > hp->nodes[Left(i)]->key) | |
507 | correct = 0; | |
508 | if (_heap_node_exist(hp, Right(i))) | |
509 | if (hp->nodes[i]->key > hp->nodes[Right(i)]->key) | |
510 | correct = 0; | |
511 | if (!correct) { | |
512 | printf("verifyHeap: violated at %d", i); | |
513 | heap_print_inorder(hp, 0); | |
514 | break; | |
515 | } | |
ad19eafb | 516 | } |
517 | return correct; | |
518 | } | |
519 | ||
520 | #ifdef MEASURE_HEAP_SKEW | |
521 | ||
522 | /**************************************************************************** | |
523 | * Heap skew computation | |
524 | ****************************************************************************/ | |
525 | ||
526 | int | |
527 | compare_heap_keys(const void *a, const void *b) | |
528 | { | |
529 | heap_node **an = (heap_node **) a; | |
530 | heap_node **bn = (heap_node **) b; | |
531 | float cmp = (*an)->key - (*bn)->key; | |
532 | if (cmp < 0) | |
26ac0430 | 533 | return -1; |
ad19eafb | 534 | else |
26ac0430 | 535 | return 1; |
ad19eafb | 536 | } |
537 | ||
538 | /* | |
539 | * Compute the heap skew for HEAP, a measure of how out-of-order the | |
540 | * elements in the heap are. The skew of a heap node is the difference | |
541 | * between its current position in the heap and where it would be if the | |
542 | * heap were in sorted order. To compute this we have to sort the heap. At | |
543 | * the end if the flag REPLACE is non-zero the heap will be returned in | |
544 | * sorted order (with skew == 0). Note: using REPLACE does not help the | |
545 | * performance of the heap, so only do this if you really want to have a | |
546 | * sorted heap. It is faster not to replace. | |
547 | */ | |
548 | float | |
549 | calc_heap_skew(heap * heap, int replace) | |
550 | { | |
551 | heap_node **nodes; | |
552 | long id, diff, skew = 0; | |
553 | #ifdef HEAP_DEBUG_SKEW | |
554 | long skewsq = 0; | |
555 | #endif /* HEAP_DEBUG_SKEW */ | |
556 | float norm = 0; | |
557 | unsigned long max; | |
558 | ||
26ac0430 | 559 | /* |
ad19eafb | 560 | * Lock the heap to copy it. If replacing it need to keep the heap locked |
561 | * until we are all done. | |
562 | */ | |
563 | mutex_lock(hp->lock); | |
564 | ||
565 | max = heap_nodes(heap); | |
566 | ||
26ac0430 | 567 | /* |
ad19eafb | 568 | * Copy the heap nodes to a new storage area for offline sorting. |
569 | */ | |
7e3ce7b9 | 570 | nodes = xmalloc(max * sizeof(heap_node *)); |
ad19eafb | 571 | memcpy(nodes, heap->nodes, max * sizeof(heap_node *)); |
572 | ||
573 | if (replace == 0) { | |
26ac0430 AJ |
574 | /* |
575 | * Unlock the heap to allow updates from other threads before the sort. | |
576 | * This allows other heap operations to proceed concurrently with the | |
577 | * heap skew computation on the heap at the time of the call ... | |
578 | */ | |
579 | mutex_unlock(hp->lock); | |
ad19eafb | 580 | } |
581 | qsort(nodes, max, sizeof(heap_node *), compare_heap_keys); | |
582 | ||
583 | for (id = 0; id < max; id++) { | |
26ac0430 AJ |
584 | diff = id - nodes[id]->id; |
585 | skew += abs(diff); | |
ad19eafb | 586 | |
587 | #ifdef HEAP_DEBUG_SKEW | |
26ac0430 | 588 | skewsq += diff * diff; |
ad19eafb | 589 | #ifdef HEAP_DEBUG_ALL |
26ac0430 | 590 | printf("%d\tKey = %f, diff = %d\n", id, nodes[id]->key, diff); |
ad19eafb | 591 | #endif /* HEAP_DEBUG */ |
592 | #endif /* HEAP_DEBUG_SKEW */ | |
593 | } | |
594 | ||
595 | if (replace != 0) { | |
26ac0430 AJ |
596 | /* |
597 | * Replace the original heap with the newly sorted heap and let it | |
598 | * continue. Then compute the skew using the copy of the previous heap | |
599 | * which we maintain as private data. | |
600 | */ | |
601 | memcpy(heap->nodes, nodes, max * sizeof(heap_node *)); | |
602 | ||
603 | for (id = 0; id < max; id++) { | |
604 | /* | |
605 | * Fix up all the ID values in the copied nodes. | |
606 | */ | |
607 | heap->nodes[id]->id = id; | |
608 | } | |
609 | ||
610 | mutex_unlock(hp->lock); | |
ad19eafb | 611 | } |
26ac0430 | 612 | /* |
ad19eafb | 613 | * The skew value is normalized to a range of [0..1]; the distribution |
614 | * appears to be a skewed Gaussian distribution. For random insertions | |
615 | * into a heap the normalized skew will be slightly less than 0.5. The | |
616 | * maximum value of skew/N^2 (for any value of N) is about 0.39 and is | |
617 | * fairly stable. | |
618 | */ | |
619 | norm = skew * 2.56 / (max * max); | |
620 | ||
26ac0430 | 621 | /* |
ad19eafb | 622 | * Free the nodes array; note this is just an array of pointers, not data! |
623 | */ | |
7e3ce7b9 | 624 | xfree(nodes); |
ad19eafb | 625 | return norm; |
626 | } | |
627 | ||
628 | #endif /* MEASURE_HEAP_SKEW */ |