]> git.sommitrealweird.co.uk Git - quagga-debian.git/blob - lib/pqueue.c
New upstream version 1.2.4
[quagga-debian.git] / lib / pqueue.c
1 /* Priority queue functions.
2    Copyright (C) 2003 Yasuhiro Ohara
3
4 This file is part of GNU Zebra.
5
6 GNU Zebra is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published
8 by the Free Software Foundation; either version 2, or (at your
9 option) any later version.
10
11 GNU Zebra is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GNU Zebra; see the file COPYING.  If not, write to the
18 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.  */
20
21 #include <zebra.h>
22
23 #include "memory.h"
24 #include "pqueue.h"
25
26 /* priority queue using heap sort */
27
28 /* pqueue->cmp() controls the order of sorting (i.e, ascending or
29    descending). If you want the left node to move upper of the heap
30    binary tree, make cmp() to return less than 0.  for example, if cmp
31    (10, 20) returns -1, the sorting is ascending order. if cmp (10,
32    20) returns 1, the sorting is descending order. if cmp (10, 20)
33    returns 0, this library does not do sorting (which will not be what
34    you want).  To be brief, if the contents of cmp_func (left, right)
35    is left - right, dequeue () returns the smallest node.  Otherwise
36    (if the contents is right - left), dequeue () returns the largest
37    node.  */
38
39 #define DATA_SIZE (sizeof (void *))
40 #define PARENT_OF(x) ((x - 1) / 2)
41 #define LEFT_OF(x)  (2 * x + 1)
42 #define RIGHT_OF(x) (2 * x + 2)
43 #define HAVE_CHILD(x,q) (x < (q)->size / 2)
44
45 void
46 trickle_up (int index, struct pqueue *queue)
47 {
48   void *tmp;
49
50   /* Save current node as tmp node.  */
51   tmp = queue->array[index];
52
53   /* Continue until the node reaches top or the place where the parent
54      node should be upper than the tmp node.  */
55   while (index > 0 &&
56          (*queue->cmp) (tmp, queue->array[PARENT_OF (index)]) < 0)
57     {
58       /* actually trickle up */
59       queue->array[index] = queue->array[PARENT_OF (index)];
60       if (queue->update != NULL)
61         (*queue->update) (queue->array[index], index);
62       index = PARENT_OF (index);
63     }
64
65   /* Restore the tmp node to appropriate place.  */
66   queue->array[index] = tmp;
67   if (queue->update != NULL)
68     (*queue->update) (tmp, index);
69 }
70
71 void
72 trickle_down (int index, struct pqueue *queue)
73 {
74   void *tmp;
75   int which;
76
77   /* Save current node as tmp node.  */
78   tmp = queue->array[index];
79
80   /* Continue until the node have at least one (left) child.  */
81   while (HAVE_CHILD (index, queue))
82     {
83       /* If right child exists, and if the right child is more proper
84          to be moved upper.  */
85       if (RIGHT_OF (index) < queue->size &&
86           (*queue->cmp) (queue->array[LEFT_OF (index)],
87                          queue->array[RIGHT_OF (index)]) > 0)
88         which = RIGHT_OF (index);
89       else
90         which = LEFT_OF (index);
91
92       /* If the tmp node should be upper than the child, break.  */
93       if ((*queue->cmp) (queue->array[which], tmp) > 0)
94         break;
95
96       /* Actually trickle down the tmp node.  */
97       queue->array[index] = queue->array[which];
98        if (queue->update != NULL)
99          (*queue->update) (queue->array[index], index);
100       index = which;
101     }
102
103   /* Restore the tmp node to appropriate place.  */
104   queue->array[index] = tmp;
105   if (queue->update != NULL)
106     (*queue->update) (tmp, index);
107 }
108
109 struct pqueue *
110 pqueue_create (void)
111 {
112   struct pqueue *queue;
113
114   queue = XCALLOC (MTYPE_PQUEUE, sizeof (struct pqueue));
115
116   queue->array = XCALLOC (MTYPE_PQUEUE_DATA, 
117                           DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
118   queue->array_size = PQUEUE_INIT_ARRAYSIZE;
119
120   /* By default we want nothing to happen when a node changes. */
121   queue->update = NULL;
122   return queue;
123 }
124
125 void
126 pqueue_delete (struct pqueue *queue)
127 {
128   XFREE (MTYPE_PQUEUE_DATA, queue->array);
129   XFREE (MTYPE_PQUEUE, queue);
130 }
131
132 static int
133 pqueue_expand (struct pqueue *queue)
134 {
135   void **newarray;
136
137   newarray = XCALLOC (MTYPE_PQUEUE_DATA, queue->array_size * DATA_SIZE * 2);
138   if (newarray == NULL)
139     return 0;
140
141   memcpy (newarray, queue->array, queue->array_size * DATA_SIZE);
142
143   XFREE (MTYPE_PQUEUE_DATA, queue->array);
144   queue->array = newarray;
145   queue->array_size *= 2;
146
147   return 1;
148 }
149
150 void
151 pqueue_enqueue (void *data, struct pqueue *queue)
152 {
153   if (queue->size + 2 >= queue->array_size && ! pqueue_expand (queue))
154     return;
155
156   queue->array[queue->size] = data;
157   if (queue->update != NULL)
158     (*queue->update) (data, queue->size);
159   trickle_up (queue->size, queue);
160   queue->size ++;
161 }
162
163 void *
164 pqueue_dequeue (struct pqueue *queue)
165 {
166   void *data = queue->array[0];
167   queue->array[0] =  queue->array[--queue->size];
168   trickle_down (0, queue);
169   return data;
170 }
171
172 void
173 pqueue_remove_at (int index, struct pqueue *queue)
174 {
175   queue->array[index] = queue->array[--queue->size];
176
177   if (index > 0
178       && (*queue->cmp) (queue->array[index],
179                         queue->array[PARENT_OF(index)]) < 0)
180     {
181       trickle_up (index, queue);
182     }
183   else
184     {
185       trickle_down (index, queue);
186     }
187 }