FatPkg/EnhancedFatDxe/Hash.c

   1 /*++
   2
   3 Copyright (c) 2005 - 2014, 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   StrnCpy (UpCasedLongFileName, LongNameString, EFI_PATH_STRING_LENGTH - 1);
  51   UpCasedLongFileName[EFI_PATH_STRING_LENGTH - 1] = L'\0';
  52   FatStrUpr (UpCasedLongFileName);
  53   gBS->CalculateCrc32 (UpCasedLongFileName, StrSize (UpCasedLongFileName), &HashValue);
  54   return (HashValue & HASH_TABLE_MASK);
  55 }
  56
  57 STATIC
  58 UINT32
  59 FatHashShortName (
  60   IN CHAR8   *ShortNameString
  61   )
  62 /*++
  63
  64 Routine Description:
  65
  66   Get hash value for short name.
  67
  68 Arguments:
  69
  70   ShortNameString       - The short name string to be hashed.
  71
  72 Returns:
  73
  74   HashValue
  75
  76 --*/
  77 {
  78   UINT32  HashValue;
  79   gBS->CalculateCrc32 (ShortNameString, FAT_NAME_LEN, &HashValue);
  80   return (HashValue & HASH_TABLE_MASK);
  81 }
  82
  83 FAT_DIRENT **
  84 FatLongNameHashSearch (
  85   IN FAT_ODIR       *ODir,
  86   IN CHAR16         *LongNameString
  87   )
  88 /*++
  89
  90 Routine Description:
  91
  92   Search the long name hash table for the directory entry.
  93
  94 Arguments:
  95
  96   ODir                  - The directory to be searched.
  97   LongNameString        - The long name string to search.
  98
  99 Returns:
 100
 101   The previous long name hash node of the directory entry.
 102
 103 --*/
 104 {
 105   FAT_DIRENT  **PreviousHashNode;
 106   for (PreviousHashNode   = &ODir->LongNameHashTable[FatHashLongName (LongNameString)];
 107        *PreviousHashNode != NULL;
 108        PreviousHashNode   = &(*PreviousHashNode)->LongNameForwardLink
 109       ) {
 110     if (FatStriCmp (LongNameString, (*PreviousHashNode)->FileString) == 0) {
 111       break;
 112     }
 113   }
 114
 115   return PreviousHashNode;
 116 }
 117
 118 FAT_DIRENT **
 119 FatShortNameHashSearch (
 120   IN FAT_ODIR      *ODir,
 121   IN CHAR8         *ShortNameString
 122   )
 123 /*++
 124
 125 Routine Description:
 126
 127   Search the short name hash table for the directory entry.
 128
 129 Arguments:
 130
 131   ODir                  - The directory to be searched.
 132   ShortNameString       - The short name string to search.
 133
 134 Returns:
 135
 136   The previous short name hash node of the directory entry.
 137
 138 --*/
 139 {
 140   FAT_DIRENT  **PreviousHashNode;
 141   for (PreviousHashNode   = &ODir->ShortNameHashTable[FatHashShortName (ShortNameString)];
 142        *PreviousHashNode != NULL;
 143        PreviousHashNode   = &(*PreviousHashNode)->ShortNameForwardLink
 144       ) {
 145     if (CompareMem (ShortNameString, (*PreviousHashNode)->Entry.FileName, FAT_NAME_LEN) == 0) {
 146       break;
 147     }
 148   }
 149
 150   return PreviousHashNode;
 151 }
 152
 153 VOID
 154 FatInsertToHashTable (
 155   IN FAT_ODIR     *ODir,
 156   IN FAT_DIRENT   *DirEnt
 157   )
 158 /*++
 159
 160 Routine Description:
 161
 162   Insert directory entry to hash table.
 163
 164 Arguments:
 165
 166   ODir                  - The parent directory.
 167   DirEnt                - The directory entry node.
 168
 169 Returns:
 170
 171   None.
 172
 173 --*/
 174 {
 175   FAT_DIRENT  **HashTable;
 176   UINT32      HashTableIndex;
 177
 178   //
 179   // Insert hash table index for short name
 180   //
 181   HashTableIndex                = FatHashShortName (DirEnt->Entry.FileName);
 182   HashTable                     = ODir->ShortNameHashTable;
 183   DirEnt->ShortNameForwardLink  = HashTable[HashTableIndex];
 184   HashTable[HashTableIndex]     = DirEnt;
 185   //
 186   // Insert hash table index for long name
 187   //
 188   HashTableIndex                = FatHashLongName (DirEnt->FileString);
 189   HashTable                     = ODir->LongNameHashTable;
 190   DirEnt->LongNameForwardLink   = HashTable[HashTableIndex];
 191   HashTable[HashTableIndex]     = DirEnt;
 192 }
 193
 194 VOID
 195 FatDeleteFromHashTable (
 196   IN FAT_ODIR     *ODir,
 197   IN FAT_DIRENT   *DirEnt
 198   )
 199 /*++
 200
 201 Routine Description:
 202
 203   Delete directory entry from hash table.
 204
 205 Arguments:
 206
 207   ODir                  - The parent directory.
 208   DirEnt                - The directory entry node.
 209
 210 Returns:
 211
 212   None.
 213
 214 --*/
 215 {
 216   *FatShortNameHashSearch (ODir, DirEnt->Entry.FileName) = DirEnt->ShortNameForwardLink;
 217   *FatLongNameHashSearch (ODir, DirEnt->FileString)      = DirEnt->LongNameForwardLink;
 218 }