src/WINNT/afsrdr/kernel/fs/AFSBTreeSupport.cpp

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011 Kernel Drivers, LLC.
   3  * Copyright (c) 2009, 2010, 2011 Your File System, Inc.
   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:
   9  *
  10  * - Redistributions of source code must retain the above copyright notice,
  11  *   this list of conditions and the following disclaimer.
  12  * - Redistributions in binary form must reproduce the above copyright
  13  *   notice,
  14  *   this list of conditions and the following disclaimer in the
  15  *   documentation
  16  *   and/or other materials provided with the distribution.
  17  * - Neither the names of Kernel Drivers, LLC and Your File System, Inc.
  18  *   nor the names of their contributors may be used to endorse or promote
  19  *   products derived from this software without specific prior written
  20  *   permission from Kernel Drivers, LLC and Your File System, Inc.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  23  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  24  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  25  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
  26  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  27  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  28  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  29  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  30  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  31  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  32  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  33  */
  34
  35 //
  36 // File: AFSBTreeSupport.cpp
  37 //
  38
  39 #include "AFSCommon.h"
  40
  41 NTSTATUS
  42 AFSLocateHashEntry( IN AFSBTreeEntry *TopNode,
  43                     IN ULONGLONG HashIndex,
  44                     IN OUT AFSBTreeEntry **TreeEntry)
  45 {
  46
  47     NTSTATUS         ntStatus = STATUS_SUCCESS;
  48     AFSBTreeEntry   *pEntry = NULL;
  49     AFSBTreeEntry   *pCurrentEntry = NULL;
  50
  51     pCurrentEntry = TopNode;
  52
  53     __Enter
  54     {
  55
  56         //
  57         // If the rootnode passed is null then the directory is empty
  58         //
  59
  60         if( TopNode == NULL)
  61         {
  62
  63             try_return( ntStatus = STATUS_INVALID_PARAMETER);
  64         }
  65
  66         //
  67         // If the requestor is looking for the root node itself, then return it.
  68         //
  69
  70         if( TopNode->HashIndex == HashIndex)
  71         {
  72
  73             *TreeEntry = TopNode;
  74
  75             try_return( ntStatus);
  76         }
  77
  78         //
  79         // Loop through the nodes in the tree
  80         //
  81
  82         while( pCurrentEntry != NULL)
  83         {
  84
  85             //
  86             // Greater values are to the right link.
  87             //
  88
  89             if( HashIndex > pCurrentEntry->HashIndex)
  90             {
  91
  92                 //
  93                 // Go to the next RIGHT entry, if there is one
  94                 //
  95
  96                 if( pCurrentEntry->rightLink != NULL)
  97                 {
  98
  99                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
 100                 }
 101                 else
 102                 {
 103
 104                     //
 105                     // Came to the end of the branch so bail
 106                     //
 107
 108                     pCurrentEntry = NULL;
 109
 110                     break;
 111                 }
 112             }
 113             else if( HashIndex < pCurrentEntry->HashIndex)
 114             {
 115
 116                 //
 117                 // Go to the next LEFT entry, if one exists
 118                 //
 119
 120                 if( pCurrentEntry->leftLink != NULL)
 121                 {
 122
 123                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
 124                 }
 125                 else
 126                 {
 127
 128                     //
 129                     // End of the branch ...
 130                     //
 131
 132                     pCurrentEntry = NULL;
 133
 134                     break;
 135                 }
 136             }
 137             else
 138             {
 139
 140                 //
 141                 // Found the entry.
 142                 //
 143
 144                 *TreeEntry = pCurrentEntry;
 145
 146                 break;
 147             }
 148         }
 149
 150 try_exit:
 151
 152         NOTHING;
 153     }
 154
 155     return ntStatus;
 156 }
 157
 158 NTSTATUS
 159 AFSInsertHashEntry( IN AFSBTreeEntry *TopNode,
 160                     IN AFSBTreeEntry *FileIDEntry)
 161 {
 162
 163     NTSTATUS ntStatus = STATUS_SUCCESS;
 164     AFSBTreeEntry *pCurrentEntry = NULL;
 165
 166     pCurrentEntry = TopNode;
 167
 168     __Enter
 169     {
 170
 171         //
 172         // If we have no root node then we can;t start the search.
 173         //
 174
 175         if( pCurrentEntry == NULL)
 176         {
 177
 178             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
 179                           AFS_TRACE_LEVEL_WARNING,
 180                           "AFSInsertHashEntry Invalid root node\n");
 181
 182             try_return( ntStatus = STATUS_UNSUCCESSFUL);
 183         }
 184
 185         //
 186         // Locate the branch end to insert the node
 187         //
 188
 189         while( pCurrentEntry != NULL)
 190         {
 191
 192             //
 193             // Greater vlued indices are to the right link
 194             //
 195
 196             if( FileIDEntry->HashIndex > pCurrentEntry->HashIndex)
 197             {
 198
 199                 //
 200                 // Go to the next RIGHT entry, if it exists
 201                 //
 202
 203                 if( pCurrentEntry->rightLink != NULL)
 204                 {
 205                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
 206                 }
 207                 else
 208                 {
 209
 210                     //
 211                     // Located the end of the branch line so insert the node
 212                     //
 213
 214                     pCurrentEntry->rightLink = (void *)FileIDEntry;
 215
 216                     FileIDEntry->parentLink = (void *)pCurrentEntry;
 217
 218                     break;
 219                 }
 220             }
 221             else if( FileIDEntry->HashIndex < pCurrentEntry->HashIndex)
 222             {
 223
 224                 //
 225                 // Go to the next LEFT entry, if it exists
 226                 //
 227
 228                 if( pCurrentEntry->leftLink != NULL)
 229                 {
 230                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
 231                 }
 232                 else
 233                 {
 234
 235                     //
 236                     // Located the branch line end so insert the node here
 237                     //
 238
 239                     pCurrentEntry->leftLink = (void *)FileIDEntry;
 240
 241                     FileIDEntry->parentLink = (void *)pCurrentEntry;
 242
 243                     break;
 244                 }
 245             }
 246             else
 247             {
 248
 249                 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
 250                               AFS_TRACE_LEVEL_WARNING,
 251                               "AFSInsertHashEntry Attempt to re-insert a CRC %I64X\n",
 252                               FileIDEntry->HashIndex);
 253
 254                 ASSERT( FALSE);
 255
 256                 ntStatus = STATUS_UNSUCCESSFUL;
 257
 258                 break;
 259             }
 260         }
 261
 262 try_exit:
 263
 264         NOTHING;
 265     }
 266
 267     return ntStatus;
 268 }
 269
 270 NTSTATUS
 271 AFSRemoveHashEntry( IN AFSBTreeEntry **TopNode,
 272                     IN AFSBTreeEntry *FileIDEntry)
 273 {
 274
 275     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
 276     AFSBTreeEntry *pRightNode = NULL;
 277     AFSBTreeEntry *pLeftNode = NULL;
 278     AFSBTreeEntry *pCurrentNode = NULL;
 279     AFSBTreeEntry *pParentNode = NULL;
 280
 281     pRightNode = (AFSBTreeEntry *)FileIDEntry->rightLink;
 282     pLeftNode = (AFSBTreeEntry *)FileIDEntry->leftLink;
 283     pParentNode = (AFSBTreeEntry *)FileIDEntry->parentLink;
 284
 285     __Enter
 286     {
 287
 288         if( (pRightNode == NULL) && (pLeftNode == NULL))
 289         {
 290
 291             if( pParentNode != NULL)
 292             {
 293
 294                 if( pParentNode->leftLink == FileIDEntry)
 295                 {
 296
 297                     pParentNode->leftLink = NULL;
 298                 }
 299                 else
 300                 {
 301
 302                     pParentNode->rightLink = NULL;
 303                 }
 304             }
 305             else
 306             {
 307
 308                 //
 309                 // Removing the top node
 310                 //
 311
 312                 *TopNode = NULL;
 313             }
 314         }
 315         else
 316         {
 317
 318             if( pRightNode != NULL)
 319             {
 320
 321                 if( pParentNode != NULL)
 322                 {
 323
 324                     // Replace the parent node where this entry was.
 325                     if( pParentNode->rightLink == FileIDEntry)
 326                     {
 327
 328                         pParentNode->rightLink = pRightNode;
 329                     }
 330                     else
 331                     {
 332
 333                         pParentNode->leftLink = pRightNode;
 334                     }
 335                 }
 336                 else
 337                 {
 338
 339                     *TopNode = pRightNode;
 340
 341                     pRightNode->parentLink = NULL;
 342                 }
 343
 344                 pRightNode->parentLink = pParentNode;
 345             }
 346
 347             if( pLeftNode != NULL)
 348             {
 349
 350                 // To connect the left node, we must walk the chain of the
 351                 // right nodes left side until we reach the end.
 352                 // At the end attach the leftNode
 353                 if( pRightNode != NULL)
 354                 {
 355
 356                     pCurrentNode = pRightNode;
 357
 358                     while( pCurrentNode->leftLink != NULL)
 359                     {
 360
 361                         pCurrentNode = (AFSBTreeEntry *)pCurrentNode->leftLink;
 362                     }
 363
 364                     pCurrentNode->leftLink = pLeftNode;
 365
 366                     pLeftNode->parentLink = pCurrentNode;
 367                 }
 368                 else
 369                 {
 370
 371                     if( pParentNode != NULL)
 372                     {
 373
 374                         // This is where we have a left node with no right node.
 375                         // So, attach the left node to the parent of
 376                         // the removed nodes branch
 377                         if( pParentNode->rightLink == FileIDEntry)
 378                         {
 379
 380                             pParentNode->rightLink = pLeftNode;
 381                         }
 382                         else
 383                         {
 384
 385                             pParentNode->leftLink = pLeftNode;
 386                         }
 387
 388                         pLeftNode->parentLink = pParentNode;
 389                     }
 390                     else
 391                     {
 392
 393                         *TopNode = pLeftNode;
 394
 395                         pLeftNode->parentLink = NULL;
 396                     }
 397                 }
 398             }
 399         }
 400
 401         //
 402         // Cleanup the just removed node
 403         //
 404
 405         FileIDEntry->leftLink = NULL;
 406         FileIDEntry->parentLink = NULL;
 407         FileIDEntry->rightLink = NULL;
 408
 409         ntStatus = STATUS_SUCCESS;
 410     }
 411
 412     return ntStatus;
 413 }