strcache.cpp@ 73041

Last change on this file since 73041 was 69111, checked in by vboxsync, 7 years ago
(C) year
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 41.9 KB

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

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

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

Download in other formats: