libcfs/libcfs/winnt/winnt-strusup.c

   1 /*
   2  *  Copyright (C) 2001 Cluster File Systems, Inc. <braam@clusterfs.com>
   3  *
   4  *   This file is part of Lustre, http://www.lustre.org.
   5  *
   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.
   9  *
  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.
  14  *
  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.
  18  *
  19  */
  20
  21 # define DEBUG_SUBSYSTEM S_LNET
  22
  23 #include <libcfs/libcfs.h>
  24
  25 /*
  26  * Windows generic table support routines
  27  */
  28
  29 #define TAG_RADIX_TABLE 'XIDR'
  30 typedef struct _RADIX_TABLE_ELEMENT {
  31     ULONG       Key;
  32     PVOID       Value;
  33 } RADIX_TABLE_ELEMENT, *PRADIX_TABLE_ELEMENT;
  34
  35
  36 RTL_GENERIC_COMPARE_RESULTS
  37 RadixCompareElement (
  38     IN PRTL_GENERIC_TABLE   Table,
  39     IN PVOID                Index1,
  40     IN PVOID                Index2
  41     )
  42 {
  43     ULONG   Key1, Key2;
  44
  45     Key1 = *((ULONG UNALIGNED *) Index1);
  46     Key2 = *((ULONG UNALIGNED *) Index2);
  47
  48     if (Key1 < Key2) {
  49         return GenericLessThan;
  50     } else if (Key1 > Key2) {
  51         return GenericGreaterThan;
  52     }
  53
  54     return GenericEqual;
  55 }
  56
  57 PVOID
  58 RadixAllocateElement (
  59     IN PRTL_GENERIC_TABLE   Table,
  60     IN CLONG                Size
  61     )
  62 {
  63     return FsRtlAllocatePoolWithTag(NonPagedPool,Size, TAG_RADIX_TABLE);
  64 }
  65
  66 VOID
  67 RadixDestroyElement (
  68     IN PRTL_GENERIC_TABLE   Table,
  69     IN PVOID                Buffer
  70     )
  71 {
  72     ExFreePoolWithTag(Buffer, TAG_RADIX_TABLE);
  73 }
  74
  75
  76 PVOID
  77 RadixInsertElement(
  78     IN PRTL_GENERIC_TABLE   Table,
  79     IN ULONG                Key,
  80     IN PVOID                Value
  81     )
  82 {
  83     RADIX_TABLE_ELEMENT element;
  84     element.Key = Key;
  85     element.Value = Value;
  86     return RtlInsertElementGenericTable( Table, &element,
  87                       sizeof(RADIX_TABLE_ELEMENT), NULL );
  88 }
  89
  90 BOOLEAN
  91 RadixDeleteElement(
  92     IN PRTL_GENERIC_TABLE   Table,
  93     IN ULONG                Key
  94     )
  95 {
  96     RADIX_TABLE_ELEMENT element;
  97     element.Key = Key;
  98     return RtlDeleteElementGenericTable(Table, &element);
  99 }
 100
 101
 102 PRADIX_TABLE_ELEMENT
 103 RadixLookupElement (
 104     IN PRTL_GENERIC_TABLE   Table,
 105     IN ULONG                Key
 106     )
 107 {
 108     RADIX_TABLE_ELEMENT     element;
 109
 110     element.Key = Key;
 111     return (PRADIX_TABLE_ELEMENT)
 112             RtlLookupElementGenericTable(Table, &element);
 113 }
 114
 115 PRADIX_TABLE_ELEMENT
 116 RadixGetNextElement (
 117     IN PRTL_GENERIC_TABLE   Table,
 118     IN PVOID *               Restart
 119     )
 120 {
 121     return (PRADIX_TABLE_ELEMENT)
 122             RtlEnumerateGenericTableWithoutSplaying(Table, Restart);
 123 }
 124
 125
 126
 127 VOID
 128 RadixInitTable(
 129     IN PRTL_GENERIC_TABLE   Table
 130     )
 131 {
 132
 133     /*  initialize rafix generic table. */
 134
 135     RtlInitializeGenericTable(
 136         Table,
 137         RadixCompareElement,
 138         RadixAllocateElement,
 139         RadixDestroyElement,
 140         NULL
 141         );
 142 }
 143
 144 VOID
 145 RadixDestroyTable(
 146     IN PRTL_GENERIC_TABLE   Table
 147     )
 148 {
 149     PRADIX_TABLE_ELEMENT element;
 150     PVOID                restart = NULL;
 151
 152 Again:
 153     element = (PRADIX_TABLE_ELEMENT) RadixGetNextElement(Table, &restart);
 154     if (element) {
 155         RadixDeleteElement(Table, element->Key);
 156         goto Again;
 157     }
 158 }
 159
 160 /*
 161  *  Radix Tree Suppoert Rotuines
 162  *
 163  */
 164
 165 /**
 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
 171  *
 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
 174  *      *\a results.
 175  *
 176  */
 177 unsigned int
 178 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 179                         unsigned long first_index, unsigned int max_items)
 180 {
 181     PRADIX_TABLE_ELEMENT element;
 182     PVOID                restart = NULL;
 183     unsigned int         i = 0;
 184
 185     element = RadixLookupElement(&root->table, first_index);
 186     restart = element;
 187     while (element && i < max_items) {
 188         results[i++] = element->Value;
 189         element = RadixGetNextElement(&root->table, &restart);
 190     }
 191
 192     return i;
 193 }
 194
 195
 196 /**
 197  *      radix_tree_lookup    -    perform lookup operation on a radix tree
 198  *      \param root radix tree root
 199  *      \param index index key
 200  *
 201  *      Lookup the item at the position \a index in the radix tree \a root.
 202  *
 203  */
 204 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 205 {
 206     PRADIX_TABLE_ELEMENT element;
 207     int                  i = 0;
 208
 209     element = RadixLookupElement(&root->table, index);
 210     if (element) {
 211         return element->Value;
 212     }
 213
 214     return NULL;
 215 }
 216
 217 /**
 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
 222  *
 223  *      Insert an item into the radix tree at position \a index.
 224  */
 225 int radix_tree_insert(struct radix_tree_root *root,
 226                         unsigned long index, void *item)
 227 {
 228     if (RadixInsertElement(&root->table, index, item)) {
 229         return 0;
 230     }
 231
 232     return -ENOMEM;
 233 }
 234
 235 /**
 236  *      radix_tree_delete    -    delete an item from a radix tree
 237  *      \param root radix tree root
 238  *      \param index index key
 239  *
 240  *      Remove the item at \a index from the radix tree rooted at \a root.
 241  *
 242  *      Returns the address of the deleted item, or NULL if it was not present.
 243  */
 244 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
 245 {
 246     RadixDeleteElement(&root->table, index);
 247     return NULL;
 248 }