FatPkg/EnhancedFatDxe/Hash.c

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