]>
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 | ||
0241684e | 23 | #include "memory.h" |
6708fa3c | 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 | static 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)]; | |
c3c07f28 | 60 | if (queue->update != NULL) |
61 | (*queue->update) (queue->array[index], index); | |
6708fa3c | 62 | index = PARENT_OF (index); |
63 | } | |
64 | ||
65 | /* Restore the tmp node to appropriate place. */ | |
66 | queue->array[index] = tmp; | |
c3c07f28 | 67 | if (queue->update != NULL) |
68 | (*queue->update) (tmp, index); | |
6708fa3c | 69 | } |
70 | ||
c3c07f28 | 71 | void |
6708fa3c | 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]; | |
c3c07f28 | 98 | if (queue->update != NULL) |
99 | (*queue->update) (queue->array[index], index); | |
6708fa3c | 100 | index = which; |
101 | } | |
102 | ||
103 | /* Restore the tmp node to appropriate place. */ | |
104 | queue->array[index] = tmp; | |
c3c07f28 | 105 | if (queue->update != NULL) |
106 | (*queue->update) (tmp, index); | |
6708fa3c | 107 | } |
108 | ||
109 | struct pqueue * | |
8cc4198f | 110 | pqueue_create (void) |
6708fa3c | 111 | { |
112 | struct pqueue *queue; | |
113 | ||
0241684e | 114 | queue = XCALLOC (MTYPE_PQUEUE, sizeof (struct pqueue)); |
6708fa3c | 115 | |
0241684e | 116 | queue->array = XCALLOC (MTYPE_PQUEUE_DATA, |
117 | DATA_SIZE * PQUEUE_INIT_ARRAYSIZE); | |
6708fa3c | 118 | queue->array_size = PQUEUE_INIT_ARRAYSIZE; |
119 | ||
c3c07f28 | 120 | /* By default we want nothing to happen when a node changes. */ |
121 | queue->update = NULL; | |
6708fa3c | 122 | return queue; |
123 | } | |
124 | ||
125 | void | |
126 | pqueue_delete (struct pqueue *queue) | |
127 | { | |
0241684e | 128 | XFREE (MTYPE_PQUEUE_DATA, queue->array); |
129 | XFREE (MTYPE_PQUEUE, queue); | |
6708fa3c | 130 | } |
131 | ||
132 | static int | |
133 | pqueue_expand (struct pqueue *queue) | |
134 | { | |
135 | void **newarray; | |
136 | ||
0241684e | 137 | newarray = XCALLOC (MTYPE_PQUEUE_DATA, queue->array_size * DATA_SIZE * 2); |
6708fa3c | 138 | if (newarray == NULL) |
139 | return 0; | |
140 | ||
6708fa3c | 141 | memcpy (newarray, queue->array, queue->array_size * DATA_SIZE); |
142 | ||
0241684e | 143 | XFREE (MTYPE_PQUEUE_DATA, queue->array); |
6708fa3c | 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; | |
c3c07f28 | 157 | if (queue->update != NULL) |
158 | (*queue->update) (data, queue->size); | |
6708fa3c | 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 | } |