Hash.c 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217
  1. /*++
  2. Copyright (c) 2005 - 2007, Intel Corporation
  3. All rights reserved. This program and the accompanying materials are licensed and made available
  4. under the terms and conditions of the BSD License which accompanies this
  5. distribution. The full text of the license may be found at
  6. http://opensource.org/licenses/bsd-license.php
  7. THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  8. WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  9. Module Name:
  10. Hash.c
  11. Abstract:
  12. Hash table operations
  13. Revision History
  14. --*/
  15. #include "Fat.h"
  16. STATIC
  17. UINT32
  18. FatHashLongName (
  19. IN CHAR16 *LongNameString
  20. )
  21. /*++
  22. Routine Description:
  23. Get hash value for long name.
  24. Arguments:
  25. LongNameString - The long name string to be hashed.
  26. Returns:
  27. HashValue.
  28. --*/
  29. {
  30. UINT32 HashValue;
  31. CHAR16 UpCasedLongFileName[EFI_PATH_STRING_LENGTH];
  32. StrCpy (UpCasedLongFileName, LongNameString);
  33. FatStrUpr (UpCasedLongFileName);
  34. gBS->CalculateCrc32 (UpCasedLongFileName, StrSize (UpCasedLongFileName), &HashValue);
  35. return (HashValue & HASH_TABLE_MASK);
  36. }
  37. STATIC
  38. UINT32
  39. FatHashShortName (
  40. IN CHAR8 *ShortNameString
  41. )
  42. /*++
  43. Routine Description:
  44. Get hash value for short name.
  45. Arguments:
  46. ShortNameString - The short name string to be hashed.
  47. Returns:
  48. HashValue
  49. --*/
  50. {
  51. UINT32 HashValue;
  52. gBS->CalculateCrc32 (ShortNameString, FAT_NAME_LEN, &HashValue);
  53. return (HashValue & HASH_TABLE_MASK);
  54. }
  55. FAT_DIRENT **
  56. FatLongNameHashSearch (
  57. IN FAT_ODIR *ODir,
  58. IN CHAR16 *LongNameString
  59. )
  60. /*++
  61. Routine Description:
  62. Search the long name hash table for the directory entry.
  63. Arguments:
  64. ODir - The directory to be searched.
  65. LongNameString - The long name string to search.
  66. Returns:
  67. The previous long name hash node of the directory entry.
  68. --*/
  69. {
  70. FAT_DIRENT **PreviousHashNode;
  71. for (PreviousHashNode = &ODir->LongNameHashTable[FatHashLongName (LongNameString)];
  72. *PreviousHashNode != NULL;
  73. PreviousHashNode = &(*PreviousHashNode)->LongNameForwardLink
  74. ) {
  75. if (FatStriCmp (LongNameString, (*PreviousHashNode)->FileString) == 0) {
  76. break;
  77. }
  78. }
  79. return PreviousHashNode;
  80. }
  81. FAT_DIRENT **
  82. FatShortNameHashSearch (
  83. IN FAT_ODIR *ODir,
  84. IN CHAR8 *ShortNameString
  85. )
  86. /*++
  87. Routine Description:
  88. Search the short name hash table for the directory entry.
  89. Arguments:
  90. ODir - The directory to be searched.
  91. ShortNameString - The short name string to search.
  92. Returns:
  93. The previous short name hash node of the directory entry.
  94. --*/
  95. {
  96. FAT_DIRENT **PreviousHashNode;
  97. for (PreviousHashNode = &ODir->ShortNameHashTable[FatHashShortName (ShortNameString)];
  98. *PreviousHashNode != NULL;
  99. PreviousHashNode = &(*PreviousHashNode)->ShortNameForwardLink
  100. ) {
  101. if (CompareMem (ShortNameString, (*PreviousHashNode)->Entry.FileName, FAT_NAME_LEN) == 0) {
  102. break;
  103. }
  104. }
  105. return PreviousHashNode;
  106. }
  107. VOID
  108. FatInsertToHashTable (
  109. IN FAT_ODIR *ODir,
  110. IN FAT_DIRENT *DirEnt
  111. )
  112. /*++
  113. Routine Description:
  114. Insert directory entry to hash table.
  115. Arguments:
  116. ODir - The parent directory.
  117. DirEnt - The directory entry node.
  118. Returns:
  119. None.
  120. --*/
  121. {
  122. FAT_DIRENT **HashTable;
  123. UINT32 HashTableIndex;
  124. //
  125. // Insert hash table index for short name
  126. //
  127. HashTableIndex = FatHashShortName (DirEnt->Entry.FileName);
  128. HashTable = ODir->ShortNameHashTable;
  129. DirEnt->ShortNameForwardLink = HashTable[HashTableIndex];
  130. HashTable[HashTableIndex] = DirEnt;
  131. //
  132. // Insert hash table index for long name
  133. //
  134. HashTableIndex = FatHashLongName (DirEnt->FileString);
  135. HashTable = ODir->LongNameHashTable;
  136. DirEnt->LongNameForwardLink = HashTable[HashTableIndex];
  137. HashTable[HashTableIndex] = DirEnt;
  138. }
  139. VOID
  140. FatDeleteFromHashTable (
  141. IN FAT_ODIR *ODir,
  142. IN FAT_DIRENT *DirEnt
  143. )
  144. /*++
  145. Routine Description:
  146. Delete directory entry from hash table.
  147. Arguments:
  148. ODir - The parent directory.
  149. DirEnt - The directory entry node.
  150. Returns:
  151. None.
  152. --*/
  153. {
  154. *FatShortNameHashSearch (ODir, DirEnt->Entry.FileName) = DirEnt->ShortNameForwardLink;
  155. *FatLongNameHashSearch (ODir, DirEnt->FileString) = DirEnt->LongNameForwardLink;
  156. }