Line data Source code
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 763 : trickle_up (int index, struct pqueue *queue)
47 : {
48 : void *tmp;
49 :
50 : /* Save current node as tmp node. */
51 763 : 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 1706 : while (index > 0 &&
56 90 : (*queue->cmp) (tmp, queue->array[PARENT_OF (index)]) < 0)
57 : {
58 : /* actually trickle up */
59 90 : queue->array[index] = queue->array[PARENT_OF (index)];
60 90 : if (queue->update != NULL)
61 90 : (*queue->update) (queue->array[index], index);
62 90 : index = PARENT_OF (index);
63 : }
64 :
65 : /* Restore the tmp node to appropriate place. */
66 763 : queue->array[index] = tmp;
67 763 : if (queue->update != NULL)
68 763 : (*queue->update) (tmp, index);
69 763 : }
70 :
71 : void
72 665 : trickle_down (int index, struct pqueue *queue)
73 : {
74 : void *tmp;
75 : int which;
76 :
77 : /* Save current node as tmp node. */
78 665 : tmp = queue->array[index];
79 :
80 : /* Continue until the node have at least one (left) child. */
81 1330 : 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 0 : if (RIGHT_OF (index) < queue->size &&
86 0 : (*queue->cmp) (queue->array[LEFT_OF (index)],
87 0 : queue->array[RIGHT_OF (index)]) > 0)
88 0 : which = RIGHT_OF (index);
89 : else
90 0 : which = LEFT_OF (index);
91 :
92 : /* If the tmp node should be upper than the child, break. */
93 0 : if ((*queue->cmp) (queue->array[which], tmp) > 0)
94 0 : break;
95 :
96 : /* Actually trickle down the tmp node. */
97 0 : queue->array[index] = queue->array[which];
98 0 : if (queue->update != NULL)
99 0 : (*queue->update) (queue->array[index], index);
100 0 : index = which;
101 : }
102 :
103 : /* Restore the tmp node to appropriate place. */
104 665 : queue->array[index] = tmp;
105 665 : if (queue->update != NULL)
106 665 : (*queue->update) (tmp, index);
107 665 : }
108 :
109 : struct pqueue *
110 104 : pqueue_create (void)
111 : {
112 : struct pqueue *queue;
113 :
114 104 : queue = XCALLOC (MTYPE_PQUEUE, sizeof (struct pqueue));
115 :
116 104 : queue->array = XCALLOC (MTYPE_PQUEUE_DATA,
117 : DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
118 104 : queue->array_size = PQUEUE_INIT_ARRAYSIZE;
119 :
120 : /* By default we want nothing to happen when a node changes. */
121 104 : queue->update = NULL;
122 104 : return queue;
123 : }
124 :
125 : void
126 2 : pqueue_delete (struct pqueue *queue)
127 : {
128 2 : XFREE (MTYPE_PQUEUE_DATA, queue->array);
129 2 : XFREE (MTYPE_PQUEUE, queue);
130 2 : }
131 :
132 : static int
133 0 : pqueue_expand (struct pqueue *queue)
134 : {
135 : void **newarray;
136 :
137 0 : newarray = XCALLOC (MTYPE_PQUEUE_DATA, queue->array_size * DATA_SIZE * 2);
138 0 : if (newarray == NULL)
139 0 : return 0;
140 :
141 0 : memcpy (newarray, queue->array, queue->array_size * DATA_SIZE);
142 :
143 0 : XFREE (MTYPE_PQUEUE_DATA, queue->array);
144 0 : queue->array = newarray;
145 0 : queue->array_size *= 2;
146 :
147 0 : return 1;
148 : }
149 :
150 : void
151 763 : pqueue_enqueue (void *data, struct pqueue *queue)
152 : {
153 763 : if (queue->size + 2 >= queue->array_size && ! pqueue_expand (queue))
154 0 : return;
155 :
156 763 : queue->array[queue->size] = data;
157 763 : if (queue->update != NULL)
158 763 : (*queue->update) (data, queue->size);
159 763 : trickle_up (queue->size, queue);
160 763 : queue->size ++;
161 : }
162 :
163 : void *
164 665 : pqueue_dequeue (struct pqueue *queue)
165 : {
166 665 : void *data = queue->array[0];
167 665 : queue->array[0] = queue->array[--queue->size];
168 665 : trickle_down (0, queue);
169 665 : return data;
170 : }
171 :
172 : void
173 0 : pqueue_remove_at (int index, struct pqueue *queue)
174 : {
175 0 : queue->array[index] = queue->array[--queue->size];
176 :
177 0 : if (index > 0
178 0 : && (*queue->cmp) (queue->array[index],
179 0 : queue->array[PARENT_OF(index)]) < 0)
180 : {
181 0 : trickle_up (index, queue);
182 : }
183 : else
184 : {
185 0 : trickle_down (index, queue);
186 : }
187 0 : }
|
