]>
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 along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 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)
48 void trickle_up(int index
, struct pqueue
*queue
)
52 /* Save current node as tmp node. */
53 tmp
= queue
->array
[index
];
55 /* Continue until the node reaches top or the place where the parent
56 node should be upper than the tmp node. */
58 && (*queue
->cmp
)(tmp
, queue
->array
[PARENT_OF(index
)]) < 0) {
59 /* actually trickle up */
60 queue
->array
[index
] = queue
->array
[PARENT_OF(index
)];
61 if (queue
->update
!= NULL
)
62 (*queue
->update
)(queue
->array
[index
], index
);
63 index
= PARENT_OF(index
);
66 /* Restore the tmp node to appropriate place. */
67 queue
->array
[index
] = tmp
;
68 if (queue
->update
!= NULL
)
69 (*queue
->update
)(tmp
, index
);
72 void trickle_down(int index
, struct pqueue
*queue
)
77 /* Save current node as tmp node. */
78 tmp
= queue
->array
[index
];
80 /* Continue until the node have at least one (left) child. */
81 while (HAVE_CHILD(index
, queue
)) {
82 /* If right child exists, and if the right child is more proper
84 if (RIGHT_OF(index
) < queue
->size
85 && (*queue
->cmp
)(queue
->array
[LEFT_OF(index
)],
86 queue
->array
[RIGHT_OF(index
)])
88 which
= RIGHT_OF(index
);
90 which
= LEFT_OF(index
);
92 /* If the tmp node should be upper than the child, break. */
93 if ((*queue
->cmp
)(queue
->array
[which
], tmp
) > 0)
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
);
103 /* Restore the tmp node to appropriate place. */
104 queue
->array
[index
] = tmp
;
105 if (queue
->update
!= NULL
)
106 (*queue
->update
)(tmp
, index
);
109 struct pqueue
*pqueue_create(void)
111 struct pqueue
*queue
;
113 queue
= XCALLOC(MTYPE_PQUEUE
, sizeof(struct pqueue
));
116 XCALLOC(MTYPE_PQUEUE_DATA
, DATA_SIZE
* PQUEUE_INIT_ARRAYSIZE
);
117 queue
->array_size
= PQUEUE_INIT_ARRAYSIZE
;
119 /* By default we want nothing to happen when a node changes. */
120 queue
->update
= NULL
;
124 void pqueue_delete(struct pqueue
*queue
)
126 XFREE(MTYPE_PQUEUE_DATA
, queue
->array
);
127 XFREE(MTYPE_PQUEUE
, queue
);
130 static int pqueue_expand(struct pqueue
*queue
)
135 XCALLOC(MTYPE_PQUEUE_DATA
, queue
->array_size
* DATA_SIZE
* 2);
136 if (newarray
== NULL
)
139 memcpy(newarray
, queue
->array
, queue
->array_size
* DATA_SIZE
);
141 XFREE(MTYPE_PQUEUE_DATA
, queue
->array
);
142 queue
->array
= newarray
;
143 queue
->array_size
*= 2;
148 void pqueue_enqueue(void *data
, struct pqueue
*queue
)
150 if (queue
->size
+ 2 >= queue
->array_size
&& !pqueue_expand(queue
))
153 queue
->array
[queue
->size
] = data
;
154 if (queue
->update
!= NULL
)
155 (*queue
->update
)(data
, queue
->size
);
156 trickle_up(queue
->size
, queue
);
160 void *pqueue_dequeue(struct pqueue
*queue
)
162 void *data
= queue
->array
[0];
163 queue
->array
[0] = queue
->array
[--queue
->size
];
164 trickle_down(0, queue
);
168 void pqueue_remove_at(int index
, struct pqueue
*queue
)
170 queue
->array
[index
] = queue
->array
[--queue
->size
];
173 && (*queue
->cmp
)(queue
->array
[index
],
174 queue
->array
[PARENT_OF(index
)])
176 trickle_up(index
, queue
);
178 trickle_down(index
, queue
);
182 void pqueue_remove(void *data
, struct pqueue
*queue
)
184 for (int i
= 0; i
< queue
->size
; i
++)
185 if (queue
->array
[i
] == data
)
186 pqueue_remove_at(i
, queue
);