Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
splint'able
[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/error.h"
12 #include "heap_private.h"
13
14
15 /** \defgroup XBT_heap A generic heap data structure
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 /** \name Functions 
22  *  \ingroup XBT_heap
23  */
24 /* @{ */
25 /**
26  * \param init_size initial size of the heap
27  * \param free_func function to call on each element when you want to free
28  *             the whole heap (or NULL if nothing to do).
29  *
30  * Creates a new heap.
31  */
32 xbt_heap_t xbt_heap_new(int init_size, void_f_pvoid_t * const free_func)
33 {
34   xbt_heap_t H = xbt_new0(struct xbt_heap, 1);
35   H->size = init_size;
36   H->count = 0;
37   H->items = (xbt_heapItem_t) xbt_new0(struct xbt_heapItem, init_size);
38   H->free = free_func;
39   return H;
40 }
41
42 /**
43  * \param H poor victim
44  *
45  * kilkil a heap and its content
46  */
47 void xbt_heap_free(xbt_heap_t H)
48 {
49   int i;
50   if (H->free)
51     for (i = 0; i < H->count; i++)
52       H->free(H->items[i].content);
53   free(H->items);
54   free(H);
55   return;
56 }
57
58 /**
59  * \param H the heap we're working on
60  * \return the number of elements in the heap
61  */
62 int xbt_heap_size(xbt_heap_t H)
63 {
64   return (H->count);
65 }
66
67 /**
68  * \param H the heap we're working on
69  * \param content the object you want to add to the heap
70  * \param key the key associated to this object
71  *
72  * Add an element int the heap. The element with the smallest key is
73  * automatically moved at the top of the heap.
74  */
75 void xbt_heap_push(xbt_heap_t H, void *content, double key)
76 {
77   int count = ++(H->count);
78   int size = H->size;
79   xbt_heapItem_t item;
80   if (count > size) {
81     H->size = 2 * size + 1;
82     H->items =
83         (void *) realloc(H->items,
84                          (H->size) * sizeof(struct xbt_heapItem));
85   }
86   item = &(H->items[count - 1]);
87   item->key = key;
88   item->content = content;
89   xbt_heap_increaseKey(H, count - 1);
90   return;
91 }
92
93 /**
94  * \param H the heap we're working on
95  * \return the element with the smallest key
96  *
97  * Extracts from the heap and returns the element with the smallest
98  * key. The element with the next smallest key is automatically moved
99  * at the top of the heap.
100  */
101 void *xbt_heap_pop(xbt_heap_t H)
102 {
103   void *max;
104
105   if (H->count == 0)
106     return NULL;
107
108   max = CONTENT(H, 0);
109
110   H->items[0] = H->items[(H->count) - 1];
111   (H->count)--;
112   xbt_heap_maxHeapify(H);
113   if (H->count < H->size / 4 && H->size > 16) {
114     H->size = H->size / 2 + 1;
115     H->items =
116         (void *) realloc(H->items,
117                          (H->size) * sizeof(struct xbt_heapItem));
118   }
119   return max;
120 }
121
122 /**
123  * \param H the heap we're working on
124  *
125  * \return the smallest key in the heap without modifying the heap.
126  */
127 double xbt_heap_maxkey(xbt_heap_t H)
128 {
129   xbt_assert0(H->count != 0,"Empty heap");
130   return KEY(H, 0);
131 }
132
133 /**
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 }
189 /* @} */