strcache.cpp@ 73102

Last change on this file since 73102 was 73102, checked in by vboxsync, 6 years ago
iprt/strcache: Try shut up gcc about array bounds.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 42.0 KB

Line
1	/* $Id: strcache.cpp 73102 2018-07-12 23:36:45Z vboxsync $ */
2	/** @file
3	* IPRT - String Cache.
4	*/
5
6	/*
7	* Copyright (C) 2009-2017 Oracle Corporation
8	*
9	* This file is part of VirtualBox Open Source Edition (OSE), as
10	* available from http://www.virtualbox.org. This file is free software;
11	* you can redistribute it and/or modify it under the terms of the GNU
12	* General Public License (GPL) as published by the Free Software
13	* Foundation, in version 2 as it comes in the "COPYING" file of the
14	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16	*
17	* The contents of this file may alternatively be used under the terms
18	* of the Common Development and Distribution License Version 1.0
19	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20	* VirtualBox OSE distribution, in which case the provisions of the
21	* CDDL are applicable instead of those of the GPL.
22	*
23	* You may elect to license modified versions of this file under the
24	* terms and conditions of either the GPL or the CDDL or both.
25	*/
26
27
28	/*********************************************************************************************************************************
29	* Header Files *
30	*********************************************************************************************************************************/
31	#include <iprt/strcache.h>
32	#include "internal/iprt.h"
33
34	#include <iprt/alloca.h>
35	#include <iprt/asm.h>
36	#include <iprt/assert.h>
37	#include <iprt/critsect.h>
38	#include <iprt/err.h>
39	#include <iprt/list.h>
40	#include <iprt/mem.h>
41	#include <iprt/once.h>
42	#include <iprt/param.h>
43	#include <iprt/string.h>
44
45	#include "internal/strhash.h"
46	#include "internal/magics.h"
47
48
49	/*********************************************************************************************************************************
50	* Defined Constants And Macros *
51	*********************************************************************************************************************************/
52	/** Special NIL pointer for the hash table. It differs from NULL in that it is
53	* a valid hash table entry when doing a lookup. */
54	#define PRTSTRCACHEENTRY_NIL ((PRTSTRCACHEENTRY)~(uintptr_t)1)
55
56	/** Calcuates the increment when handling a collision.
57	* The current formula makes sure it's always odd so we cannot possibly end
58	* up a cyclic loop with an even sized table. It also takes more bits from
59	* the length part. */
60	#define RTSTRCACHE_COLLISION_INCR(uHashLen) ( ((uHashLen >> 8) \| 1) )
61
62	/** The initial hash table size. Must be power of two. */
63	#define RTSTRCACHE_INITIAL_HASH_SIZE 512
64	/** The hash table growth factor. */
65	#define RTSTRCACHE_HASH_GROW_FACTOR 4
66
67	/**
68	* The RTSTRCACHEENTRY size threshold at which we stop using our own allocator
69	* and switch to the application heap, expressed as a power of two.
70	*
71	* Using a 1KB as a reasonable limit here.
72	*/
73	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
74	# define RTSTRCACHE_HEAP_THRESHOLD_BIT 10
75	#else
76	# define RTSTRCACHE_HEAP_THRESHOLD_BIT 9
77	#endif
78	/** The RTSTRCACHE_HEAP_THRESHOLD_BIT as a byte limit. */
79	#define RTSTRCACHE_HEAP_THRESHOLD RT_BIT_32(RTSTRCACHE_HEAP_THRESHOLD_BIT)
80	/** Big (heap) entry size alignment. */
81	#define RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN 16
82
83	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
84	/**
85	* The RTSTRCACHEENTRY size threshold at which we start using the merge free
86	* list for allocations, expressed as a power of two.
87	*/
88	# define RTSTRCACHE_MERGED_THRESHOLD_BIT 6
89
90	/** The number of bytes (power of two) that the merged allocation lists should
91	* be grown by. Must be much greater than RTSTRCACHE_MERGED_THRESHOLD. */
92	# define RTSTRCACHE_MERGED_GROW_SIZE _32K
93	#endif
94
95	/** The number of bytes (power of two) that the fixed allocation lists should
96	* be grown by. */
97	#define RTSTRCACHE_FIXED_GROW_SIZE _32K
98
99	/** The number of fixed sized lists. */
100	#define RTSTRCACHE_NUM_OF_FIXED_SIZES 12
101
102
103	/** Validates a string cache handle, translating RTSTRCACHE_DEFAULT when found,
104	* and returns rc if not valid. */
105	#define RTSTRCACHE_VALID_RETURN_RC(pStrCache, rc) \
106	do { \
107	if ((pStrCache) == RTSTRCACHE_DEFAULT) \
108	{ \
109	int rcOnce = RTOnce(&g_rtStrCacheOnce, rtStrCacheInitDefault, NULL); \
110	if (RT_FAILURE(rcOnce)) \
111	return (rc); \
112	(pStrCache) = g_hrtStrCacheDefault; \
113	} \
114	else \
115	{ \
116	AssertPtrReturn((pStrCache), (rc)); \
117	AssertReturn((pStrCache)->u32Magic == RTSTRCACHE_MAGIC, (rc)); \
118	} \
119	} while (0)
120
121
122
123	/*********************************************************************************************************************************
124	* Structures and Typedefs *
125	*********************************************************************************************************************************/
126	/**
127	* String cache entry.
128	*/
129	typedef struct RTSTRCACHEENTRY
130	{
131	/** The number of references. */
132	uint32_t volatile cRefs;
133	/** The lower 16-bit hash value. */
134	uint16_t uHash;
135	/** The string length (excluding the terminator).
136	* If this is set to RTSTRCACHEENTRY_BIG_LEN, this is a BIG entry
137	* (RTSTRCACHEBIGENTRY). */
138	uint16_t cchString;
139	/** The string. */
140	char szString[8];
141	} RTSTRCACHEENTRY;
142	AssertCompileSize(RTSTRCACHEENTRY, 16);
143	/** Pointer to a string cache entry. */
144	typedef RTSTRCACHEENTRY *PRTSTRCACHEENTRY;
145	/** Pointer to a const string cache entry. */
146	typedef RTSTRCACHEENTRY *PCRTSTRCACHEENTRY;
147
148	/** RTSTCACHEENTRY::cchString value for big cache entries. */
149	#define RTSTRCACHEENTRY_BIG_LEN UINT16_MAX
150
151	/**
152	* Big string cache entry.
153	*
154	* These are allocated individually from the application heap.
155	*/
156	typedef struct RTSTRCACHEBIGENTRY
157	{
158	/** List entry. */
159	RTLISTNODE ListEntry;
160	/** The string length. */
161	uint32_t cchString;
162	/** The full hash value / padding. */
163	uint32_t uHash;
164	/** The core entry. */
165	RTSTRCACHEENTRY Core;
166	} RTSTRCACHEBIGENTRY;
167	AssertCompileSize(RTSTRCACHEENTRY, 16);
168	/** Pointer to a big string cache entry. */
169	typedef RTSTRCACHEBIGENTRY *PRTSTRCACHEBIGENTRY;
170	/** Pointer to a const big string cache entry. */
171	typedef RTSTRCACHEBIGENTRY *PCRTSTRCACHEBIGENTRY;
172
173
174	/**
175	* A free string cache entry.
176	*/
177	typedef struct RTSTRCACHEFREE
178	{
179	/** Zero value indicating that it's a free entry (no refs, no hash). */
180	uint32_t uZero;
181	/** Number of free bytes. Only used for > 32 byte allocations. */
182	uint32_t cbFree;
183	/** Pointer to the next free item. */
184	struct RTSTRCACHEFREE *pNext;
185	} RTSTRCACHEFREE;
186	AssertCompileSize(RTSTRCACHEENTRY, 16);
187	AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, cRefs, RTSTRCACHEFREE, uZero);
188	AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, szString, RTSTRCACHEFREE, pNext);
189	/** Pointer to a free string cache entry. */
190	typedef RTSTRCACHEFREE *PRTSTRCACHEFREE;
191
192	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
193
194	/**
195	* A free string cache entry with merging.
196	*
197	* This differs from RTSTRCACHEFREE only in having a back pointer for more
198	* efficient list management (doubly vs. singly linked lists).
199	*/
200	typedef struct RTSTRCACHEFREEMERGE
201	{
202	/** Marker that indicates what kind of entry this is, either . */
203	uint32_t uMarker;
204	/** Number of free bytes. Only used for > 32 byte allocations. */
205	uint32_t cbFree;
206	/** Pointer to the main node. NULL for main nodes. */
207	struct RTSTRCACHEFREEMERGE *pMain;
208	/** The free list entry. */
209	RTLISTNODE ListEntry;
210	/** Pads the size up to the minimum allocation unit for the merge list.
211	* This both defines the minimum allocation unit and simplifies pointer
212	* manipulation during merging and splitting. */
213	uint8_t abPadding[ARCH_BITS == 32 ? 44 : 32];
214	} RTSTRCACHEFREEMERGE;
215	AssertCompileSize(RTSTRCACHEFREEMERGE, RT_BIT_32(RTSTRCACHE_MERGED_THRESHOLD_BIT));
216	/** Pointer to a free cache string in the merge list. */
217	typedef RTSTRCACHEFREEMERGE *PRTSTRCACHEFREEMERGE;
218
219	/** RTSTRCACHEFREEMERGE::uMarker value indicating that it's the real free chunk
220	* header. Must be something that's invalid UTF-8 for both little and big
221	* endian system. */
222	# define RTSTRCACHEFREEMERGE_MAIN UINT32_C(0xfffffff1)
223	/** RTSTRCACHEFREEMERGE::uMarker value indicating that it's part of a larger
224	* chunk of free memory. Must be something that's invalid UTF-8 for both little
225	* and big endian system. */
226	# define RTSTRCACHEFREEMERGE_PART UINT32_C(0xfffffff2)
227
228	#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
229
230	/**
231	* Tracking structure chunk of memory used by the 16 byte or 32 byte
232	* allocations.
233	*
234	* This occupies the first entry in the chunk.
235	*/
236	typedef struct RTSTRCACHECHUNK
237	{
238	/** The size of the chunk. */
239	size_t cb;
240	/** Pointer to the next chunk. */
241	struct RTSTRCACHECHUNK *pNext;
242	} RTSTRCACHECHUNK;
243	AssertCompile(sizeof(RTSTRCACHECHUNK) <= sizeof(RTSTRCACHEENTRY));
244	/** Pointer to the chunk tracking structure. */
245	typedef RTSTRCACHECHUNK *PRTSTRCACHECHUNK;
246
247
248	/**
249	* Cache instance data.
250	*/
251	typedef struct RTSTRCACHEINT
252	{
253	/** The string cache magic (RTSTRCACHE_MAGIC). */
254	uint32_t u32Magic;
255	/** Ref counter for the cache handle. */
256	uint32_t volatile cRefs;
257	/** The number of strings currently entered in the cache. */
258	uint32_t cStrings;
259	/** The size of the hash table. */
260	uint32_t cHashTab;
261	/** Pointer to the hash table. */
262	PRTSTRCACHEENTRY *papHashTab;
263	/** Free list for allocations of the sizes defined by g_acbFixedLists. */
264	PRTSTRCACHEFREE apFreeLists[RTSTRCACHE_NUM_OF_FIXED_SIZES];
265	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
266	/** Free lists based on */
267	RTLISTANCHOR aMergedFreeLists[RTSTRCACHE_HEAP_THRESHOLD_BIT - RTSTRCACHE_MERGED_THRESHOLD_BIT + 1];
268	#endif
269	/** List of allocated memory chunks. */
270	PRTSTRCACHECHUNK pChunkList;
271	/** List of big cache entries. */
272	RTLISTANCHOR BigEntryList;
273
274	/** @name Statistics
275	* @{ */
276	/** The total size of all chunks. */
277	size_t cbChunks;
278	/** The total length of all the strings, terminators included. */
279	size_t cbStrings;
280	/** The total size of all the big entries. */
281	size_t cbBigEntries;
282	/** Hash collisions. */
283	uint32_t cHashCollisions;
284	/** Secondary hash collisions. */
285	uint32_t cHashCollisions2;
286	/** The number of inserts to compare cHashCollisions to. */
287	uint32_t cHashInserts;
288	/** The number of rehashes. */
289	uint32_t cRehashes;
290	/** @} */
291
292	/** Critical section protecting the cache structures. */
293	RTCRITSECT CritSect;
294	} RTSTRCACHEINT;
295	/** Pointer to a cache instance. */
296	typedef RTSTRCACHEINT *PRTSTRCACHEINT;
297
298
299
300	/*********************************************************************************************************************************
301	* Global Variables *
302	*********************************************************************************************************************************/
303	/** The entry sizes of the fixed lists (RTSTRCACHEINT::apFreeLists). */
304	static const uint32_t g_acbFixedLists[RTSTRCACHE_NUM_OF_FIXED_SIZES] =
305	{
306	16, 32, 48, 64, 96, 128, 192, 256, 320, 384, 448, 512
307	};
308
309	/** Init once for the default string cache. */
310	static RTONCE g_rtStrCacheOnce = RTONCE_INITIALIZER;
311	/** The default string cache. */
312	static RTSTRCACHE g_hrtStrCacheDefault = NIL_RTSTRCACHE;
313
314
315	/** @callback_method_impl{FNRTONCE, Initializes g_hrtStrCacheDefault} */
316	static DECLCALLBACK(int) rtStrCacheInitDefault(void *pvUser)
317	{
318	NOREF(pvUser);
319	return RTStrCacheCreate(&g_hrtStrCacheDefault, "Default");
320	}
321
322
323	RTDECL(int) RTStrCacheCreate(PRTSTRCACHE phStrCache, const char *pszName)
324	{
325	int rc = VERR_NO_MEMORY;
326	PRTSTRCACHEINT pThis = (PRTSTRCACHEINT)RTMemAllocZ(sizeof(*pThis));
327	if (pThis)
328	{
329	pThis->cHashTab = RTSTRCACHE_INITIAL_HASH_SIZE;
330	pThis->papHashTab = (PRTSTRCACHEENTRY)RTMemAllocZ(sizeof(pThis->papHashTab[0]) pThis->cHashTab);
331	if (pThis->papHashTab)
332	{
333	rc = RTCritSectInit(&pThis->CritSect);
334	if (RT_SUCCESS(rc))
335	{
336	RTListInit(&pThis->BigEntryList);
337	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
338	for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
339	RTListInit(&pThis->aMergedFreeLists[i]);
340	#endif
341	pThis->cRefs = 1;
342	pThis->u32Magic = RTSTRCACHE_MAGIC;
343
344	*phStrCache = pThis;
345	return VINF_SUCCESS;
346	}
347	RTMemFree(pThis->papHashTab);
348	}
349	RTMemFree(pThis);
350	}
351
352	RT_NOREF_PV(pszName);
353	return rc;
354	}
355	RT_EXPORT_SYMBOL(RTStrCacheCreate);
356
357
358	RTDECL(int) RTStrCacheDestroy(RTSTRCACHE hStrCache)
359	{
360	if ( hStrCache == NIL_RTSTRCACHE
361	\|\| hStrCache == RTSTRCACHE_DEFAULT)
362	return VINF_SUCCESS;
363
364	PRTSTRCACHEINT pThis = hStrCache;
365	RTSTRCACHE_VALID_RETURN_RC(pThis, VERR_INVALID_HANDLE);
366
367	/*
368	* Invalidate it. Enter the crit sect just to be on the safe side.
369	*/
370	AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTSTRCACHE_MAGIC_DEAD, RTSTRCACHE_MAGIC), VERR_INVALID_HANDLE);
371	RTCritSectEnter(&pThis->CritSect);
372	Assert(pThis->cRefs == 1);
373
374	PRTSTRCACHECHUNK pChunk;
375	while ((pChunk = pThis->pChunkList) != NULL)
376	{
377	pThis->pChunkList = pChunk->pNext;
378	RTMemPageFree(pChunk, pChunk->cb);
379	}
380
381	RTMemFree(pThis->papHashTab);
382	pThis->papHashTab = NULL;
383	pThis->cHashTab = 0;
384
385	PRTSTRCACHEBIGENTRY pCur, pNext;
386	RTListForEachSafe(&pThis->BigEntryList, pCur, pNext, RTSTRCACHEBIGENTRY, ListEntry)
387	{
388	RTMemFree(pCur);
389	}
390
391	RTCritSectLeave(&pThis->CritSect);
392	RTCritSectDelete(&pThis->CritSect);
393
394	RTMemFree(pThis);
395	return VINF_SUCCESS;
396	}
397	RT_EXPORT_SYMBOL(RTStrCacheDestroy);
398
399
400	/**
401	* Selects the fixed free list index for a given minimum entry size.
402	*
403	* @returns Free list index.
404	* @param cbMin Minimum entry size.
405	*/
406	DECLINLINE(uint32_t) rtStrCacheSelectFixedList(uint32_t cbMin)
407	{
408	Assert(cbMin <= g_acbFixedLists[RT_ELEMENTS(g_acbFixedLists) - 1]);
409	unsigned i = 0;
410	while (cbMin > g_acbFixedLists[i])
411	i++;
412	return i;
413	}
414
415
416	#ifdef RT_STRICT
417	# define RTSTRCACHE_CHECK(a_pThis) do { rtStrCacheCheck(pThis); } while (0)
418	/**
419	* Internal cache check.
420	*/
421	static void rtStrCacheCheck(PRTSTRCACHEINT pThis)
422	{
423	# ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
424	for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
425	{
426	PRTSTRCACHEFREEMERGE pFree;
427	RTListForEach(&pThis->aMergedFreeLists[i], pFree, RTSTRCACHEFREEMERGE, ListEntry)
428	{
429	Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
430	Assert(pFree->cbFree > 0);
431	Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
432	}
433	}
434	# endif
435	RT_NOREF_PV(pThis);
436	}
437	#else
438	# define RTSTRCACHE_CHECK(a_pThis) do { } while (0)
439	#endif
440
441
442	/**
443	* Finds the first empty hash table entry given a hash+length value.
444	*
445	* ASSUMES that the hash table isn't full.
446	*
447	* @returns Hash table index.
448	* @param pThis The string cache instance.
449	* @param uHashLen The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
450	*/
451	static uint32_t rtStrCacheFindEmptyHashTabEntry(PRTSTRCACHEINT pThis, uint32_t uHashLen)
452	{
453	uint32_t iHash = uHashLen % pThis->cHashTab;
454	for (;;)
455	{
456	PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
457	if (pEntry == NULL \|\| pEntry == PRTSTRCACHEENTRY_NIL)
458	return iHash;
459
460	/* Advance. */
461	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
462	iHash %= pThis->cHashTab;
463	}
464	}
465
466	/**
467	* Grows the hash table.
468	*
469	* @returns vINF_SUCCESS or VERR_NO_MEMORY.
470	* @param pThis The string cache instance.
471	*/
472	static int rtStrCacheGrowHashTab(PRTSTRCACHEINT pThis)
473	{
474	/*
475	* Allocate a new hash table two times the size of the old one.
476	*/
477	uint32_t cNew = pThis->cHashTab * RTSTRCACHE_HASH_GROW_FACTOR;
478	PRTSTRCACHEENTRY papNew = (PRTSTRCACHEENTRY )RTMemAllocZ(sizeof(papNew[0]) * cNew);
479	if (papNew == NULL)
480	return VERR_NO_MEMORY;
481
482	/*
483	* Install the new table and move the items from the old table and into the new one.
484	*/
485	PRTSTRCACHEENTRY *papOld = pThis->papHashTab;
486	uint32_t iOld = pThis->cHashTab;
487
488	pThis->papHashTab = papNew;
489	pThis->cHashTab = cNew;
490	pThis->cRehashes++;
491
492	while (iOld-- > 0)
493	{
494	PRTSTRCACHEENTRY pEntry = papOld[iOld];
495	if (pEntry != NULL && pEntry != PRTSTRCACHEENTRY_NIL)
496	{
497	uint32_t cchString = pEntry->cchString;
498	if (cchString == RTSTRCACHEENTRY_BIG_LEN)
499	cchString = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core)->cchString;
500
501	uint32_t iHash = rtStrCacheFindEmptyHashTabEntry(pThis, RT_MAKE_U32(pEntry->uHash, cchString));
502	pThis->papHashTab[iHash] = pEntry;
503	}
504	}
505
506	/*
507	* Free the old hash table.
508	*/
509	RTMemFree(papOld);
510	return VINF_SUCCESS;
511	}
512
513	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
514
515	/**
516	* Link/Relink into the free right list.
517	*
518	* @param pThis The string cache instance.
519	* @param pFree The free string entry.
520	*/
521	static void rtStrCacheRelinkMerged(PRTSTRCACHEINT pThis, PRTSTRCACHEFREEMERGE pFree)
522	{
523	Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
524	Assert(pFree->cbFree > 0);
525	Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
526
527	if (!RTListIsEmpty(&pFree->ListEntry))
528	RTListNodeRemove(&pFree->ListEntry);
529
530	uint32_t iList = (ASMBitLastSetU32(pFree->cbFree) - 1) - RTSTRCACHE_MERGED_THRESHOLD_BIT;
531	if (iList >= RT_ELEMENTS(pThis->aMergedFreeLists))
532	iList = RT_ELEMENTS(pThis->aMergedFreeLists) - 1;
533
534	RTListPrepend(&pThis->aMergedFreeLists[iList], &pFree->ListEntry);
535	}
536
537
538	/**
539	* Allocate a cache entry from the merged free lists.
540	*
541	* @returns Pointer to the cache entry on success, NULL on allocation error.
542	* @param pThis The string cache instance.
543	* @param uHash The full hash of the string.
544	* @param pchString The string.
545	* @param cchString The string length.
546	* @param cbEntry The required entry size.
547	*/
548	static PRTSTRCACHEENTRY rtStrCacheAllocMergedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
549	const char *pchString, uint32_t cchString, uint32_t cbEntry)
550	{
551	cbEntry = RT_ALIGN_32(cbEntry, sizeof(RTSTRCACHEFREEMERGE));
552	Assert(cbEntry > cchString);
553
554	/*
555	* Search the list heads first.
556	*/
557	PRTSTRCACHEFREEMERGE pFree = NULL;
558
559	uint32_t iList = ASMBitLastSetU32(cbEntry) - 1;
560	if (!RT_IS_POWER_OF_TWO(cbEntry))
561	iList++;
562	iList -= RTSTRCACHE_MERGED_THRESHOLD_BIT;
563
564	while (iList < RT_ELEMENTS(pThis->aMergedFreeLists))
565	{
566	pFree = RTListGetFirst(&pThis->aMergedFreeLists[iList], RTSTRCACHEFREEMERGE, ListEntry);
567	if (pFree)
568	{
569	/*
570	* Found something. Should we we split it? We split from the end
571	* to avoid having to update all the sub entries.
572	*/
573	Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
574	Assert(pFree->cbFree >= cbEntry);
575	Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
576
577	if (pFree->cbFree == cbEntry)
578	RTListNodeRemove(&pFree->ListEntry);
579	else
580	{
581	uint32_t cRemainder = (pFree->cbFree - cbEntry) / sizeof(*pFree);
582	PRTSTRCACHEFREEMERGE pRemainder = pFree;
583	pFree += cRemainder;
584
585	Assert((pRemainder->cbFree - cbEntry) == cRemainder * sizeof(*pFree));
586	pRemainder->cbFree = cRemainder * sizeof(*pFree);
587
588	rtStrCacheRelinkMerged(pThis, pRemainder);
589	}
590	break;
591	}
592	iList++;
593	}
594	if (!pFree)
595	{
596	/*
597	* Allocate a new block. (We could search the list below in some
598	* cases, but it's too much effort to write and execute).
599	*/
600	size_t const cbChunk = RTSTRCACHE_MERGED_GROW_SIZE; AssertReturn(cbChunk > cbEntry * 2, NULL);
601	PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(cbChunk);
602	if (!pChunk)
603	return NULL;
604	pChunk->cb = cbChunk;
605	pChunk->pNext = pThis->pChunkList;
606	pThis->pChunkList = pChunk;
607	pThis->cbChunks += cbChunk;
608	AssertCompile(sizeof(pChunk) <= sizeof(pFree));
609
610	/*
611	* Get one node for the allocation at hand.
612	*/
613	pFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pChunk + sizeof(*pFree));
614
615	/*
616	* Create a free block out of the remainder (always a reminder).
617	*/
618	PRTSTRCACHEFREEMERGE pNewFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pFree + cbEntry);
619	pNewFree->uMarker = RTSTRCACHEFREEMERGE_MAIN;
620	pNewFree->cbFree = cbChunk - sizeof(*pNewFree) - cbEntry; Assert(pNewFree->cbFree < cbChunk && pNewFree->cbFree > 0);
621	pNewFree->pMain = NULL;
622	RTListInit(&pNewFree->ListEntry);
623
624	uint32_t iInternalBlock = pNewFree->cbFree / sizeof(*pNewFree);
625	while (iInternalBlock-- > 1)
626	{
627	pNewFree[iInternalBlock].uMarker = RTSTRCACHEFREEMERGE_PART;
628	pNewFree[iInternalBlock].cbFree = 0;
629	pNewFree[iInternalBlock].pMain = pNewFree;
630	}
631
632	rtStrCacheRelinkMerged(pThis, pNewFree);
633	}
634
635	/*
636	* Initialize the entry. We zero all bytes we don't use so they cannot
637	* accidentally be mistaken for a free entry.
638	*/
639	ASMCompilerBarrier();
640	PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
641	pEntry->cRefs = 1;
642	pEntry->uHash = (uint16_t)uHash;
643	pEntry->cchString = (uint16_t)cchString;
644	memcpy(pEntry->szString, pchString, cchString);
645	RT_BZERO(&pEntry->szString[cchString], cbEntry - RT_UOFFSETOF(RTSTRCACHEENTRY, szString) - cchString);
646
647	RTSTRCACHE_CHECK(pThis);
648
649	return pEntry;
650	}
651
652	#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
653
654	/**
655	* Allocate a cache entry from the heap.
656	*
657	* @returns Pointer to the cache entry on success, NULL on allocation error.
658	* @param pThis The string cache instance.
659	* @param uHash The full hash of the string.
660	* @param pchString The string.
661	* @param cchString The string length.
662	*/
663	static PRTSTRCACHEENTRY rtStrCacheAllocHeapEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
664	const char *pchString, uint32_t cchString)
665	{
666	/*
667	* Allocate a heap block for storing the string. We do some size aligning
668	* here to encourage the heap to give us optimal alignment.
669	*/
670	size_t cbEntry = RT_UOFFSETOF_DYN(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]);
671	PRTSTRCACHEBIGENTRY pBigEntry = (PRTSTRCACHEBIGENTRY)RTMemAlloc(RT_ALIGN_Z(cbEntry, RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN));
672	if (!pBigEntry)
673	return NULL;
674
675	/*
676	* Initialize the block.
677	*/
678	RTListAppend(&pThis->BigEntryList, &pBigEntry->ListEntry);
679	pThis->cbBigEntries += cbEntry;
680	pBigEntry->cchString = cchString;
681	pBigEntry->uHash = uHash;
682	pBigEntry->Core.cRefs = 1;
683	pBigEntry->Core.uHash = (uint16_t)uHash;
684	pBigEntry->Core.cchString = RTSTRCACHEENTRY_BIG_LEN;
685	/* The following is to try avoid gcc warnings/errors regarding array bounds: */
686	char *pszDst = pBigEntry->Core.szString;
687	memcpy(pszDst, pchString, cchString);
688	pszDst[cchString] = '\0';
689	ASMCompilerBarrier();
690
691	return &pBigEntry->Core;
692	}
693
694
695	/**
696	* Allocate a cache entry from a fixed size free list.
697	*
698	* @returns Pointer to the cache entry on success, NULL on allocation error.
699	* @param pThis The string cache instance.
700	* @param uHash The full hash of the string.
701	* @param pchString The string.
702	* @param cchString The string length.
703	* @param iFreeList Which free list.
704	*/
705	static PRTSTRCACHEENTRY rtStrCacheAllocFixedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
706	const char *pchString, uint32_t cchString, uint32_t iFreeList)
707	{
708	/*
709	* Get an entry from the free list. If empty, allocate another chunk of
710	* memory and split it up into free entries of the desired size.
711	*/
712	PRTSTRCACHEFREE pFree = pThis->apFreeLists[iFreeList];
713	if (!pFree)
714	{
715	PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(RTSTRCACHE_FIXED_GROW_SIZE);
716	if (!pChunk)
717	return NULL;
718	pChunk->cb = RTSTRCACHE_FIXED_GROW_SIZE;
719	pChunk->pNext = pThis->pChunkList;
720	pThis->pChunkList = pChunk;
721	pThis->cbChunks += RTSTRCACHE_FIXED_GROW_SIZE;
722
723	PRTSTRCACHEFREE pPrev = NULL;
724	uint32_t const cbEntry = g_acbFixedLists[iFreeList];
725	uint32_t cLeft = RTSTRCACHE_FIXED_GROW_SIZE / cbEntry - 1;
726	pFree = (PRTSTRCACHEFREE)((uintptr_t)pChunk + cbEntry);
727
728	Assert(sizeof(*pChunk) <= cbEntry);
729	Assert(sizeof(*pFree) <= cbEntry);
730	Assert(cbEntry < RTSTRCACHE_FIXED_GROW_SIZE / 16);
731
732	while (cLeft-- > 0)
733	{
734	pFree->uZero = 0;
735	pFree->cbFree = cbEntry;
736	pFree->pNext = pPrev;
737	pPrev = pFree;
738	pFree = (PRTSTRCACHEFREE)((uintptr_t)pFree + cbEntry);
739	}
740
741	Assert(pPrev);
742	pThis->apFreeLists[iFreeList] = pFree = pPrev;
743	}
744
745	/*
746	* Unlink it.
747	*/
748	pThis->apFreeLists[iFreeList] = pFree->pNext;
749	ASMCompilerBarrier();
750
751	/*
752	* Initialize the entry.
753	*/
754	PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
755	pEntry->cRefs = 1;
756	pEntry->uHash = (uint16_t)uHash;
757	pEntry->cchString = (uint16_t)cchString;
758	memcpy(pEntry->szString, pchString, cchString);
759	pEntry->szString[cchString] = '\0';
760
761	return pEntry;
762	}
763
764
765	/**
766	* Looks up a string in the hash table.
767	*
768	* @returns Pointer to the string cache entry, NULL + piFreeHashTabEntry if not
769	* found.
770	* @param pThis The string cache instance.
771	* @param uHashLen The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
772	* @param cchString The real length.
773	* @param pchString The string.
774	* @param piFreeHashTabEntry Where to store the index insertion index if NULL
775	* is returned (same as what
776	* rtStrCacheFindEmptyHashTabEntry would return).
777	* @param pcCollisions Where to return a collision counter.
778	*/
779	static PRTSTRCACHEENTRY rtStrCacheLookUp(PRTSTRCACHEINT pThis, uint32_t uHashLen, uint32_t cchString, const char *pchString,
780	uint32_t piFreeHashTabEntry, uint32_t pcCollisions)
781	{
782	*piFreeHashTabEntry = UINT32_MAX;
783	*pcCollisions = 0;
784
785	uint16_t cchStringFirst = RT_UOFFSETOF_DYN(RTSTRCACHEENTRY, szString[cchString + 1]) < RTSTRCACHE_HEAP_THRESHOLD
786	? (uint16_t)cchString : RTSTRCACHEENTRY_BIG_LEN;
787	uint32_t iHash = uHashLen % pThis->cHashTab;
788	for (;;)
789	{
790	PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
791
792	/* Give up if NULL, but record the index for insertion. */
793	if (pEntry == NULL)
794	{
795	if (*piFreeHashTabEntry == UINT32_MAX)
796	*piFreeHashTabEntry = iHash;
797	return NULL;
798	}
799
800	if (pEntry != PRTSTRCACHEENTRY_NIL)
801	{
802	/* Compare. */
803	if ( pEntry->uHash == (uint16_t)uHashLen
804	&& pEntry->cchString == cchStringFirst)
805	{
806	if (pEntry->cchString != RTSTRCACHEENTRY_BIG_LEN)
807	{
808	if ( !memcmp(pEntry->szString, pchString, cchString)
809	&& pEntry->szString[cchString] == '\0')
810	return pEntry;
811	}
812	else
813	{
814	PRTSTRCACHEBIGENTRY pBigEntry = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core);
815	if ( pBigEntry->cchString == cchString
816	&& !memcmp(pBigEntry->Core.szString, pchString, cchString))
817	return &pBigEntry->Core;
818	}
819	}
820
821	if (*piFreeHashTabEntry == UINT32_MAX)
822	*pcCollisions += 1;
823	}
824	/* Record the first NIL index for insertion in case we don't get a hit. */
825	else if (*piFreeHashTabEntry == UINT32_MAX)
826	*piFreeHashTabEntry = iHash;
827
828	/* Advance. */
829	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
830	iHash %= pThis->cHashTab;
831	}
832	}
833
834
835	RTDECL(const char ) RTStrCacheEnterN(RTSTRCACHE hStrCache, const char pchString, size_t cchString)
836	{
837	PRTSTRCACHEINT pThis = hStrCache;
838	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
839
840
841	/*
842	* Calculate the hash and figure the exact string length, then look for an existing entry.
843	*/
844	uint32_t const uHash = sdbmN(pchString, cchString, &cchString);
845	uint32_t const uHashLen = RT_MAKE_U32(uHash, cchString);
846	AssertReturn(cchString < _1G, NULL);
847	uint32_t const cchString32 = (uint32_t)cchString;
848
849	RTCritSectEnter(&pThis->CritSect);
850	RTSTRCACHE_CHECK(pThis);
851
852	uint32_t cCollisions;
853	uint32_t iFreeHashTabEntry;
854	PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString32, pchString, &iFreeHashTabEntry, &cCollisions);
855	if (pEntry)
856	{
857	uint32_t cRefs = ASMAtomicIncU32(&pEntry->cRefs);
858	Assert(cRefs < UINT32_MAX / 2); NOREF(cRefs);
859	}
860	else
861	{
862	/*
863	* Allocate a new entry.
864	*/
865	uint32_t cbEntry = cchString32 + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
866	if (cbEntry >= RTSTRCACHE_HEAP_THRESHOLD)
867	pEntry = rtStrCacheAllocHeapEntry(pThis, uHash, pchString, cchString32);
868	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
869	else if (cbEntry >= RTSTRCACHE_MERGED_THRESHOLD_BIT)
870	pEntry = rtStrCacheAllocMergedEntry(pThis, uHash, pchString, cchString32, cbEntry);
871	#endif
872	else
873	pEntry = rtStrCacheAllocFixedEntry(pThis, uHash, pchString, cchString32,
874	rtStrCacheSelectFixedList(cbEntry));
875	if (!pEntry)
876	{
877	RTSTRCACHE_CHECK(pThis);
878	RTCritSectLeave(&pThis->CritSect);
879	return NULL;
880	}
881
882	/*
883	* Insert it into the hash table.
884	*/
885	if (pThis->cHashTab - pThis->cStrings < pThis->cHashTab / 2)
886	{
887	int rc = rtStrCacheGrowHashTab(pThis);
888	if (RT_SUCCESS(rc))
889	iFreeHashTabEntry = rtStrCacheFindEmptyHashTabEntry(pThis, uHashLen);
890	else if (pThis->cHashTab - pThis->cStrings <= pThis->cHashTab / 8) /* 12.5% full => error */
891	{
892	pThis->papHashTab[iFreeHashTabEntry] = pEntry;
893	pThis->cStrings++;
894	pThis->cHashInserts++;
895	pThis->cHashCollisions += cCollisions > 0;
896	pThis->cHashCollisions2 += cCollisions > 1;
897	pThis->cbStrings += cchString32 + 1;
898	RTStrCacheRelease(hStrCache, pEntry->szString);
899
900	RTSTRCACHE_CHECK(pThis);
901	RTCritSectLeave(&pThis->CritSect);
902	return NULL;
903	}
904	}
905
906	pThis->papHashTab[iFreeHashTabEntry] = pEntry;
907	pThis->cStrings++;
908	pThis->cHashInserts++;
909	pThis->cHashCollisions += cCollisions > 0;
910	pThis->cHashCollisions2 += cCollisions > 1;
911	pThis->cbStrings += cchString32 + 1;
912	Assert(pThis->cStrings < pThis->cHashTab && pThis->cStrings > 0);
913	}
914
915	RTSTRCACHE_CHECK(pThis);
916	RTCritSectLeave(&pThis->CritSect);
917	return pEntry->szString;
918	}
919	RT_EXPORT_SYMBOL(RTStrCacheEnterN);
920
921
922	RTDECL(const char ) RTStrCacheEnter(RTSTRCACHE hStrCache, const char psz)
923	{
924	return RTStrCacheEnterN(hStrCache, psz, strlen(psz));
925	}
926	RT_EXPORT_SYMBOL(RTStrCacheEnter);
927
928
929	static const char rtStrCacheEnterLowerWorker(PRTSTRCACHEINT pThis, const char pchString, size_t cchString)
930	{
931	/*
932	* Try use a dynamic heap buffer first.
933	*/
934	if (cchString < 512)
935	{
936	char pszStackBuf = (char )alloca(cchString + 1);
937	if (pszStackBuf)
938	{
939	memcpy(pszStackBuf, pchString, cchString);
940	pszStackBuf[cchString] = '\0';
941	RTStrToLower(pszStackBuf);
942	return RTStrCacheEnterN(pThis, pszStackBuf, cchString);
943	}
944	}
945
946	/*
947	* Fall back on heap.
948	*/
949	char pszHeapBuf = (char )RTMemTmpAlloc(cchString + 1);
950	if (!pszHeapBuf)
951	return NULL;
952	memcpy(pszHeapBuf, pchString, cchString);
953	pszHeapBuf[cchString] = '\0';
954	RTStrToLower(pszHeapBuf);
955	const char *pszRet = RTStrCacheEnterN(pThis, pszHeapBuf, cchString);
956	RTMemTmpFree(pszHeapBuf);
957	return pszRet;
958	}
959
960	RTDECL(const char ) RTStrCacheEnterLowerN(RTSTRCACHE hStrCache, const char pchString, size_t cchString)
961	{
962	PRTSTRCACHEINT pThis = hStrCache;
963	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
964	return rtStrCacheEnterLowerWorker(pThis, pchString, RTStrNLen(pchString, cchString));
965	}
966	RT_EXPORT_SYMBOL(RTStrCacheEnterLowerN);
967
968
969	RTDECL(const char ) RTStrCacheEnterLower(RTSTRCACHE hStrCache, const char psz)
970	{
971	PRTSTRCACHEINT pThis = hStrCache;
972	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
973	return rtStrCacheEnterLowerWorker(pThis, psz, strlen(psz));
974	}
975	RT_EXPORT_SYMBOL(RTStrCacheEnterLower);
976
977
978	RTDECL(uint32_t) RTStrCacheRetain(const char *psz)
979	{
980	AssertPtr(psz);
981
982	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
983	Assert(!((uintptr_t)pStr & 15) \|\| pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
984
985	uint32_t cRefs = ASMAtomicIncU32(&pStr->cRefs);
986	Assert(cRefs > 1);
987	Assert(cRefs < UINT32_MAX / 2);
988
989	return cRefs;
990	}
991	RT_EXPORT_SYMBOL(RTStrCacheRetain);
992
993
994	static uint32_t rtStrCacheFreeEntry(PRTSTRCACHEINT pThis, PRTSTRCACHEENTRY pStr)
995	{
996	RTCritSectEnter(&pThis->CritSect);
997	RTSTRCACHE_CHECK(pThis);
998
999	/* Remove it from the hash table. */
1000	uint32_t cchString = pStr->cchString == RTSTRCACHEENTRY_BIG_LEN
1001	? RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core)->cchString
1002	: pStr->cchString;
1003	uint32_t uHashLen = RT_MAKE_U32(pStr->uHash, cchString);
1004	uint32_t iHash = uHashLen % pThis->cHashTab;
1005	if (pThis->papHashTab[iHash] == pStr)
1006	pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
1007	else
1008	{
1009	do
1010	{
1011	AssertBreak(pThis->papHashTab[iHash] != NULL);
1012	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
1013	iHash %= pThis->cHashTab;
1014	} while (pThis->papHashTab[iHash] != pStr);
1015	if (RT_LIKELY(pThis->papHashTab[iHash] == pStr))
1016	pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
1017	else
1018	{
1019	AssertFailed();
1020	iHash = pThis->cHashTab;
1021	while (iHash-- > 0)
1022	if (pThis->papHashTab[iHash] == pStr)
1023	break;
1024	AssertMsgFailed(("iHash=%u cHashTab=%u\n", iHash, pThis->cHashTab));
1025	}
1026	}
1027
1028	pThis->cStrings--;
1029	pThis->cbStrings -= cchString;
1030	Assert(pThis->cStrings < pThis->cHashTab);
1031
1032	/* Free it. */
1033	if (pStr->cchString != RTSTRCACHEENTRY_BIG_LEN)
1034	{
1035	uint32_t const cbMin = pStr->cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
1036	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
1037	if (cbMin <= RTSTRCACHE_MAX_FIXED)
1038	#endif
1039	{
1040	/*
1041	* No merging, just add it to the list.
1042	*/
1043	uint32_t const iFreeList = rtStrCacheSelectFixedList(cbMin);
1044	ASMCompilerBarrier();
1045	PRTSTRCACHEFREE pFreeStr = (PRTSTRCACHEFREE)pStr;
1046	pFreeStr->cbFree = cbMin;
1047	pFreeStr->uZero = 0;
1048	pFreeStr->pNext = pThis->apFreeLists[iFreeList];
1049	pThis->apFreeLists[iFreeList] = pFreeStr;
1050	}
1051	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
1052	else
1053	{
1054	/*
1055	* Complicated mode, we merge with adjecent nodes.
1056	*/
1057	ASMCompilerBarrier();
1058	PRTSTRCACHEFREEMERGE pFreeStr = (PRTSTRCACHEFREEMERGE)pStr;
1059	pFreeStr->cbFree = RT_ALIGN_32(cbMin, sizeof(*pFreeStr));
1060	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_MAIN;
1061	pFreeStr->pMain = NULL;
1062	RTListInit(&pFreeStr->ListEntry);
1063
1064	/*
1065	* Merge with previous?
1066	* (Reading one block back is safe because there is always the
1067	* RTSTRCACHECHUNK structure at the head of each memory chunk.)
1068	*/
1069	uint32_t cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
1070	PRTSTRCACHEFREEMERGE pMain = pFreeStr - 1;
1071	if ( pMain->uMarker == RTSTRCACHEFREEMERGE_MAIN
1072	\|\| pMain->uMarker == RTSTRCACHEFREEMERGE_PART)
1073	{
1074	while (pMain->uMarker != RTSTRCACHEFREEMERGE_MAIN)
1075	pMain--;
1076	pMain->cbFree += pFreeStr->cbFree;
1077	}
1078	else
1079	{
1080	pMain = pFreeStr;
1081	pFreeStr++;
1082	cInternalBlocks--;
1083	}
1084
1085	/*
1086	* Mark internal blocks in the string we're freeing.
1087	*/
1088	while (cInternalBlocks-- > 0)
1089	{
1090	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
1091	pFreeStr->cbFree = 0;
1092	pFreeStr->pMain = pMain;
1093	RTListInit(&pFreeStr->ListEntry);
1094	pFreeStr++;
1095	}
1096
1097	/*
1098	* Merge with next? Limitation: We won't try cross page boundraries.
1099	* (pFreeStr points to the next first free enter after the string now.)
1100	*/
1101	if ( PAGE_ADDRESS(pFreeStr) == PAGE_ADDRESS(&pFreeStr[-1])
1102	&& pFreeStr->uMarker == RTSTRCACHEFREEMERGE_MAIN)
1103	{
1104	pMain->cbFree += pFreeStr->cbFree;
1105	cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
1106	Assert(cInternalBlocks > 0);
1107
1108	/* Update the main block we merge with. */
1109	pFreeStr->cbFree = 0;
1110	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
1111	RTListNodeRemove(&pFreeStr->ListEntry);
1112	RTListInit(&pFreeStr->ListEntry);
1113
1114	/* Change the internal blocks we merged in. */
1115	cInternalBlocks--;
1116	while (cInternalBlocks-- > 0)
1117	{
1118	pFreeStr++;
1119	pFreeStr->pMain = pMain;
1120	Assert(pFreeStr->uMarker == RTSTRCACHEFREEMERGE_PART);
1121	Assert(!pFreeStr->cbFree);
1122	}
1123	}
1124
1125	/*
1126	* Add/relink into the appropriate free list.
1127	*/
1128	rtStrCacheRelinkMerged(pThis, pMain);
1129	}
1130	#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
1131	RTSTRCACHE_CHECK(pThis);
1132	RTCritSectLeave(&pThis->CritSect);
1133	}
1134	else
1135	{
1136	/* Big string. */
1137	PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core);
1138	RTListNodeRemove(&pBigStr->ListEntry);
1139	pThis->cbBigEntries -= RT_ALIGN_32(RT_UOFFSETOF_DYN(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]),
1140	RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN);
1141
1142	RTSTRCACHE_CHECK(pThis);
1143	RTCritSectLeave(&pThis->CritSect);
1144
1145	RTMemFree(pBigStr);
1146	}
1147
1148	return 0;
1149	}
1150
1151	RTDECL(uint32_t) RTStrCacheRelease(RTSTRCACHE hStrCache, const char *psz)
1152	{
1153	if (!psz)
1154	return 0;
1155
1156	PRTSTRCACHEINT pThis = hStrCache;
1157	RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
1158
1159	AssertPtr(psz);
1160	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1161	Assert(!((uintptr_t)pStr & 15) \|\| pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
1162
1163	/*
1164	* Drop a reference and maybe free the entry.
1165	*/
1166	uint32_t cRefs = ASMAtomicDecU32(&pStr->cRefs);
1167	Assert(cRefs < UINT32_MAX / 2);
1168	if (!cRefs)
1169	return rtStrCacheFreeEntry(pThis, pStr);
1170
1171	return cRefs;
1172	}
1173	RT_EXPORT_SYMBOL(RTStrCacheRelease);
1174
1175
1176	RTDECL(size_t) RTStrCacheLength(const char *psz)
1177	{
1178	if (!psz)
1179	return 0;
1180
1181	AssertPtr(psz);
1182	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1183	if (pStr->cchString == RTSTRCACHEENTRY_BIG_LEN)
1184	{
1185	PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(psz, RTSTRCACHEBIGENTRY, Core.szString);
1186	return pBigStr->cchString;
1187	}
1188	Assert(!((uintptr_t)pStr & 15));
1189	return pStr->cchString;
1190	}
1191	RT_EXPORT_SYMBOL(RTStrCacheLength);
1192
1193
1194	RTDECL(bool) RTStrCacheIsRealImpl(void)
1195	{
1196	return true;
1197	}
1198	RT_EXPORT_SYMBOL(RTStrCacheIsRealImpl);
1199
1200
1201	RTDECL(uint32_t) RTStrCacheGetStats(RTSTRCACHE hStrCache, size_t pcbStrings, size_t pcbChunks, size_t *pcbBigEntries,
1202	uint32_t pcHashCollisions, uint32_t pcHashCollisions2, uint32_t *pcHashInserts,
1203	uint32_t *pcRehashes)
1204	{
1205	PRTSTRCACHEINT pThis = hStrCache;
1206	RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
1207
1208	RTCritSectEnter(&pThis->CritSect);
1209
1210	if (pcbStrings)
1211	*pcbStrings = pThis->cbStrings;
1212	if (pcbChunks)
1213	*pcbChunks = pThis->cbChunks;
1214	if (pcbBigEntries)
1215	*pcbBigEntries = pThis->cbBigEntries;
1216	if (pcHashCollisions)
1217	*pcHashCollisions = pThis->cHashCollisions;
1218	if (pcHashCollisions2)
1219	*pcHashCollisions2 = pThis->cHashCollisions2;
1220	if (pcHashInserts)
1221	*pcHashInserts = pThis->cHashInserts;
1222	if (pcRehashes)
1223	*pcRehashes = pThis->cRehashes;
1224	uint32_t cStrings = pThis->cStrings;
1225
1226	RTCritSectLeave(&pThis->CritSect);
1227	return cStrings;
1228	}
1229	RT_EXPORT_SYMBOL(RTStrCacheRelease);
1230

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/Runtime/common/string/strcache.cpp@ 73102

Download in other formats: