diff options
| -rw-r--r-- | lib/ChangeLog | 4 | ||||
| -rw-r--r-- | lib/Makefile.am | 4 | ||||
| -rw-r--r-- | lib/pqueue.c | 160 | ||||
| -rw-r--r-- | lib/pqueue.h | 41 |
4 files changed, 207 insertions, 2 deletions
diff --git a/lib/ChangeLog b/lib/ChangeLog index d02fb50f..b42f4611 100644 --- a/lib/ChangeLog +++ b/lib/ChangeLog @@ -1,3 +1,7 @@ +2004-05-18 Hasso Tepper <hasso@estpak.ee> + + * pqueue.[c|h]: Added as part of ospf6d merge from Zebra repository. + 2004-05-08 Paul Jakma <paul@dishone.st> * zclient.c (zapi_ipv4_route) Follow Sowmini's lead and describe diff --git a/lib/Makefile.am b/lib/Makefile.am index d8621c56..45d60ced 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -11,7 +11,7 @@ libzebra_a_SOURCES = \ sockunion.c prefix.c thread.c if.c memory.c buffer.c table.c hash.c \ filter.c routemap.c distribute.c stream.c str.c log.c plist.c \ zclient.c sockopt.c smux.c md5.c if_rmap.c keychain.c privs.c \ - debug.c sigevent.c + debug.c sigevent.c pqueue.c libzebra_a_DEPENDENCIES = @LIB_REGEX@ @@ -22,7 +22,7 @@ pkginclude_HEADERS = \ memory.h network.h prefix.h routemap.h distribute.h sockunion.h \ str.h stream.h table.h thread.h vector.h version.h vty.h zebra.h \ plist.h zclient.h sockopt.h smux.h md5-gnu.h if_rmap.h keychain.h \ - privs.h debug.h sigevent.h + privs.h debug.h sigevent.h pqueue.h EXTRA_DIST = regex.c regex-gnu.h diff --git a/lib/pqueue.c b/lib/pqueue.c new file mode 100644 index 00000000..1e41b092 --- /dev/null +++ b/lib/pqueue.c @@ -0,0 +1,160 @@ +/* Priority queue functions. + Copyright (C) 2003 Yasuhiro Ohara + +This file is part of GNU Zebra. + +GNU Zebra is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published +by the Free Software Foundation; either version 2, or (at your +option) any later version. + +GNU Zebra is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Zebra; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +#include <zebra.h> + +#include "pqueue.h" + +/* priority queue using heap sort */ + +/* pqueue->cmp() controls the order of sorting (i.e, ascending or + descending). If you want the left node to move upper of the heap + binary tree, make cmp() to return less than 0. for example, if cmp + (10, 20) returns -1, the sorting is ascending order. if cmp (10, + 20) returns 1, the sorting is descending order. if cmp (10, 20) + returns 0, this library does not do sorting (which will not be what + you want). To be brief, if the contents of cmp_func (left, right) + is left - right, dequeue () returns the smallest node. Otherwise + (if the contents is right - left), dequeue () returns the largest + node. */ + +#define DATA_SIZE (sizeof (void *)) +#define PARENT_OF(x) ((x - 1) / 2) +#define LEFT_OF(x) (2 * x + 1) +#define RIGHT_OF(x) (2 * x + 2) +#define HAVE_CHILD(x,q) (x < (q)->size / 2) + +static void +trickle_up (int index, struct pqueue *queue) +{ + void *tmp; + + /* Save current node as tmp node. */ + tmp = queue->array[index]; + + /* Continue until the node reaches top or the place where the parent + node should be upper than the tmp node. */ + while (index > 0 && + (*queue->cmp) (tmp, queue->array[PARENT_OF (index)]) < 0) + { + /* actually trickle up */ + queue->array[index] = queue->array[PARENT_OF (index)]; + index = PARENT_OF (index); + } + + /* Restore the tmp node to appropriate place. */ + queue->array[index] = tmp; +} + +static void +trickle_down (int index, struct pqueue *queue) +{ + void *tmp; + int which; + + /* Save current node as tmp node. */ + tmp = queue->array[index]; + + /* Continue until the node have at least one (left) child. */ + while (HAVE_CHILD (index, queue)) + { + /* If right child exists, and if the right child is more proper + to be moved upper. */ + if (RIGHT_OF (index) < queue->size && + (*queue->cmp) (queue->array[LEFT_OF (index)], + queue->array[RIGHT_OF (index)]) > 0) + which = RIGHT_OF (index); + else + which = LEFT_OF (index); + + /* If the tmp node should be upper than the child, break. */ + if ((*queue->cmp) (queue->array[which], tmp) > 0) + break; + + /* Actually trickle down the tmp node. */ + queue->array[index] = queue->array[which]; + index = which; + } + + /* Restore the tmp node to appropriate place. */ + queue->array[index] = tmp; +} + +struct pqueue * +pqueue_create () +{ + struct pqueue *queue; + + queue = (struct pqueue *) malloc (sizeof (struct pqueue)); + memset (queue, 0, sizeof (struct pqueue)); + + queue->array = (void **) + malloc (DATA_SIZE * PQUEUE_INIT_ARRAYSIZE); + memset (queue->array, 0, DATA_SIZE * PQUEUE_INIT_ARRAYSIZE); + queue->array_size = PQUEUE_INIT_ARRAYSIZE; + + return queue; +} + +void +pqueue_delete (struct pqueue *queue) +{ + free (queue->array); + free (queue); +} + +static int +pqueue_expand (struct pqueue *queue) +{ + void **newarray; + + newarray = (void **) malloc (queue->array_size * DATA_SIZE * 2); + if (newarray == NULL) + return 0; + + memset (newarray, 0, queue->array_size * DATA_SIZE * 2); + memcpy (newarray, queue->array, queue->array_size * DATA_SIZE); + + free (queue->array); + queue->array = newarray; + queue->array_size *= 2; + + return 1; +} + +void +pqueue_enqueue (void *data, struct pqueue *queue) +{ + if (queue->size + 2 >= queue->array_size && ! pqueue_expand (queue)) + return; + + queue->array[queue->size] = data; + trickle_up (queue->size, queue); + queue->size ++; +} + +void * +pqueue_dequeue (struct pqueue *queue) +{ + void *data = queue->array[0]; + queue->array[0] = queue->array[--queue->size]; + trickle_down (0, queue); + return data; +} diff --git a/lib/pqueue.h b/lib/pqueue.h new file mode 100644 index 00000000..95f79b8c --- /dev/null +++ b/lib/pqueue.h @@ -0,0 +1,41 @@ +/* Priority queue functions. + Copyright (C) 2003 Yasuhiro Ohara + +This file is part of GNU Zebra. + +GNU Zebra is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published +by the Free Software Foundation; either version 2, or (at your +option) any later version. + +GNU Zebra is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Zebra; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +#ifndef _ZEBRA_PQUEUE_H +#define _ZEBRA_PQUEUE_H + +struct pqueue +{ + void **array; + int array_size; + int size; + + int (*cmp) (void *, void *); +}; + +#define PQUEUE_INIT_ARRAYSIZE 32 + +struct pqueue *pqueue_create (); +void pqueue_delete (struct pqueue *queue); + +void pqueue_enqueue (void *data, struct pqueue *queue); +void *pqueue_dequeue (struct pqueue *queue); + +#endif /* _ZEBRA_PQUEUE_H */ |