Annotation of embedaddon/quagga/lib/pqueue.c, revision 1.1.1.2
1.1 misho 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: 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)];
60: if (queue->update != NULL)
61: (*queue->update) (queue->array[index], index);
62: index = PARENT_OF (index);
63: }
64:
65: /* Restore the tmp node to appropriate place. */
66: queue->array[index] = tmp;
67: if (queue->update != NULL)
68: (*queue->update) (tmp, index);
69: }
70:
71: void
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];
98: if (queue->update != NULL)
99: (*queue->update) (queue->array[index], index);
100: index = which;
101: }
102:
103: /* Restore the tmp node to appropriate place. */
104: queue->array[index] = tmp;
105: if (queue->update != NULL)
106: (*queue->update) (tmp, index);
107: }
108:
109: struct pqueue *
110: pqueue_create (void)
111: {
112: struct pqueue *queue;
113:
114: queue = XCALLOC (MTYPE_PQUEUE, sizeof (struct pqueue));
115:
116: queue->array = XCALLOC (MTYPE_PQUEUE_DATA,
117: DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
118: queue->array_size = PQUEUE_INIT_ARRAYSIZE;
119:
120: /* By default we want nothing to happen when a node changes. */
121: queue->update = NULL;
122: return queue;
123: }
124:
125: void
126: pqueue_delete (struct pqueue *queue)
127: {
128: XFREE (MTYPE_PQUEUE_DATA, queue->array);
129: XFREE (MTYPE_PQUEUE, queue);
130: }
131:
132: static int
133: pqueue_expand (struct pqueue *queue)
134: {
135: void **newarray;
136:
137: newarray = XCALLOC (MTYPE_PQUEUE_DATA, queue->array_size * DATA_SIZE * 2);
138: if (newarray == NULL)
139: return 0;
140:
141: memcpy (newarray, queue->array, queue->array_size * DATA_SIZE);
142:
143: XFREE (MTYPE_PQUEUE_DATA, queue->array);
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;
157: if (queue->update != NULL)
158: (*queue->update) (data, queue->size);
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: }
1.1.1.2 ! misho 171:
! 172: void
! 173: pqueue_remove_at (int index, struct pqueue *queue)
! 174: {
! 175: queue->array[index] = queue->array[--queue->size];
! 176:
! 177: if (index > 0
! 178: && (*queue->cmp) (queue->array[index],
! 179: queue->array[PARENT_OF(index)]) < 0)
! 180: {
! 181: trickle_up (index, queue);
! 182: }
! 183: else
! 184: {
! 185: trickle_down (index, queue);
! 186: }
! 187: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to pqueue.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / lib