From 32f13ca1c7961662a097b1b906f589a851bb3611 Mon Sep 17 00:00:00 2001 From: alegrand Date: Fri, 29 Oct 2004 18:22:13 +0000 Subject: [PATCH 1/1] First version of the xbt_heap, trying to follow the coding convention. git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@446 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- include/xbt/heap.h | 29 +++++++ src/xbt/heap.c | 161 +++++++++++++++++++++++++++++++++++++ src/xbt/heap_private.h | 29 +++++++ testsuite/xbt/heap_bench.c | 93 +++++++++++++++++++++ 4 files changed, 312 insertions(+) create mode 100644 include/xbt/heap.h create mode 100644 src/xbt/heap.c create mode 100644 src/xbt/heap_private.h create mode 100644 testsuite/xbt/heap_bench.c diff --git a/include/xbt/heap.h b/include/xbt/heap.h new file mode 100644 index 0000000000..ec853b622e --- /dev/null +++ b/include/xbt/heap.h @@ -0,0 +1,29 @@ +/* Authors: Arnaud Legrand */ + +/* This program is free software; you can redistribute it and/or modify it + under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef _XBT_HEAP_H +#define _XBT_HEAP_H + +typedef struct xbt_heap *xbt_heap_t; + +/* The following two definitions concern the type of the keys used for + the heaps. That should be handled via configure (FIXME). */ +typedef long double xbt_heap_float_t; +#define XBT_HEAP_FLOAT_T "%Lg" /* for printing purposes */ + + +/* pointer to a function freeing something (should be common to all .h : FIXME) */ +typedef void (void_f_pvoid_t) (void*); + +xbt_heap_t xbt_heap_new(int num, void_f_pvoid_t free_func); +void xbt_heap_free(xbt_heap_t H); + +void xbt_heap_push(xbt_heap_t H, void *content, xbt_heap_float_t key); +void *xbt_heap_pop(xbt_heap_t H); + +xbt_heap_float_t xbt_heap_maxkey(xbt_heap_t H); +void *xbt_heap_maxcontent(xbt_heap_t H); + +#endif /* _XBT_HEAP_H */ diff --git a/src/xbt/heap.c b/src/xbt/heap.c new file mode 100644 index 0000000000..917cd6ca8d --- /dev/null +++ b/src/xbt/heap.c @@ -0,0 +1,161 @@ +/* a generic and efficient heap */ + +/* Authors: Arnaud Legrand */ + +/* This program is free software; you can redistribute it and/or modify it + under the terms of the license (GNU LGPL) which comes with this package. */ + +#include "xbt_heap_private.h" + +/** + * xbt_heap_new: + * @init_size: initial size of the heap + * @free_func: function to call on each element when you want to free the whole heap (or NULL if nothing to do). + * + * Creates a new heap. + */ +xbt_heap_t xbt_heap_new(int init_size, void_f_pvoid_t * const free_func) +{ + xbt_heap_t H = calloc(1, sizeof(struct xbt_heap)); + H->size = init_size; + H->count = 0; + H->items = (xbt_heapItem_t) calloc(init_size, sizeof(struct xbt_heapItem)); + H->free = free; + return H; +} + +/** + * xbt_heap_free: + * @H: poor victim + * + * kilkil a heap and its content + */ +void xbt_heap_free(xbt_heap_t H) +{ + int i ; + if(H->free) + for(i=0;i < H->size;i++) + H->free(H->items[i].content); + free(H->items); + free(H); + return; +} + +/** + * xbt_heap_push: + * @H: the heap we're working on + * @content: the object you want to add to the heap + * @key: the key associated to this object + * + * Add an element int the heap. The element with the smallest key is + * automatically moved at the top of the heap. + */ +void xbt_heap_push(xbt_heap_t H, void *content, xbt_heap_float_t key) +{ + int count = ++(H->count); + int size = H->size; + xbt_heapItem_t item; + if (count > size) { + H->size = 2 * size + 1; + H->items = + (void *) realloc(H->items, + (H->size) * sizeof(struct xbt_heapItem)); + } + item = &(H->items[count - 1]); + item->key = key; + item->content = content; + xbt_heap_increaseKey(H, count - 1); + return; +} + +/** + * xbt_heap_pop: + * @H: the heap we're working on + * + * Extracts from the heap and returns the element with the smallest + * key. The element with the next smallest key is automatically moved + * at the top of the heap. + */ +void *xbt_heap_pop(xbt_heap_t H) +{ + void *max = CONTENT(H, 0); + H->items[0] = H->items[(H->count) - 1]; + (H->count)--; + xbt_heap_maxHeapify(H); + if (H->count < H->size / 4 && H->size > 16) { + H->size = H->size / 2 + 1; + H->items = + (void *) realloc(H->items, + (H->size) * sizeof(struct xbt_heapItem)); + } + return max; +} + +/** + * xbt_heap_maxkey: + * @H: the heap we're working on + * + * Returns the smallest key in the heap without modifying the heap. + */ +xbt_heap_float_t xbt_heap_maxkey(xbt_heap_t H) +{ + return KEY(H, 0); +} + +/** + * xbt_heap_maxcontent: + * @H: the heap we're working on + * + * Returns the value associated to the smallest key in the heap + * without modifying the heap. + */ +void *xbt_heap_maxcontent(xbt_heap_t H) +{ + return CONTENT(H, 0); +} + +/** + * xbt_heap_maxcontent: + * @H: the heap we're working on + * + * Restores the heap property once an element has been deleted. + */ +void xbt_heap_maxHeapify(xbt_heap_t H) +{ + int i=0; + while(1) { + int greatest = i; + int l = LEFT(i); + int r = RIGHT(i); + int count = H->count; + if (l < count && KEY(H, l) < KEY(H, i)) + greatest = l; + if (r < count && KEY(H, r) < KEY(H, greatest)) + greatest = r; + if (greatest != i) { + struct xbt_heapItem tmp = H->items[i]; + H->items[i] = H->items[greatest]; + H->items[greatest] = tmp; + i=greatest; + } else return; + } +} + +/** + * xbt_heap_maxcontent: + * @H: the heap we're working on + * @i: an item position in the heap + * + * Moves up an item at position i to its correct position. Works only + * when called from xbt_heap_push. Do not use otherwise. + */ +void xbt_heap_increaseKey(xbt_heap_t H, int i) +{ + while (i > 0 && KEY(H, PARENT(i)) > KEY(H, i)) { + struct xbt_heapItem tmp = H->items[i]; + H->items[i] = H->items[PARENT(i)]; + H->items[PARENT(i)] = tmp; + i = PARENT(i); + } + return; +} diff --git a/src/xbt/heap_private.h b/src/xbt/heap_private.h new file mode 100644 index 0000000000..40928142ad --- /dev/null +++ b/src/xbt/heap_private.h @@ -0,0 +1,29 @@ +/* Authors: Arnaud Legrand */ + +/* This program is free software; you can redistribute it and/or modify it + under the terms of the license (GNU LGPL) which comes with this package. */ + +#include +#include "xbt_heap.h" + +typedef struct xbt_heapItem { + void *content; + xbt_heap_float_t key; +} s_xbt_heapItem_t ,*xbt_heapItem_t; + +typedef struct xbt_heap { + int size; + int count; + xbt_heapItem_t items; + void_f_pvoid_t *free; +} s_xbt_heap_t; + +#define PARENT(i) i/2 +#define LEFT(i) 2*i +#define RIGHT(i) 2*i+1 + +#define KEY(H,i) ((H->items)[i]).key +#define CONTENT(H,i) ((H->items)[i]).content + +void xbt_heap_maxHeapify(xbt_heap_t H); +void xbt_heap_increaseKey(xbt_heap_t H, int i); diff --git a/testsuite/xbt/heap_bench.c b/testsuite/xbt/heap_bench.c new file mode 100644 index 0000000000..4a7449a1a3 --- /dev/null +++ b/testsuite/xbt/heap_bench.c @@ -0,0 +1,93 @@ +#include +#include +#include +#include "xbt_heap.h" + +#define MAX_TEST 1000000 + +/* Pour le bench */ +long us_time(void); +long us_time(void) +{ + struct timeval start; + gettimeofday(&start, NULL); + + return (start.tv_sec * 1000000 + start.tv_usec); +} + +int compare_xbt_heap_float_t (const void *a, const void *b); +void test_heap_validity(int size); +void test_heap_mean_operation(int size); + +int compare_xbt_heap_float_t (const void *a, const void *b) +{ + xbt_heap_float_t pa, pb; + + pa=* ((xbt_heap_float_t *)a); + pb=* ((xbt_heap_float_t *)b); + + if(pa>pb) return 1; + if(pa==pb) return 0; + return -1; +} + +void test_heap_validity(int size) +{ + xbt_heap_t heap = xbt_heap_new(size,NULL); + xbt_heap_float_t *tab = calloc(size,sizeof(xbt_heap_float_t)); + int i; + + for(i=0; i