| vm_radix.h (226983) | vm_radix.h (227544) |
|---|---|
| 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: --- 30 unchanged lines hidden (view full) --- 39#define VM_RADIX_FLAGS 0x3 /* Flag bits stored in node pointers. */ 40#define VM_RADIX_BLACK 0x1 /* Black node. (leaf only) */ 41#define VM_RADIX_RED 0x2 /* Red node. (leaf only) */ 42#define VM_RADIX_ANY (VM_RADIX_RED | VM_RADIX_BLACK) 43#define VM_RADIX_EMPTY 0x1 /* Empty hint. (internal only) */ 44#define VM_RADIX_HEIGHT 0xf /* Bits of height in root */ 45#define VM_RADIX_STACK 8 /* Nodes to store on stack. */ 46 | 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: --- 30 unchanged lines hidden (view full) --- 39#define VM_RADIX_FLAGS 0x3 /* Flag bits stored in node pointers. */ 40#define VM_RADIX_BLACK 0x1 /* Black node. (leaf only) */ 41#define VM_RADIX_RED 0x2 /* Red node. (leaf only) */ 42#define VM_RADIX_ANY (VM_RADIX_RED | VM_RADIX_BLACK) 43#define VM_RADIX_EMPTY 0x1 /* Empty hint. (internal only) */ 44#define VM_RADIX_HEIGHT 0xf /* Bits of height in root */ 45#define VM_RADIX_STACK 8 /* Nodes to store on stack. */ 46 |
| 47CTASSERT(VM_RADIX_HEIGHT >= VM_RADIX_LIMIT); 48 | |
| 49/* Calculates maximum value for a tree of height h. */ 50#define VM_RADIX_MAX(h) \ 51 ((h) == VM_RADIX_LIMIT ? ((vm_pindex_t)-1) : \ 52 (((vm_pindex_t)1 << ((h) * VM_RADIX_WIDTH)) - 1)) 53 | 47/* Calculates maximum value for a tree of height h. */ 48#define VM_RADIX_MAX(h) \ 49 ((h) == VM_RADIX_LIMIT ? ((vm_pindex_t)-1) : \ 50 (((vm_pindex_t)1 << ((h) * VM_RADIX_WIDTH)) - 1)) 51 |
| 54#ifdef _KERNEL 55 56struct vm_radix_node { 57 void *rn_child[VM_RADIX_COUNT]; /* child nodes. */ 58 uint16_t rn_count; /* Valid children. */ 59}; 60 | |
| 61/* 62 * Radix tree root. The height and pointer are set together to permit 63 * coherent lookups while the root is modified. 64 */ 65struct vm_radix { 66 uintptr_t rt_root; /* root + height */ 67}; 68 | 52/* 53 * Radix tree root. The height and pointer are set together to permit 54 * coherent lookups while the root is modified. 55 */ 56struct vm_radix { 57 uintptr_t rt_root; /* root + height */ 58}; 59 |
| 60#ifdef _KERNEL 61CTASSERT(VM_RADIX_HEIGHT >= VM_RADIX_LIMIT); 62 63struct vm_radix_node { 64 void *rn_child[VM_RADIX_COUNT]; /* child nodes. */ 65 uint16_t rn_count; /* Valid children. */ 66}; 67 |
|
| 69void vm_radix_init(void); 70 71/* 72 * Functions which only work with black nodes. (object lock) 73 */ 74int vm_radix_insert(struct vm_radix *, vm_pindex_t, void *); 75void vm_radix_shrink(struct vm_radix *); 76 --- 60 unchanged lines hidden --- | 68void vm_radix_init(void); 69 70/* 71 * Functions which only work with black nodes. (object lock) 72 */ 73int vm_radix_insert(struct vm_radix *, vm_pindex_t, void *); 74void vm_radix_shrink(struct vm_radix *); 75 --- 60 unchanged lines hidden --- |