]>
git.proxmox.com Git - mirror_frr.git/blob - lib/pqueue.c
1 /* Priority queue functions.
2 Copyright (C) 2003 Yasuhiro Ohara
4 This file is part of GNU Zebra.
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.
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.
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. */
26 DEFINE_MTYPE_STATIC(LIB
, PQUEUE
, "Priority queue")
27 DEFINE_MTYPE_STATIC(LIB
, PQUEUE_DATA
, "Priority queue data")
29 /* priority queue using heap sort */
31 /* pqueue->cmp() controls the order of sorting (i.e, ascending or
32 descending). If you want the left node to move upper of the heap
33 binary tree, make cmp() to return less than 0. for example, if cmp
34 (10, 20) returns -1, the sorting is ascending order. if cmp (10,
35 20) returns 1, the sorting is descending order. if cmp (10, 20)
36 returns 0, this library does not do sorting (which will not be what
37 you want). To be brief, if the contents of cmp_func (left, right)
38 is left - right, dequeue () returns the smallest node. Otherwise
39 (if the contents is right - left), dequeue () returns the largest
42 #define DATA_SIZE (sizeof (void *))
43 #define PARENT_OF(x) ((x - 1) / 2)
44 #define LEFT_OF(x) (2 * x + 1)
45 #define RIGHT_OF(x) (2 * x + 2)
46 #define HAVE_CHILD(x,q) (x < (q)->size / 2)
49 trickle_up (int index
, struct pqueue
*queue
)
53 /* Save current node as tmp node. */
54 tmp
= queue
->array
[index
];
56 /* Continue until the node reaches top or the place where the parent
57 node should be upper than the tmp node. */
59 (*queue
->cmp
) (tmp
, queue
->array
[PARENT_OF (index
)]) < 0)
61 /* actually trickle up */
62 queue
->array
[index
] = queue
->array
[PARENT_OF (index
)];
63 if (queue
->update
!= NULL
)
64 (*queue
->update
) (queue
->array
[index
], index
);
65 index
= PARENT_OF (index
);
68 /* Restore the tmp node to appropriate place. */
69 queue
->array
[index
] = tmp
;
70 if (queue
->update
!= NULL
)
71 (*queue
->update
) (tmp
, index
);
75 trickle_down (int index
, struct pqueue
*queue
)
80 /* Save current node as tmp node. */
81 tmp
= queue
->array
[index
];
83 /* Continue until the node have at least one (left) child. */
84 while (HAVE_CHILD (index
, queue
))
86 /* If right child exists, and if the right child is more proper
88 if (RIGHT_OF (index
) < queue
->size
&&
89 (*queue
->cmp
) (queue
->array
[LEFT_OF (index
)],
90 queue
->array
[RIGHT_OF (index
)]) > 0)
91 which
= RIGHT_OF (index
);
93 which
= LEFT_OF (index
);
95 /* If the tmp node should be upper than the child, break. */
96 if ((*queue
->cmp
) (queue
->array
[which
], tmp
) > 0)
99 /* Actually trickle down the tmp node. */
100 queue
->array
[index
] = queue
->array
[which
];
101 if (queue
->update
!= NULL
)
102 (*queue
->update
) (queue
->array
[index
], index
);
106 /* Restore the tmp node to appropriate place. */
107 queue
->array
[index
] = tmp
;
108 if (queue
->update
!= NULL
)
109 (*queue
->update
) (tmp
, index
);
115 struct pqueue
*queue
;
117 queue
= XCALLOC (MTYPE_PQUEUE
, sizeof (struct pqueue
));
119 queue
->array
= XCALLOC (MTYPE_PQUEUE_DATA
,
120 DATA_SIZE
* PQUEUE_INIT_ARRAYSIZE
);
121 queue
->array_size
= PQUEUE_INIT_ARRAYSIZE
;
123 /* By default we want nothing to happen when a node changes. */
124 queue
->update
= NULL
;
129 pqueue_delete (struct pqueue
*queue
)
131 XFREE (MTYPE_PQUEUE_DATA
, queue
->array
);
132 XFREE (MTYPE_PQUEUE
, queue
);
136 pqueue_expand (struct pqueue
*queue
)
140 newarray
= XCALLOC (MTYPE_PQUEUE_DATA
, queue
->array_size
* DATA_SIZE
* 2);
141 if (newarray
== NULL
)
144 memcpy (newarray
, queue
->array
, queue
->array_size
* DATA_SIZE
);
146 XFREE (MTYPE_PQUEUE_DATA
, queue
->array
);
147 queue
->array
= newarray
;
148 queue
->array_size
*= 2;
154 pqueue_enqueue (void *data
, struct pqueue
*queue
)
156 if (queue
->size
+ 2 >= queue
->array_size
&& ! pqueue_expand (queue
))
159 queue
->array
[queue
->size
] = data
;
160 if (queue
->update
!= NULL
)
161 (*queue
->update
) (data
, queue
->size
);
162 trickle_up (queue
->size
, queue
);
167 pqueue_dequeue (struct pqueue
*queue
)
169 void *data
= queue
->array
[0];
170 queue
->array
[0] = queue
->array
[--queue
->size
];
171 trickle_down (0, queue
);
176 pqueue_remove_at (int index
, struct pqueue
*queue
)
178 queue
->array
[index
] = queue
->array
[--queue
->size
];
181 && (*queue
->cmp
) (queue
->array
[index
],
182 queue
->array
[PARENT_OF(index
)]) < 0)
184 trickle_up (index
, queue
);
188 trickle_down (index
, queue
);