Hash.c 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166
  1. /** @file
  2. Hash table operations.
  3. Copyright (c) 2005 - 2015, Intel Corporation. All rights reserved.<BR>
  4. SPDX-License-Identifier: BSD-2-Clause-Patent
  5. **/
  6. #include "Fat.h"
  7. /**
  8. Get hash value for long name.
  9. @param LongNameString - The long name string to be hashed.
  10. @return HashValue.
  11. **/
  12. STATIC
  13. UINT32
  14. FatHashLongName (
  15. IN CHAR16 *LongNameString
  16. )
  17. {
  18. UINT32 HashValue;
  19. CHAR16 UpCasedLongFileName[EFI_PATH_STRING_LENGTH];
  20. StrnCpyS (
  21. UpCasedLongFileName,
  22. ARRAY_SIZE (UpCasedLongFileName),
  23. LongNameString,
  24. ARRAY_SIZE (UpCasedLongFileName) - 1
  25. );
  26. FatStrUpr (UpCasedLongFileName);
  27. gBS->CalculateCrc32 (UpCasedLongFileName, StrSize (UpCasedLongFileName), &HashValue);
  28. return (HashValue & HASH_TABLE_MASK);
  29. }
  30. /**
  31. Get hash value for short name.
  32. @param ShortNameString - The short name string to be hashed.
  33. @return HashValue
  34. **/
  35. STATIC
  36. UINT32
  37. FatHashShortName (
  38. IN CHAR8 *ShortNameString
  39. )
  40. {
  41. UINT32 HashValue;
  42. gBS->CalculateCrc32 (ShortNameString, FAT_NAME_LEN, &HashValue);
  43. return (HashValue & HASH_TABLE_MASK);
  44. }
  45. /**
  46. Search the long name hash table for the directory entry.
  47. @param ODir - The directory to be searched.
  48. @param LongNameString - The long name string to search.
  49. @return The previous long name hash node of the directory entry.
  50. **/
  51. FAT_DIRENT **
  52. FatLongNameHashSearch (
  53. IN FAT_ODIR *ODir,
  54. IN CHAR16 *LongNameString
  55. )
  56. {
  57. FAT_DIRENT **PreviousHashNode;
  58. for (PreviousHashNode = &ODir->LongNameHashTable[FatHashLongName (LongNameString)];
  59. *PreviousHashNode != NULL;
  60. PreviousHashNode = &(*PreviousHashNode)->LongNameForwardLink
  61. ) {
  62. if (FatStriCmp (LongNameString, (*PreviousHashNode)->FileString) == 0) {
  63. break;
  64. }
  65. }
  66. return PreviousHashNode;
  67. }
  68. /**
  69. Search the short name hash table for the directory entry.
  70. @param ODir - The directory to be searched.
  71. @param ShortNameString - The short name string to search.
  72. @return The previous short name hash node of the directory entry.
  73. **/
  74. FAT_DIRENT **
  75. FatShortNameHashSearch (
  76. IN FAT_ODIR *ODir,
  77. IN CHAR8 *ShortNameString
  78. )
  79. {
  80. FAT_DIRENT **PreviousHashNode;
  81. for (PreviousHashNode = &ODir->ShortNameHashTable[FatHashShortName (ShortNameString)];
  82. *PreviousHashNode != NULL;
  83. PreviousHashNode = &(*PreviousHashNode)->ShortNameForwardLink
  84. ) {
  85. if (CompareMem (ShortNameString, (*PreviousHashNode)->Entry.FileName, FAT_NAME_LEN) == 0) {
  86. break;
  87. }
  88. }
  89. return PreviousHashNode;
  90. }
  91. /**
  92. Insert directory entry to hash table.
  93. @param ODir - The parent directory.
  94. @param DirEnt - The directory entry node.
  95. **/
  96. VOID
  97. FatInsertToHashTable (
  98. IN FAT_ODIR *ODir,
  99. IN FAT_DIRENT *DirEnt
  100. )
  101. {
  102. FAT_DIRENT **HashTable;
  103. UINT32 HashTableIndex;
  104. //
  105. // Insert hash table index for short name
  106. //
  107. HashTableIndex = FatHashShortName (DirEnt->Entry.FileName);
  108. HashTable = ODir->ShortNameHashTable;
  109. DirEnt->ShortNameForwardLink = HashTable[HashTableIndex];
  110. HashTable[HashTableIndex] = DirEnt;
  111. //
  112. // Insert hash table index for long name
  113. //
  114. HashTableIndex = FatHashLongName (DirEnt->FileString);
  115. HashTable = ODir->LongNameHashTable;
  116. DirEnt->LongNameForwardLink = HashTable[HashTableIndex];
  117. HashTable[HashTableIndex] = DirEnt;
  118. }
  119. /**
  120. Delete directory entry from hash table.
  121. @param ODir - The parent directory.
  122. @param DirEnt - The directory entry node.
  123. **/
  124. VOID
  125. FatDeleteFromHashTable (
  126. IN FAT_ODIR *ODir,
  127. IN FAT_DIRENT *DirEnt
  128. )
  129. {
  130. *FatShortNameHashSearch (ODir, DirEnt->Entry.FileName) = DirEnt->ShortNameForwardLink;
  131. *FatLongNameHashSearch (ODir, DirEnt->FileString) = DirEnt->LongNameForwardLink;
  132. }