strcache.cpp@ 96563

Last change on this file since 96563 was 96407, checked in by vboxsync, 2 years ago
scm copyright and license note update
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 42.3 KB

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

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

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

Download in other formats: