FatPkg/EnhancedFatDxe/Hash.c

   1 /** @file
   2   Hash table operations.
   3
   4 Copyright (c) 2005 - 2015, Intel Corporation. All rights reserved.<BR>
   5 This program and the accompanying materials are licensed and made available
   6 under the terms and conditions of the BSD License which accompanies this
   7 distribution. The full text of the license may be found at
   8 http://opensource.org/licenses/bsd-license.php
   9
  10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  12
  13 **/
  14
  15 #include "Fat.h"
  16
  17 /**
  18
  19   Get hash value for long name.
  20
  21   @param  LongNameString        - The long name string to be hashed.
  22
  23   @return HashValue.
  24
  25 **/
  26 STATIC
  27 UINT32
  28 FatHashLongName (
  29   IN CHAR16   *LongNameString
  30   )
  31 {
  32   UINT32  HashValue;
  33   CHAR16  UpCasedLongFileName[EFI_PATH_STRING_LENGTH];
  34   StrnCpyS (
  35     UpCasedLongFileName,
  36     ARRAY_SIZE (UpCasedLongFileName),
  37     LongNameString,
  38     ARRAY_SIZE (UpCasedLongFileName) - 1
  39     );
  40   FatStrUpr (UpCasedLongFileName);
  41   gBS->CalculateCrc32 (UpCasedLongFileName, StrSize (UpCasedLongFileName), &HashValue);
  42   return (HashValue & HASH_TABLE_MASK);
  43 }
  44
  45 /**
  46
  47   Get hash value for short name.
  48
  49   @param  ShortNameString       - The short name string to be hashed.
  50
  51   @return HashValue
  52
  53 **/
  54 STATIC
  55 UINT32
  56 FatHashShortName (
  57   IN CHAR8   *ShortNameString
  58   )
  59 {
  60   UINT32  HashValue;
  61   gBS->CalculateCrc32 (ShortNameString, FAT_NAME_LEN, &HashValue);
  62   return (HashValue & HASH_TABLE_MASK);
  63 }
  64
  65 /**
  66
  67   Search the long name hash table for the directory entry.
  68
  69   @param  ODir                  - The directory to be searched.
  70   @param  LongNameString        - The long name string to search.
  71
  72   @return The previous long name hash node of the directory entry.
  73
  74 **/
  75 FAT_DIRENT **
  76 FatLongNameHashSearch (
  77   IN FAT_ODIR       *ODir,
  78   IN CHAR16         *LongNameString
  79   )
  80 {
  81   FAT_DIRENT  **PreviousHashNode;
  82   for (PreviousHashNode   = &ODir->LongNameHashTable[FatHashLongName (LongNameString)];
  83        *PreviousHashNode != NULL;
  84        PreviousHashNode   = &(*PreviousHashNode)->LongNameForwardLink
  85       ) {
  86     if (FatStriCmp (LongNameString, (*PreviousHashNode)->FileString) == 0) {
  87       break;
  88     }
  89   }
  90
  91   return PreviousHashNode;
  92 }
  93
  94 /**
  95
  96   Search the short name hash table for the directory entry.
  97
  98   @param  ODir                  - The directory to be searched.
  99   @param  ShortNameString       - The short name string to search.
 100
 101   @return The previous short name hash node of the directory entry.
 102
 103 **/
 104 FAT_DIRENT **
 105 FatShortNameHashSearch (
 106   IN FAT_ODIR      *ODir,
 107   IN CHAR8         *ShortNameString
 108   )
 109 {
 110   FAT_DIRENT  **PreviousHashNode;
 111   for (PreviousHashNode   = &ODir->ShortNameHashTable[FatHashShortName (ShortNameString)];
 112        *PreviousHashNode != NULL;
 113        PreviousHashNode   = &(*PreviousHashNode)->ShortNameForwardLink
 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 }