aboutsummaryrefslogtreecommitdiff
path: root/sys/sys/_rangeset.h
diff options
context:
space:
mode:
authorKonstantin Belousov <kib@FreeBSD.org>2019-02-20 09:38:19 +0000
committerKonstantin Belousov <kib@FreeBSD.org>2019-02-20 09:38:19 +0000
commit1809ef7836aeabe13c91cb41aed695a306ae1b46 (patch)
tree34dcf2b4c9567f8037251763dbeeb960b455ef22 /sys/sys/_rangeset.h
parent90ce6e8cfdc105d26e13b3908cc8c87348031da7 (diff)
downloadsrc-1809ef7836aeabe13c91cb41aed695a306ae1b46.tar.gz
src-1809ef7836aeabe13c91cb41aed695a306ae1b46.zip
Implement rangesets.
The data structure implements non-intersecting intervals over the [0, UINT64_MAX] range, and supports fast insert, predicated clearing of subrange, and lookup of an interval containing the specified address. Internally it is a pctrie over the interval start addresses. Implementation provides additional guarantees over the structure state in case of memory allocation failures. Reviewed by: markj Tested by: pho Sponsored by: The FreeBSD Foundation MFC after: 2 weeks Differential revision: https://reviews.freebsd.org/D18893
Notes
Notes: svn path=/head/; revision=344351
Diffstat (limited to 'sys/sys/_rangeset.h')
-rw-r--r--sys/sys/_rangeset.h51
1 files changed, 51 insertions, 0 deletions
diff --git a/sys/sys/_rangeset.h b/sys/sys/_rangeset.h
new file mode 100644
index 000000000000..a700c6eaf23e
--- /dev/null
+++ b/sys/sys/_rangeset.h
@@ -0,0 +1,51 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * Copyright (c) 2019 The FreeBSD Foundation
+ * All rights reserved.
+ *
+ * This software was developed by Konstantin Belousov <kib@FreeBSD.org>
+ * under sponsorship from the FreeBSD Foundation.
+ *
+ * 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, 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 AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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.
+ *
+ * $FreeBSD$
+ */
+
+#ifndef _SYS__RANGESET_H
+#define _SYS__RANGESET_H
+
+#include <sys/_pctrie.h>
+
+typedef void *(*rs_dup_data_t)(void *ctx, void *data);
+typedef void (*rs_free_data_t)(void *ctx, void *data);
+
+struct rangeset {
+ struct pctrie rs_trie;
+ rs_dup_data_t rs_dup_data;
+ rs_free_data_t rs_free_data;
+ void *rs_data_ctx;
+ u_int rs_alloc_flags;
+};
+
+#endif
+