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