← Back to branch summary

~ubuntu-branches/debian/stretch/gnome-builder/stretch

« back to all changes in this revision

Viewing changes to contrib/egg/egg-heap.c

  • Committer: Package Import Robot
  • Author(s): Andreas Henriksson
  • Date: 2015-10-11 12:38:45 UTC
  • Revision ID: package-import@ubuntu.com-20151011123845-a0hvkz01se0p1p5a
Tags: upstream-3.16.3
Import upstream version 3.16.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/egg/egg-heap.c
 
1
/* egg-heap.c
 
2
 *
 
3
 * Copyright (C) 2014 Christian Hergert <christian@hergert.me>
 
4
 *
 
5
 * This file is free software; you can redistribute it and/or
 
6
 * modify it under the terms of the GNU Lesser General Public
 
7
 * License as published by the Free Software Foundation; either
 
8
 * version 2.1 of the License, or (at your option) any later version.
 
9
 *
 
10
 * This file is distributed in the hope that it will be useful,
 
11
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
13
 * Lesser General Public License for more details.
 
14
 *
 
15
 * You should have received a copy of the GNU General Public License
 
16
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
17
 */
 
18
 
 
19
#define G_LOG_DOMAIN "egg-heap"
 
20
 
 
21
#include <string.h>
 
22
 
 
23
#include "egg-heap.h"
 
24
 
 
25
/**
 
26
 * SECTION:egg-heap
 
27
 * @title: Heaps
 
28
 * @short_description: efficient priority queues using min/max heaps
 
29
 *
 
30
 * Heaps are similar to a partially sorted tree but implemented as an
 
31
 * array. They allow for efficient O(1) lookup of the highest priority
 
32
 * item as it will always be the first item of the array.
 
33
 *
 
34
 * To create a new heap use egg_heap_new().
 
35
 *
 
36
 * To add items to the heap, use egg_heap_insert_val() or
 
37
 * egg_heap_insert_vals() to insert in bulk.
 
38
 *
 
39
 * To access an item in the heap, use egg_heap_index().
 
40
 *
 
41
 * To remove an arbitrary item from the heap, use egg_heap_extract_index().
 
42
 *
 
43
 * To remove the highest priority item in the heap, use egg_heap_extract().
 
44
 *
 
45
 * To free a heap, use egg_heap_unref().
 
46
 *
 
47
 * Here is an example that stores integers in a #EggHeap:
 
48
 * |[<!-- language="C" -->
 
49
 * static int
 
50
 * cmpint (gconstpointer a,
 
51
 *         gconstpointer b)
 
52
 * {
 
53
 *   return *(const gint *)a - *(const gint *)b;
 
54
 * }
 
55
 *
 
56
 * int
 
57
 * main (gint   argc,
 
58
 *       gchar *argv[])
 
59
 * {
 
60
 *   EggHeap *heap;
 
61
 *   gint i;
 
62
 *   gint v;
 
63
 *
 
64
 *   heap = egg_heap_new (sizeof (gint), cmpint);
 
65
 *
 
66
 *   for (i = 0; i < 10000; i++)
 
67
 *     egg_heap_insert_val (heap, i);
 
68
 *   for (i = 0; i < 10000; i++)
 
69
 *     egg_heap_extract (heap, &v);
 
70
 *
 
71
 *   egg_heap_unref (heap);
 
72
 * }
 
73
 * ]|
 
74
 */
 
75
 
 
76
#define MIN_HEAP_SIZE 16
 
77
 
 
78
/*
 
79
 * Based upon Mastering Algorithms in C by Kyle Loudon.
 
80
 * Section 10 - Heaps and Priority Queues.
 
81
 */
 
82
 
 
83
typedef struct _EggHeapReal EggHeapReal;
 
84
 
 
85
struct _EggHeapReal
 
86
{
 
87
  gchar          *data;
 
88
  gsize           len;
 
89
  volatile gint   ref_count;
 
90
  guint           element_size;
 
91
  gsize           allocated_len;
 
92
  GCompareFunc    compare;
 
93
  gchar           tmp[0];
 
94
};
 
95
 
 
96
#define heap_parent(npos)   (((npos)-1)/2)
 
97
#define heap_left(npos)     (((npos)*2)+1)
 
98
#define heap_right(npos)    (((npos)*2)+2)
 
99
#define heap_index(h,i)     ((h)->data + (i * (h)->element_size))
 
100
#define heap_compare(h,a,b) ((h)->compare(heap_index(h,a), heap_index(h,b)))
 
101
#define heap_swap(h,a,b)                                                \
 
