vm_radix.h revision 238395
1151564Snjl/* 2151564Snjl * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> 3151564Snjl * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> 4151564Snjl * All rights reserved. 5151564Snjl * 6151564Snjl * Redistribution and use in source and binary forms, with or without 7151564Snjl * modification, are permitted provided that the following conditions 8151564Snjl * are met: 9151564Snjl * 1. Redistributions of source code must retain the above copyright 10151564Snjl * notice, this list of conditions and the following disclaimer. 11151564Snjl * 2. Redistributions in binary form must reproduce the above copyright 12151564Snjl * notice, this list of conditions and the following disclaimer in the 13151564Snjl * documentation and/or other materials provided with the distribution. 14151564Snjl * 15151564Snjl * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16151564Snjl * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17151564Snjl * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18151564Snjl * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19151564Snjl * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20151564Snjl * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21151564Snjl * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22151564Snjl * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23151564Snjl * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24151564Snjl * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25151564Snjl * SUCH DAMAGE. 26151564Snjl * 27151564Snjl */ 28151564Snjl 29151564Snjl#ifndef _VM_RADIX_H_ 30151564Snjl#define _VM_RADIX_H_ 31151564Snjl 32151564Snjl/* 33151564Snjl * Radix tree root. The height and pointer are set together to permit 34151564Snjl * coherent lookups while the root is modified. 35151564Snjl */ 36193530Sjkimstruct vm_radix { 37193530Sjkim uintptr_t rt_root; /* root + height */ 38151564Snjl}; 39151564Snjl 40151564Snjl#ifdef _KERNEL 41151564Snjl 42151564Snjlvoid vm_radix_init(void); 43151564Snjlint vm_radix_insert(struct vm_radix *, vm_pindex_t, void *); 44151564Snjlvoid *vm_radix_lookup(struct vm_radix *, vm_pindex_t); 45151564Snjlint vm_radix_lookupn(struct vm_radix *, vm_pindex_t, vm_pindex_t, void **, 46151564Snjl int, vm_pindex_t *, u_int *); 47151564Snjlvoid *vm_radix_lookup_le(struct vm_radix *, vm_pindex_t); 48152677Sumevoid vm_radix_reclaim_allnodes(struct vm_radix *); 49152677Sumevoid vm_radix_remove(struct vm_radix *, vm_pindex_t); 50152677Sume 51152677Sume/* 52152677Sume * Look up any entry at a position greater or equal to index. 53151564Snjl */ 54151564Snjlstatic inline void * 55151564Snjlvm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) 56151564Snjl{ 57151564Snjl void *val; 58152677Sume u_int dummy; 59152677Sume 60151564Snjl if (vm_radix_lookupn(rtree, index, 0, &val, 1, &index, &dummy)) 61151564Snjl return (val); 62151564Snjl return (NULL); 63151564Snjl} 64151564Snjl 65186026Ssilby#endif /* _KERNEL */ 66186026Ssilby#endif /* !_VM_RADIX_H_ */ 67186026Ssilby