1/*
2 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright

--- 21 unchanged lines hidden (view full) ---

30
31#include <sys/queue.h>
32
33/* Default values of the tree parameters */
34#define VM_RADIX_WIDTH 5
35#define VM_RADIX_COUNT (1 << VM_RADIX_WIDTH)
36#define VM_RADIX_MASK (VM_RADIX_COUNT - 1)
37#define VM_RADIX_LIMIT howmany((sizeof(vm_pindex_t) * NBBY), VM_RADIX_WIDTH)
38
39/* Calculates maximum value for a tree of height h. */
40#define VM_RADIX_MAX(h) \
41 ((h) == VM_RADIX_LIMIT ? ((vm_pindex_t)-1) : \
42 (((vm_pindex_t)1 << ((h) * VM_RADIX_WIDTH)) - 1))
43
44struct vm_radix_node {
45 SLIST_ENTRY(vm_radix_node) next;
46 void *rn_child[VM_RADIX_COUNT]; /* child nodes. */
47 uint16_t rn_count; /* Valid children. */
48};
49
50struct vm_radix {
51 struct vm_radix_node *rt_root; /* Root node. */
52 int rt_height; /* Number of levels + 1. */
53};
54
55void vm_radix_init(void);
56int vm_radix_insert(struct vm_radix *, vm_pindex_t, void *);
57void *vm_radix_remove(struct vm_radix *, vm_pindex_t);
58void *vm_radix_lookup(struct vm_radix *, vm_pindex_t);
59int vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
60 vm_pindex_t end, void **out, int cnt, vm_pindex_t *next);

--- 18 unchanged lines hidden ---