Source code of Windows XP (NT5)
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

485 lines
7.2 KiB

  1. /*++
  2. Copyright (c) 1996 Microsoft Corporation
  3. Module Name:
  4. tlink.hxx
  5. Abstract:
  6. This class implements a doubly linked list of big integers.
  7. These link maintain the list in the original order. The
  8. array of data is maintained in sorted order.
  9. This class in intended for use in index verification of chkdsk.
  10. A lot of error checking only exists in checked version of this
  11. class and many others are skipped for performance reason.
  12. Author:
  13. Daniel Chan (danielch) 12-06-96
  14. --*/
  15. #if !defined(TLINK_DEFN )
  16. #define TLINK_DEFN
  17. #include "bigint.hxx"
  18. #if defined ( _AUTOCHECK_ )
  19. #define IFSUTIL_EXPORT
  20. #elif defined ( _IFSUTIL_MEMBER_ )
  21. #define IFSUTIL_EXPORT __declspec(dllexport)
  22. #else
  23. #define IFSUTIL_EXPORT __declspec(dllimport)
  24. #endif
  25. DECLARE_CLASS( TLINK );
  26. DEFINE_TYPE( struct _BIG_INT_NODE, BIG_INT_NODE );
  27. struct _BIG_INT_NODE {
  28. PBIG_INT_NODE next;
  29. PBIG_INT_NODE prev;
  30. BIG_INT data;
  31. PVOID buffer;
  32. };
  33. class TLINK: public OBJECT {
  34. public:
  35. IFSUTIL_EXPORT
  36. DECLARE_CONSTRUCTOR( TLINK );
  37. VIRTUAL
  38. IFSUTIL_EXPORT
  39. ~TLINK(
  40. );
  41. NONVIRTUAL
  42. IFSUTIL_EXPORT
  43. BOOLEAN
  44. Initialize(
  45. IN USHORT Size
  46. );
  47. NONVIRTUAL
  48. IFSUTIL_EXPORT
  49. RBIG_INT
  50. GetNextDataSlot(
  51. );
  52. INLINE
  53. NONVIRTUAL
  54. IFSUTIL_EXPORT
  55. USHORT
  56. QueryMemberCount(
  57. ) CONST;
  58. INLINE
  59. NONVIRTUAL
  60. IFSUTIL_EXPORT
  61. USHORT
  62. QuerySize(
  63. ) CONST;
  64. INLINE
  65. NONVIRTUAL
  66. IFSUTIL_EXPORT
  67. VOID
  68. Sort(
  69. );
  70. NONVIRTUAL
  71. IFSUTIL_EXPORT
  72. RBIG_INT
  73. GetData(
  74. IN USHORT index
  75. );
  76. INLINE
  77. NONVIRTUAL
  78. IFSUTIL_EXPORT
  79. RBIG_INT
  80. GetData(
  81. IN PVOID pNode
  82. );
  83. INLINE
  84. NONVIRTUAL
  85. IFSUTIL_EXPORT
  86. PVOID
  87. GetSortedFirst(
  88. );
  89. INLINE
  90. NONVIRTUAL
  91. IFSUTIL_EXPORT
  92. PVOID
  93. GetSortedNext(
  94. IN PVOID Pnode
  95. );
  96. INLINE
  97. NONVIRTUAL
  98. IFSUTIL_EXPORT
  99. PVOID
  100. GetFirst(
  101. );
  102. INLINE
  103. NONVIRTUAL
  104. IFSUTIL_EXPORT
  105. PVOID
  106. GetNext(
  107. IN PVOID Pnode
  108. );
  109. INLINE
  110. NONVIRTUAL
  111. IFSUTIL_EXPORT
  112. PVOID
  113. GetBuffer(
  114. IN PVOID Pnode
  115. );
  116. NONVIRTUAL
  117. IFSUTIL_EXPORT
  118. PVOID
  119. QueryDisjointRangeAndAssignBuffer(
  120. OUT PBIG_INT Start,
  121. OUT PUSHORT Length,
  122. OUT PUSHORT EffectiveLength,
  123. IN PVOID Buffer,
  124. IN ULONG DataSize,
  125. IN PVOID Pnode
  126. );
  127. NONVIRTUAL
  128. IFSUTIL_EXPORT
  129. void
  130. ShellSort(
  131. );
  132. #if DBG == 1
  133. NONVIRTUAL
  134. IFSUTIL_EXPORT
  135. void
  136. CheckLinkList(
  137. );
  138. NONVIRTUAL
  139. IFSUTIL_EXPORT
  140. void
  141. TraverseLinkList(
  142. );
  143. #endif
  144. private:
  145. NONVIRTUAL
  146. VOID
  147. Construct (
  148. );
  149. NONVIRTUAL
  150. VOID
  151. Destroy(
  152. );
  153. PBIG_INT_NODE _array;
  154. USHORT _size;
  155. USHORT _maxSize;
  156. };
  157. INLINE
  158. USHORT
  159. TLINK::QueryMemberCount(
  160. ) CONST
  161. /*++
  162. Routine Description:
  163. This routine computes the number of elements in the list.
  164. Arguments:
  165. None.
  166. Return Value:
  167. The number of elements in the list.
  168. --*/
  169. {
  170. return _size;
  171. }
  172. INLINE
  173. USHORT
  174. TLINK::QuerySize(
  175. ) CONST
  176. /*++
  177. Routine Description:
  178. This routine computes the maximum number of elements supported by the list.
  179. Arguments:
  180. None.
  181. Return Value:
  182. The maximum number of elements that can be in the list.
  183. --*/
  184. {
  185. return _maxSize;
  186. }
  187. INLINE
  188. VOID
  189. TLINK::Sort(
  190. )
  191. /*++
  192. Routine Description:
  193. This routine sorts the data in the link list.
  194. Arguments:
  195. None.
  196. Return Value:
  197. None.
  198. --*/
  199. {
  200. PBIG_INT_NODE pArray;
  201. DebugPtrAssert(_array);
  202. if (_size) {
  203. pArray = _array + _size + 1;
  204. pArray->data = 0;
  205. pArray->prev = pArray-1;
  206. pArray->next = NULL;
  207. if (_size > 1)
  208. ShellSort();
  209. #if DBG == 1
  210. TraverseLinkList();
  211. CheckLinkList();
  212. #endif
  213. }
  214. }
  215. INLINE
  216. PVOID
  217. TLINK::GetSortedFirst(
  218. )
  219. /*++
  220. Routine Description:
  221. This routine computes the first sorted data node in the link list.
  222. Arguments:
  223. None.
  224. Return Value:
  225. The first sorted data node of the link list.
  226. NULL if there isn't any element in the list.
  227. --*/
  228. {
  229. DebugPtrAssert(_array);
  230. if (_size)
  231. return _array+1;
  232. else
  233. return NULL;
  234. }
  235. INLINE
  236. PVOID
  237. TLINK::GetSortedNext(
  238. IN PVOID Pnode
  239. )
  240. /*++
  241. Routine Description:
  242. This routine computes the next sorted data node in the link list.
  243. Arguments:
  244. None.
  245. Return Value:
  246. The next sorted data node after Pnode in the link list.
  247. --*/
  248. {
  249. DebugPtrAssert(Pnode);
  250. DebugAssert((_array+1) <= Pnode && Pnode <= (_array+_size));
  251. return ((PBIG_INT_NODE)Pnode)+1;
  252. }
  253. INLINE
  254. PVOID
  255. TLINK::GetFirst(
  256. )
  257. /*++
  258. Routine Description:
  259. This routine computes the first unsorted data node in the link list.
  260. Arguments:
  261. None.
  262. Return Value:
  263. The first unsorted data node of the link list.
  264. NULL if there isn't any element in the list.
  265. --*/
  266. {
  267. DebugPtrAssert(_array);
  268. if (_size)
  269. return _array->next;
  270. else
  271. return NULL;
  272. }
  273. INLINE
  274. PVOID
  275. TLINK::GetNext(
  276. IN PVOID Pnode
  277. )
  278. /*++
  279. Routine Description:
  280. This routine computes the next unsorted data node in the link list.
  281. Arguments:
  282. None.
  283. Return Value:
  284. The next unsorted data node after Pnode in the link list.
  285. --*/
  286. {
  287. DebugPtrAssert(Pnode);
  288. DebugAssert((_array+1) <= Pnode && Pnode <= (_array+_size));
  289. return ((PBIG_INT_NODE)Pnode)->next;
  290. }
  291. INLINE
  292. RBIG_INT
  293. TLINK::GetData(
  294. IN USHORT Index
  295. )
  296. /*++
  297. Routine Description:
  298. This routine computes the unsorted data at the specified entry
  299. in the link list. An Index value of zero returns the first
  300. data element in the link list.
  301. Arguments:
  302. None.
  303. Return Value:
  304. The Index(th) data element in the link list.
  305. --*/
  306. {
  307. PBIG_INT_NODE pNode;
  308. DebugPtrAssert(_array);
  309. DebugAssert(_size > Index);
  310. pNode = _array->next;
  311. while (Index-- > 0)
  312. pNode = pNode->next;
  313. return pNode->data;
  314. }
  315. INLINE
  316. RBIG_INT
  317. TLINK::GetData(
  318. IN PVOID Pnode
  319. )
  320. /*++
  321. Routine Description:
  322. This routine computes the unsorted data at the specified entry
  323. in the link list.
  324. Arguments:
  325. None.
  326. Return Value:
  327. The data element in the Pnode.
  328. --*/
  329. {
  330. DebugPtrAssert(Pnode);
  331. return ((PBIG_INT_NODE)Pnode)->data;
  332. }
  333. INLINE
  334. PVOID
  335. TLINK::GetBuffer(
  336. IN PVOID Pnode
  337. )
  338. /*++
  339. Routine Description:
  340. This routine computes the address of the buffer stored at the given
  341. node.
  342. Arguments:
  343. None.
  344. Return Value:
  345. The data element in the Pnode.
  346. --*/
  347. {
  348. DebugPtrAssert(Pnode);
  349. return ((PBIG_INT_NODE)Pnode)->buffer;
  350. }
  351. #endif // TLINK_DEFN