OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libiberty/] [fibheap.c] - Blame information for rev 758

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 736 jeremybenn
/* A Fibonacci heap datatype.
2
   Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3
   Contributed by Daniel Berlin (dan@cgsoftware.com).
4
 
5
This file is part of GNU CC.
6
 
7
GNU CC is free software; you can redistribute it and/or modify it
8
under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 2, or (at your option)
10
any later version.
11
 
12
GNU CC is distributed in the hope that it will be useful, but
13
WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15
General Public License for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GNU CC; see the file COPYING.  If not, write to
19
the Free Software Foundation, 51 Franklin Street - Fifth Floor,
20
Boston, MA 02110-1301, USA.  */
21
 
22
#ifdef HAVE_CONFIG_H
23
#include "config.h"
24
#endif
25
#ifdef HAVE_LIMITS_H
26
#include <limits.h>
27
#endif
28
#ifdef HAVE_STDLIB_H
29
#include <stdlib.h>
30
#endif
31
#ifdef HAVE_STRING_H
32
#include <string.h>
33
#endif
34
#include "libiberty.h"
35
#include "fibheap.h"
36
 
37
 
38
#define FIBHEAPKEY_MIN  LONG_MIN
39
 
40
static void fibheap_ins_root (fibheap_t, fibnode_t);
41
static void fibheap_rem_root (fibheap_t, fibnode_t);
42
static void fibheap_consolidate (fibheap_t);
43
static void fibheap_link (fibheap_t, fibnode_t, fibnode_t);
44
static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t);
45
static void fibheap_cascading_cut (fibheap_t, fibnode_t);
46
static fibnode_t fibheap_extr_min_node (fibheap_t);
47
static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t);
48
static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t);
49
static fibnode_t fibnode_new (void);
50
static void fibnode_insert_after (fibnode_t, fibnode_t);
51
#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
52
static fibnode_t fibnode_remove (fibnode_t);
53
 
54
 
55
/* Create a new fibonacci heap.  */
56
fibheap_t
57
fibheap_new (void)
58
{
59
  return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
60
}
61
 
62
/* Create a new fibonacci heap node.  */
63
static fibnode_t
64
fibnode_new (void)
65
{
66
  fibnode_t node;
67
 
68
  node = (fibnode_t) xcalloc (1, sizeof *node);
69
  node->left = node;
70
  node->right = node;
71
 
72
  return node;
73
}
74
 
75
static inline int
76
fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b)
77
{
78
  if (a->key < b->key)
79
    return -1;
80
  if (a->key > b->key)
81
    return 1;
82
  return 0;
83
}
84
 
85
static inline int
86
fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b)
87
{
88
  struct fibnode a;
89
 
90
  a.key = key;
91
  a.data = data;
92
 
93
  return fibheap_compare (heap, &a, b);
94
}
95
 
96
/* Insert DATA, with priority KEY, into HEAP.  */
97
fibnode_t
98
fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data)
99
{
100
  fibnode_t node;
101
 
102
  /* Create the new node.  */
103
  node = fibnode_new ();
104
 
105
  /* Set the node's data.  */
106
  node->data = data;
107
  node->key = key;
108
 
109
  /* Insert it into the root list.  */
110
  fibheap_ins_root (heap, node);
111
 
112
  /* If their was no minimum, or this key is less than the min,
113
     it's the new min.  */
114
  if (heap->min == NULL || node->key < heap->min->key)
115
    heap->min = node;
116
 
117
  heap->nodes++;
118
 
119
  return node;
120
}
121
 
122
/* Return the data of the minimum node (if we know it).  */
123
void *
124
fibheap_min (fibheap_t heap)
125
{
126
  /* If there is no min, we can't easily return it.  */
127
  if (heap->min == NULL)
128
    return NULL;
129
  return heap->min->data;
130
}
131
 
132
/* Return the key of the minimum node (if we know it).  */
133
fibheapkey_t
134
fibheap_min_key (fibheap_t heap)
135
{
136
  /* If there is no min, we can't easily return it.  */
137
  if (heap->min == NULL)
138
    return 0;
139
  return heap->min->key;
140
}
141
 
142
/* Union HEAPA and HEAPB into a new heap.  */
143
fibheap_t
144
fibheap_union (fibheap_t heapa, fibheap_t heapb)
145
{
146
  fibnode_t a_root, b_root, temp;
147
 
148
  /* If one of the heaps is empty, the union is just the other heap.  */
149
  if ((a_root = heapa->root) == NULL)
150
    {
151
      free (heapa);
152
      return heapb;
153
    }
154
  if ((b_root = heapb->root) == NULL)
155
    {
156
      free (heapb);
157
      return heapa;
158
    }
159
 
160
  /* Merge them to the next nodes on the opposite chain.  */
161
  a_root->left->right = b_root;
162
  b_root->left->right = a_root;
163
  temp = a_root->left;
164
  a_root->left = b_root->left;
165
  b_root->left = temp;
166
  heapa->nodes += heapb->nodes;
167
 
168
  /* And set the new minimum, if it's changed.  */
169
  if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
170
    heapa->min = heapb->min;
171
 
172
  free (heapb);
173
  return heapa;
174
}
175
 
