From 3ea1a77fb5419ffd2f9c997977b383b5faf75423 Mon Sep 17 00:00:00 2001 From: Timo Teras Date: Tue, 24 Nov 2009 11:36:24 +0200 Subject: libtf: implement timeouts internally put sleepers to d-ary heap based priority queue. the heap value is compared with overflow. --- include/libtf/heap.h | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 71 insertions(+) create mode 100644 include/libtf/heap.h (limited to 'include/libtf/heap.h') 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 + * 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 + +#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 -- cgit v1.2.3