1 /** @file
2 Hash table operations.
3
4 Copyright (c) 2005 - 2015, Intel Corporation. All rights reserved.<BR>
5 This program and the accompanying materials are licensed and made available
6 under the terms and conditions of the BSD License which accompanies this
7 distribution. The full text of the license may be found at
8 http://opensource.org/licenses/bsd-license.php
9
10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
12
13 **/
14
15 #include "Fat.h"
16
17 /**
18
19 Get hash value for long name.
20
21 @param LongNameString - The long name string to be hashed.
22
23 @return HashValue.
24
25 **/
26 STATIC
27 UINT32
FatHashLongName(IN CHAR16 * LongNameString)28 FatHashLongName (
29 IN CHAR16 *LongNameString
30 )
31 {
32 UINT32 HashValue;
33 CHAR16 UpCasedLongFileName[EFI_PATH_STRING_LENGTH];
34 StrnCpyS (
35 UpCasedLongFileName,
36 ARRAY_SIZE (UpCasedLongFileName),
37 LongNameString,
38 ARRAY_SIZE (UpCasedLongFileName) - 1
39 );
40 FatStrUpr (UpCasedLongFileName);
41 gBS->CalculateCrc32 (UpCasedLongFileName, StrSize (UpCasedLongFileName), &HashValue);
42 return (HashValue & HASH_TABLE_MASK);
43 }
44
45 /**
46
47 Get hash value for short name.
48
49 @param ShortNameString - The short name string to be hashed.
50
51 @return HashValue
52
53 **/
54 STATIC
55 UINT32
FatHashShortName(IN CHAR8 * ShortNameString)56 FatHashShortName (
57 IN CHAR8 *ShortNameString
58 )
59 {
60 UINT32 HashValue;
61 gBS->CalculateCrc32 (ShortNameString, FAT_NAME_LEN, &HashValue);
62 return (HashValue & HASH_TABLE_MASK);
63 }
64
65 /**
66
67 Search the long name hash table for the directory entry.
68
69 @param ODir - The directory to be searched.
70 @param LongNameString - The long name string to search.
71
72 @return The previous long name hash node of the directory entry.
73
74 **/
75 FAT_DIRENT **
FatLongNameHashSearch(IN FAT_ODIR * ODir,IN CHAR16 * LongNameString)76 FatLongNameHashSearch (
77 IN FAT_ODIR *ODir,
78 IN CHAR16 *LongNameString
79 )
80 {
81 FAT_DIRENT **PreviousHashNode;
82 for (PreviousHashNode = &ODir->LongNameHashTable[FatHashLongName (LongNameString)];
83 *PreviousHashNode != NULL;
84 PreviousHashNode = &(*PreviousHashNode)->LongNameForwardLink
85 ) {
86 if (FatStriCmp (LongNameString, (*PreviousHashNode)->FileString) == 0) {
87 break;
88 }
89 }
90
91 return PreviousHashNode;
92 }
93
94 /**
95
96 Search the short name hash table for the directory entry.
97
98 @param ODir - The directory to be searched.
99 @param ShortNameString - The short name string to search.
100
101 @return The previous short name hash node of the directory entry.
102
103 **/
104 FAT_DIRENT **
FatShortNameHashSearch(IN FAT_ODIR * ODir,IN CHAR8 * ShortNameString)105 FatShortNameHashSearch (
106 IN FAT_ODIR *ODir,
107 IN CHAR8 *ShortNameString
108 )
109 {
110 FAT_DIRENT **PreviousHashNode;
111 for (PreviousHashNode = &ODir->ShortNameHashTable[FatHashShortName (ShortNameString)];
112 *PreviousHashNode != NULL;
113 PreviousHashNode = &(*PreviousHashNode)->ShortNameForwardLink
114 ) {
115 if (CompareMem (ShortNameString, (*PreviousHashNode)->Entry.FileName, FAT_NAME_LEN) == 0) {
116 break;
117 }
118 }
119
120 return PreviousHashNode;
121 }
122
123 /**
124
125 Insert directory entry to hash table.
126
127 @param ODir - The parent directory.
128 @param DirEnt - The directory entry node.
129
130 **/
131 VOID
FatInsertToHashTable(IN FAT_ODIR * ODir,IN FAT_DIRENT * DirEnt)132 FatInsertToHashTable (
133 IN FAT_ODIR *ODir,
134 IN FAT_DIRENT *DirEnt
135 )
136 {
137 FAT_DIRENT **HashTable;
138 UINT32 HashTableIndex;
139
140 //
141 // Insert hash table index for short name
142 //
143 HashTableIndex = FatHashShortName (DirEnt->Entry.FileName);
144 HashTable = ODir->ShortNameHashTable;
145 DirEnt->ShortNameForwardLink = HashTable[HashTableIndex];
146 HashTable[HashTableIndex] = DirEnt;
147 //
148 // Insert hash table index for long name
149 //
150 HashTableIndex = FatHashLongName (DirEnt->FileString);
151 HashTable = ODir->LongNameHashTable;
152 DirEnt->LongNameForwardLink = HashTable[HashTableIndex];
153 HashTable[HashTableIndex] = DirEnt;
154 }
155
156 /**
157
158 Delete directory entry from hash table.
159
160 @param ODir - The parent directory.
161 @param DirEnt - The directory entry node.
162
163 **/
164 VOID
FatDeleteFromHashTable(IN FAT_ODIR * ODir,IN FAT_DIRENT * DirEnt)165 FatDeleteFromHashTable (
166 IN FAT_ODIR *ODir,
167 IN FAT_DIRENT *DirEnt
168 )
169 {
170 *FatShortNameHashSearch (ODir, DirEnt->Entry.FileName) = DirEnt->ShortNameForwardLink;
171 *FatLongNameHashSearch (ODir, DirEnt->FileString) = DirEnt->LongNameForwardLink;
172 }
173