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_ */
