Annotation of embedaddon/quagga/lib/pqueue.c, revision 1.1
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: }
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