This will be needed to keep track of multiple different deadlines
using a single timer.
Signed-off-by: Richard Cochran <richardcoch...@gmail.com>
---
makefile | 6 +--
pqueue.c | 138 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
pqueue.h | 38 ++++++++++++++++++
3 files changed, 179 insertions(+), 3 deletions(-)
create mode 100644 pqueue.c
create mode 100644 pqueue.h
diff --git a/makefile b/makefile
index 4fca3f0..fdc9e5e 100644
--- a/makefile
+++ b/makefile
@@ -25,9 +25,9 @@ LDLIBS = -lm -lrt $(EXTRA_LDFLAGS)
PRG = ptp4l hwstamp_ctl nsm phc2sys phc_ctl pmc timemaster
OBJ = bmc.o clock.o clockadj.o clockcheck.o config.o e2e_tc.o fault.o \
filter.o fsm.o hash.o linreg.o mave.o mmedian.o msg.o ntpshm.o nullf.o phc.o \
- pi.o port.o port_signaling.o print.o ptp4l.o p2p_tc.o raw.o rtnl.o servo.o \
- sk.o stats.o tc.o telecom.o tlv.o transport.o tsproc.o udp.o udp6.o uds.o \
- unicast_client.o unicast_fsm.o util.o version.o
+ pi.o port.o port_signaling.o pqueue.o print.o ptp4l.o p2p_tc.o raw.o rtnl.o \
+ servo.o sk.o stats.o tc.o telecom.o tlv.o transport.o tsproc.o udp.o udp6.o \
+ uds.o unicast_client.o unicast_fsm.o util.o version.o
OBJECTS = $(OBJ) hwstamp_ctl.o nsm.o phc2sys.o phc_ctl.o pmc.o
pmc_common.o \
sysoff.o timemaster.o
diff --git a/pqueue.c b/pqueue.c
new file mode 100644
index 0000000..846faca
--- /dev/null
+++ b/pqueue.c
@@ -0,0 +1,138 @@
+/**
+ * @file pqueue.c
+ * @brief Implements a priority queue.
+ * @note Copyright (c) 2015 Richard Cochran <richardcoch...@gmail.com>
+ *
+ * This program 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 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA.
+ */
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+#include "pqueue.h"
+
+#define parent(x) (((1 + (x)) >> 1) - 1)
+#define left(x) (((1 + (x)) << 1) - 1)
+#define right(x) (((1 + (x)) << 1))
+
+struct pqueue {
+ int len;
+ int max;
+ int (*cmp)(void *a, void *b);
+ void **data;
+};
+
+static int pq_greater(struct pqueue *q, int a, int b)
+{
+ return q->cmp(q->data[a], q->data[b]) > 0 ? 1 : 0;
+}
+
+static void heapify(struct pqueue *q, int index)
+{
+ int i_max = index;
+ int left = left(index);
+ int right = right(index);
+
+ if (left < q->len) {
+ if (pq_greater(q, left, i_max))
+ i_max = left;
+ }
+
+ if (right < q->len && pq_greater(q, right, i_max)) {
+ i_max = right;
+ }
+
+ if (i_max != index) {
+ void *tmp = q->data[index];
+ q->data[index] = q->data[i_max];
+ q->data[i_max] = tmp;
+ heapify(q, i_max);
+ }
+}
+
+/* public methods */
+
+struct pqueue *pqueue_create(int max_length,
+ int (*compare)(void *a, void *b))
+{
+ struct pqueue *q = calloc(1, sizeof(*q));
+ if (!q) {
+ return NULL;
+ }
+ q->len = 0;
+ q->max = max_length;
+ q->cmp = compare;
+ q->data = calloc(max_length, sizeof(void *));
+ if (!q->data) {
+ free(q);
+ return NULL;
+ }
+ return q;
+}
+
+void pqueue_destroy(struct pqueue *q)
+{
+ free(q->data);
+ free(q);
+}
+
+void *pqueue_extract(struct pqueue *q)
+{
+ void *data;
+
+ if (!q->len) {
+ return NULL;
+ }
+ data = q->data[0];
+ q->data[0] = q->data[q->len - 1];
+ q->len--;
+ heapify(q, 0);
+
+ return data;
+}
+
+int pqueue_insert(struct pqueue *q, void *d)
+{
+ int index;
+
+ if (q->len >= q->max) {
+ void **buf = realloc(q->data, 2 * q->max * sizeof(void *));
+ if (buf) {
+ q->data = buf;
+ q->max *= 2;
+ } else {
+ return -ENOMEM;
+ }
+ }
+ index = q->len;
+ q->len++;
+
+ while (index && (q->cmp(q->data[parent(index)], d) < 0)) {
+ q->data[index] = q->data[parent(index)];
+ index = parent(index);
+ }
+ q->data[index] = d;
+
+ return 0;
+}
+
+int pqueue_length(struct pqueue *q)
+{
+ return q->len;
+}
+
+void *pqueue_peek(struct pqueue *q)
+{
+ return q->len ? q->data[0] : (void *) 0;
+}
diff --git a/pqueue.h b/pqueue.h
new file mode 100644
index 0000000..94b7250
--- /dev/null
+++ b/pqueue.h
@@ -0,0 +1,38 @@
+/**
+ * @file pqueue.h
+ * @brief Implements a priority queue.
+ * @note Copyright (c) 2015 Richard Cochran <richardcoch...@gmail.com>
+ *
+ * This program 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 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA.
+ */
+#ifndef HAVE_PQUEUE_H
+#define HAVE_PQUEUE_H
+
+struct pqueue;
+
+struct pqueue *pqueue_create(int max_length,
+ int (*compare)(void *a, void *b));
+
+void pqueue_destroy(struct pqueue *q);
+
+void *pqueue_extract(struct pqueue *q);
+
+int pqueue_insert(struct pqueue *q, void *d);
+
+int pqueue_length(struct pqueue *q);
+
+void *pqueue_peek(struct pqueue *q);
+
+#endif
--
2.11.0
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Linuxptp-devel mailing list
Linuxptp-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linuxptp-devel
