2 * Copyright (C) 2001 Cluster File Systems, Inc. <braam@clusterfs.com>
4 * This file is part of Lustre, http://www.lustre.org.
6 * Lustre is free software; you can redistribute it and/or
7 * modify it under the terms of version 2 of the GNU General Public
8 * License as published by the Free Software Foundation.
10 * Lustre is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with Lustre; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 # define DEBUG_SUBSYSTEM S_LNET
23 #include <libcfs/libcfs.h>
26 * Windows generic table support routines
29 #define TAG_RADIX_TABLE 'XIDR'
30 typedef struct _RADIX_TABLE_ELEMENT {
33 } RADIX_TABLE_ELEMENT, *PRADIX_TABLE_ELEMENT;
36 RTL_GENERIC_COMPARE_RESULTS
38 IN PRTL_GENERIC_TABLE Table,
45 Key1 = *((ULONG UNALIGNED *) Index1);
46 Key2 = *((ULONG UNALIGNED *) Index2);
49 return GenericLessThan;
50 } else if (Key1 > Key2) {
51 return GenericGreaterThan;
58 RadixAllocateElement (
59 IN PRTL_GENERIC_TABLE Table,
63 return FsRtlAllocatePoolWithTag(NonPagedPool,Size, TAG_RADIX_TABLE);
68 IN PRTL_GENERIC_TABLE Table,
72 ExFreePoolWithTag(Buffer, TAG_RADIX_TABLE);
78 IN PRTL_GENERIC_TABLE Table,
83 RADIX_TABLE_ELEMENT element;
85 element.Value = Value;
86 return RtlInsertElementGenericTable( Table, &element,
87 sizeof(RADIX_TABLE_ELEMENT), NULL );
92 IN PRTL_GENERIC_TABLE Table,
96 RADIX_TABLE_ELEMENT element;
98 return RtlDeleteElementGenericTable(Table, &element);
104 IN PRTL_GENERIC_TABLE Table,
108 RADIX_TABLE_ELEMENT element;
111 return (PRADIX_TABLE_ELEMENT)
112 RtlLookupElementGenericTable(Table, &element);
116 RadixGetNextElement (
117 IN PRTL_GENERIC_TABLE Table,
121 return (PRADIX_TABLE_ELEMENT)
122 RtlEnumerateGenericTableWithoutSplaying(Table, Restart);
129 IN PRTL_GENERIC_TABLE Table
133 /* initialize rafix generic table. */
135 RtlInitializeGenericTable(
138 RadixAllocateElement,
146 IN PRTL_GENERIC_TABLE Table
149 PRADIX_TABLE_ELEMENT element;
150 PVOID restart = NULL;
153 element = (PRADIX_TABLE_ELEMENT) RadixGetNextElement(Table, &restart);
155 RadixDeleteElement(Table, element->Key);
161 * Radix Tree Suppoert Rotuines
166 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
167 * \param root radix tree root
168 * \param results where the results of the lookup are placed
169 * \param first_index start the lookup from this key
170 * \param max_items place up to this many items at *results
172 * Performs an index-ascending scan of the tree for present items. Places
173 * them at * \a results and returns the number of items which were placed at
178 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
179 unsigned long first_index, unsigned int max_items)
181 PRADIX_TABLE_ELEMENT element;
182 PVOID restart = NULL;
185 element = RadixLookupElement(&root->table, first_index);
187 while (element && i < max_items) {
188 results[i++] = element->Value;
189 element = RadixGetNextElement(&root->table, &restart);
197 * radix_tree_lookup - perform lookup operation on a radix tree
198 * \param root radix tree root
199 * \param index index key
201 * Lookup the item at the position \a index in the radix tree \a root.
204 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
206 PRADIX_TABLE_ELEMENT element;
209 element = RadixLookupElement(&root->table, index);
211 return element->Value;
218 * radix_tree_insert - insert into a radix tree
219 * \param root radix tree root
220 * \param index index key
221 * \param item item to insert
223 * Insert an item into the radix tree at position \a index.
225 int radix_tree_insert(struct radix_tree_root *root,
226 unsigned long index, void *item)
228 if (RadixInsertElement(&root->table, index, item)) {
236 * radix_tree_delete - delete an item from a radix tree
237 * \param root radix tree root
238 * \param index index key
240 * Remove the item at \a index from the radix tree rooted at \a root.
242 * Returns the address of the deleted item, or NULL if it was not present.
244 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
246 RadixDeleteElement(&root->table, index);