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 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 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 ** 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 ** 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 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 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