Windows: RDR File System Framework driver
[openafs.git] / 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 }