| /freebsd/sys/contrib/openzfs/module/zfs/ |
| H A D | btree.c | 1 // SPDX-License-Identifier: CDDL-1.0
7 * You may only use this file in accordance with the terms of version
33 * Intensity 1: Verify that the tree's height is consistent throughout.
36 * Intensity 3: Verify that the total number of elements in the tree matches the
37 * sum of the number of elements in each node. Also verifies that each node's
43 * than the last element in the first of the two nodes it separates, and less
44 * than the first element in the second of the two nodes.
52 * operations per element. In addition, when creating large btrees, these
53 * operations are called at every step, resulting in extremely slow operation
78 return (hdr->bth_first == -1); in zfs_btree_is_core()
[all …]
|
| /freebsd/contrib/unbound/edns-subnet/ |
| H A D | addrtree.c | 2 * edns-subnet/addrtree.c -- radix tree for edns subnet cache.
8 * Redistribution and use in source and binary forms, with or without
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 * addrtree -- radix tree for edns subnet cache.
62 edge->node = node; in edge_create()
63 edge->len = addrlen; in edge_create()
[all …]
|
| H A D | addrtree.h | 2 * edns-subnet/addrtree.h -- radix tree for edns subnet cache.
8 * Redistribution and use in source and binary forms, with or without
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
38 * The addrtree is a radix tree designed for edns subnet. Most notable
44 * (sourcemask). While traversing the tree the first matching node is
54 * tree the scope of all visited nodes is updated. This ensures we are
[all …]
|
| /freebsd/share/man/man3/ |
| H A D | tree.3 | 1 .\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
6 .\" Redistribution and use in source and binary forms, with or without
11 .\" 2. Redistributions in binary form must reproduce the above copyright
12 .\" notice, this list of conditions and the following disclaimer in the
23 .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
27 .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
105 .Nd "implementations of splay and rank-balanced (wavl) trees"
211 splay trees and rank-balanced (wavl) trees.
230 has to be a unique name prefix for every tree that is defined.
[all …]
|
| H A D | arb.3 | 1 .\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
4 .\" Copyright 2018-2019 Netflix, Inc.
7 .\" Redistribution and use in source and binary forms, with or without
12 .\" 2. Redistributions in binary form must reproduce the above copyright
13 .\" notice, this list of conditions and the following disclaimer in the
24 .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
28 .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
98 .Nd "array-based red-black trees"
185 These macros define data structures for and array-based red-black trees.
[all …]
|
| /freebsd/usr.sbin/etcupdate/ |
| H A D | etcupdate.8 | 1 .\" Copyright (c) 2010-2013 Hudson River Trading LLC
5 .\" Redistribution and use in source and binary forms, with or without
10 .\" 2. Redistributions in binary form must reproduce the above copyright
11 .\" notice, this list of conditions and the following disclaimer in the
17 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
89 such as files in
91 It manages updates by doing a three-way merge of changes made to these
96 To perform a three-way merge,
[all …]
|
| /freebsd/sys/contrib/openzfs/include/sys/ |
| H A D | avl.h | 1 // SPDX-License-Identifier: CDDL-1.0
7 * You may not use this file except in compliance with the License.
10 * or https://opensource.org/licenses/CDDL-1.0.
14 * When distributing Covered Code, include this CDDL HEADER in each
47 * This is a generic implementation of AVL trees for use in the Solaris kernel.
53 * linked list in general requires 2 pointers in each data structure. The
54 * AVL tree implementation uses 3 pointers. The following chart gives the
57 * Operation Link List AVL tree
58 * --------- -------- --------
75 * The type "avl_index_t" is used to indicate a position in the list for
[all …]
|
| H A D | btree.h | 1 // SPDX-License-Identifier: CDDL-1.0
7 * You may only use this file in accordance with the terms of version
30 * This file defines the interface for a B-Tree implementation for ZFS. The
31 * tree can be used to store arbitrary sortable data types with low overhead
32 * and good operation performance. In addition the tree intelligently
33 * optimizes bulk in-order insertions to improve memory use and performance.
35 * Note that for all B-Tree functions, the values returned are pointers to the
36 * internal copies of the data in the tree. The internal data can only be
38 * with respect to any other elements in the tree.
40 * The major drawback of the B-Tree is that any returned elements or indexes
[all …]
|
| /freebsd/sys/cddl/contrib/opensolaris/uts/common/sys/ |
| H A D | avl.h | 6 * You may not use this file except in compliance with the License.
13 * When distributing Covered Code, include this CDDL HEADER in each
46 * This is a generic implementation of AVL trees for use in the Solaris kernel.
52 * linked list in general requires 2 pointers in each data structure. The
53 * AVL tree implementation uses 3 pointers. The following chart gives the
56 * Operation Link List AVL tree
57 * --------- -------- --------
74 * The type "avl_index_t" is used to indicate a position in the list for
79 * 1. Create the list/tree with: avl_create()
86 * avl_first() - returns the lowest valued node
[all …]
|
| /freebsd/sys/contrib/openzfs/module/avl/ |
| H A D | avl.c | 1 // SPDX-License-Identifier: CDDL-1.0
7 * You may not use this file except in compliance with the License.
10 * or https://opensource.org/licenses/CDDL-1.0.
14 * When distributing Covered Code, include this CDDL HEADER in each
33 * AVL - generic AVL tree implementation for kernel use
35 * A complete description of AVL trees can be found in many CS textbooks.
37 * Here is a very brief overview. An AVL tree is a binary search tree that is
39 * any given node, the left and right subtrees are allowed to differ in height
42 * This relaxation from a perfectly balanced binary tree allows doing
43 * insertion and deletion relatively efficiently. Searching the tree is
[all …]
|
| /freebsd/contrib/kyua/engine/ |
| H A D | config.cpp | 4 // Redistribution and use in source and binary forms, with or without
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
41 #include "utils/config/tree.ipp"
56 /// Defines the schema of a configuration tree.
58 /// \param [in,out] tree The tree to populate. The tree should be empty on
59 /// entry to prevent collisions with the keys defined in here.
[all …]
|
| /freebsd/contrib/ldns/ldns/ |
| H A D | rbtree.h | 2 * rbtree.h -- generic red-black tree
4 * Copyright (c) 2001-2008, NLnet Labs. All rights reserved.
8 * Redistribution and use in source and binary forms, with or without
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
39 * Red black tree. Implementation taken from NSD 3.0.5, adjusted for use
40 * in unbound (memory allocation, logging and so on).
[all …]
|
| H A D | radix.h | 2 * radix.h -- generic radix tree
8 * Redistribution and use in source and binary forms, with or without
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
39 * Radix tree. Implementation taken from NSD 4, adjusted for use in ldns.
67 /** A node in a radix tree */
77 /** Index in the the parent node select edge array. */
[all …]
|
| /freebsd/contrib/unbound/util/ |
| H A D | rbtree.h | 2 * rbtree.h -- generic red-black tree
4 * Copyright (c) 2001-2007, NLnet Labs. All rights reserved.
8 * Redistribution and use in source and binary forms, with or without
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
39 * Red black tree. Implementation taken from NSD 3.0.5, adjusted for use
40 * in unbound (memory allocation, logging and so on).
[all …]
|
| /freebsd/usr.bin/dtc/ |
| H A D | dtc.1 | 1 .\"-
6 .\" Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
10 .\" Redistribution and use in source and binary forms, with or without
15 .\" 2. Redistributions in binary form must reproduce the above copyright
16 .\" notice, this list of conditions and the following disclaimer in the
22 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
26 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36 .Nd device tree compiler
43 .Op Fl E Ar [no-]checker_name
[all …]
|
| /freebsd/crypto/openssl/crypto/x509/ |
| H A D | pcy_tree.c | 2 * Copyright 2004-2023 The OpenSSL Project Authors. All Rights Reserved.
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
18 * If the maximum number of nodes in the policy tree isn't defined, set it to
21 * Defining this to be zero means unlimited policy tree growth which opens the
22 * door on CVE-2023-0464.
34 if ((lev->flags & X509_V_FLAG_INHIBIT_MAP) in expected_print()
35 || !(node->data->flags & POLICY_DATA_FLAG_MAP_MASK)) in expected_print()
40 STACK_OF(ASN1_OBJECT) *pset = node->data->expected_policy_set; in expected_print()
54 char *str, X509_POLICY_TREE *tree, in tree_print() argument
[all …]
|
| /freebsd/contrib/llvm-project/llvm/include/llvm/Support/ |
| H A D | SuffixTree.h | 1 //===- llvm/ADT/SuffixTree.h - Tree for substrings --------------*- C++ -*-===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 // Suffix trees represent the suffixes of their input strings in their leaves.
11 // A suffix tree is a type of compressed trie structure where each node
13 // of the tree is a suffix.
15 // A suffix tree can be seen as a type of state machine where each state is a
16 // substring of the full string. The tree is structured so that, for a string
17 // of length N, there are exactly N leaves in the tree. This structure allows
20 // In this implementation, a "string" is a vector of unsigned integers.
[all …]
|
| /freebsd/usr.sbin/etcupdate/tests/ |
| H A D | ignore_test.sh | 7 # Redistribution and use in source and binary forms, with or without
12 # 2. Redistributions in binary form must reproduce the above copyright
13 # notice, this list of conditions and the following disclaimer in the
19 # ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23 # HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 # Various regression tests to test the -I flag to the 'update' command.
36 echo "Usage: ignore.sh [-s script] [-w workdir]"
43 case $option in
56 shift $((OPTIND - 1))
[all …]
|
| /freebsd/contrib/ofed/opensm/include/opensm/ |
| H A D | osm_mtree.h | 2 * Copyright (c) 2004-2009 Voltaire, Inc. All rights reserved.
3 * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved.
4 * Copyright (c) 1996-2003 Intel Corporation. All rights reserved.
9 * COPYING in the main directory of this source tree, or the
12 * Redistribution and use in source and binary forms, with or
16 * - Redistributions of source code must retain the above
20 * - Redistributions in binary form must reproduce the above
22 * disclaimer in the documentation and/or other materials
28 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
29 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
[all …]
|
| /freebsd/contrib/kyua/utils/config/ |
| H A D | lua_module_test.cpp | 4 // Redistribution and use in source and binary forms, with or without
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 #include <atf-c++.hpp>
37 #include "utils/config/tree.ipp"
46 /// Non-native type to use as a leaf node.
48 /// The value recorded in the object.
[all …]
|
| H A D | tree_test.cpp | 4 // Redistribution and use in source and binary forms, with or without
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 #include "utils/config/tree.ipp"
31 #include <atf-c++.hpp>
47 /// constructors to validate that we can use it as a leaf of a tree.
55 /// \param value_ The value to store in the object.
[all …]
|
| H A D | lua_module.cpp | 4 // Redistribution and use in source and binary forms, with or without
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
36 #include "utils/config/tree.ipp"
45 /// Gets the tree singleton stored in the Lua state.
48 /// "tree" with a pointer to the singleton.
50 /// \return A reference to the tree associated with the Lua state.
[all …]
|
| /freebsd/share/man/man4/ |
| H A D | fdt.4 | 7 .\" Redistribution and use in source and binary forms, with or without
12 .\" 2. Redistributions in binary form must reproduce the above copyright
13 .\" notice, this list of conditions and the following disclaimer in the
19 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 .Nd Flattened Device Tree support
39 .Em Flattened Device Tree
41 probed or self enumerated, in a uniform and portable way.
48 Configuration data, which cannot be self discovered in run-time, has to be
[all …]
|
| /freebsd/contrib/ncurses/ncurses/base/ |
| H A D | tries.c | 3 * Copyright 1998-2009,2010 Free Software Foundation, Inc. *
7 * "Software"), to deal in the Software without restriction, including *
14 * in all copies or substantial portions of the Software. *
19 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, *
20 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR *
21 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR *
22 * THE USE OR OTHER DEALINGS IN THE SOFTWARE. *
24 * Except as contained in this notice, the name(s) of the above copyright *
25 * holders shall not be used in advertising or otherwise to promote the *
26 * sale, use or other dealings in this Software without prior written *
[all …]
|
| /freebsd/contrib/unbound/util/storage/ |
| H A D | dnstree.h | 2 * util/storage/dnstree.h - support for rbtree types suitable for DNS code.
8 * Redistribution and use in source and binary forms, with or without
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
48 * Tree of domain names. Sorted first by class then by name.
52 * The tree itself is a rbtree_type.
53 * This is the element node put as first entry in the client structure.
[all …]
|