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 "classp.h"
27 
28 #define DICTIONARY_SIGNATURE 'dsig'
29 
30 typedef struct _DICTIONARY_HEADER {
31     struct _DICTIONARY_HEADER* Next;
32     ULONGLONG Key;
33     UCHAR Data[0];
34 } DICTIONARY_HEADER, *PDICTIONARY_HEADER;
35 
36 
37 VOID
38 NTAPI
39 InitializeDictionary(
40     IN PDICTIONARY Dictionary
41     )
42 {
43     RtlZeroMemory(Dictionary, sizeof(DICTIONARY));
44     Dictionary->Signature = DICTIONARY_SIGNATURE;
45     KeInitializeSpinLock(&Dictionary->SpinLock);
46     return;
47 }
48 
49 BOOLEAN
50 NTAPI
51 TestDictionarySignature(
52     IN PDICTIONARY Dictionary
53     )
54 {
55     return Dictionary->Signature == DICTIONARY_SIGNATURE;
56 }
57 
58 NTSTATUS
59 NTAPI
60 AllocateDictionaryEntry(
61     IN PDICTIONARY Dictionary,
62     IN ULONGLONG Key,
63     IN ULONG Size,
64     IN ULONG Tag,
65     OUT PVOID *Entry
66     )
67 {
68     PDICTIONARY_HEADER header;
69     KIRQL oldIrql;
70     PDICTIONARY_HEADER *entry;
71 
72     NTSTATUS status = STATUS_SUCCESS;
73 
74     *Entry = NULL;
75 
76     header = ExAllocatePoolWithTag(NonPagedPool,
77                                    Size + sizeof(DICTIONARY_HEADER),
78                                    Tag);
79 
80     if(header == NULL) {
81         return STATUS_INSUFFICIENT_RESOURCES;
82     }
83 
84     RtlZeroMemory(header, sizeof(DICTIONARY_HEADER) + Size);
85     header->Key = Key;
86 
87     //
88     // Find the correct location for this entry in the dictionary.
89     //
90 
91     KeAcquireSpinLock(&(Dictionary->SpinLock), &oldIrql);
92 
93     TRY {
94 
95         entry = &(Dictionary->List);
96 
97         while(*entry != NULL) {
98             if((*entry)->Key == Key) {
99 
100                 //
101                 // Dictionary must have unique keys.
102                 //
103 
104                 status = STATUS_OBJECT_NAME_COLLISION;
105                 LEAVE;
106 
107             } else if ((*entry)->Key < Key) {
108 
109                 //
110                 // We will go ahead and insert the key in here.
111                 //
112                 break;
113             } else {
114                 entry = &((*entry)->Next);
115             }
116         }
117 
118         //
119         // If we make it here then we will go ahead and do the insertion.
120         //
121 
122         header->Next = *entry;
123         *entry = header;
124 
125     } FINALLY {
126         KeReleaseSpinLock(&(Dictionary->SpinLock), oldIrql);
127 
128         if(!NT_SUCCESS(status)) {
129             ExFreePool(header);
130         } else {
131             *Entry = (PVOID) header->Data;
132         }
133     }
134     return status;
135 }
136 
137 PVOID
138 NTAPI
139 GetDictionaryEntry(
140     IN PDICTIONARY Dictionary,
141     IN ULONGLONG Key
142     )
143 {
144     PDICTIONARY_HEADER entry;
145     PVOID data;
146     KIRQL oldIrql;
147 
148 
149     data = NULL;
150 
151     KeAcquireSpinLock(&(Dictionary->SpinLock), &oldIrql);
152 
153     entry = Dictionary->List;
154     while (entry != NULL) {
155 
156         if (entry->Key == Key) {
157             data = entry->Data;
158             break;
159         } else {
160             entry = entry->Next;
161         }
162     }
163 
164     KeReleaseSpinLock(&(Dictionary->SpinLock), oldIrql);
165 
166     return data;
167 }
168 
169 VOID
170 NTAPI
171 FreeDictionaryEntry(
172     IN PDICTIONARY Dictionary,
173     IN PVOID Entry
174     )
175 {
176     PDICTIONARY_HEADER header;
177     PDICTIONARY_HEADER *entry;
178     KIRQL oldIrql;
179     BOOLEAN found;
180 
181     found = FALSE;
182     header = CONTAINING_RECORD(Entry, DICTIONARY_HEADER, Data);
183 
184     KeAcquireSpinLock(&(Dictionary->SpinLock), &oldIrql);
185 
186     entry = &(Dictionary->List);
187     while(*entry != NULL) {
188 
189         if(*entry == header) {
190             *entry = header->Next;
191             found = TRUE;
192             break;
193         } else {
194             entry = &(*entry)->Next;
195         }
196     }
197 
198     KeReleaseSpinLock(&(Dictionary->SpinLock), oldIrql);
199 
200     //
201     // calling this w/an invalid pointer invalidates the dictionary system,
202     // so ASSERT() that we never try to Free something not in the list
203     //
204 
205     ASSERT(found);
206     if (found) {
207         ExFreePool(header);
208     }
209 
210     return;
211 
212 }
213