Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
some windows thread functions versus pthread for context API
[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 #include <stdio.h>
15
16
17 /** @addtogroup XBT_heap 
18  *  \brief This section describes the API to generic heap with O(log(n)) access.
19  */
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
76         int size = H->size;
77         xbt_heapItem_t item;
78         
79         if (count > size) {
80                 H->size = 2 * size + 1;
81                 H->items =(void *) realloc(H->items,(H->size) * sizeof(struct xbt_heapItem));
82         }
83         
84         item = &(H->items[count - 1]);
85         item->key = key;
86         item->content = content;
87         xbt_heap_increaseKey(H, count - 1);
88         return;
89 }
90
91 /**
92  * @brief Extracts from the heap and returns the element with the smallest key.
93  * \param H the heap we're working on
94  * \return the element with the smallest key
95  *
96  * Extracts from the heap and returns the element with the smallest
97  * key. The element with the next smallest key is automatically moved
98  * at the top of the heap.
99  */
100 void *xbt_heap_pop(xbt_heap_t H)
101 {
102   void *max;
103
104   if (H->count == 0)
105     return NULL;
106
107   max = CONTENT(H, 0);
108
109   H->items[0] = H->items[(H->count) - 1];
110   (H->count)--;
111   xbt_heap_maxHeapify(H);
112   if (H->count < H->size / 4 && H->size > 16) {
113     H->size = H->size / 2 + 1;
114     H->items =
115         (void *) realloc(H->items,
116                          (H->size) * sizeof(struct xbt_heapItem));
117   }
118   return max;
119 }
120
121 /**
122  * @brief returns the smallest key in the heap (heap unchanged)
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  * @brief returns the value associated to the smallest key in the heap (heap unchanged)
135  * \param H the heap we're working on
136  *
137  * \return the value associated to the smallest key in the heap
138  * without modifying the heap.
139  */
140 void *xbt_heap_maxcontent(xbt_heap_t H)
141 {
142   xbt_assert0(H->count != 0,"Empty heap");
143   return CONTENT(H, 0);
144 }
145
146 /* <<<< private >>>>
147  * \param H the heap we're working on
148  * 
149  * Restores the heap property once an element has been deleted.
150  */
151 static void xbt_heap_maxHeapify(xbt_heap_t H)
152 {
153   int i = 0;
154   while (1) {
155     int greatest = i;
156     int l = LEFT(i);
157     int r = RIGHT(i);
158     int count = H->count;
159     if (l < count && KEY(H, l) < KEY(H, i))
160       greatest = l;
161     if (r < count && KEY(H, r) < KEY(H, greatest))
162       greatest = r;
163     if (greatest != i) {
164       struct xbt_heapItem tmp = H->items[i];
165       H->items[i] = H->items[greatest];
166       H->items[greatest] = tmp;
167       i = greatest;
168     } else
169       return;
170   }
171 }
172
173 /* <<<< private >>>>
174  * \param H the heap we're working on
175  * \param i an item position in the heap
176  * 
177  * Moves up an item at position i to its correct position. Works only
178  * when called from xbt_heap_push. Do not use otherwise.
179  */
180 static void xbt_heap_increaseKey(xbt_heap_t H, int i)
181 {
182   while (i > 0 && KEY(H, PARENT(i)) > KEY(H, i)) {
183     struct xbt_heapItem tmp = H->items[i];
184     H->items[i] = H->items[PARENT(i)];
185     H->items[PARENT(i)] = tmp;
186     i = PARENT(i);
187   }
188   return;
189 }