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