libtf: implement timeouts

internally put sleepers to d-ary heap based priority queue. the
heap value is compared with overflow.

1 files changed, 71 insertions, 0 deletions

diff --git a/include/libtf/heap.h b/include/libtf/heap.h
new file mode 100644
index 0000000..24f4767
--- /dev/null
+++ b/include/libtf/heap.h
@@ -0,0 +1,71 @@
+/* heap.h - libtf heap
+ *
+ * Copyright (C) 2009 Timo Teräs <timo.teras@iki.fi>
+ * All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 or later as
+ * published by the Free Software Foundation.
+ *
+ * See http://www.gnu.org/ for details.
+ */
+
+#ifndef TF_HEAP_H
+#define TF_HEAP_H
+
+#include <libtf/defines.h>
+
+#define TF_HEAP_D		4
+#define TF_HEAP_ITEM0		(TF_HEAP_D - 1)
+
+typedef tf_mtime_t tf_heap_priority;
+
+struct tf_heap_child {
+	struct tf_heap_node *	ptr;
+	tf_heap_priority	val;
+};
+
+struct tf_heap_node {
+	uint32_t		index;
+};
+
+struct tf_heap_head {
+	uint32_t		num_items;
+	uint32_t		allocated;
+	struct tf_heap_child *	item;
+};
+
+int __tf_heap_grow(struct tf_heap_head *head);
+void tf_heap_insert(struct tf_heap_node *node, struct tf_heap_head *head,
+		    tf_heap_priority val);
+void tf_heap_delete(struct tf_heap_node *node, struct tf_heap_head *head);
+void tf_heap_change(struct tf_heap_node *node, struct tf_heap_head *head,
+		    tf_heap_priority val);
+
+static inline
+tf_heap_priority tf_heap_get_value(struct tf_heap_head *head)
+{
+	return head->item[TF_HEAP_ITEM0].val;
+}
+
+static inline
+struct tf_heap_node *tf_heap_get_node(struct tf_heap_head *head)
+{
+	return head->item[TF_HEAP_ITEM0].ptr;
+}
+
+static inline
+int tf_heap_empty(struct tf_heap_head *head)
+{
+	return head->num_items == 0;
+}
+
+static inline
+int tf_heap_prealloc(struct tf_heap_head *head, uint32_t size)
+{
+	if (unlikely(head->num_items + TF_HEAP_ITEM0 >= head->allocated))
+		return __tf_heap_grow(head);
+	return 0;
+}
+
+#endif