Fix RtlQueryAtomInAtomTable and add regression tests
[reactos.git] / reactos / lib / rtl / atom.c
1 /* COPYRIGHT: See COPYING in the top level directory
2 * PROJECT: ReactOS system libraries
3 * FILE: lib/rtl/atom.c
4 * PURPOSE: Atom managment
5 * PROGRAMMER: Thomas Weidenmueller
6 */
7
8 /* INCLUDES *****************************************************************/
9
10 #include <rtl.h>
11
12 #define NDEBUG
13 #include <debug.h>
14
15 /* PROTOTYPES ****************************************************************/
16
17 extern NTSTATUS RtlpInitAtomTableLock(PRTL_ATOM_TABLE AtomTable);
18 extern VOID RtlpDestroyAtomTableLock(PRTL_ATOM_TABLE AtomTable);
19 extern BOOLEAN RtlpLockAtomTable(PRTL_ATOM_TABLE AtomTable);
20 extern VOID RtlpUnlockAtomTable(PRTL_ATOM_TABLE AtomTable);
21
22 extern BOOLEAN RtlpCreateAtomHandleTable(PRTL_ATOM_TABLE AtomTable);
23 extern VOID RtlpDestroyAtomHandleTable(PRTL_ATOM_TABLE AtomTable);
24
25 extern PRTL_ATOM_TABLE RtlpAllocAtomTable(ULONG Size);
26 extern VOID RtlpFreeAtomTable(PRTL_ATOM_TABLE AtomTable);
27 extern PRTL_ATOM_TABLE_ENTRY RtlpAllocAtomTableEntry(ULONG Size);
28 extern VOID RtlpFreeAtomTableEntry(PRTL_ATOM_TABLE_ENTRY Entry);
29
30 extern BOOLEAN RtlpCreateAtomHandle(PRTL_ATOM_TABLE AtomTable, PRTL_ATOM_TABLE_ENTRY Entry);
31 extern VOID RtlpFreeAtomHandle(PRTL_ATOM_TABLE AtomTable, PRTL_ATOM_TABLE_ENTRY Entry);
32 extern PRTL_ATOM_TABLE_ENTRY RtlpGetAtomEntry(PRTL_ATOM_TABLE AtomTable, ULONG Index);
33
34 /* FUNCTIONS *****************************************************************/
35
36 static PRTL_ATOM_TABLE_ENTRY
37 RtlpHashAtomName(IN PRTL_ATOM_TABLE AtomTable,
38 IN PWSTR AtomName,
39 OUT PRTL_ATOM_TABLE_ENTRY **HashLink)
40 {
41 UNICODE_STRING Name;
42 ULONG Hash;
43
44 RtlInitUnicodeString(&Name,
45 AtomName);
46
47 if (Name.Length != 0 &&
48 NT_SUCCESS(RtlHashUnicodeString(&Name,
49 TRUE,
50 HASH_STRING_ALGORITHM_X65599,
51 &Hash)))
52 {
53 PRTL_ATOM_TABLE_ENTRY Current;
54 PRTL_ATOM_TABLE_ENTRY *Link;
55
56 Link = &AtomTable->Buckets[Hash % AtomTable->NumberOfBuckets];
57
58 /* search for an existing entry */
59 Current = *Link;
60 while (Current != NULL)
61 {
62 if (Current->NameLength == Name.Length / sizeof(WCHAR) &&
63 !_wcsicmp(Current->Name, Name.Buffer))
64 {
65 *HashLink = Link;
66 return Current;
67 }
68 Link = &Current->HashLink;
69 Current = Current->HashLink;
70 }
71
72 /* no matching atom found, return the hash link */
73 *HashLink = Link;
74 }
75 else
76 *HashLink = NULL;
77
78 return NULL;
79 }
80
81 static BOOLEAN
82 RtlpCheckIntegerAtom(PWSTR AtomName,
83 PUSHORT AtomValue)
84 {
85 UNICODE_STRING AtomString;
86 ULONG LongValue;
87 USHORT LoValue;
88 PWCHAR p;
89
90 DPRINT("RtlpCheckIntegerAtom(AtomName '%S' AtomValue %p)\n",
91 AtomName, AtomValue);
92
93 if (!((ULONG)AtomName & 0xFFFF0000))
94 {
95 LoValue = (USHORT)((ULONG)AtomName & 0xFFFF);
96
97 if (LoValue == 0)
98 LoValue = 0xC000;
99
100 if (AtomValue != NULL)
101 *AtomValue = LoValue;
102
103 return TRUE;
104 }
105
106 if (*AtomName != L'#')
107 return FALSE;
108
109 p = AtomName;
110 p++;
111 while (*p)
112 {
113 if ((*p < L'0') || (*p > L'9'))
114 return FALSE;
115 p++;
116 }
117
118 p = AtomName;
119 p++;
120 RtlInitUnicodeString(&AtomString,
121 p);
122
123 DPRINT("AtomString: %wZ\n", &AtomString);
124
125 RtlUnicodeStringToInteger(&AtomString,10, &LongValue);
126
127 DPRINT("LongValue: %lu\n", LongValue);
128
129 *AtomValue = (USHORT)(LongValue & 0x0000FFFF);
130
131 return TRUE;
132 }
133
134
135 /*
136 * @implemented
137 */
138 NTSTATUS STDCALL
139 RtlCreateAtomTable(IN ULONG TableSize,
140 IN OUT PRTL_ATOM_TABLE *AtomTable)
141 {
142 PRTL_ATOM_TABLE Table;
143 NTSTATUS Status;
144
145 DPRINT("RtlCreateAtomTable(TableSize %lu AtomTable %p)\n",
146 TableSize, AtomTable);
147
148 if (*AtomTable != NULL)
149 {
150 return STATUS_SUCCESS;
151 }
152
153 /* allocate atom table */
154 Table = RtlpAllocAtomTable(((TableSize - 1) * sizeof(PRTL_ATOM_TABLE_ENTRY)) +
155 sizeof(RTL_ATOM_TABLE));
156 if (Table == NULL)
157 {
158 return STATUS_NO_MEMORY;
159 }
160
161 /* initialize atom table */
162 Table->NumberOfBuckets = TableSize;
163
164 Status = RtlpInitAtomTableLock(Table);
165 if (!NT_SUCCESS(Status))
166 {
167 RtlpFreeAtomTable(Table);
168 return Status;
169 }
170
171 if (!RtlpCreateAtomHandleTable(Table))
172 {
173 RtlpDestroyAtomTableLock(Table);
174 RtlpFreeAtomTable(Table);
175 return STATUS_NO_MEMORY;
176 }
177
178 *AtomTable = Table;
179 return STATUS_SUCCESS;
180 }
181
182
183 /*
184 * @implemented
185 */
186 NTSTATUS STDCALL
187 RtlDestroyAtomTable(IN PRTL_ATOM_TABLE AtomTable)
188 {
189 PRTL_ATOM_TABLE_ENTRY *CurrentBucket, *LastBucket;
190 PRTL_ATOM_TABLE_ENTRY CurrentEntry, NextEntry;
191
192 DPRINT("RtlDestroyAtomTable (AtomTable %p)\n", AtomTable);
193
194 if (!RtlpLockAtomTable(AtomTable))
195 {
196 return (STATUS_INVALID_PARAMETER);
197 }
198
199 /* delete all atoms */
200 LastBucket = AtomTable->Buckets + AtomTable->NumberOfBuckets;
201 for (CurrentBucket = AtomTable->Buckets;
202 CurrentBucket != LastBucket;
203 CurrentBucket++)
204 {
205 NextEntry = *CurrentBucket;
206 *CurrentBucket = NULL;
207
208 while (NextEntry != NULL)
209 {
210 CurrentEntry = NextEntry;
211 NextEntry = NextEntry->HashLink;
212
213 /* no need to delete the atom handle, the handles will all be freed
214 up when destroying the atom handle table! */
215
216 RtlpFreeAtomTableEntry(CurrentEntry);
217 }
218 }
219
220 RtlpDestroyAtomHandleTable(AtomTable);
221
222 RtlpUnlockAtomTable(AtomTable);
223
224 RtlpDestroyAtomTableLock(AtomTable);
225
226 RtlpFreeAtomTable(AtomTable);
227
228 return STATUS_SUCCESS;
229 }
230
231
232 /*
233 * @implemented
234 */
235 NTSTATUS STDCALL
236 RtlEmptyAtomTable(PRTL_ATOM_TABLE AtomTable,
237 BOOLEAN DeletePinned)
238 {
239 PRTL_ATOM_TABLE_ENTRY *CurrentBucket, *LastBucket;
240 PRTL_ATOM_TABLE_ENTRY CurrentEntry, NextEntry, *PtrEntry;
241
242 DPRINT("RtlEmptyAtomTable (AtomTable %p DeletePinned %x)\n",
243 AtomTable, DeletePinned);
244
245 if (RtlpLockAtomTable(AtomTable) == FALSE)
246 {
247 return (STATUS_INVALID_PARAMETER);
248 }
249
250 /* delete all atoms */
251 LastBucket = AtomTable->Buckets + AtomTable->NumberOfBuckets;
252 for (CurrentBucket = AtomTable->Buckets;
253 CurrentBucket != LastBucket;
254 CurrentBucket++)
255 {
256 NextEntry = *CurrentBucket;
257 PtrEntry = CurrentBucket;
258
259 while (NextEntry != NULL)
260 {
261 CurrentEntry = NextEntry;
262 NextEntry = NextEntry->HashLink;
263
264 if (DeletePinned || !(CurrentEntry->Flags & RTL_ATOM_IS_PINNED))
265 {
266 *PtrEntry = NextEntry;
267
268 RtlpFreeAtomHandle(AtomTable,
269 CurrentEntry);
270
271 RtlpFreeAtomTableEntry(CurrentEntry);
272 }
273 else
274 {
275 PtrEntry = &CurrentEntry->HashLink;
276 }
277 }
278 }
279
280 RtlpUnlockAtomTable(AtomTable);
281
282 return STATUS_SUCCESS;
283 }
284
285
286 /*
287 * @implemented
288 */
289 NTSTATUS STDCALL
290 RtlAddAtomToAtomTable(IN PRTL_ATOM_TABLE AtomTable,
291 IN PWSTR AtomName,
292 OUT PRTL_ATOM Atom)
293 {
294 USHORT AtomValue;
295 PRTL_ATOM_TABLE_ENTRY *HashLink;
296 PRTL_ATOM_TABLE_ENTRY Entry = NULL;
297 NTSTATUS Status = STATUS_SUCCESS;
298
299 DPRINT("RtlAddAtomToAtomTable (AtomTable %p AtomName %S Atom %p)\n",
300 AtomTable, AtomName, Atom);
301
302 if (RtlpCheckIntegerAtom (AtomName, &AtomValue))
303 {
304 /* integer atom */
305 if (AtomValue >= 0xC000)
306 {
307 Status = STATUS_INVALID_PARAMETER;
308 }
309 else if (Atom != NULL)
310 {
311 *Atom = (RTL_ATOM)AtomValue;
312 }
313
314 return Status;
315 }
316
317 RtlpLockAtomTable(AtomTable);
318
319 /* string atom, hash it and try to find an existing atom with the same name */
320 Entry = RtlpHashAtomName(AtomTable,
321 AtomName,
322 &HashLink);
323
324 if (Entry != NULL)
325 {
326 /* found another atom, increment the reference counter unless it's pinned */
327
328 if (!(Entry->Flags & RTL_ATOM_IS_PINNED))
329 {
330 if (++Entry->ReferenceCount == 0)
331 {
332 /* FIXME - references overflowed, pin the atom? */
333 Entry->Flags |= RTL_ATOM_IS_PINNED;
334 }
335 }
336
337 if (Atom != NULL)
338 {
339 *Atom = (RTL_ATOM)Entry->Atom;
340 }
341 }
342 else
343 {
344 /* couldn't find an existing atom, HashLink now points to either the
345 HashLink pointer of the previous atom or to the bucket so we can
346 simply add it to the list */
347 if (HashLink != NULL)
348 {
349 ULONG AtomNameLen = wcslen(AtomName);
350
351 Entry = RtlpAllocAtomTableEntry(sizeof(RTL_ATOM_TABLE_ENTRY) -
352 sizeof(Entry->Name) +
353 (AtomNameLen + 1) * sizeof(WCHAR));
354 if (Entry != NULL)
355 {
356 Entry->HashLink = NULL;
357 Entry->ReferenceCount = 1;
358 Entry->Flags = 0x0;
359
360 Entry->NameLength = AtomNameLen;
361 RtlCopyMemory(Entry->Name,
362 AtomName,
363 (AtomNameLen + 1) * sizeof(WCHAR));
364
365 if (RtlpCreateAtomHandle(AtomTable,
366 Entry))
367 {
368 /* append the atom to the list */
369 *HashLink = Entry;
370
371 if (Atom != NULL)
372 {
373 *Atom = (RTL_ATOM)Entry->Atom;
374 }
375 }
376 else
377 {
378 RtlpFreeAtomTableEntry(Entry);
379 Status = STATUS_NO_MEMORY;
380 }
381 }
382 else
383 {
384 Status = STATUS_NO_MEMORY;
385 }
386 }
387 else
388 {
389 /* The caller supplied an empty atom name! */
390 Status = STATUS_OBJECT_NAME_INVALID;
391 }
392 }
393
394 RtlpUnlockAtomTable(AtomTable);
395
396 return Status;
397 }
398
399
400 /*
401 * @implemented
402 */
403 NTSTATUS STDCALL
404 RtlDeleteAtomFromAtomTable(IN PRTL_ATOM_TABLE AtomTable,
405 IN RTL_ATOM Atom)
406 {
407 PRTL_ATOM_TABLE_ENTRY Entry;
408 NTSTATUS Status = STATUS_SUCCESS;
409
410 DPRINT("RtlDeleteAtomFromAtomTable (AtomTable %p Atom %x)\n",
411 AtomTable, Atom);
412
413 if (Atom >= 0xC000)
414 {
415 RtlpLockAtomTable(AtomTable);
416
417 Entry = RtlpGetAtomEntry(AtomTable,
418 (ULONG)((USHORT)Atom - 0xC000));
419
420 if (Entry != NULL && Entry->Atom == (USHORT)Atom)
421 {
422 if (!(Entry->Flags & RTL_ATOM_IS_PINNED))
423 {
424 if (--Entry->ReferenceCount == 0)
425 {
426 PRTL_ATOM_TABLE_ENTRY *HashLink;
427
428 /* it's time to delete the atom. we need to unlink it from
429 the list. The easiest way is to take the atom name and
430 hash it again, this way we get the pointer to either
431 the hash bucket or the previous atom that links to the
432 one we want to delete. This way we can easily bypass
433 this item. */
434 if (RtlpHashAtomName(AtomTable,
435 Entry->Name,
436 &HashLink) != NULL)
437 {
438 /* bypass this atom */
439 *HashLink = Entry->HashLink;
440
441 RtlpFreeAtomHandle(AtomTable,
442 Entry);
443
444 RtlpFreeAtomTableEntry(Entry);
445 }
446 else
447 {
448 /* WTF?! This should never happen!!! */
449 ASSERT(FALSE);
450 }
451 }
452 }
453 else
454 {
455 /* tried to delete a pinned atom, do nothing and return
456 STATUS_WAS_LOCKED, which is NOT a failure code! */
457 Status = STATUS_WAS_LOCKED;
458 }
459 }
460 else
461 {
462 Status = STATUS_INVALID_HANDLE;
463 }
464
465 RtlpUnlockAtomTable(AtomTable);
466 }
467
468 return Status;
469 }
470
471
472 /*
473 * @implemented
474 */
475 NTSTATUS STDCALL
476 RtlLookupAtomInAtomTable(IN PRTL_ATOM_TABLE AtomTable,
477 IN PWSTR AtomName,
478 OUT PRTL_ATOM Atom)
479 {
480 PRTL_ATOM_TABLE_ENTRY Entry, *HashLink;
481 USHORT AtomValue;
482 RTL_ATOM FoundAtom = 0;
483 NTSTATUS Status = STATUS_SUCCESS;
484
485 DPRINT("RtlLookupAtomInAtomTable (AtomTable %p AtomName %S Atom %p)\n",
486 AtomTable, AtomName, Atom);
487
488 if (RtlpCheckIntegerAtom (AtomName, &AtomValue))
489 {
490 /* integer atom */
491 if (AtomValue >= 0xC000)
492 {
493 Status = STATUS_INVALID_PARAMETER;
494 }
495 else if (Atom != NULL)
496 {
497 *Atom = (RTL_ATOM)AtomValue;
498 }
499
500 return Status;
501 }
502
503 RtlpLockAtomTable(AtomTable);
504
505 Status = STATUS_OBJECT_NAME_NOT_FOUND;
506
507 /* string atom */
508 Entry = RtlpHashAtomName(AtomTable,
509 AtomName,
510 &HashLink);
511
512 if (Entry != NULL)
513 {
514 Status = STATUS_SUCCESS;
515 FoundAtom = (RTL_ATOM)Entry->Atom;
516 }
517
518 RtlpUnlockAtomTable(AtomTable);
519
520 if (NT_SUCCESS(Status) && Atom != NULL)
521 {
522 *Atom = FoundAtom;
523 }
524
525 return Status;
526 }
527
528
529 /*
530 * @implemented
531 */
532 NTSTATUS STDCALL
533 RtlPinAtomInAtomTable(IN PRTL_ATOM_TABLE AtomTable,
534 IN RTL_ATOM Atom)
535 {
536 NTSTATUS Status = STATUS_SUCCESS;
537
538 DPRINT("RtlPinAtomInAtomTable (AtomTable %p Atom %x)\n",
539 AtomTable, Atom);
540
541 if (Atom >= 0xC000)
542 {
543 PRTL_ATOM_TABLE_ENTRY Entry;
544
545 RtlpLockAtomTable(AtomTable);
546
547 Entry = RtlpGetAtomEntry(AtomTable,
548 (ULONG)((USHORT)Atom - 0xC000));
549
550 if (Entry != NULL && Entry->Atom == (USHORT)Atom)
551 {
552 Entry->Flags |= RTL_ATOM_IS_PINNED;
553 }
554 else
555 {
556 Status = STATUS_INVALID_HANDLE;
557 }
558
559 RtlpUnlockAtomTable(AtomTable);
560 }
561
562 return Status;
563 }
564
565
566 /*
567 * @implemented
568 *
569 * This API is really messed up with regards to NameLength. If you pass in a
570 * valid buffer for AtomName, NameLength should be the size of the buffer
571 * (in bytes, not characters). So if you expect the string to be 6 char long,
572 * you need to allocate a buffer of 7 WCHARs and pass 14 for NameLength.
573 * The AtomName returned is always null terminated. If the NameLength you pass
574 * is smaller than 4 (4 would leave room for 1 character) the function will
575 * return with status STATUS_BUFFER_TOO_SMALL. If you pass more than 4, the
576 * return status will be STATUS_SUCCESS, even if the buffer is not large enough
577 * to hold the complete string. In that case, the string is silently truncated
578 * and made to fit in the provided buffer. On return NameLength is set to the
579 * number of bytes (but EXCLUDING the bytes for the null terminator) copied.
580 * So, if the string is 6 char long, you pass a buffer of 10 bytes, on return
581 * NameLength will be set to 8.
582 * If you pass in a NULL value for AtomName, the length of the string in bytes
583 * (again EXCLUDING the null terminator) is returned in NameLength, at least
584 * on Win2k, XP and ReactOS. NT4 will return 0 in that case.
585 */
586 NTSTATUS STDCALL
587 RtlQueryAtomInAtomTable(PRTL_ATOM_TABLE AtomTable,
588 RTL_ATOM Atom,
589 PULONG RefCount,
590 PULONG PinCount,
591 PWSTR AtomName,
592 PULONG NameLength)
593 {
594 ULONG Length;
595 union
596 {
597 /* A RTL_ATOM_TABLE_ENTRY has a "WCHAR Name[1]" entry at the end.
598 * Make sure we reserve enough room to facilitate a 12 character name */
599 RTL_ATOM_TABLE_ENTRY AtomTableEntry;
600 WCHAR StringBuffer[sizeof(RTL_ATOM_TABLE_ENTRY) / sizeof(WCHAR) + 12];
601 } NumberEntry;
602 PRTL_ATOM_TABLE_ENTRY Entry;
603 NTSTATUS Status = STATUS_SUCCESS;
604
605 if (Atom < 0xC000)
606 {
607 /* Synthesize an entry */
608 NumberEntry.AtomTableEntry.Atom = Atom;
609 NumberEntry.AtomTableEntry.NameLength = swprintf(NumberEntry.AtomTableEntry.Name,
610 L"#%lu",
611 (ULONG)Atom);
612 NumberEntry.AtomTableEntry.ReferenceCount = 1;
613 NumberEntry.AtomTableEntry.Flags = RTL_ATOM_IS_PINNED;
614 Entry = &NumberEntry.AtomTableEntry;
615 }
616 else
617 {
618 RtlpLockAtomTable(AtomTable);
619
620 Entry = RtlpGetAtomEntry(AtomTable,
621 (ULONG)((USHORT)Atom - 0xC000));
622 }
623
624 if (Entry != NULL && Entry->Atom == (USHORT)Atom)
625 {
626 DPRINT("Atom name: %wZ\n", &Entry->Name);
627
628 if (RefCount != NULL)
629 {
630 *RefCount = Entry->ReferenceCount;
631 }
632
633 if (PinCount != NULL)
634 {
635 *PinCount = ((Entry->Flags & RTL_ATOM_IS_PINNED) != 0);
636 }
637
638 if (NULL != NameLength)
639 {
640 Length = Entry->NameLength * sizeof(WCHAR);
641 if (NULL != AtomName)
642 {
643 if (*NameLength < Length + sizeof(WCHAR))
644 {
645 if (*NameLength < 4)
646 {
647 *NameLength = Length;
648 Status = STATUS_BUFFER_TOO_SMALL;
649 }
650 else
651 {
652 Length = *NameLength - sizeof(WCHAR);
653 }
654 }
655 if (NT_SUCCESS(Status))
656 {
657 RtlCopyMemory(AtomName,
658 Entry->Name,
659 Length);
660 AtomName[Length / sizeof(WCHAR)] = L'\0';
661 *NameLength = Length;
662 }
663 }
664 else
665 {
666 *NameLength = Length;
667 }
668 }
669 else if (NULL != AtomName)
670 {
671 Status = STATUS_INVALID_PARAMETER;
672 }
673 }
674 else
675 {
676 Status = STATUS_INVALID_HANDLE;
677 }
678
679 if (NULL != Entry && Entry != &NumberEntry.AtomTableEntry)
680 {
681 RtlpUnlockAtomTable(AtomTable);
682 }
683
684 return Status;
685 }
686
687
688 /*
689 * @private - only used by NtQueryInformationAtom
690 */
691 NTSTATUS STDCALL
692 RtlQueryAtomListInAtomTable(IN PRTL_ATOM_TABLE AtomTable,
693 IN ULONG MaxAtomCount,
694 OUT ULONG *AtomCount,
695 OUT RTL_ATOM *AtomList)
696 {
697 PRTL_ATOM_TABLE_ENTRY *CurrentBucket, *LastBucket;
698 PRTL_ATOM_TABLE_ENTRY CurrentEntry;
699 ULONG Atoms = 0;
700 NTSTATUS Status = STATUS_SUCCESS;
701
702 RtlpLockAtomTable(AtomTable);
703
704 LastBucket = AtomTable->Buckets + AtomTable->NumberOfBuckets;
705 for (CurrentBucket = AtomTable->Buckets;
706 CurrentBucket != LastBucket;
707 CurrentBucket++)
708 {
709 CurrentEntry = *CurrentBucket;
710
711 while (CurrentEntry != NULL)
712 {
713 if (MaxAtomCount > 0)
714 {
715 *(AtomList++) = (RTL_ATOM)CurrentEntry->Atom;
716 MaxAtomCount--;
717 }
718 else
719 {
720 /* buffer too small, but don't bail. we need to determine the
721 total number of atoms in the table! */
722 Status = STATUS_INFO_LENGTH_MISMATCH;
723 }
724
725 Atoms++;
726 CurrentEntry = CurrentEntry->HashLink;
727 }
728 }
729
730 *AtomCount = Atoms;
731
732 RtlpUnlockAtomTable(AtomTable);
733
734 return Status;
735 }
736