FatPkg/EnhancedFatDxe/Hash.c

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