Home | History | Annotate | Download | only in EnhancedFatDxe 
      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 }
    173