summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/ChangeLog4
-rw-r--r--lib/Makefile.am4
-rw-r--r--lib/pqueue.c160
-rw-r--r--lib/pqueue.h41
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 */
generated by cgit v1.2.1 (git 2.18.0) at 2024-12-25 16:53:46 +0000