BaseTools: Library hashing fix and optimization for --hash feature

[mirror_edk2.git] / FatPkg / EnhancedFatDxe / Hash.c

/** @file\r
  Hash table operations.\r
\r
Copyright (c) 2005 - 2015, Intel Corporation. All rights reserved.<BR>\r
SPDX-License-Identifier: BSD-2-Clause-Patent\r
\r
**/\r
\r
#include "Fat.h"\r
\r
/**\r
\r
  Get hash value for long name.\r
\r
  @param  LongNameString        - The long name string to be hashed.\r
\r
  @return HashValue.\r
\r
**/\r
STATIC\r
UINT32\r
FatHashLongName (\r
  IN CHAR16   *LongNameString\r
  )\r
{\r
  UINT32  HashValue;\r
  CHAR16  UpCasedLongFileName[EFI_PATH_STRING_LENGTH];\r
  StrnCpyS (\r
    UpCasedLongFileName,\r
    ARRAY_SIZE (UpCasedLongFileName),\r
    LongNameString,\r
    ARRAY_SIZE (UpCasedLongFileName) - 1\r
    );\r
  FatStrUpr (UpCasedLongFileName);\r
  gBS->CalculateCrc32 (UpCasedLongFileName, StrSize (UpCasedLongFileName), &HashValue);\r
  return (HashValue & HASH_TABLE_MASK);\r
}\r
\r
/**\r
\r
  Get hash value for short name.\r
\r
  @param  ShortNameString       - The short name string to be hashed.\r
\r
  @return HashValue\r
\r
**/\r
STATIC\r
UINT32\r
FatHashShortName (\r
  IN CHAR8   *ShortNameString\r
  )\r
{\r
  UINT32  HashValue;\r
  gBS->CalculateCrc32 (ShortNameString, FAT_NAME_LEN, &HashValue);\r
  return (HashValue & HASH_TABLE_MASK);\r
}\r
\r
/**\r
\r
  Search the long name hash table for the directory entry.\r
\r
  @param  ODir                  - The directory to be searched.\r
  @param  LongNameString        - The long name string to search.\r
\r
  @return The previous long name hash node of the directory entry.\r
\r
**/\r
FAT_DIRENT **\r
FatLongNameHashSearch (\r
  IN FAT_ODIR       *ODir,\r
  IN CHAR16         *LongNameString\r
  )\r
{\r
  FAT_DIRENT  **PreviousHashNode;\r
  for (PreviousHashNode   = &ODir->LongNameHashTable[FatHashLongName (LongNameString)];\r
       *PreviousHashNode != NULL;\r
       PreviousHashNode   = &(*PreviousHashNode)->LongNameForwardLink\r
      ) {\r
    if (FatStriCmp (LongNameString, (*PreviousHashNode)->FileString) == 0) {\r
      break;\r
    }\r
  }\r
\r
  return PreviousHashNode;\r
}\r
\r
/**\r
\r
  Search the short name hash table for the directory entry.\r
\r
  @param  ODir                  - The directory to be searched.\r
  @param  ShortNameString       - The short name string to search.\r
\r
  @return The previous short name hash node of the directory entry.\r
\r
**/\r
FAT_DIRENT **\r
FatShortNameHashSearch (\r
  IN FAT_ODIR      *ODir,\r
  IN CHAR8         *ShortNameString\r
  )\r
{\r
  FAT_DIRENT  **PreviousHashNode;\r
  for (PreviousHashNode   = &ODir->ShortNameHashTable[FatHashShortName (ShortNameString)];\r
       *PreviousHashNode != NULL;\r
       PreviousHashNode   = &(*PreviousHashNode)->ShortNameForwardLink\r
      ) {\r
    if (CompareMem (ShortNameString, (*PreviousHashNode)->Entry.FileName, FAT_NAME_LEN) == 0) {\r
      break;\r
    }\r
  }\r
\r
  return PreviousHashNode;\r
}\r
\r
/**\r
\r
  Insert directory entry to hash table.\r
\r
  @param  ODir                  - The parent directory.\r
  @param  DirEnt                - The directory entry node.\r
\r
**/\r
VOID\r
FatInsertToHashTable (\r
  IN FAT_ODIR     *ODir,\r
  IN FAT_DIRENT   *DirEnt\r
  )\r
{\r
  FAT_DIRENT  **HashTable;\r
  UINT32      HashTableIndex;\r
\r
  //\r
  // Insert hash table index for short name\r
  //\r
  HashTableIndex                = FatHashShortName (DirEnt->Entry.FileName);\r
  HashTable                     = ODir->ShortNameHashTable;\r
  DirEnt->ShortNameForwardLink  = HashTable[HashTableIndex];\r
  HashTable[HashTableIndex]     = DirEnt;\r
  //\r
  // Insert hash table index for long name\r
  //\r
  HashTableIndex                = FatHashLongName (DirEnt->FileString);\r
  HashTable                     = ODir->LongNameHashTable;\r
  DirEnt->LongNameForwardLink   = HashTable[HashTableIndex];\r
  HashTable[HashTableIndex]     = DirEnt;\r
}\r
\r
/**\r
\r
  Delete directory entry from hash table.\r
\r
  @param  ODir                  - The parent directory.\r
  @param  DirEnt                - The directory entry node.\r
\r
**/\r
VOID\r
FatDeleteFromHashTable (\r
  IN FAT_ODIR     *ODir,\r
  IN FAT_DIRENT   *DirEnt\r
  )\r
{\r
  *FatShortNameHashSearch (ODir, DirEnt->Entry.FileName) = DirEnt->ShortNameForwardLink;\r
  *FatLongNameHashSearch (ODir, DirEnt->FileString)      = DirEnt->LongNameForwardLink;\r
}\r