Differential D32869 Diff 101218 sys/compat/linuxkpi/common/include/linux/interval_tree_generic.h

Changeset View

Standalone View

sys/compat/linuxkpi/common/include/linux/interval_tree_generic.h

This file was added.

				/*-
				* SPDX-License-Identifier: BSD-2-Clause-FreeBSD
				*
				* Copyright (c) 2019 Mark Kettenis <kettenis@OpenBSD.org>
				* Copyright (c) 2021 Vladimir Kondratyev <wulf@FreeBSD.org>
				gbeUnsubmitted Not Done Inline Actions When these functions are imported from OpenBSD, should that be somewhere noticed in the copyright statement? gbe: When these functions are imported from OpenBSD, should that be somewhere noticed in the…
				wulfAuthorUnsubmitted Done Inline Actions They are not imported directly from OpenBSD. OpenBSD version of linux/interval_tree_generic.h is dummy file [1]. But our generic version is inspired by their particular interval_tree implementation, so I agree, I have to add kettenis@ to authors. [1] https://github.com/openbsd/src/blob/master/sys/dev/pci/drm/include/linux/interval_tree_generic.h wulf: They are not imported directly from OpenBSD. OpenBSD version of linux/interval_tree_generic.h…
				*
				* Redistribution and use in source and binary forms, with or without
				* modification, are permitted provided that the following conditions
				* are met:
				* 1. Redistributions of source code must retain the above copyright
				* notice unmodified, this list of conditions, and the following
				* disclaimer.
				* 2. Redistributions in binary form must reproduce the above copyright
				* notice, this list of conditions and the following disclaimer in the
				* documentation and/or other materials provided with the distribution.
				*
				* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
				* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
				* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
				* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
				* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
				* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
				* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
				* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
				* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
				* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
				*/

				#include <linux/rbtree.h>

				#define INTERVAL_TREE_DEFINE(type, field, valtype, dummy, START, LAST, \
				attr, name) \
				__IT_DEFINE_ITER_FROM(type, field, valtype, START, LAST, name) \
				__IT_DEFINE_ITER_FIRST(type, valtype, attr, name) \
				__IT_DEFINE_ITER_NEXT(type, field, valtype, attr, name) \
				__IT_DEFINE_INSERT(type, field, START, attr, name) \
				__IT_DEFINE_REMOVE(type, field, attr, name)

				#define __IT_DEFINE_ITER_FROM(type, field, valtype, START, LAST, name) \
				static inline type * \
				name##_iter_from(struct rb_node *rb, valtype start, valtype last) \
				{ \
				type *node; \
				\
				while (rb != NULL) { \
				node = rb_entry(rb, type, field); \
				if (LAST(node) >= start && START(node) <= last) \
				return (node); \
				else if (START(node) > last) \
				break; \
				rb = rb_next(rb); \
				} \
				return (NULL); \
				}

				#define __IT_DEFINE_ITER_FIRST(type, valtype, attr, name) \
				attr type * \
				name##_iter_first(struct rb_root_cached *root, valtype start, valtype last) \
				{ \
				return (name##_iter_from(rb_first_cached(root), start, last)); \
				}

				#define __IT_DEFINE_ITER_NEXT(type, field, valtype, attr, name) \
				attr type * \
				name##_iter_next(type *node, valtype start, valtype last) \
				{ \
				return (name##_iter_from(rb_next(&node->field), start, last)); \
				}

				#define __IT_DEFINE_INSERT(type, field, START, attr, name) \
				attr void \
				name##_insert(type node, struct rb_root_cached root) \
				{ \
				struct rb_node **iter = &root->rb_root.rb_node; \
				struct rb_node *parent = NULL; \
				type *iter_node; \
				bool min_entry = true; \
				\
				while (*iter != NULL) { \
				parent = *iter; \
				iter_node = rb_entry(parent, type, field); \
				if (START(node) < START(iter_node)) \
				iter = &parent->rb_left; \
				else { \
				iter = &parent->rb_right; \
				min_entry = false; \
				} \
				} \
				\
				rb_link_node(&node->field, parent, iter); \
				rb_insert_color_cached(&node->field, root, min_entry); \
				}

				#define __IT_DEFINE_REMOVE(type, field, attr, name) \
				attr void \
				name##_remove(type node, struct rb_root_cached root) \
				{ \
				rb_erase_cached(&node->field, root); \
				}