102
  G_STMT_START {                                                        \
 
103
      memcpy ((h)->tmp, heap_index (h, a), (h)->element_size);          \
 
104
      memcpy (heap_index (h, a), heap_index (h, b), (h)->element_size); \
 
105
      memcpy (heap_index (h, b), (h)->tmp, (h)->element_size);          \
 
106
 } G_STMT_END
 
107
 
 
108
EggHeap *
 
109
egg_heap_new (guint        element_size,
 
110
              GCompareFunc compare_func)
 
111
{
 
112
    EggHeapReal *real;
 
113
 
 
114
    g_return_val_if_fail (element_size, NULL);
 
115
    g_return_val_if_fail (compare_func, NULL);
 
116
 
 
117
    real = g_malloc_n (1, sizeof (EggHeapReal) + element_size);
 
118
    real->data = NULL;
 
119
    real->len = 0;
 
120
    real->ref_count = 1;
 
121
    real->element_size = element_size;
 
122
    real->allocated_len = 0;
 
123
    real->compare = compare_func;
 
124
 
 
125
    return (EggHeap *)real;
 
126
}
 
127
 
 
128
EggHeap *
 
129
egg_heap_ref (EggHeap *heap)
 
130
{
 
131
  EggHeapReal *real = (EggHeapReal *)heap;
 
132
 
 
133
  g_return_val_if_fail (heap, NULL);
 
134
  g_return_val_if_fail (real->ref_count, NULL);
 
135
 
 
136
  g_atomic_int_inc (&real->ref_count);
 
137
 
 
138
  return heap;
 
139
}
 
140
 
 
141
static void
 
142
egg_heap_real_free (EggHeapReal *real)
 
143
{
 
144
  g_assert (real);
 
145
  g_assert_cmpint (real->ref_count, ==, 0);
 
146
 
 
147
  g_free (real->data);
 
148
  g_free (real);
 
149
}
 
150
 
 
151
void
 
152
egg_heap_unref (EggHeap *heap)
 
153
{
 
154
  EggHeapReal *real = (EggHeapReal *)heap;
 
155
 
 
156
  g_return_if_fail (heap);
 
157
  g_return_if_fail (real->ref_count);
 
158
 
 
159
  if (g_atomic_int_dec_and_test (&real->ref_count))
 
160
    egg_heap_real_free (real);
 
161
}
 
162
 
 
163
static void
 
164
egg_heap_real_grow (EggHeapReal *real)
 
165
{
 
166
  g_assert (real);
 
167
  g_assert_cmpint (real->allocated_len, <, G_MAXSIZE / 2);
 
168
 
 
169
  real->allocated_len = MAX (MIN_HEAP_SIZE, (real->allocated_len * 2));
 
170
  real->data = g_realloc_n (real->data,
 
171
                            real->allocated_len,
 
172
                            real->element_size);
 
173
}
 
174
 
 
175
static void
 
176
egg_heap_real_shrink (EggHeapReal *real)
 
177
{
 
178
  g_assert (real);
 
179
  g_assert ((real->allocated_len / 2) >= real->len);
 
180
 
 
181
  real->allocated_len = MAX (MIN_HEAP_SIZE, real->allocated_len / 2);
 
182
  real->data = g_realloc_n (real->data,
 
183
                            real->allocated_len,
 
184
                            real->element_size);
 
185
}
 
186
 
 
187
static void
 
188
egg_heap_real_insert_val (EggHeapReal   *real,
 
189
                          gconstpointer  data)
 
190
{
 
191
  gint ipos;
 
192
  gint ppos;
 
193
 
 
194
  g_assert (real);
 
195
  g_assert (data);
 
196
 
 
197
  if (G_UNLIKELY (real->len == real->allocated_len))
 
198
    egg_heap_real_grow (real);
 
199
 
 
200
  memcpy (real->data + (real->element_size * real->len),
 
201
          data,
 
202
          real->element_size);
 
203
 
 
204
  ipos = real->len;
 
205
  ppos = heap_parent (ipos);
 
206
 
 
207
  while ((ipos > 0) && (heap_compare (real, ppos, ipos) < 0))
 
208
    {
 
209
      heap_swap (real, ppos, ipos);
 
210
      ipos = ppos;
 
211
      ppos = heap_parent (ipos);
 
212
    }
 
213
 
 
214
  real->len++;
 
215
}
 
216
 
 
217
void
 
218
egg_heap_insert_vals (EggHeap       *heap,
 
219
                      gconstpointer  data,
 
220
                      guint          len)
 