176
/* Extract the data of the minimum node from HEAP.  */
177
void *
178
fibheap_extract_min (fibheap_t heap)
179
{
180
  fibnode_t z;
181
  void *ret = NULL;
182
 
183
  /* If we don't have a min set, it means we have no nodes.  */
184
  if (heap->min != NULL)
185
    {
186
      /* Otherwise, extract the min node, free the node, and return the
187
         node's data.  */
188
      z = fibheap_extr_min_node (heap);
189
      ret = z->data;
190
      free (z);
191
    }
192
 
193
  return ret;
194
}
195
 
196
/* Replace both the KEY and the DATA associated with NODE.  */
197
void *
198
fibheap_replace_key_data (fibheap_t heap, fibnode_t node,
199
                          fibheapkey_t key, void *data)
200
{
201
  void *odata;
202
  fibheapkey_t okey;
203
  fibnode_t y;
204
 
205
  /* If we wanted to, we could actually do a real increase by redeleting and
206
     inserting. However, this would require O (log n) time. So just bail out
207
     for now.  */
208
  if (fibheap_comp_data (heap, key, data, node) > 0)
209
    return NULL;
210
 
211
  odata = node->data;
212
  okey = node->key;
213
  node->data = data;
214
  node->key = key;
215
  y = node->parent;
216
 
217
  /* Short-circuit if the key is the same, as we then don't have to
218
     do anything.  Except if we're trying to force the new node to
219
     be the new minimum for delete.  */
220
  if (okey == key && okey != FIBHEAPKEY_MIN)
221
    return odata;
222
 
223
  /* These two compares are specifically <= 0 to make sure that in the case
224
     of equality, a node we replaced the data on, becomes the new min.  This
225
     is needed so that delete's call to extractmin gets the right node.  */
226
  if (y != NULL && fibheap_compare (heap, node, y) <= 0)
227
    {
228
      fibheap_cut (heap, node, y);
229
      fibheap_cascading_cut (heap, y);
230
    }
231
 
232
  if (fibheap_compare (heap, node, heap->min) <= 0)
233
    heap->min = node;
234
 
235
  return odata;
236
}
237
 
238
/* Replace the DATA associated with NODE.  */
239
void *
240
fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
241
{
242
  return fibheap_replace_key_data (heap, node, node->key, data);
243
}
244
 
245
/* Replace the KEY associated with NODE.  */
246
fibheapkey_t
247
fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
248
{
249
  int okey = node->key;
250
  fibheap_replace_key_data (heap, node, key, node->data);
251
  return okey;
252
}
253
 
254
/* Delete NODE from HEAP.  */
255
void *
256
fibheap_delete_node (fibheap_t heap, fibnode_t node)
257
{
258
  void *ret = node->data;
259
 
260
  /* To perform delete, we just make it the min key, and extract.  */
261
  fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
262
  if (node != heap->min)
263
    {
264
      fprintf (stderr, "Can't force minimum on fibheap.\n");
265
      abort ();
266
    }
267
  fibheap_extract_min (heap);
268
 
269
  return ret;
270
}
271
 
272
/* Delete HEAP.  */
273
void
274
fibheap_delete (fibheap_t heap)
275
{
276
  while (heap->min != NULL)
277
    free (fibheap_extr_min_node (heap));
278
 
279
  free (heap);
280
}
281
 
282
/* Determine if HEAP is empty.  */
283
int
284
fibheap_empty (fibheap_t heap)
285
{
286
  return heap->nodes == 0;
287
}
288
 
289
/* Extract the minimum node of the heap.  */
290
static fibnode_t
291
fibheap_extr_min_node (fibheap_t heap)
292
{
293
  fibnode_t ret = heap->min;
294
  fibnode_t x, y, orig;
295
 
296
  /* Attach the child list of the minimum node to the root list of the heap.
297
     If there is no child list, we don't do squat.  */
298
  for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y)
299
    {
300
      if (orig == NULL)
301
        orig = x;
302
      y = x->right;
303
      x->parent = NULL;
304
      fibheap_ins_root (heap, x);
305
    }
306
 
307
  /* Remove the old root.  */
308
  fibheap_rem_root (heap, ret);
