Hash.c 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172
  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. {
  63. if (FatStriCmp (LongNameString, (*PreviousHashNode)->FileString) == 0) {
  64. break;
  65. }
  66. }
  67. return PreviousHashNode;
  68. }
  69. /**
  70. Search the short name hash table for the directory entry.
  71. @param ODir - The directory to be searched.
  72. @param ShortNameString - The short name string to search.
  73. @return The previous short name hash node of the directory entry.
  74. **/
  75. FAT_DIRENT **
  76. FatShortNameHashSearch (
  77. IN FAT_ODIR *ODir,
  78. IN CHAR8 *ShortNameString
  79. )
  80. {
  81. FAT_DIRENT **PreviousHashNode;
  82. for (PreviousHashNode = &ODir->ShortNameHashTable[FatHashShortName (ShortNameString)];
  83. *PreviousHashNode != NULL;
  84. PreviousHashNode = &(*PreviousHashNode)->ShortNameForwardLink
  85. )
  86. {
  87. if (CompareMem (ShortNameString, (*PreviousHashNode)->Entry.FileName, FAT_NAME_LEN) == 0) {
  88. break;
  89. }
  90. }
  91. return PreviousHashNode;
  92. }
  93. /**
  94. Insert directory entry to hash table.
  95. @param ODir - The parent directory.
  96. @param DirEnt - The directory entry node.
  97. **/
  98. VOID
  99. FatInsertToHashTable (
  100. IN FAT_ODIR *ODir,
  101. IN FAT_DIRENT *DirEnt
  102. )
  103. {
  104. FAT_DIRENT **HashTable;
  105. UINT32 HashTableIndex;
  106. //
  107. // Insert hash table index for short name
  108. //
  109. HashTableIndex = FatHashShortName (DirEnt->Entry.FileName);
  110. HashTable = ODir->ShortNameHashTable;
  111. DirEnt->ShortNameForwardLink = HashTable[HashTableIndex];
  112. HashTable[HashTableIndex] = DirEnt;
  113. //
  114. // Insert hash table index for long name
  115. //
  116. HashTableIndex = FatHashLongName (DirEnt->FileString);
  117. HashTable = ODir->LongNameHashTable;
  118. DirEnt->LongNameForwardLink = HashTable[HashTableIndex];
  119. HashTable[HashTableIndex] = DirEnt;
  120. }
  121. /**
  122. Delete directory entry from hash table.
  123. @param ODir - The parent directory.
  124. @param DirEnt - The directory entry node.
  125. **/
  126. VOID
  127. FatDeleteFromHashTable (
  128. IN FAT_ODIR *ODir,
  129. IN FAT_DIRENT *DirEnt
  130. )
  131. {
  132. *FatShortNameHashSearch (ODir, DirEnt->Entry.FileName) = DirEnt->ShortNameForwardLink;
  133. *FatLongNameHashSearch (ODir, DirEnt->FileString) = DirEnt->LongNameForwardLink;
  134. }