221
{
 
222
  EggHeapReal *real = (EggHeapReal *)heap;
 
223
  const gchar *ptr = data;
 
224
  guint i;
 
225
 
 
226
  g_return_if_fail (heap);
 
227
  g_return_if_fail (data);
 
228
  g_return_if_fail (len);
 
229
 
 
230
  for (i = 0; i < len; i++, ptr += real->element_size)
 
231
    egg_heap_real_insert_val (real, ptr);
 
232
}
 
233
 
 
234
gboolean
 
235
egg_heap_extract (EggHeap  *heap,
 
236
                  gpointer  result)
 
237
{
 
238
  EggHeapReal *real = (EggHeapReal *)heap;
 
239
  gint ipos;
 
240
  gint lpos;
 
241
  gint rpos;
 
242
  gint mpos;
 
243
 
 
244
  g_return_val_if_fail (heap, FALSE);
 
245
 
 
246
  if (real->len == 0)
 
247
    return FALSE;
 
248
 
 
249
  if (result)
 
250
    memcpy (result, heap_index (real, 0), real->element_size);
 
251
 
 
252
  if (--real->len > 0)
 
253
    {
 
254
      memmove (real->data,
 
255
               heap_index (real, real->len),
 
256
               real->element_size);
 
257
 
 
258
      ipos = 0;
 
259
 
 
260
      while (TRUE)
 
261
        {
 
262
          lpos = heap_left (ipos);
 
263
          rpos = heap_right (ipos);
 
264
 
 
265
          if ((lpos < real->len) && (heap_compare (real, lpos, ipos) > 0))
 
266
            mpos = lpos;
 
267
          else
 
268
            mpos = ipos;
 
269
 
 
270
          if ((rpos < real->len) && (heap_compare (real, rpos, mpos) > 0))
 
271
            mpos = rpos;
 
272
 
 
273
          if (mpos == ipos)
 
274
            break;
 
275
 
 
276
          heap_swap (real, mpos, ipos);
 
277
 
 
278
          ipos = mpos;
 
279
        }
 
280
    }
 
281
 
 
282
  if ((real->len > MIN_HEAP_SIZE) && (real->allocated_len / 2) >= real->len)
 
283
    egg_heap_real_shrink (real);
 
284
 
 
285
  return TRUE;
 
286
}
 
287
 
 
288
gboolean
 
289
egg_heap_extract_index (EggHeap  *heap,
 
290
                        guint     index_,
 
291
                        gpointer  result)
 
292
{
 
293
  EggHeapReal *real = (EggHeapReal *)heap;
 
294
  gint ipos;
 
295
  gint lpos;
 
296
  gint mpos;
 
297
  gint ppos;
 
298
  gint rpos;
 
299
 
 
300
  g_return_val_if_fail (heap, FALSE);
 
301
 
 
302
  if (real->len == 0)
 
303
    return FALSE;
 
304
 
 
305
  if (result)
 
306
    memcpy (result, heap_index (real, index_), real->element_size);
 
307
 
 
308
  real->len--;
 
309
 
 
310
  if (real->len && index_ != real->len)
 
311
    {
 
312
      memcpy (heap_index (real, index_),
 
313
              heap_index (real, real->len),
 
314
              real->element_size);
 
315
 
 
316
      ipos = index_;
 
317
      ppos = heap_parent (ipos);
 
318
 
 
319
      while (heap_compare (real, ipos, ppos) > 0)
 
320
        {
 
321
          heap_swap (real, ipos, ppos);
 
322
          ipos = ppos;
 
323
          ppos = heap_parent (ppos);
 
324
        }
 
325
 
 
326
      if (ipos == index_)
 
327
        {
 
328
          while (TRUE)
 
329
            {
 
330
              lpos = heap_left (ipos);
 
331
              rpos = heap_right (ipos);
 
332
 
 
333
              if ((lpos < real->len) && (heap_compare (real, lpos, ipos) > 0))
 
334
                mpos = lpos;
 
335
              else
 
336
                mpos = ipos;
 
337
 
 
338
              if ((rpos < real->len) && (heap_compare (real, rpos, mpos) > 0))
 
339
                mpos = rpos;
 
340
 
 
341
              if (mpos == ipos)
 
342
                break;
 
343
 
 
344
              heap_swap (real, mpos, ipos);
 
345
 
 
346
              ipos = mpos;
 
347
            }
 
348
        }
 
349
    }
 
350
 
 
351
  if ((real->len > MIN_HEAP_SIZE) && (real->allocated_len / 2) >= real->len)
 
352
    egg_heap_real_shrink (real);
 
353
 
 
354
  return TRUE;
 
355
}