1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=4:tabstop=4:
4 * Copyright (C) 2001 Cluster File Systems, Inc. <braam@clusterfs.com>
6 * This file is part of Lustre, http://www.lustre.org.
8 * Lustre is free software; you can redistribute it and/or
9 * modify it under the terms of version 2 of the GNU General Public
10 * License as published by the Free Software Foundation.
12 * Lustre is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with Lustre; if not, write to the Free Software
19 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 # define DEBUG_SUBSYSTEM S_LNET
25 #include <libcfs/libcfs.h>
28 * Windows generic table support routines
31 #define TAG_RADIX_TABLE 'XIDR'
32 typedef struct _RADIX_TABLE_ELEMENT {
35 } RADIX_TABLE_ELEMENT, *PRADIX_TABLE_ELEMENT;
38 RTL_GENERIC_COMPARE_RESULTS
40 IN PRTL_GENERIC_TABLE Table,
47 Key1 = *((ULONG UNALIGNED *) Index1);
48 Key2 = *((ULONG UNALIGNED *) Index2);
51 return GenericLessThan;
52 } else if (Key1 > Key2) {
53 return GenericGreaterThan;
60 RadixAllocateElement (
61 IN PRTL_GENERIC_TABLE Table,
65 return FsRtlAllocatePoolWithTag(NonPagedPool,Size, TAG_RADIX_TABLE);
70 IN PRTL_GENERIC_TABLE Table,
74 ExFreePoolWithTag(Buffer, TAG_RADIX_TABLE);
80 IN PRTL_GENERIC_TABLE Table,
85 RADIX_TABLE_ELEMENT element;
87 element.Value = Value;
88 return RtlInsertElementGenericTable( Table, &element,
89 sizeof(RADIX_TABLE_ELEMENT), NULL );
94 IN PRTL_GENERIC_TABLE Table,
98 RADIX_TABLE_ELEMENT element;
100 return RtlDeleteElementGenericTable(Table, &element);
106 IN PRTL_GENERIC_TABLE Table,
110 RADIX_TABLE_ELEMENT element;
113 return (PRADIX_TABLE_ELEMENT)
114 RtlLookupElementGenericTable(Table, &element);
118 RadixGetNextElement (
119 IN PRTL_GENERIC_TABLE Table,
123 return (PRADIX_TABLE_ELEMENT)
124 RtlEnumerateGenericTableWithoutSplaying(Table, Restart);
131 IN PRTL_GENERIC_TABLE Table
135 /* initialize rafix generic table. */
137 RtlInitializeGenericTable(
140 RadixAllocateElement,
148 IN PRTL_GENERIC_TABLE Table
151 PRADIX_TABLE_ELEMENT element;
152 PVOID restart = NULL;
155 element = (PRADIX_TABLE_ELEMENT) RadixGetNextElement(Table, &restart);
157 RadixDeleteElement(Table, element->Key);
163 * Radix Tree Suppoert Rotuines
168 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
169 * @root: radix tree root
170 * @results: where the results of the lookup are placed
171 * @first_index: start the lookup from this key
172 * @max_items: place up to this many items at *results
174 * Performs an index-ascending scan of the tree for present items. Places
175 * them at *@results and returns the number of items which were placed at
180 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
181 unsigned long first_index, unsigned int max_items)
183 PRADIX_TABLE_ELEMENT element;
184 PVOID restart = NULL;
187 element = RadixLookupElement(&root->table, first_index);
189 while (element && i < max_items) {
190 results[i++] = element->Value;
191 element = RadixGetNextElement(&root->table, &restart);
199 * radix_tree_lookup - perform lookup operation on a radix tree
200 * @root: radix tree root
203 * Lookup the item at the position @index in the radix tree @root.
206 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
208 PRADIX_TABLE_ELEMENT element;
211 element = RadixLookupElement(&root->table, index);
213 return element->Value;
220 * radix_tree_insert - insert into a radix tree
221 * @root: radix tree root
223 * @item: item to insert
225 * Insert an item into the radix tree at position @index.
227 int radix_tree_insert(struct radix_tree_root *root,
228 unsigned long index, void *item)
230 if (RadixInsertElement(&root->table, index, item)) {
238 * radix_tree_delete - delete an item from a radix tree
239 * @root: radix tree root
242 * Remove the item at @index from the radix tree rooted at @root.
244 * Returns the address of the deleted item, or NULL if it was not present.
246 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
248 RadixDeleteElement(&root->table, index);