Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
05c0a7af44db22d18d70f157dfb7a3d895bf0512
[simgrid.git] / src / xbt / heap.c
1 /*      $Id$     */
2
3 /* a generic and efficient heap                                             */
4
5 /* Copyright (c) 2004 Arnaud Legrand. All rights reserved.                  */
6
7 /* This program is free software; you can redistribute it and/or modify it
8  * under the terms of the license (GNU LGPL) which comes with this package. */
9
10 #include "xbt/sysdep.h"
11 #include "xbt/log.h"
12 #include "heap_private.h"
13
14
15 /** @addtogroup XBT_heap 
16  *  \brief This section describes the API to generic heap with O(log(n)) access.
17  */
18
19 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(heap, xbt, "Heap");
20
21 /**
22  * @brief Creates a new heap.
23  * \param init_size initial size of the heap
24  * \param free_func function to call on each element when you want to free
25  *             the whole heap (or NULL if nothing to do).
26  *
27  * Creates a new heap.
28  */
29 xbt_heap_t xbt_heap_new(int init_size, void_f_pvoid_t * const free_func)
30 {
31   xbt_heap_t H = xbt_new0(struct xbt_heap, 1);
32   H->size = init_size;
33   H->count = 0;
34   H->items = (xbt_heapItem_t) xbt_new0(struct xbt_heapItem, init_size);
35   H->free = free_func;
36   return H;
37 }
38
39 /**
40  * @brief kilkil a heap and its content
41  * @param H poor victim
42  */
43 void xbt_heap_free(xbt_heap_t H)
44 {
45   int i;
46   if (H->free)
47     for (i = 0; i < H->count; i++)
48       H->free(H->items[i].content);
49   free(H->items);
50   free(H);
51   return;
52 }
53
54 /**
55  * @brief returns the number of elements in the heap
56  * @param H the heap we're working on
57  * @return the number of elements in the heap
58  */
59 int xbt_heap_size(xbt_heap_t H)
60 {
61   return (H->count);
62 }
63
64 /**
65  * @brief Add an element into the heap.
66  * \param H the heap we're working on
67  * \param content the object you want to add to the heap
68  * \param key the key associated to this object
69  *
70  * The element with the smallest key is automatically moved at the top of the heap.
71  */
72 void xbt_heap_push(xbt_heap_t H, void *content, double key)
73 {
74   int count = ++(H->count);
75   int size = H->size;
76   xbt_heapItem_t item;
77   if (count > size) {
78     H->size = 2 * size + 1;
79     H->items =
80         (void *) realloc(H->items,
81                          (H->size) * sizeof(struct xbt_heapItem));
82   }
83   item = &(H->items[count - 1]);
84   item->key = key;
85   item->content = content;
86   xbt_heap_increaseKey(H, count - 1);
87   return;
88 }
89
90 /**
91  * @brief Extracts from the heap and returns the element with the smallest key.
92  * \param H the heap we're working on
93  * \return the element with the smallest key
94  *
95  * Extracts from the heap and returns the element with the smallest
96  * key. The element with the next smallest key is automatically moved
97  * at the top of the heap.
98  */
99 void *xbt_heap_pop(xbt_heap_t H)
100 {
101   void *max;
102
103   if (H->count == 0)
104     return NULL;
105
106   max = CONTENT(H, 0);
107
108   H->items[0] = H->items[(H->count) - 1];
109   (H->count)--;
110   xbt_heap_maxHeapify(H);
111   if (H->count < H->size / 4 && H->size > 16) {
112     H->size = H->size / 2 + 1;
113     H->items =
114         (void *) realloc(H->items,
115                          (H->size) * sizeof(struct xbt_heapItem));
116   }
117   return max;
118 }
119
120 /**
121  * @brief returns the smallest key in the heap (heap unchanged)
122  * \param H the heap we're working on
123  *
124  * \return the smallest key in the heap without modifying the heap.
125  */
126 double xbt_heap_maxkey(xbt_heap_t H)
127 {
128   xbt_assert0(H->count != 0,"Empty heap");
129   return KEY(H, 0);
130 }
131
132 /**
133  * @brief returns the value associated to the smallest key in the heap (heap unchanged)
134  * \param H the heap we're working on
135  *
136  * \return the value associated to the smallest key in the heap
137  * without modifying the heap.
138  */
139 void *xbt_heap_maxcontent(xbt_heap_t H)
140 {
141   xbt_assert0(H->count != 0,"Empty heap");
142   return CONTENT(H, 0);
143 }
144
145 /* <<<< private >>>>
146  * \param H the heap we're working on
147  * 
148  * Restores the heap property once an element has been deleted.
149  */
150 static void xbt_heap_maxHeapify(xbt_heap_t H)
151 {
152   int i = 0;
153   while (1) {
154     int greatest = i;
155     int l = LEFT(i);
156     int r = RIGHT(i);
157     int count = H->count;
158     if (l < count && KEY(H, l) < KEY(H, i))
159       greatest = l;
160     if (r < count && KEY(H, r) < KEY(H, greatest))
161       greatest = r;
162     if (greatest != i) {
163       struct xbt_heapItem tmp = H->items[i];
164       H->items[i] = H->items[greatest];
165       H->items[greatest] = tmp;
166       i = greatest;
167     } else
168       return;
169   }
170 }
171
172 /* <<<< private >>>>
173  * \param H the heap we're working on
174  * \param i an item position in the heap
175  * 
176  * Moves up an item at position i to its correct position. Works only
177  * when called from xbt_heap_push. Do not use otherwise.
178  */
179 static void xbt_heap_increaseKey(xbt_heap_t H, int i)
180 {
181   while (i > 0 && KEY(H, PARENT(i)) > KEY(H, i)) {
182     struct xbt_heapItem tmp = H->items[i];
183     H->items[i] = H->items[PARENT(i)];
184     H->items[PARENT(i)] = tmp;
185     i = PARENT(i);
186   }
187   return;
188 }