1 /*++
2 
3 Copyright (C) Microsoft Corporation, 1990 - 1999
4 
5 Module Name:
6 
7     dictlib.c
8 
9 Abstract:
10 
11     Support library for maintaining a dictionary list (list of objects
12     referenced by a key value).
13 
14 Environment:
15 
16     kernel mode only
17 
18 Notes:
19 
20     This module generates a static library
21 
22 Revision History:
23 
24 --*/
25 
26 #include <ntddk.h>
27 #include <classpnp.h>
28 
29 #ifdef __REACTOS__
30 #undef MdlMappingNoExecute
31 #define MdlMappingNoExecute 0
32 #define NonPagedPoolNx NonPagedPool
33 #define NonPagedPoolNxCacheAligned NonPagedPoolCacheAligned
34 #undef POOL_NX_ALLOCATION
35 #define POOL_NX_ALLOCATION 0
36 #endif
37 
38 #define DICTIONARY_SIGNATURE 'tciD'
39 
40 #ifdef _MSC_VER
41 #pragma warning(push)
42 #pragma warning(disable:4200) // nonstandard extension used : zero-sized array in struct/union
43 #endif
44 struct _DICTIONARY_HEADER {
45     PDICTIONARY_HEADER Next;
46     ULONGLONG Key;
47     UCHAR Data[0];
48 };
49 #ifdef _MSC_VER
50 #pragma warning(pop)
51 #endif
52 
53 struct _DICTIONARY_HEADER;
54 typedef struct _DICTIONARY_HEADER DICTIONARY_HEADER, *PDICTIONARY_HEADER;
55 
56 
57 VOID
58 InitializeDictionary(
59     IN PDICTIONARY Dictionary
60     )
61 {
62     RtlZeroMemory(Dictionary, sizeof(DICTIONARY));
63     Dictionary->Signature = DICTIONARY_SIGNATURE;
64     KeInitializeSpinLock(&Dictionary->SpinLock);
65     return;
66 }
67 
68 
69 BOOLEAN
70 TestDictionarySignature(
71     IN PDICTIONARY Dictionary
72     )
73 {
74     return Dictionary->Signature == DICTIONARY_SIGNATURE;
75 }
76 
77 NTSTATUS
78 AllocateDictionaryEntry(
79     IN PDICTIONARY Dictionary,
80     IN ULONGLONG Key,
81     _In_range_(0, sizeof(FILE_OBJECT_EXTENSION)) IN ULONG Size,
82     IN ULONG Tag,
83     OUT PVOID *Entry
84     )
85 {
86     PDICTIONARY_HEADER header;
87     KIRQL oldIrql;
88     PDICTIONARY_HEADER *entry;
89 
90     NTSTATUS status = STATUS_SUCCESS;
91 
92     *Entry = NULL;
93 
94     header = ExAllocatePoolWithTag(NonPagedPoolNx,
95                                    Size + sizeof(DICTIONARY_HEADER),
96                                    Tag);
97 
98     if(header == NULL) {
99         return STATUS_INSUFFICIENT_RESOURCES;
100     }
101 
102     RtlZeroMemory(header, sizeof(DICTIONARY_HEADER) + Size);
103     header->Key = Key;
104 
105     //
106     // Find the correct location for this entry in the dictionary.
107     //
108 
109     KeAcquireSpinLock(&(Dictionary->SpinLock), &oldIrql);
110 
111     TRY {
112 
113         entry = &(Dictionary->List);
114 
115         while(*entry != NULL) {
116             if((*entry)->Key == Key) {
117 
118                 //
119                 // Dictionary must have unique keys.
120                 //
121 
122                 status = STATUS_OBJECT_NAME_COLLISION;
123                 LEAVE;
124 
125             } else if ((*entry)->Key < Key) {
126 
127                 //
128                 // We will go ahead and insert the key in here.
129                 //
130                 break;
131             } else {
132                 entry = &((*entry)->Next);
133             }
134         }
135 
136         //
137         // If we make it here then we will go ahead and do the insertion.
138         //
139 
140         header->Next = *entry;
141         *entry = header;
142 
143     } FINALLY {
144         KeReleaseSpinLock(&(Dictionary->SpinLock), oldIrql);
145 
146         if(!NT_SUCCESS(status)) {
147             FREE_POOL(header);
148         } else {
149             *Entry = (PVOID) header->Data;
150         }
151     }
152     return status;
153 }
154 
155 
156 PVOID
157 GetDictionaryEntry(
158     IN PDICTIONARY Dictionary,
159     IN ULONGLONG Key
160     )
161 {
162     PDICTIONARY_HEADER entry;
163     PVOID data;
164     KIRQL oldIrql;
165 
166 
167     data = NULL;
168 
169     KeAcquireSpinLock(&(Dictionary->SpinLock), &oldIrql);
170 
171     entry = Dictionary->List;
172     while (entry != NULL) {
173 
174         if (entry->Key == Key) {
175             data = entry->Data;
176             break;
177         } else {
178             entry = entry->Next;
179         }
180     }
181 
182     KeReleaseSpinLock(&(Dictionary->SpinLock), oldIrql);
183 
184     return data;
185 }
186 
187 
188 VOID
189 FreeDictionaryEntry(
190     IN PDICTIONARY Dictionary,
191     IN PVOID Entry
192     )
193 {
194     PDICTIONARY_HEADER header;
195     PDICTIONARY_HEADER *entry;
196     KIRQL oldIrql;
197     BOOLEAN found;
198 
199     found = FALSE;
200     header = CONTAINING_RECORD(Entry, DICTIONARY_HEADER, Data);
201 
202     KeAcquireSpinLock(&(Dictionary->SpinLock), &oldIrql);
203 
204     entry = &(Dictionary->List);
205     while(*entry != NULL) {
206 
207         if(*entry == header) {
208             *entry = header->Next;
209             found = TRUE;
210             break;
211         } else {
212             entry = &(*entry)->Next;
213         }
214     }
215 
216     KeReleaseSpinLock(&(Dictionary->SpinLock), oldIrql);
217 
218     //
219     // calling this w/an invalid pointer invalidates the dictionary system,
220     // so NT_ASSERT() that we never try to Free something not in the list
221     //
222 
223     NT_ASSERT(found);
224     if (found) {
225         FREE_POOL(header);
226     }
227 
228     return;
229 
230 }
231 
232