The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/sys/ptree.h

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10  
    1 /*      $NetBSD: ptree.h,v 1.8 2012/10/06 22:15:09 matt Exp $   */
    2 
    3 /*-
    4  * Copyright (c) 2008 The NetBSD Foundation, Inc.
    5  * All rights reserved.
    6  *
    7  * This code is derived from software contributed to The NetBSD Foundation
    8  * by Matt Thomas <matt@3am-software.com>
    9  *
   10  * Redistribution and use in source and binary forms, with or without
   11  * modification, are permitted provided that the following conditions
   12  * are met:
   13  * 1. Redistributions of source code must retain the above copyright
   14  *    notice, this list of conditions and the following disclaimer.
   15  * 2. Redistributions in binary form must reproduce the above copyright
   16  *    notice, this list of conditions and the following disclaimer in the
   17  *    documentation and/or other materials provided with the distribution.
   18  *
   19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
   20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
   23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   29  * POSSIBILITY OF SUCH DAMAGE.
   30  */
   31 
   32 #ifndef _SYS_PTREE_H_
   33 #define _SYS_PTREE_H_
   34 
   35 #if !defined(_KERNEL) && !defined(_STANDALONE)
   36 #include <stdbool.h>
   37 #include <stdint.h>
   38 #endif
   39 
   40 typedef enum {
   41         PT_DESCENDING=-1,
   42         PT_ASCENDING=1
   43 } pt_direction_t;
   44 
   45 typedef unsigned int pt_slot_t;
   46 typedef unsigned int pt_bitoff_t;
   47 typedef unsigned int pt_bitlen_t;
   48 
   49 typedef struct pt_node {
   50         uintptr_t ptn_slots[2];         /* must be first */
   51 #define PT_SLOT_LEFT                    0u
   52 #define PT_SLOT_RIGHT                   1u
   53 #ifdef _PT_PRIVATE
   54 #define PT_SLOT_ROOT                    0u
   55 #define PT_SLOT_OTHER                   1u
   56 #define PT_SLOT_ODDMAN                  1u
   57 #define PT_TYPE_LEAF                    ((uintptr_t)0x00000000u)
   58 #define PT_TYPE_BRANCH                  ((uintptr_t)0x00000001u)
   59 #define PT_TYPE_MASK                    ((uintptr_t)0x00000001u)
   60 #endif /* _PT_PRIVATE */
   61 
   62         uint32_t ptn_nodedata;
   63 #ifdef _PT_PRIVATE
   64 #define PTN_LEAF_POSITION_BITS          8u
   65 #define PTN_LEAF_POSITION_SHIFT         0u
   66 #define PTN_BRANCH_POSITION_BITS        8u
   67 #define PTN_BRANCH_POSITION_SHIFT       8u
   68 #ifndef PTNOMASK
   69 #define PTN_MASK_BITLEN_BITS            15u
   70 #define PTN_MASK_BITLEN_SHIFT           16u
   71 #define PTN_MASK_FLAG                   0x80000000u
   72 #endif
   73 #endif /* _PT_PRIVATE */
   74 
   75         uint32_t ptn_branchdata;
   76 #ifdef _PT_PRIVATE
   77 #define PTN_BRANCH_BITOFF_BITS          15u
   78 #define PTN_BRANCH_BITOFF_SHIFT         0u
   79 #define PTN_BRANCH_BITLEN_BITS          8u
   80 #define PTN_BRANCH_BITLEN_SHIFT         16u
   81 #if 0
   82 #define PTN_ORIENTATION_BITS            1u
   83 #define PTN_ORIENTATION_SHIFT           30u
   84 #endif
   85 #define PTN_BRANCH_UNUSED               0x3f000000u
   86 #define PTN_XBRANCH_FLAG                0x80000000u
   87 #endif /* _PT_PRIVATE */
   88 } pt_node_t;
   89 
   90 #ifdef _PT_PRIVATE
   91 #define PT_NODE(node)           ((pt_node_t *)(node & ~PT_TYPE_MASK))
   92 #define PT_TYPE(node)           ((node) & PT_TYPE_MASK)
   93 #define PT_NULL                 0
   94 #define PT_NULL_P(node)         ((node) == PT_NULL)
   95 #define PT_LEAF_P(node)         (PT_TYPE(node) == PT_TYPE_LEAF)
   96 #define PT_BRANCH_P(node)       (PT_TYPE(node) == PT_TYPE_BRANCH)
   97 #define PTN__TYPELESS(ptn)      (((uintptr_t)ptn) & ~PT_TYPE_MASK)
   98 #define PTN_LEAF(ptn)           (PTN__TYPELESS(ptn) | PT_TYPE_LEAF)
   99 #define PTN_BRANCH(ptn)         (PTN__TYPELESS(ptn) | PT_TYPE_BRANCH)
  100 
  101 #ifndef PTNOMASK
  102 #define PTN_MARK_MASK(ptn)      ((ptn)->ptn_nodedata |= PTN_MASK_FLAG)
  103 #define PTN_ISMASK_P(ptn)       (((ptn)->ptn_nodedata & PTN_MASK_FLAG) != 0)
  104 #endif
  105 #define PTN_MARK_XBRANCH(ptn)   ((ptn)->ptn_branchdata |= PTN_XBRANCH_FLAG)
  106 #define PTN_ISXBRANCH_P(ptn)    (((ptn)->ptn_branchdata & PTN_XBRANCH_FLAG) != 0)
  107 #define PTN_ISROOT_P(pt, ptn)   ((ptn) == &(pt)->pt_rootnode)
  108 
  109 #define PTN_BRANCH_SLOT(ptn,slot)       ((ptn)->ptn_slots[slot])
  110 #define PTN_BRANCH_ROOT_SLOT(ptn)       ((ptn)->ptn_slots[PT_SLOT_ROOT])
  111 #define PTN_BRANCH_ODDMAN_SLOT(ptn)     ((ptn)->ptn_slots[PT_SLOT_ODDMAN])
  112 #define PTN_COPY_BRANCH_SLOTS(dst,src)  \
  113         ((dst)->ptn_slots[PT_SLOT_LEFT ] = (src)->ptn_slots[PT_SLOT_LEFT ], \
  114          (dst)->ptn_slots[PT_SLOT_RIGHT] = (src)->ptn_slots[PT_SLOT_RIGHT])
  115 #define PTN_ISSLOTVALID_P(ptn,slot)     ((slot) < (1 << PTN_BRANCH_BITLEN(pt)))
  116 
  117 #define PT__MASK(n)             ((1 << n ## _BITS) - 1)  
  118 #define PT__SHIFT(n)            (n ## _SHIFT)
  119 #define PTN__EXTRACT(field, b) \
  120         (((field) >> PT__SHIFT(b)) & PT__MASK(b))
  121 #define PTN__INSERT2(field, v, shift, mask) \
  122         ((field) = ((field) & ~((mask) << (shift))) | ((v) << (shift)))
  123 #define PTN__INSERT(field, b, v) \
  124         PTN__INSERT2(field, v, PT__SHIFT(b), PT__MASK(b))
  125 
  126 #define PTN_BRANCH_BITOFF(ptn)          \
  127         PTN__EXTRACT((ptn)->ptn_branchdata, PTN_BRANCH_BITOFF)
  128 #define PTN_BRANCH_BITLEN(ptn)          \
  129         PTN__EXTRACT((ptn)->ptn_branchdata, PTN_BRANCH_BITLEN)
  130 #define PTN_SET_BRANCH_BITOFF(ptn,bitoff) \
  131         PTN__INSERT((ptn)->ptn_branchdata, PTN_BRANCH_BITOFF, bitoff)
  132 #define PTN_SET_BRANCH_BITLEN(ptn,bitlen) \
  133         PTN__INSERT((ptn)->ptn_branchdata, PTN_BRANCH_BITLEN, bitlen)
  134 
  135 #define PTN_LEAF_POSITION(ptn)          \
  136         PTN__EXTRACT((ptn)->ptn_nodedata, PTN_LEAF_POSITION)
  137 #define PTN_BRANCH_POSITION(ptn)        \
  138         PTN__EXTRACT((ptn)->ptn_nodedata, PTN_BRANCH_POSITION)
  139 #define PTN_SET_LEAF_POSITION(ptn,slot) \
  140         PTN__INSERT((ptn)->ptn_nodedata, PTN_LEAF_POSITION, slot)
  141 #define PTN_SET_BRANCH_POSITION(ptn,slot) \
  142         PTN__INSERT((ptn)->ptn_nodedata, PTN_BRANCH_POSITION, slot)
  143 
  144 #ifndef PTNOMASK
  145 #define PTN_MASK_BITLEN(ptn)            \
  146         PTN__EXTRACT((ptn)->ptn_nodedata, PTN_MASK_BITLEN)
  147 #define PTN_SET_MASK_BITLEN(ptn,masklen) \
  148         PTN__INSERT((ptn)->ptn_nodedata, PTN_MASK_BITLEN, masklen)
  149 #endif
  150 
  151 #if 0
  152 #define PTN_ORIENTATION(ptn)    \
  153         PTN__EXTRACT((ptn)->ptn_branchdata, PTN_ORIENTATION)
  154 #define PTN_SET_ORIENTATION(ptn,slot) \
  155         PTN__INSERT((ptn)->ptn_branchdata, PTN_ORIENTATION, slot)
  156 #endif
  157 #endif /* _PT_PRIVATE */
  158 
  159 typedef struct pt_tree_ops {
  160         bool (*ptto_matchnode)(const void *, const void *,
  161                 pt_bitoff_t, pt_bitoff_t *, pt_slot_t *, void *);
  162         bool (*ptto_matchkey)(const void *, const void *,
  163                 pt_bitoff_t, pt_bitlen_t, void *);
  164         pt_slot_t (*ptto_testnode)(const void *,
  165                 pt_bitoff_t, pt_bitlen_t, void *);
  166         pt_slot_t (*ptto_testkey)(const void *,
  167                 pt_bitoff_t, pt_bitlen_t, void *);
  168 } pt_tree_ops_t;
  169 
  170 typedef struct pt_tree {
  171         pt_node_t pt_rootnode;
  172 #define pt_root                 pt_rootnode.ptn_slots[PT_SLOT_ROOT]
  173 #define pt_oddman               pt_rootnode.ptn_slots[PT_SLOT_ODDMAN]
  174         const pt_tree_ops_t *pt_ops;
  175         size_t pt_node_offset;
  176         size_t pt_key_offset;
  177         void *pt_context;
  178         uintptr_t pt_spare[3];
  179 } pt_tree_t;
  180 
  181 #define PT_FILTER_MASK          0x00000001      /* node is a mask */
  182 typedef bool (*pt_filter_t)(void *, const void *, int);
  183 
  184 void    ptree_init(pt_tree_t *, const pt_tree_ops_t *, void *, size_t, size_t);
  185 bool    ptree_insert_node(pt_tree_t *, void *);
  186 bool    ptree_insert_mask_node(pt_tree_t *, void *, pt_bitlen_t);
  187 bool    ptree_mask_node_p(pt_tree_t *, const void *, pt_bitlen_t *);
  188 void *  ptree_find_filtered_node(pt_tree_t *, const void *, pt_filter_t, void *);
  189 #define ptree_find_node(pt,key) \
  190         ptree_find_filtered_node((pt), (key), NULL, NULL)
  191 void    ptree_remove_node(pt_tree_t *, void *);
  192 void *  ptree_iterate(pt_tree_t *, const void *, pt_direction_t);
  193 
  194 #endif /* _SYS_PTREE_H_ */

Cache object: c70edfa0895567142d48292adff7e262

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.