Added a binary tree implementation
[reactos.git] / reactos / include / ddk / extypes.h
1 /* $Id: extypes.h,v 1.7 2002/03/22 20:58:23 chorns Exp $ */
2
3 #ifndef __INCLUDE_DDK_EXTYPES_H
4 #define __INCLUDE_DDK_EXTYPES_H
5
6 #ifdef __NTOSKRNL__
7 extern POBJECT_TYPE EXPORTED ExDesktopObjectType;
8 extern POBJECT_TYPE EXPORTED ExEventObjectType;
9 extern POBJECT_TYPE EXPORTED ExWindowStationObjectType;
10 #else
11 extern POBJECT_TYPE IMPORTED ExDesktopObjectType;
12 extern POBJECT_TYPE IMPORTED ExEventObjectType;
13 extern POBJECT_TYPE IMPORTED ExWindowStationObjectType;
14 #endif
15
16 typedef ULONG INTERLOCKED_RESULT;
17 typedef ULONG WORK_QUEUE_TYPE;
18
19 typedef ULONG ERESOURCE_THREAD, *PERESOURCE_THREAD;
20
21 typedef struct _OWNER_ENTRY
22 {
23 ERESOURCE_THREAD OwnerThread;
24 union
25 {
26 LONG OwnerCount;
27 ULONG TableSize;
28 } a;
29 } OWNER_ENTRY, *POWNER_ENTRY;
30
31 typedef struct _ERESOURCE
32 {
33 LIST_ENTRY SystemResourcesList;
34 POWNER_ENTRY OwnerTable;
35 SHORT ActiveCount;
36 USHORT Flag;
37 PKSEMAPHORE SharedWaiters;
38 PKEVENT ExclusiveWaiters;
39 OWNER_ENTRY OwnerThreads[2];
40 ULONG ContentionCount;
41 USHORT NumberOfSharedWaiters;
42 USHORT NumberOfExclusiveWaiters;
43 union
44 {
45 PVOID Address;
46 ULONG CreatorBackTraceIndex;
47 } a;
48 KSPIN_LOCK SpinLock;
49 } ERESOURCE, *PERESOURCE;
50
51
52 typedef struct
53 {
54 LONG Count;
55 struct _KTHREAD* Owner;
56 ULONG Contention;
57 KEVENT Event;
58 ULONG OldIrql;
59 } FAST_MUTEX, *PFAST_MUTEX;
60
61 typedef struct _ZONE_HEADER
62 {
63 SINGLE_LIST_ENTRY FreeList;
64 SINGLE_LIST_ENTRY SegmentList;
65 ULONG BlockSize;
66 ULONG TotalSegmentSize;
67 } ZONE_HEADER, *PZONE_HEADER;
68
69 typedef struct _ZONE_SEGMENT
70 {
71 SINGLE_LIST_ENTRY Entry;
72 ULONG size;
73 } ZONE_SEGMENT, *PZONE_SEGMENT;
74
75 typedef struct _ZONE_ENTRY
76 {
77 SINGLE_LIST_ENTRY Entry;
78 } ZONE_ENTRY, *PZONE_ENTRY;
79
80
81 typedef VOID STDCALL
82 (*PWORKER_THREAD_ROUTINE)(PVOID Parameter);
83
84 typedef struct _WORK_QUEUE_ITEM
85 {
86 LIST_ENTRY Entry;
87 PWORKER_THREAD_ROUTINE Routine;
88 PVOID Context;
89 } WORK_QUEUE_ITEM, *PWORK_QUEUE_ITEM;
90
91 typedef PVOID STDCALL
92 (*PALLOCATE_FUNCTION)(POOL_TYPE PoolType,
93 ULONG NumberOfBytes,
94 ULONG Tag);
95
96 typedef VOID STDCALL
97 (*PFREE_FUNCTION)(PVOID Buffer);
98
99 typedef union _SLIST_HEADER
100 {
101 ULONGLONG Alignment;
102 struct
103 {
104 SINGLE_LIST_ENTRY Next;
105 USHORT Depth;
106 USHORT Sequence;
107 } s;
108 } SLIST_HEADER, *PSLIST_HEADER;
109
110 typedef struct _NPAGED_LOOKASIDE_LIST
111 {
112 SLIST_HEADER ListHead;
113 USHORT MinimumDepth;
114 USHORT MaximumDepth;
115 ULONG TotalAllocates;
116 ULONG AllocateMisses;
117 ULONG TotalFrees;
118 ULONG FreeMisses;
119 POOL_TYPE Type;
120 ULONG Tag;
121 ULONG Size;
122 PALLOCATE_FUNCTION Allocate;
123 PFREE_FUNCTION Free;
124 LIST_ENTRY ListEntry;
125 ULONG LastTotalAllocates;
126 ULONG LastAllocateMisses;
127 ULONG Pad[2];
128 KSPIN_LOCK Lock;
129 } NPAGED_LOOKASIDE_LIST, *PNPAGED_LOOKASIDE_LIST;
130
131 typedef struct _PAGED_LOOKASIDE_LIST
132 {
133 SLIST_HEADER ListHead;
134 USHORT MinimumDepth;
135 USHORT MaximumDepth;
136 ULONG TotalAllocates;
137 ULONG AllocateMisses;
138 ULONG TotalFrees;
139 ULONG FreeMisses;
140 POOL_TYPE Type;
141 ULONG Tag;
142 ULONG Size;
143 PALLOCATE_FUNCTION Allocate;
144 PFREE_FUNCTION Free;
145 LIST_ENTRY ListEntry;
146 ULONG LastTotalAllocates;
147 ULONG LastAllocateMisses;
148 FAST_MUTEX Lock;
149 } PAGED_LOOKASIDE_LIST, *PPAGED_LOOKASIDE_LIST;
150
151
152 /* callback object (not functional in NT4)*/
153
154 typedef struct _CALLBACK_OBJECT *PCALLBACK_OBJECT;
155
156 typedef VOID STDCALL
157 (*PCALLBACK_FUNCTION)(PVOID CallbackContext,
158 PVOID Argument1,
159 PVOID Argument2);
160
161 /* BEGIN REACTOS ONLY */
162
163 typedef LONG STDCALL (*PKEY_COMPARATOR)(PVOID Key1,
164 PVOID Key2);
165
166 struct _BINARY_TREE_NODE;
167
168 typedef struct _BINARY_TREE
169 {
170 struct _BINARY_TREE_NODE * RootNode;
171 PKEY_COMPARATOR Compare;
172 PAGED_LOOKASIDE_LIST LookasideList;
173 FAST_MUTEX Lock;
174 } BINARY_TREE, *PBINARY_TREE;
175
176
177 struct _SPLAY_TREE_NODE;
178
179 typedef struct _SPLAY_TREE
180 {
181 struct _SPLAY_TREE_NODE * RootNode;
182 PKEY_COMPARATOR Compare;
183 BOOLEAN Weighted;
184 PAGED_LOOKASIDE_LIST LookasideList;
185 FAST_MUTEX Lock;
186 PVOID Reserved[4];
187 } SPLAY_TREE, *PSPLAY_TREE;
188
189
190 typedef struct _HASH_TABLE
191 {
192 // Lock for this structure
193 FAST_MUTEX Lock;
194
195 // Size of hash table in number of bits
196 ULONG HashTableSize;
197
198 // Pointer to array of hash buckets with splay trees
199 PSPLAY_TREE HashTrees;
200 } HASH_TABLE, *PHASH_TABLE;
201
202 /* END REACTOS ONLY */
203
204 #endif /* __INCLUDE_DDK_EXTYPES_H */
205
206 /* EOF */