309
  heap->nodes--;
310
 
311
  /* If we are left with no nodes, then the min is NULL.  */
312
  if (heap->nodes == 0)
313
    heap->min = NULL;
314
  else
315
    {
316
      /* Otherwise, consolidate to find new minimum, as well as do the reorg
317
         work that needs to be done.  */
318
      heap->min = ret->right;
319
      fibheap_consolidate (heap);
320
    }
321
 
322
  return ret;
323
}
324
 
325
/* Insert NODE into the root list of HEAP.  */
326
static void
327
fibheap_ins_root (fibheap_t heap, fibnode_t node)
328
{
329
  /* If the heap is currently empty, the new node becomes the singleton
330
     circular root list.  */
331
  if (heap->root == NULL)
332
    {
333
      heap->root = node;
334
      node->left = node;
335
      node->right = node;
336
      return;
337
    }
338
 
339
  /* Otherwise, insert it in the circular root list between the root
340
     and it's right node.  */
341
  fibnode_insert_after (heap->root, node);
342
}
343
 
344
/* Remove NODE from the rootlist of HEAP.  */
345
static void
346
fibheap_rem_root (fibheap_t heap, fibnode_t node)
347
{
348
  if (node->left == node)
349
    heap->root = NULL;
350
  else
351
    heap->root = fibnode_remove (node);
352
}
353
 
354
/* Consolidate the heap.  */
355
static void
356
fibheap_consolidate (fibheap_t heap)
357
{
358
  fibnode_t a[1 + 8 * sizeof (long)];
359
  fibnode_t w;
360
  fibnode_t y;
361
  fibnode_t x;
362
  int i;
363
  int d;
364
  int D;
365
 
366
  D = 1 + 8 * sizeof (long);
367
 
368
  memset (a, 0, sizeof (fibnode_t) * D);
369
 
370
  while ((w = heap->root) != NULL)
371
    {
372
      x = w;
373
      fibheap_rem_root (heap, w);
374
      d = x->degree;
375
      while (a[d] != NULL)
376
        {
377
          y = a[d];
378
          if (fibheap_compare (heap, x, y) > 0)
379
            {
380
              fibnode_t temp;
381
              temp = x;
382
              x = y;
383
              y = temp;
384
            }
385
          fibheap_link (heap, y, x);
386
          a[d] = NULL;
387
          d++;
388
        }
389
      a[d] = x;
390
    }
391
  heap->min = NULL;
392
  for (i = 0; i < D; i++)
393
    if (a[i] != NULL)
394
      {
395
        fibheap_ins_root (heap, a[i]);
396
        if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
397
          heap->min = a[i];
398
      }
399
}
400
 
401
/* Make NODE a child of PARENT.  */
402
static void
403
fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED,
404
              fibnode_t node, fibnode_t parent)
405
{
406
  if (parent->child == NULL)
407
    parent->child = node;
408
  else
409
    fibnode_insert_before (parent->child, node);
410
  node->parent = parent;
411
  parent->degree++;
412
  node->mark = 0;
413
}
414
 
415
/* Remove NODE from PARENT's child list.  */
416
static void
417
fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
418
{
419
  fibnode_remove (node);
420
  parent->degree--;
421
  fibheap_ins_root (heap, node);
422
  node->parent = NULL;
423
  node->mark = 0;
424
}
425
 
426
static void
427
fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
428
{
429
  fibnode_t z;
430
 
431
  while ((z = y->parent) != NULL)
432
    {
433
      if (y->mark == 0)
434
        {
435
          y->mark = 1;
436
          return;
437
        }
438
      else
439
        {
440
          fibheap_cut (heap, y, z);
441
          y = z;
442
        }
443
    }
444
}
445
 
446
static void
447
fibnode_insert_after (fibnode_t a, fibnode_t b)
448
{
449
  if (a == a->right)
450
    {
451
      a->right = b;
452
      a->left = b;
453
      b->right = a;
454
      b->left = a;
455
    }
456
  else
457
    {
458
      b->right = a->right;
459
      a->right->left = b;
460
      a->right = b;
461
      b->left = a;
462
    }
463
}
464
 
465
static fibnode_t
466
fibnode_remove (fibnode_t node)
467
{
468
  fibnode_t ret;
469
 
470
  if (node == node->left)
471
    ret = NULL;
472
  else
473
    ret = node->left;
474
 
475
  if (node->parent != NULL && node->parent->child == node)
476
    node->parent->child = ret;
477
 
478
  node->right->left = node->left;
479
  node->left->right = node->right;
480
 
481
  node->parent = NULL;
482
  node->left = node;
483
  node->right = node;
484
 
485
  return ret;
486
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.