strcache.cpp@ 93103

Last change on this file since 93103 was 90686, checked in by vboxsync, 3 years ago
iprt/strcache.cpp: small correction in disabled code.
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 90686 2021-08-13 23:55:23Z vboxsync $ */
2	/** @file
3	* IPRT - String Cache.
4	*/
5
6	/*
7	* Copyright (C) 2009-2020 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/errcore.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 = (char )memcpy(pBigEntry->Core.szString, pchString, cchString);
687	pszDst[cchString] = '\0';
688	ASMCompilerBarrier();
689
690	return &pBigEntry->Core;
691	}
692
693
694	/**
695	* Allocate a cache entry from a fixed size free list.
696	*
697	* @returns Pointer to the cache entry on success, NULL on allocation error.
698	* @param pThis The string cache instance.
699	* @param uHash The full hash of the string.
700	* @param pchString The string.
701	* @param cchString The string length.
702	* @param iFreeList Which free list.
703	*/
704	static PRTSTRCACHEENTRY rtStrCacheAllocFixedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
705	const char *pchString, uint32_t cchString, uint32_t iFreeList)
706	{
707	/*
708	* Get an entry from the free list. If empty, allocate another chunk of
709	* memory and split it up into free entries of the desired size.
710	*/
711	PRTSTRCACHEFREE pFree = pThis->apFreeLists[iFreeList];
712	if (!pFree)
713	{
714	PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(RTSTRCACHE_FIXED_GROW_SIZE);
715	if (!pChunk)
716	return NULL;
717	pChunk->cb = RTSTRCACHE_FIXED_GROW_SIZE;
718	pChunk->pNext = pThis->pChunkList;
719	pThis->pChunkList = pChunk;
720	pThis->cbChunks += RTSTRCACHE_FIXED_GROW_SIZE;
721
722	PRTSTRCACHEFREE pPrev = NULL;
723	uint32_t const cbEntry = g_acbFixedLists[iFreeList];
724	uint32_t cLeft = RTSTRCACHE_FIXED_GROW_SIZE / cbEntry - 1;
725	pFree = (PRTSTRCACHEFREE)((uintptr_t)pChunk + cbEntry);
726
727	Assert(sizeof(*pChunk) <= cbEntry);
728	Assert(sizeof(*pFree) <= cbEntry);
729	Assert(cbEntry < RTSTRCACHE_FIXED_GROW_SIZE / 16);
730
731	while (cLeft-- > 0)
732	{
733	pFree->uZero = 0;
734	pFree->cbFree = cbEntry;
735	pFree->pNext = pPrev;
736	pPrev = pFree;
737	pFree = (PRTSTRCACHEFREE)((uintptr_t)pFree + cbEntry);
738	}
739
740	Assert(pPrev);
741	pThis->apFreeLists[iFreeList] = pFree = pPrev;
742	}
743
744	/*
745	* Unlink it.
746	*/
747	pThis->apFreeLists[iFreeList] = pFree->pNext;
748	ASMCompilerBarrier();
749
750	/*
751	* Initialize the entry.
752	*/
753	PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
754	pEntry->cRefs = 1;
755	pEntry->uHash = (uint16_t)uHash;
756	pEntry->cchString = (uint16_t)cchString;
757	memcpy(pEntry->szString, pchString, cchString);
758	pEntry->szString[cchString] = '\0';
759
760	return pEntry;
761	}
762
763
764	/**
765	* Looks up a string in the hash table.
766	*
767	* @returns Pointer to the string cache entry, NULL + piFreeHashTabEntry if not
768	* found.
769	* @param pThis The string cache instance.
770	* @param uHashLen The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
771	* @param cchString The real length.
772	* @param pchString The string.
773	* @param piFreeHashTabEntry Where to store the index insertion index if NULL
774	* is returned (same as what
775	* rtStrCacheFindEmptyHashTabEntry would return).
776	* @param pcCollisions Where to return a collision counter.
777	*/
778	static PRTSTRCACHEENTRY rtStrCacheLookUp(PRTSTRCACHEINT pThis, uint32_t uHashLen, uint32_t cchString, const char *pchString,
779	uint32_t piFreeHashTabEntry, uint32_t pcCollisions)
780	{
781	*piFreeHashTabEntry = UINT32_MAX;
782	*pcCollisions = 0;
783
784	uint16_t cchStringFirst = RT_UOFFSETOF_DYN(RTSTRCACHEENTRY, szString[cchString + 1]) < RTSTRCACHE_HEAP_THRESHOLD
785	? (uint16_t)cchString : RTSTRCACHEENTRY_BIG_LEN;
786	uint32_t iHash = uHashLen % pThis->cHashTab;
787	for (;;)
788	{
789	PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
790
791	/* Give up if NULL, but record the index for insertion. */
792	if (pEntry == NULL)
793	{
794	if (*piFreeHashTabEntry == UINT32_MAX)
795	*piFreeHashTabEntry = iHash;
796	return NULL;
797	}
798
799	if (pEntry != PRTSTRCACHEENTRY_NIL)
800	{
801	/* Compare. */
802	if ( pEntry->uHash == (uint16_t)uHashLen
803	&& pEntry->cchString == cchStringFirst)
804	{
805	if (pEntry->cchString != RTSTRCACHEENTRY_BIG_LEN)
806	{
807	if ( !memcmp(pEntry->szString, pchString, cchString)
808	&& pEntry->szString[cchString] == '\0')
809	return pEntry;
810	}
811	else
812	{
813	PRTSTRCACHEBIGENTRY pBigEntry = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core);
814	if ( pBigEntry->cchString == cchString
815	&& !memcmp(pBigEntry->Core.szString, pchString, cchString))
816	return &pBigEntry->Core;
817	}
818	}
819
820	if (*piFreeHashTabEntry == UINT32_MAX)
821	*pcCollisions += 1;
822	}
823	/* Record the first NIL index for insertion in case we don't get a hit. */
824	else if (*piFreeHashTabEntry == UINT32_MAX)
825	*piFreeHashTabEntry = iHash;
826
827	/* Advance. */
828	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
829	iHash %= pThis->cHashTab;
830	}
831	}
832
833
834	RTDECL(const char ) RTStrCacheEnterN(RTSTRCACHE hStrCache, const char pchString, size_t cchString)
835	{
836	PRTSTRCACHEINT pThis = hStrCache;
837	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
838
839
840	/*
841	* Calculate the hash and figure the exact string length, then look for an existing entry.
842	*/
843	uint32_t const uHash = sdbmN(pchString, cchString, &cchString);
844	uint32_t const uHashLen = RT_MAKE_U32(uHash, cchString);
845	AssertReturn(cchString < _1G, NULL);
846	uint32_t const cchString32 = (uint32_t)cchString;
847
848	RTCritSectEnter(&pThis->CritSect);
849	RTSTRCACHE_CHECK(pThis);
850
851	uint32_t cCollisions;
852	uint32_t iFreeHashTabEntry;
853	PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString32, pchString, &iFreeHashTabEntry, &cCollisions);
854	if (pEntry)
855	{
856	uint32_t cRefs = ASMAtomicIncU32(&pEntry->cRefs);
857	Assert(cRefs < UINT32_MAX / 2); NOREF(cRefs);
858	}
859	else
860	{
861	/*
862	* Allocate a new entry.
863	*/
864	uint32_t cbEntry = cchString32 + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
865	if (cbEntry >= RTSTRCACHE_HEAP_THRESHOLD)
866	pEntry = rtStrCacheAllocHeapEntry(pThis, uHash, pchString, cchString32);
867	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
868	else if (cbEntry >= RT_BIT_32(RTSTRCACHE_MERGED_THRESHOLD_BIT))
869	pEntry = rtStrCacheAllocMergedEntry(pThis, uHash, pchString, cchString32, cbEntry);
870	#endif
871	else
872	pEntry = rtStrCacheAllocFixedEntry(pThis, uHash, pchString, cchString32,
873	rtStrCacheSelectFixedList(cbEntry));
874	if (!pEntry)
875	{
876	RTSTRCACHE_CHECK(pThis);
877	RTCritSectLeave(&pThis->CritSect);
878	return NULL;
879	}
880
881	/*
882	* Insert it into the hash table.
883	*/
884	if (pThis->cHashTab - pThis->cStrings < pThis->cHashTab / 2)
885	{
886	int rc = rtStrCacheGrowHashTab(pThis);
887	if (RT_SUCCESS(rc))
888	iFreeHashTabEntry = rtStrCacheFindEmptyHashTabEntry(pThis, uHashLen);
889	else if (pThis->cHashTab - pThis->cStrings <= pThis->cHashTab / 8) /* 12.5% full => error */
890	{
891	pThis->papHashTab[iFreeHashTabEntry] = pEntry;
892	pThis->cStrings++;
893	pThis->cHashInserts++;
894	pThis->cHashCollisions += cCollisions > 0;
895	pThis->cHashCollisions2 += cCollisions > 1;
896	pThis->cbStrings += cchString32 + 1;
897	RTStrCacheRelease(hStrCache, pEntry->szString);
898
899	RTSTRCACHE_CHECK(pThis);
900	RTCritSectLeave(&pThis->CritSect);
901	return NULL;
902	}
903	}
904
905	pThis->papHashTab[iFreeHashTabEntry] = pEntry;
906	pThis->cStrings++;
907	pThis->cHashInserts++;
908	pThis->cHashCollisions += cCollisions > 0;
909	pThis->cHashCollisions2 += cCollisions > 1;
910	pThis->cbStrings += cchString32 + 1;
911	Assert(pThis->cStrings < pThis->cHashTab && pThis->cStrings > 0);
912	}
913
914	RTSTRCACHE_CHECK(pThis);
915	RTCritSectLeave(&pThis->CritSect);
916	return pEntry->szString;
917	}
918	RT_EXPORT_SYMBOL(RTStrCacheEnterN);
919
920
921	RTDECL(const char ) RTStrCacheEnter(RTSTRCACHE hStrCache, const char psz)
922	{
923	return RTStrCacheEnterN(hStrCache, psz, strlen(psz));
924	}
925	RT_EXPORT_SYMBOL(RTStrCacheEnter);
926
927
928	static const char rtStrCacheEnterLowerWorker(PRTSTRCACHEINT pThis, const char pchString, size_t cchString)
929	{
930	/*
931	* Try use a dynamic heap buffer first.
932	*/
933	if (cchString < 512)
934	{
935	char pszStackBuf = (char )alloca(cchString + 1);
936	if (pszStackBuf)
937	{
938	memcpy(pszStackBuf, pchString, cchString);
939	pszStackBuf[cchString] = '\0';
940	RTStrToLower(pszStackBuf);
941	return RTStrCacheEnterN(pThis, pszStackBuf, cchString);
942	}
943	}
944
945	/*
946	* Fall back on heap.
947	*/
948	char pszHeapBuf = (char )RTMemTmpAlloc(cchString + 1);
949	if (!pszHeapBuf)
950	return NULL;
951	memcpy(pszHeapBuf, pchString, cchString);
952	pszHeapBuf[cchString] = '\0';
953	RTStrToLower(pszHeapBuf);
954	const char *pszRet = RTStrCacheEnterN(pThis, pszHeapBuf, cchString);
955	RTMemTmpFree(pszHeapBuf);
956	return pszRet;
957	}
958
959	RTDECL(const char ) RTStrCacheEnterLowerN(RTSTRCACHE hStrCache, const char pchString, size_t cchString)
960	{
961	PRTSTRCACHEINT pThis = hStrCache;
962	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
963	return rtStrCacheEnterLowerWorker(pThis, pchString, RTStrNLen(pchString, cchString));
964	}
965	RT_EXPORT_SYMBOL(RTStrCacheEnterLowerN);
966
967
968	RTDECL(const char ) RTStrCacheEnterLower(RTSTRCACHE hStrCache, const char psz)
969	{
970	PRTSTRCACHEINT pThis = hStrCache;
971	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
972	return rtStrCacheEnterLowerWorker(pThis, psz, strlen(psz));
973	}
974	RT_EXPORT_SYMBOL(RTStrCacheEnterLower);
975
976
977	RTDECL(uint32_t) RTStrCacheRetain(const char *psz)
978	{
979	AssertPtr(psz);
980
981	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
982	Assert(!((uintptr_t)pStr & 15) \|\| pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
983
984	uint32_t cRefs = ASMAtomicIncU32(&pStr->cRefs);
985	Assert(cRefs > 1);
986	Assert(cRefs < UINT32_MAX / 2);
987
988	return cRefs;
989	}
990	RT_EXPORT_SYMBOL(RTStrCacheRetain);
991
992
993	static uint32_t rtStrCacheFreeEntry(PRTSTRCACHEINT pThis, PRTSTRCACHEENTRY pStr)
994	{
995	RTCritSectEnter(&pThis->CritSect);
996	RTSTRCACHE_CHECK(pThis);
997
998	/* Remove it from the hash table. */
999	uint32_t cchString = pStr->cchString == RTSTRCACHEENTRY_BIG_LEN
1000	? RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core)->cchString
1001	: pStr->cchString;
1002	uint32_t uHashLen = RT_MAKE_U32(pStr->uHash, cchString);
1003	uint32_t iHash = uHashLen % pThis->cHashTab;
1004	if (pThis->papHashTab[iHash] == pStr)
1005	pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
1006	else
1007	{
1008	do
1009	{
1010	AssertBreak(pThis->papHashTab[iHash] != NULL);
1011	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
1012	iHash %= pThis->cHashTab;
1013	} while (pThis->papHashTab[iHash] != pStr);
1014	if (RT_LIKELY(pThis->papHashTab[iHash] == pStr))
1015	pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
1016	else
1017	{
1018	AssertFailed();
1019	iHash = pThis->cHashTab;
1020	while (iHash-- > 0)
1021	if (pThis->papHashTab[iHash] == pStr)
1022	break;
1023	AssertMsgFailed(("iHash=%u cHashTab=%u\n", iHash, pThis->cHashTab));
1024	}
1025	}
1026
1027	pThis->cStrings--;
1028	pThis->cbStrings -= cchString;
1029	Assert(pThis->cStrings < pThis->cHashTab);
1030
1031	/* Free it. */
1032	if (pStr->cchString != RTSTRCACHEENTRY_BIG_LEN)
1033	{
1034	uint32_t const cbMin = pStr->cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
1035	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
1036	if (cbMin <= RTSTRCACHE_MAX_FIXED)
1037	#endif
1038	{
1039	/*
1040	* No merging, just add it to the list.
1041	*/
1042	uint32_t const iFreeList = rtStrCacheSelectFixedList(cbMin);
1043	ASMCompilerBarrier();
1044	PRTSTRCACHEFREE pFreeStr = (PRTSTRCACHEFREE)pStr;
1045	pFreeStr->cbFree = cbMin;
1046	pFreeStr->uZero = 0;
1047	pFreeStr->pNext = pThis->apFreeLists[iFreeList];
1048	pThis->apFreeLists[iFreeList] = pFreeStr;
1049	}
1050	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
1051	else
1052	{
1053	/*
1054	* Complicated mode, we merge with adjecent nodes.
1055	*/
1056	ASMCompilerBarrier();
1057	PRTSTRCACHEFREEMERGE pFreeStr = (PRTSTRCACHEFREEMERGE)pStr;
1058	pFreeStr->cbFree = RT_ALIGN_32(cbMin, sizeof(*pFreeStr));
1059	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_MAIN;
1060	pFreeStr->pMain = NULL;
1061	RTListInit(&pFreeStr->ListEntry);
1062
1063	/*
1064	* Merge with previous?
1065	* (Reading one block back is safe because there is always the
1066	* RTSTRCACHECHUNK structure at the head of each memory chunk.)
1067	*/
1068	uint32_t cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
1069	PRTSTRCACHEFREEMERGE pMain = pFreeStr - 1;
1070	if ( pMain->uMarker == RTSTRCACHEFREEMERGE_MAIN
1071	\|\| pMain->uMarker == RTSTRCACHEFREEMERGE_PART)
1072	{
1073	while (pMain->uMarker != RTSTRCACHEFREEMERGE_MAIN)
1074	pMain--;
1075	pMain->cbFree += pFreeStr->cbFree;
1076	}
1077	else
1078	{
1079	pMain = pFreeStr;
1080	pFreeStr++;
1081	cInternalBlocks--;
1082	}
1083
1084	/*
1085	* Mark internal blocks in the string we're freeing.
1086	*/
1087	while (cInternalBlocks-- > 0)
1088	{
1089	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
1090	pFreeStr->cbFree = 0;
1091	pFreeStr->pMain = pMain;
1092	RTListInit(&pFreeStr->ListEntry);
1093	pFreeStr++;
1094	}
1095
1096	/*
1097	* Merge with next? Limitation: We won't try cross page boundraries.
1098	* (pFreeStr points to the next first free enter after the string now.)
1099	*/
1100	if ( PAGE_ADDRESS(pFreeStr) == PAGE_ADDRESS(&pFreeStr[-1])
1101	&& pFreeStr->uMarker == RTSTRCACHEFREEMERGE_MAIN)
1102	{
1103	pMain->cbFree += pFreeStr->cbFree;
1104	cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
1105	Assert(cInternalBlocks > 0);
1106
1107	/* Update the main block we merge with. */
1108	pFreeStr->cbFree = 0;
1109	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
1110	RTListNodeRemove(&pFreeStr->ListEntry);
1111	RTListInit(&pFreeStr->ListEntry);
1112
1113	/* Change the internal blocks we merged in. */
1114	cInternalBlocks--;
1115	while (cInternalBlocks-- > 0)
1116	{
1117	pFreeStr++;
1118	pFreeStr->pMain = pMain;
1119	Assert(pFreeStr->uMarker == RTSTRCACHEFREEMERGE_PART);
1120	Assert(!pFreeStr->cbFree);
1121	}
1122	}
1123
1124	/*
1125	* Add/relink into the appropriate free list.
1126	*/
1127	rtStrCacheRelinkMerged(pThis, pMain);
1128	}
1129	#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
1130	RTSTRCACHE_CHECK(pThis);
1131	RTCritSectLeave(&pThis->CritSect);
1132	}
1133	else
1134	{
1135	/* Big string. */
1136	PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core);
1137	RTListNodeRemove(&pBigStr->ListEntry);
1138	pThis->cbBigEntries -= RT_ALIGN_32(RT_UOFFSETOF_DYN(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]),
1139	RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN);
1140
1141	RTSTRCACHE_CHECK(pThis);
1142	RTCritSectLeave(&pThis->CritSect);
1143
1144	RTMemFree(pBigStr);
1145	}
1146
1147	return 0;
1148	}
1149
1150	RTDECL(uint32_t) RTStrCacheRelease(RTSTRCACHE hStrCache, const char *psz)
1151	{
1152	if (!psz)
1153	return 0;
1154
1155	PRTSTRCACHEINT pThis = hStrCache;
1156	RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
1157
1158	AssertPtr(psz);
1159	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1160	Assert(!((uintptr_t)pStr & 15) \|\| pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
1161
1162	/*
1163	* Drop a reference and maybe free the entry.
1164	*/
1165	uint32_t cRefs = ASMAtomicDecU32(&pStr->cRefs);
1166	Assert(cRefs < UINT32_MAX / 2);
1167	if (!cRefs)
1168	return rtStrCacheFreeEntry(pThis, pStr);
1169
1170	return cRefs;
1171	}
1172	RT_EXPORT_SYMBOL(RTStrCacheRelease);
1173
1174
1175	RTDECL(size_t) RTStrCacheLength(const char *psz)
1176	{
1177	if (!psz)
1178	return 0;
1179
1180	AssertPtr(psz);
1181	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1182	if (pStr->cchString == RTSTRCACHEENTRY_BIG_LEN)
1183	{
1184	PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(psz, RTSTRCACHEBIGENTRY, Core.szString);
1185	return pBigStr->cchString;
1186	}
1187	Assert(!((uintptr_t)pStr & 15));
1188	return pStr->cchString;
1189	}
1190	RT_EXPORT_SYMBOL(RTStrCacheLength);
1191
1192
1193	RTDECL(bool) RTStrCacheIsRealImpl(void)
1194	{
1195	return true;
1196	}
1197	RT_EXPORT_SYMBOL(RTStrCacheIsRealImpl);
1198
1199
1200	RTDECL(uint32_t) RTStrCacheGetStats(RTSTRCACHE hStrCache, size_t pcbStrings, size_t pcbChunks, size_t *pcbBigEntries,
1201	uint32_t pcHashCollisions, uint32_t pcHashCollisions2, uint32_t *pcHashInserts,
1202	uint32_t *pcRehashes)
1203	{
1204	PRTSTRCACHEINT pThis = hStrCache;
1205	RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
1206
1207	RTCritSectEnter(&pThis->CritSect);
1208
1209	if (pcbStrings)
1210	*pcbStrings = pThis->cbStrings;
1211	if (pcbChunks)
1212	*pcbChunks = pThis->cbChunks;
1213	if (pcbBigEntries)
1214	*pcbBigEntries = pThis->cbBigEntries;
1215	if (pcHashCollisions)
1216	*pcHashCollisions = pThis->cHashCollisions;
1217	if (pcHashCollisions2)
1218	*pcHashCollisions2 = pThis->cHashCollisions2;
1219	if (pcHashInserts)
1220	*pcHashInserts = pThis->cHashInserts;
1221	if (pcRehashes)
1222	*pcRehashes = pThis->cRehashes;
1223	uint32_t cStrings = pThis->cStrings;
1224
1225	RTCritSectLeave(&pThis->CritSect);
1226	return cStrings;
1227	}
1228	RT_EXPORT_SYMBOL(RTStrCacheRelease);
1229

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

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

Download in other formats: