libcfs/libcfs/winnt/winnt-strusup.c

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