sys/vm/vm_radix.h

   1 /*
   2  * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
   3  * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  *
  27  */
  28
  29 #ifndef _VM_RADIX_H_
  30 #define _VM_RADIX_H_
  31
  32 #define VM_RADIX_BLACK  0x1     /* Black node. (leaf only) */
  33 #define VM_RADIX_RED    0x2     /* Red node. (leaf only) */
  34 #define VM_RADIX_ANY    (VM_RADIX_RED | VM_RADIX_BLACK)
  35 #define VM_RADIX_STACK  8       /* Nodes to store on stack. */
  36
  37 /*
  38  * Radix tree root.  The height and pointer are set together to permit
  39  * coherent lookups while the root is modified.
  40  */
  41 struct vm_radix {
  42         uintptr_t       rt_root;                /* root + height */
  43 };
  44
  45 #ifdef _KERNEL
  46
  47 /*
  48  * Initialize the radix tree subsystem.
  49  */
  50 void    vm_radix_init(void);
  51
  52 /*
  53  * Functions which only work with black nodes. (object lock)
  54  */
  55 int     vm_radix_insert(struct vm_radix *, vm_pindex_t, void *);
  56
  57 /*
  58  * Functions which work on specified colors. (object, vm_page_queue_free locks)
  59  */
  60 void    *vm_radix_color(struct vm_radix *, vm_pindex_t, int);
  61 void    *vm_radix_lookup(struct vm_radix *, vm_pindex_t, int);
  62 int     vm_radix_lookupn(struct vm_radix *, vm_pindex_t, vm_pindex_t, int,
  63             void **, int, vm_pindex_t *, u_int *);
  64 void    *vm_radix_lookup_le(struct vm_radix *, vm_pindex_t, int);
  65 void    vm_radix_reclaim_allnodes(struct vm_radix *);
  66 void    vm_radix_remove(struct vm_radix *, vm_pindex_t, int);
  67
  68 /*
  69  * Look up any entry at a position greater or equal to index.
  70  */
  71 static inline void *
  72 vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index, int color)
  73 {
  74         void *val;
  75         u_int dummy;
  76
  77         if (vm_radix_lookupn(rtree, index, 0, color, &val, 1, &index, &dummy))
  78                 return (val);
  79         return (NULL);
  80 }
  81
  82 static inline void *
  83 vm_radix_last(struct vm_radix *rtree, int color)
  84 {
  85
  86         return vm_radix_lookup_le(rtree, 0, color);
  87 }
  88
  89 static inline void *
  90 vm_radix_first(struct vm_radix *rtree, int color)
  91 {
  92
  93         return vm_radix_lookup_ge(rtree, 0, color);
  94 }
  95
  96 static inline void *
  97 vm_radix_next(struct vm_radix *rtree, vm_pindex_t index, int color)
  98 {
  99
 100         if (index == -1)
 101                 return (NULL);
 102         return vm_radix_lookup_ge(rtree, index + 1, color);
 103 }
 104
 105 static inline void *
 106 vm_radix_prev(struct vm_radix *rtree, vm_pindex_t index, int color)
 107 {
 108
 109         if (index == 0)
 110                 return (NULL);
 111         return vm_radix_lookup_le(rtree, index - 1, color);
 112 }
 113
 114 #endif /* _KERNEL */
 115 #endif /* !_VM_RADIX_H_ */