]>
Commit | Line | Data |
---|---|---|
6708fa3c | 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 "pqueue.h" | |
24 | ||
25 | /* priority queue using heap sort */ | |
26 | ||
27 | /* pqueue->cmp() controls the order of sorting (i.e, ascending or | |
28 | descending). If you want the left node to move upper of the heap | |
29 | binary tree, make cmp() to return less than 0. for example, if cmp | |
30 | (10, 20) returns -1, the sorting is ascending order. if cmp (10, | |
31 | 20) returns 1, the sorting is descending order. if cmp (10, 20) | |
32 | returns 0, this library does not do sorting (which will not be what | |
33 | you want). To be brief, if the contents of cmp_func (left, right) | |
34 | is left - right, dequeue () returns the smallest node. Otherwise | |
35 | (if the contents is right - left), dequeue () returns the largest | |
36 | node. */ | |
37 | ||
38 | #define DATA_SIZE (sizeof (void *)) | |
39 | #define PARENT_OF(x) ((x - 1) / 2) | |
40 | #define LEFT_OF(x) (2 * x + 1) | |
41 | #define RIGHT_OF(x) (2 * x + 2) | |
42 | #define HAVE_CHILD(x,q) (x < (q)->size / 2) | |
43 | ||
44 | static void | |
45 | trickle_up (int index, struct pqueue *queue) | |
46 | { | |
47 | void *tmp; | |
48 | ||
49 | /* Save current node as tmp node. */ | |
50 | tmp = queue->array[index]; | |
51 | ||
52 | /* Continue until the node reaches top or the place where the parent | |
53 | node should be upper than the tmp node. */ | |
54 | while (index > 0 && | |
55 | (*queue->cmp) (tmp, queue->array[PARENT_OF (index)]) < 0) | |
56 | { | |
57 | /* actually trickle up */ | |
58 | queue->array[index] = queue->array[PARENT_OF (index)]; | |
c3c07f28 | 59 | if (queue->update != NULL) |
60 | (*queue->update) (queue->array[index], index); | |
6708fa3c | 61 | index = PARENT_OF (index); |
62 | } | |
63 | ||
64 | /* Restore the tmp node to appropriate place. */ | |
65 | queue->array[index] = tmp; | |
c3c07f28 | 66 | if (queue->update != NULL) |
67 | (*queue->update) (tmp, index); | |
6708fa3c | 68 | } |
69 | ||
c3c07f28 | 70 | void |
6708fa3c | 71 | trickle_down (int index, struct pqueue *queue) |
72 | { | |
73 | void *tmp; | |
74 | int which; | |
75 | ||
76 | /* Save current node as tmp node. */ | |
77 | tmp = queue->array[index]; | |
78 | ||
79 | /* Continue until the node have at least one (left) child. */ | |
80 | while (HAVE_CHILD (index, queue)) | |
81 | { | |
82 | /* If right child exists, and if the right child is more proper | |
83 | to be moved upper. */ | |
84 | if (RIGHT_OF (index) < queue->size && | |
85 | (*queue->cmp) (queue->array[LEFT_OF (index)], | |
86 | queue->array[RIGHT_OF (index)]) > 0) | |
87 | which = RIGHT_OF (index); | |
88 | else | |
89 | which = LEFT_OF (index); | |
90 | ||
91 | /* If the tmp node should be upper than the child, break. */ | |
92 | if ((*queue->cmp) (queue->array[which], tmp) > 0) | |
93 | break; | |
94 | ||
95 | /* Actually trickle down the tmp node. */ | |
96 | queue->array[index] = queue->array[which]; | |
c3c07f28 | 97 | if (queue->update != NULL) |
98 | (*queue->update) (queue->array[index], index); | |
6708fa3c | 99 | index = which; |
100 | } | |
101 | ||
102 | /* Restore the tmp node to appropriate place. */ | |
103 | queue->array[index] = tmp; | |
c3c07f28 | 104 | if (queue->update != NULL) |
105 | (*queue->update) (tmp, index); | |
6708fa3c | 106 | } |
107 | ||
108 | struct pqueue * | |
109 | pqueue_create () | |
110 | { | |
111 | struct pqueue *queue; | |
112 | ||
113 | queue = (struct pqueue *) malloc (sizeof (struct pqueue)); | |
114 | memset (queue, 0, sizeof (struct pqueue)); | |
115 | ||
116 | queue->array = (void **) | |
117 | malloc (DATA_SIZE * PQUEUE_INIT_ARRAYSIZE); | |
118 | memset (queue->array, 0, DATA_SIZE * PQUEUE_INIT_ARRAYSIZE); | |
119 | queue->array_size = PQUEUE_INIT_ARRAYSIZE; | |
120 | ||
c3c07f28 | 121 | /* By default we want nothing to happen when a node changes. */ |
122 | queue->update = NULL; | |
6708fa3c | 123 | return queue; |
124 | } | |
125 | ||
126 | void | |
127 | pqueue_delete (struct pqueue *queue) | |
128 | { | |
129 | free (queue->array); | |
130 | free (queue); | |
131 | } | |
132 | ||
133 | static int | |
134 | pqueue_expand (struct pqueue *queue) | |
135 | { | |
136 | void **newarray; | |
137 | ||
138 | newarray = (void **) malloc (queue->array_size * DATA_SIZE * 2); | |
139 | if (newarray == NULL) | |
140 | return 0; | |
141 | ||
142 | memset (newarray, 0, queue->array_size * DATA_SIZE * 2); | |
143 | memcpy (newarray, queue->array, queue->array_size * DATA_SIZE); | |
144 | ||
145 | free (queue->array); | |
146 | queue->array = newarray; | |
147 | queue->array_size *= 2; | |
148 | ||
149 | return 1; | |
150 | } | |
151 | ||
152 | void | |
153 | pqueue_enqueue (void *data, struct pqueue *queue) | |
154 | { | |
155 | if (queue->size + 2 >= queue->array_size && ! pqueue_expand (queue)) | |
156 | return; | |
157 | ||
158 | queue->array[queue->size] = data; | |
c3c07f28 | 159 | if (queue->update != NULL) |
160 | (*queue->update) (data, queue->size); | |
6708fa3c | 161 | trickle_up (queue->size, queue); |
162 | queue->size ++; | |
163 | } | |
164 | ||
165 | void * | |
166 | pqueue_dequeue (struct pqueue *queue) | |
167 | { | |
168 | void *data = queue->array[0]; | |
169 | queue->array[0] = queue->array[--queue->size]; | |
170 | trickle_down (0, queue); | |
171 | return data; | |
172 | } |