this is an implementation of a heap data structure, specifically a pairing heap.
it is implemented like the RB trees in that it can be used to organise arbitrary structs with arbitrary compare functions. eg, we could queue tasks on a heap and order them by an execution deadline. ok? Index: share/man/man9/HEAP_INIT.9 =================================================================== RCS file: share/man/man9/HEAP_INIT.9 diff -N share/man/man9/HEAP_INIT.9 --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ share/man/man9/HEAP_INIT.9 4 Oct 2016 00:09:00 -0000 @@ -0,0 +1,207 @@ +.\" $OpenBSD$ +.\" +.\" Copyright (c) 2016 David Gwynne <d...@openbsd.org> +.\" +.\" Permission to use, copy, modify, and distribute this software for any +.\" purpose with or without fee is hereby granted, provided that the above +.\" copyright notice and this permission notice appear in all copies. +.\" +.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +.\" +.Dd $Mdocdate: September 5 2016 $ +.Dt HEAP_INIT 9 +.Os +.Sh NAME +.Nm HEAP_INIT , +.Nm HEAP_INSERT , +.Nm HEAP_REMOVE , +.Nm HEAP_FIRST , +.Nm HEAP_EXTRACT , +.Nm HEAP_CEXTRACT +.Nd Kernel Heap Data Structure +.Sh SYNOPSIS +.In sys/tree.h +.Fn HEAP_HEAD "NAME" +.Fn HEAP_PROTOTYPE "NAME" "TYPE" +.Fc +.Fo HEAP_GENERATE +.Fa "NAME" +.Fa "TYPE" +.Fa "ENTRY" +.Fa "int (*compare)(const struct TYPE *, const struct TYPE *)" +.Fc +.Ft struct NAME +.Fn HEAP_INITIALIZER +.Ft void +.Fn HEAP_INIT "NAME" "struct NAME *heap" +.Ft struct TYPE * +.Fn HEAP_INSERT "NAME" "struct NAME *heap" "struct TYPE *elm" +.Ft struct TYPE * +.Fn HEAP_REMOVE "NAME" "struct NAME *heap" "struct TYPE *elm" +.Ft struct TYPE * +.Fn HEAP_FIRST "NAME" "struct NAME *heap" +.Ft struct TYPE * +.Fn HEAP_EXTRACT "NAME" "struct NAME *heap" +.Ft struct TYPE * +.Fn HEAP_CEXTRACT "NAME" "struct NAME *heap" "const struct TYPE *key" +.Sh DESCRIPTION +The heap API provides data structures and operations for storing elements +in a heap. The API implements a pairing heap that sorts elements +according to a user defined comparison function. +.Pp +This API is implemented as a set of functions that operate on generic +pointers, but users of the API generate wrappers and macros that provide +type safety when calling the functions. +.Pp +In the macro definitions, +.Fa TYPE +is the name of a structure that will be stored in a heap. +The +.Fa TYPE +structure must contain an +heap_entry +structure that allows the element to be connected to a heap. +The argument +.Fa NAME +is the name of a heap type that can store a particular +.Fa TYPE +element. +.Pp +The +.Fn HEAP_HEAD +macro creates a heap type to store +.Fa TYPE +structures as elements in the heap. +The argument +.Fa NAME +must uniquely identify every type of heap that is defined. +.Pp +.Fn HEAP_PROTOTYPE +produces the wrappers for a heap type identified by +.Fa NAME +to operate on elements of type +.Fa TYPE . +.Pp +.Fn HEAP_GENERATE +produces the internal data structures used by the heap +type identified by +.Fa NAME +to operate on elements of type +.Fa TYPE . +.Fa ENTRY +specifies which field in the +.Fa TYPE +structure is used to connect elements to +.Fa NAME +heaps. +Elements in the heap are ordered according to the result of comparing +them with the +.Fa compare +function. +If the first argument to +.Fa compare +is to be ordered lower than the second, +the function returns a value smaller than zero. +If the first argument is to be ordered higher than the second, +the function returns a value greater than zero. +If they are equal, the function returns zero. +.Pp +.Fn HEAP_INIT +initialises +.Fa heap +of type +.Fa NAME +to an empty state. +.Pp +.Fn HEAP_INITIALIZER +can be used to initialise a declaration of a heap +to an empty state. +.Pp +.Fn HEAP_INSERT +inserts the element +.Fa elm +into the +.Fa heap +structure of type +.Fa NAME . +.Pp +.Fn HEAP_REMOVE +removes the element +.Fa elm +from the +.Fa heap +of type +.Fa NAME . +.Fa elm +must exist in the +.Fa heap +before it is removed. +.Pp +.Fn HEAP_FIRST +returns the lowest ordered element in the +.Fa heap +of type +.Fa NAME . +.Pp +.Fn HEAP_EXTRACT +removes the lowest ordered element from the +.Fa heap +of type +.Fa NAME +and returns it. +.Pp +.Fn HEAP_CEXTRACT +conditionally removes the lowest ordered element from the +.Fa heap +of type +.Fa NAME +and returns it if it compares lower than the +.Fa key +element. +.Sh CONTEXT +.Fn HEAP_INIT , +.Fn HEAP_INSERT, +.Fn HEAP_REMOVE , +.Fn HEAP_FIRST , +.Fn HEAP_EXTRACT , +and +.Fn HEAP_CEXTRACT +can be called during autoconf, from process context, or from interrupt +context. +.Pp +It is up to the caller to provide appropriate locking around calls to +these functions to prevent concurrent access to the relevant data structures. +.Sh RETURN VALUES +.Fn HEAP_FIRST +returns a reference to the lowest ordered element in the heap, +or +.Dv NULL +if it is empty. +.Pp +.Fn HEAP_EXTRACT +returns a reference to the lowest ordered element in the heap, +or +.Dv NULL +if it is empty. +.Pp +.Fn HEAP_CEXTRACT +returns a reference to the lowest ordered element in the heap if it compares +lower than the +.Fa key +argument, +or +.Dv NULL +if it is empty or the lowest ordered element is higher than +.Fa key . +.Sh SEE ALSO +.Xr RBT_INIT 3 , +.Xr TAILQ_INIT 3 +.Sh HISTORY +The kernel heap API first appeared in +.Ox 6.1 . Index: sys/kern/subr_tree.c =================================================================== RCS file: /cvs/src/sys/kern/subr_tree.c,v retrieving revision 1.6 diff -u -p -r1.6 subr_tree.c --- sys/kern/subr_tree.c 20 Sep 2016 01:11:27 -0000 1.6 +++ sys/kern/subr_tree.c 27 Sep 2016 04:22:52 -0000 @@ -610,3 +610,181 @@ _rb_check(const struct rb_type *t, void (unsigned long)RBE_LEFT(rbe) == poison && (unsigned long)RBE_RIGHT(rbe) == poison); } + +static inline struct heap_entry * +heap_n2e(const struct heap_type *t, void *node) +{ + caddr_t addr = (caddr_t)node; + + return ((struct heap_entry *)(addr + t->t_offset)); +} + +static inline void * +heap_e2n(const struct heap_type *t, struct heap_entry *rbe) +{ + caddr_t addr = (caddr_t)rbe; + + return ((void *)(addr - t->t_offset)); +} + +static struct heap_entry * +_heap_merge(const struct heap_type *t, + struct heap_entry *he1, struct heap_entry *he2) +{ + struct heap_entry *hi, *lo; + struct heap_entry *child; + + if (he1 == NULL) + return (he2); + if (he2 == NULL) + return (he1); + + if (t->t_compare(he1, he2) >= 0) { + hi = he1; + lo = he2; + } else { + lo = he1; + hi = he2; + } + + child = lo->he_child; + + hi->he_left = lo; + hi->he_nextsibling = child; + if (child != NULL) + child->he_left = hi; + lo->he_child = hi; + lo->he_left = NULL; + lo->he_nextsibling = NULL; + + return (lo); +} + +static inline void +_heap_sibling_remove(struct heap_entry *he) +{ + if (he->he_left == NULL) + return; + + if (he->he_left->he_child == he) { + if ((he->he_left->he_child = he->he_nextsibling) != NULL) + he->he_nextsibling->he_left = he->he_left; + } else { + if ((he->he_left->he_nextsibling = he->he_nextsibling) != NULL) + he->he_nextsibling->he_left = he->he_left; + } + + he->he_left = NULL; + he->he_nextsibling = NULL; +} + +static inline struct heap_entry * +_heap_2pass_merge(const struct heap_type *t, struct heap_entry *root) +{ + struct heap_entry *node, *next = NULL; + struct heap_entry *tmp, *list = NULL; + + node = root->he_child; + if (node == NULL) + return (NULL); + + root->he_child = NULL; + + /* first pass */ + for (next = node->he_nextsibling; next != NULL; + next = (node != NULL ? node->he_nextsibling : NULL)) { + tmp = next->he_nextsibling; + node = _heap_merge(t, node, next); + + /* insert head */ + node->he_nextsibling = list; + list = node; + node = tmp; + } + + /* odd child case */ + if (node != NULL) { + node->he_nextsibling = list; + list = node; + } + + /* second pass */ + while (list->he_nextsibling != NULL) { + tmp = list->he_nextsibling->he_nextsibling; + list = _heap_merge(t, list, list->he_nextsibling); + list->he_nextsibling = tmp; + } + + list->he_left = NULL; + list->he_nextsibling = NULL; + + return (list); +} + +void +_heap_insert(const struct heap_type *t, struct heap *h, void *node) +{ + struct heap_entry *he = heap_n2e(t, node); + + he->he_left = NULL; + he->he_child = NULL; + he->he_nextsibling = NULL; + + h->h_root = _heap_merge(t, h->h_root, he); +} + +void +_heap_remove(const struct heap_type *t, struct heap *h, void *node) +{ + struct heap_entry *he = heap_n2e(t, node); + + if (he->he_left == NULL) { + _heap_extract(t, h); + return; + } + + _heap_sibling_remove(he); + h->h_root = _heap_merge(t, h->h_root, _heap_2pass_merge(t, he)); +} + +void * +_heap_first(const struct heap_type *t, struct heap *h) +{ + struct heap_entry *first = h->h_root; + + if (first == NULL) + return (NULL); + + return (heap_e2n(t, first)); +} + +void * +_heap_extract(const struct heap_type *t, struct heap *h) +{ + struct heap_entry *first = h->h_root; + + if (first == NULL) + return (NULL); + + h->h_root = _heap_2pass_merge(t, first); + + return (heap_e2n(t, first)); +} + +void * +_heap_cextract(const struct heap_type *t, struct heap *h, const void *key) +{ + struct heap_entry *first = h->h_root; + void *node; + + if (first == NULL) + return (NULL); + + node = heap_e2n(t, first); + if (t->t_compare(node, key) > 0) + return (NULL); + + h->h_root = _heap_2pass_merge(t, first); + + return (node); +} Index: sys/sys/tree.h =================================================================== RCS file: /cvs/src/sys/sys/tree.h,v retrieving revision 1.24 diff -u -p -r1.24 tree.h --- sys/sys/tree.h 15 Sep 2016 06:07:22 -0000 1.24 +++ sys/sys/tree.h 27 Sep 2016 04:22:52 -0000 @@ -984,4 +984,107 @@ RBT_GENERATE_INTERNAL(_name, _type, _fie #endif /* _KERNEL */ +struct heap_type { + int (*t_compare)(const void *, const void *); + unsigned int t_offset; /* offset of heap_entry in type */ +}; + +struct heap_entry { + struct heap_entry *he_left; + struct heap_entry *he_child; + struct heap_entry *he_nextsibling; +}; + +struct heap { + struct heap_entry *h_root; +}; + +#define HEAP_HEAD(_name) \ +struct _name { \ + struct heap heap; \ +} + +#ifdef _KERNEL + +static inline void +_heap_init(struct heap *h) +{ + h->h_root = NULL; +} + +static inline int +_heap_empty(struct heap *h) +{ + return (h->h_root == NULL); +} + +void _heap_insert(const struct heap_type *, struct heap *, void *); +void _heap_remove(const struct heap_type *, struct heap *, void *); +void *_heap_first(const struct heap_type *, struct heap *); +void *_heap_extract(const struct heap_type *, struct heap *); +void *_heap_cextract(const struct heap_type *, struct heap *, const void *); + +#define HEAP_INITIALIZER(_head) { { NULL } } + +#define HEAP_PROTOTYPE(_name, _type) \ +extern const struct heap_type *const _name##_HEAP_TYPE; \ + \ +static inline void \ +_name##_HEAP_INIT(struct _name *head) \ +{ \ + _heap_init(&head->heap); \ +} \ + \ +static inline void \ +_name##_HEAP_INSERT(struct _name *head, struct _type *elm) \ +{ \ + _heap_insert(_name##_HEAP_TYPE, &head->heap, elm); \ +} \ + \ +static inline void \ +_name##_HEAP_REMOVE(struct _name *head, struct _type *elm) \ +{ \ + _heap_remove(_name##_HEAP_TYPE, &head->heap, elm); \ +} \ + \ +static inline struct _type * \ +_name##_HEAP_FIRST(struct _name *head) \ +{ \ + return _heap_first(_name##_HEAP_TYPE, &head->heap); \ +} \ + \ +static inline struct _type * \ +_name##_HEAP_EXTRACT(struct _name *head) \ +{ \ + return _heap_extract(_name##_HEAP_TYPE, &head->heap); \ +} \ + \ +static inline struct _type * \ +_name##_HEAP_CEXTRACT(struct _name *head, const struct _type *key) \ +{ \ + return _heap_cextract(_name##_HEAP_TYPE, &head->heap, key); \ +} + +#define HEAP_GENERATE(_name, _type, _field, _cmp) \ +static int \ +_name##_HEAP_COMPARE(const void *lptr, const void *rptr) \ +{ \ + const struct _type *l = lptr, *r = rptr; \ + return _cmp(l, r); \ +} \ +static const struct heap_type _name##_HEAP_INFO = { \ + _name##_HEAP_COMPARE, \ + offsetof(struct _type, _field), \ +}; \ +const struct heap_type *const _name##_HEAP_TYPE = &_name##_HEAP_INFO + +#define HEAP_INIT(_name, _h) _name##_HEAP_INIT((_h)) +#define HEAP_INSERT(_name, _h, _e) _name##_HEAP_INSERT((_h), (_e)) +#define HEAP_REMOVE(_name, _h, _e) _name##_HEAP_REMOVE((_h), (_e)) +#define HEAP_FIRST(_name, _h) _name##_HEAP_FIRST((_h)) +#define HEAP_EXTRACT(_name, _h) _name##_HEAP_EXTRACT((_h)) +#define HEAP_CEXTRACT(_name, _h, _k) _name##_HEAP_CEXTRACT((_h), (_k)) + +#endif /* _KERNEL */ + #endif /* _SYS_TREE_H_ */