FatPkg/EnhancedFatDxe/Hash.c

   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
  22 FatHashLongName (
  23   IN CHAR16  *LongNameString
  24   )
  25 {
  26   UINT32  HashValue;
  27   CHAR16  UpCasedLongFileName[EFI_PATH_STRING_LENGTH];
  28
  29   StrnCpyS (
  30     UpCasedLongFileName,
  31     ARRAY_SIZE (UpCasedLongFileName),
  32     LongNameString,
  33     ARRAY_SIZE (UpCasedLongFileName) - 1
  34     );
  35   FatStrUpr (UpCasedLongFileName);
  36   gBS->CalculateCrc32 (UpCasedLongFileName, StrSize (UpCasedLongFileName), &HashValue);
  37   return (HashValue & HASH_TABLE_MASK);
  38 }
  39
  40 /**
  41
  42   Get hash value for short name.
  43
  44   @param  ShortNameString       - The short name string to be hashed.
  45
  46   @return HashValue
  47
  48 **/
  49 STATIC
  50 UINT32
  51 FatHashShortName (
  52   IN CHAR8  *ShortNameString
  53   )
  54 {
  55   UINT32  HashValue;
  56
  57   gBS->CalculateCrc32 (ShortNameString, FAT_NAME_LEN, &HashValue);
  58   return (HashValue & HASH_TABLE_MASK);
  59 }
  60
  61 /**
  62
  63   Search the long name hash table for the directory entry.
  64
  65   @param  ODir                  - The directory to be searched.
  66   @param  LongNameString        - The long name string to search.
  67
  68   @return The previous long name hash node of the directory entry.
  69
  70 **/
  71 FAT_DIRENT **
  72 FatLongNameHashSearch (
  73   IN FAT_ODIR  *ODir,
  74   IN CHAR16    *LongNameString
  75   )
  76 {
  77   FAT_DIRENT  **PreviousHashNode;
  78
  79   for (PreviousHashNode   = &ODir->LongNameHashTable[FatHashLongName (LongNameString)];
  80        *PreviousHashNode != NULL;
  81        PreviousHashNode   = &(*PreviousHashNode)->LongNameForwardLink
  82        )
  83   {
  84     if (FatStriCmp (LongNameString, (*PreviousHashNode)->FileString) == 0) {
  85       break;
  86     }
  87   }
  88
  89   return PreviousHashNode;
  90 }
  91
  92 /**
  93
  94   Search the short name hash table for the directory entry.
  95
  96   @param  ODir                  - The directory to be searched.
  97   @param  ShortNameString       - The short name string to search.
  98
  99   @return The previous short name hash node of the directory entry.
 100
 101 **/
 102 FAT_DIRENT **
 103 FatShortNameHashSearch (
 104   IN FAT_ODIR  *ODir,
 105   IN CHAR8     *ShortNameString
 106   )
 107 {
 108   FAT_DIRENT  **PreviousHashNode;
 109
 110   for (PreviousHashNode   = &ODir->ShortNameHashTable[FatHashShortName (ShortNameString)];
 111        *PreviousHashNode != NULL;
 112        PreviousHashNode   = &(*PreviousHashNode)->ShortNameForwardLink
 113        )
 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 }