strcache.cpp@ 59706

Last change on this file since 59706 was 57358, checked in by vboxsync, 9 years ago
*: scm cleanup run.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 41.8 KB

Line
1	/* $Id: strcache.cpp 57358 2015-08-14 15:16:38Z vboxsync $ */
2	/** @file
3	* IPRT - String Cache.
4	*/
5
6	/*
7	* Copyright (C) 2009-2015 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	return rc;
352	}
353	RT_EXPORT_SYMBOL(RTStrCacheCreate);
354
355
356	RTDECL(int) RTStrCacheDestroy(RTSTRCACHE hStrCache)
357	{
358	if ( hStrCache == NIL_RTSTRCACHE
359	\|\| hStrCache == RTSTRCACHE_DEFAULT)
360	return VINF_SUCCESS;
361
362	PRTSTRCACHEINT pThis = hStrCache;
363	RTSTRCACHE_VALID_RETURN_RC(pThis, VERR_INVALID_HANDLE);
364
365	/*
366	* Invalidate it. Enter the crit sect just to be on the safe side.
367	*/
368	AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTSTRCACHE_MAGIC_DEAD, RTSTRCACHE_MAGIC), VERR_INVALID_HANDLE);
369	RTCritSectEnter(&pThis->CritSect);
370	Assert(pThis->cRefs == 1);
371
372	PRTSTRCACHECHUNK pChunk;
373	while ((pChunk = pThis->pChunkList) != NULL)
374	{
375	pThis->pChunkList = pChunk->pNext;
376	RTMemPageFree(pChunk, pChunk->cb);
377	}
378
379	RTMemFree(pThis->papHashTab);
380	pThis->papHashTab = NULL;
381	pThis->cHashTab = 0;
382
383	PRTSTRCACHEBIGENTRY pCur, pNext;
384	RTListForEachSafe(&pThis->BigEntryList, pCur, pNext, RTSTRCACHEBIGENTRY, ListEntry)
385	{
386	RTMemFree(pCur);
387	}
388
389	RTCritSectLeave(&pThis->CritSect);
390	RTCritSectDelete(&pThis->CritSect);
391
392	RTMemFree(pThis);
393	return VINF_SUCCESS;
394	}
395	RT_EXPORT_SYMBOL(RTStrCacheDestroy);
396
397
398	/**
399	* Selects the fixed free list index for a given minimum entry size.
400	*
401	* @returns Free list index.
402	* @param cbMin Minimum entry size.
403	*/
404	DECLINLINE(uint32_t) rtStrCacheSelectFixedList(uint32_t cbMin)
405	{
406	Assert(cbMin <= g_acbFixedLists[RT_ELEMENTS(g_acbFixedLists) - 1]);
407	unsigned i = 0;
408	while (cbMin > g_acbFixedLists[i])
409	i++;
410	return i;
411	}
412
413
414	#ifdef RT_STRICT
415	# define RTSTRCACHE_CHECK(a_pThis) do { rtStrCacheCheck(pThis); } while (0)
416	/**
417	* Internal cache check.
418	*/
419	static void rtStrCacheCheck(PRTSTRCACHEINT pThis)
420	{
421	# ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
422	for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
423	{
424	PRTSTRCACHEFREEMERGE pFree;
425	RTListForEach(&pThis->aMergedFreeLists[i], pFree, RTSTRCACHEFREEMERGE, ListEntry)
426	{
427	Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
428	Assert(pFree->cbFree > 0);
429	Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
430	}
431	}
432	# endif
433	}
434	#else
435	# define RTSTRCACHE_CHECK(a_pThis) do { } while (0)
436	#endif
437
438
439	/**
440	* Finds the first empty hash table entry given a hash+length value.
441	*
442	* ASSUMES that the hash table isn't full.
443	*
444	* @returns Hash table index.
445	* @param pThis The string cache instance.
446	* @param uHashLen The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
447	*/
448	static uint32_t rtStrCacheFindEmptyHashTabEntry(PRTSTRCACHEINT pThis, uint32_t uHashLen)
449	{
450	uint32_t iHash = uHashLen % pThis->cHashTab;
451	for (;;)
452	{
453	PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
454	if (pEntry == NULL \|\| pEntry == PRTSTRCACHEENTRY_NIL)
455	return iHash;
456
457	/* Advance. */
458	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
459	iHash %= pThis->cHashTab;
460	}
461	}
462
463	/**
464	* Grows the hash table.
465	*
466	* @returns vINF_SUCCESS or VERR_NO_MEMORY.
467	* @param pThis The string cache instance.
468	*/
469	static int rtStrCacheGrowHashTab(PRTSTRCACHEINT pThis)
470	{
471	/*
472	* Allocate a new hash table two times the size of the old one.
473	*/
474	uint32_t cNew = pThis->cHashTab * RTSTRCACHE_HASH_GROW_FACTOR;
475	PRTSTRCACHEENTRY papNew = (PRTSTRCACHEENTRY )RTMemAllocZ(sizeof(papNew[0]) * cNew);
476	if (papNew == NULL)
477	return VERR_NO_MEMORY;
478
479	/*
480	* Install the new table and move the items from the old table and into the new one.
481	*/
482	PRTSTRCACHEENTRY *papOld = pThis->papHashTab;
483	uint32_t iOld = pThis->cHashTab;
484
485	pThis->papHashTab = papNew;
486	pThis->cHashTab = cNew;
487	pThis->cRehashes++;
488
489	while (iOld-- > 0)
490	{
491	PRTSTRCACHEENTRY pEntry = papOld[iOld];
492	if (pEntry != NULL && pEntry != PRTSTRCACHEENTRY_NIL)
493	{
494	uint32_t cchString = pEntry->cchString;
495	if (cchString == RTSTRCACHEENTRY_BIG_LEN)
496	cchString = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core)->cchString;
497
498	uint32_t iHash = rtStrCacheFindEmptyHashTabEntry(pThis, RT_MAKE_U32(pEntry->uHash, cchString));
499	pThis->papHashTab[iHash] = pEntry;
500	}
501	}
502
503	/*
504	* Free the old hash table.
505	*/
506	RTMemFree(papOld);
507	return VINF_SUCCESS;
508	}
509
510	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
511
512	/**
513	* Link/Relink into the free right list.
514	*
515	* @param pThis The string cache instance.
516	* @param pFree The free string entry.
517	*/
518	static void rtStrCacheRelinkMerged(PRTSTRCACHEINT pThis, PRTSTRCACHEFREEMERGE pFree)
519	{
520	Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
521	Assert(pFree->cbFree > 0);
522	Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
523
524	if (!RTListIsEmpty(&pFree->ListEntry))
525	RTListNodeRemove(&pFree->ListEntry);
526
527	uint32_t iList = (ASMBitLastSetU32(pFree->cbFree) - 1) - RTSTRCACHE_MERGED_THRESHOLD_BIT;
528	if (iList >= RT_ELEMENTS(pThis->aMergedFreeLists))
529	iList = RT_ELEMENTS(pThis->aMergedFreeLists) - 1;
530
531	RTListPrepend(&pThis->aMergedFreeLists[iList], &pFree->ListEntry);
532	}
533
534
535	/**
536	* Allocate a cache entry from the merged free lists.
537	*
538	* @returns Pointer to the cache entry on success, NULL on allocation error.
539	* @param pThis The string cache instance.
540	* @param uHash The full hash of the string.
541	* @param pchString The string.
542	* @param cchString The string length.
543	* @param cbEntry The required entry size.
544	*/
545	static PRTSTRCACHEENTRY rtStrCacheAllocMergedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
546	const char *pchString, uint32_t cchString, uint32_t cbEntry)
547	{
548	cbEntry = RT_ALIGN_32(cbEntry, sizeof(RTSTRCACHEFREEMERGE));
549	Assert(cbEntry > cchString);
550
551	/*
552	* Search the list heads first.
553	*/
554	PRTSTRCACHEFREEMERGE pFree = NULL;
555
556	uint32_t iList = ASMBitLastSetU32(cbEntry) - 1;
557	if (!RT_IS_POWER_OF_TWO(cbEntry))
558	iList++;
559	iList -= RTSTRCACHE_MERGED_THRESHOLD_BIT;
560
561	while (iList < RT_ELEMENTS(pThis->aMergedFreeLists))
562	{
563	pFree = RTListGetFirst(&pThis->aMergedFreeLists[iList], RTSTRCACHEFREEMERGE, ListEntry);
564	if (pFree)
565	{
566	/*
567	* Found something. Should we we split it? We split from the end
568	* to avoid having to update all the sub entries.
569	*/
570	Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
571	Assert(pFree->cbFree >= cbEntry);
572	Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
573
574	if (pFree->cbFree == cbEntry)
575	RTListNodeRemove(&pFree->ListEntry);
576	else
577	{
578	uint32_t cRemainder = (pFree->cbFree - cbEntry) / sizeof(*pFree);
579	PRTSTRCACHEFREEMERGE pRemainder = pFree;
580	pFree += cRemainder;
581
582	Assert((pRemainder->cbFree - cbEntry) == cRemainder * sizeof(*pFree));
583	pRemainder->cbFree = cRemainder * sizeof(*pFree);
584
585	rtStrCacheRelinkMerged(pThis, pRemainder);
586	}
587	break;
588	}
589	iList++;
590	}
591	if (!pFree)
592	{
593	/*
594	* Allocate a new block. (We could search the list below in some
595	* cases, but it's too much effort to write and execute).
596	*/
597	size_t const cbChunk = RTSTRCACHE_MERGED_GROW_SIZE; AssertReturn(cbChunk > cbEntry * 2, NULL);
598	PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(cbChunk);
599	if (!pChunk)
600	return NULL;
601	pChunk->cb = cbChunk;
602	pChunk->pNext = pThis->pChunkList;
603	pThis->pChunkList = pChunk;
604	pThis->cbChunks += cbChunk;
605	AssertCompile(sizeof(pChunk) <= sizeof(pFree));
606
607	/*
608	* Get one node for the allocation at hand.
609	*/
610	pFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pChunk + sizeof(*pFree));
611
612	/*
613	* Create a free block out of the remainder (always a reminder).
614	*/
615	PRTSTRCACHEFREEMERGE pNewFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pFree + cbEntry);
616	pNewFree->uMarker = RTSTRCACHEFREEMERGE_MAIN;
617	pNewFree->cbFree = cbChunk - sizeof(*pNewFree) - cbEntry; Assert(pNewFree->cbFree < cbChunk && pNewFree->cbFree > 0);
618	pNewFree->pMain = NULL;
619	RTListInit(&pNewFree->ListEntry);
620
621	uint32_t iInternalBlock = pNewFree->cbFree / sizeof(*pNewFree);
622	while (iInternalBlock-- > 1)
623	{
624	pNewFree[iInternalBlock].uMarker = RTSTRCACHEFREEMERGE_PART;
625	pNewFree[iInternalBlock].cbFree = 0;
626	pNewFree[iInternalBlock].pMain = pNewFree;
627	}
628
629	rtStrCacheRelinkMerged(pThis, pNewFree);
630	}
631
632	/*
633	* Initialize the entry. We zero all bytes we don't use so they cannot
634	* accidentally be mistaken for a free entry.
635	*/
636	ASMCompilerBarrier();
637	PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
638	pEntry->cRefs = 1;
639	pEntry->uHash = (uint16_t)uHash;
640	pEntry->cchString = (uint16_t)cchString;
641	memcpy(pEntry->szString, pchString, cchString);
642	RT_BZERO(&pEntry->szString[cchString], cbEntry - RT_UOFFSETOF(RTSTRCACHEENTRY, szString) - cchString);
643
644	RTSTRCACHE_CHECK(pThis);
645
646	return pEntry;
647	}
648
649	#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
650
651	/**
652	* Allocate a cache entry from the heap.
653	*
654	* @returns Pointer to the cache entry on success, NULL on allocation error.
655	* @param pThis The string cache instance.
656	* @param uHash The full hash of the string.
657	* @param pchString The string.
658	* @param cchString The string length.
659	*/
660	static PRTSTRCACHEENTRY rtStrCacheAllocHeapEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
661	const char *pchString, uint32_t cchString)
662	{
663	/*
664	* Allocate a heap block for storing the string. We do some size aligning
665	* here to encourage the heap to give us optimal alignment.
666	*/
667	size_t cbEntry = RT_UOFFSETOF(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]);
668	PRTSTRCACHEBIGENTRY pBigEntry = (PRTSTRCACHEBIGENTRY)RTMemAlloc(RT_ALIGN_Z(cbEntry, RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN));
669	if (!pBigEntry)
670	return NULL;
671
672	/*
673	* Initialize the block.
674	*/
675	RTListAppend(&pThis->BigEntryList, &pBigEntry->ListEntry);
676	pThis->cbBigEntries += cbEntry;
677	pBigEntry->cchString = cchString;
678	pBigEntry->uHash = uHash;
679	pBigEntry->Core.cRefs = 1;
680	pBigEntry->Core.uHash = (uint16_t)uHash;
681	pBigEntry->Core.cchString = RTSTRCACHEENTRY_BIG_LEN;
682	memcpy(pBigEntry->Core.szString, pchString, cchString);
683	pBigEntry->Core.szString[cchString] = '\0';
684
685	return &pBigEntry->Core;
686	}
687
688
689	/**
690	* Allocate a cache entry from a fixed size free list.
691	*
692	* @returns Pointer to the cache entry on success, NULL on allocation error.
693	* @param pThis The string cache instance.
694	* @param uHash The full hash of the string.
695	* @param pchString The string.
696	* @param cchString The string length.
697	* @param iFreeList Which free list.
698	*/
699	static PRTSTRCACHEENTRY rtStrCacheAllocFixedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
700	const char *pchString, uint32_t cchString, uint32_t iFreeList)
701	{
702	/*
703	* Get an entry from the free list. If empty, allocate another chunk of
704	* memory and split it up into free entries of the desired size.
705	*/
706	PRTSTRCACHEFREE pFree = pThis->apFreeLists[iFreeList];
707	if (!pFree)
708	{
709	PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(RTSTRCACHE_FIXED_GROW_SIZE);
710	if (!pChunk)
711	return NULL;
712	pChunk->cb = RTSTRCACHE_FIXED_GROW_SIZE;
713	pChunk->pNext = pThis->pChunkList;
714	pThis->pChunkList = pChunk;
715	pThis->cbChunks += RTSTRCACHE_FIXED_GROW_SIZE;
716
717	PRTSTRCACHEFREE pPrev = NULL;
718	uint32_t const cbEntry = g_acbFixedLists[iFreeList];
719	uint32_t cLeft = RTSTRCACHE_FIXED_GROW_SIZE / cbEntry - 1;
720	pFree = (PRTSTRCACHEFREE)((uintptr_t)pChunk + cbEntry);
721
722	Assert(sizeof(*pChunk) <= cbEntry);
723	Assert(sizeof(*pFree) <= cbEntry);
724	Assert(cbEntry < RTSTRCACHE_FIXED_GROW_SIZE / 16);
725
726	while (cLeft-- > 0)
727	{
728	pFree->uZero = 0;
729	pFree->cbFree = cbEntry;
730	pFree->pNext = pPrev;
731	pPrev = pFree;
732	pFree = (PRTSTRCACHEFREE)((uintptr_t)pFree + cbEntry);
733	}
734
735	Assert(pPrev);
736	pThis->apFreeLists[iFreeList] = pFree = pPrev;
737	}
738
739	/*
740	* Unlink it.
741	*/
742	pThis->apFreeLists[iFreeList] = pFree->pNext;
743	ASMCompilerBarrier();
744
745	/*
746	* Initialize the entry.
747	*/
748	PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
749	pEntry->cRefs = 1;
750	pEntry->uHash = (uint16_t)uHash;
751	pEntry->cchString = (uint16_t)cchString;
752	memcpy(pEntry->szString, pchString, cchString);
753	pEntry->szString[cchString] = '\0';
754
755	return pEntry;
756	}
757
758
759	/**
760	* Looks up a string in the hash table.
761	*
762	* @returns Pointer to the string cache entry, NULL + piFreeHashTabEntry if not
763	* found.
764	* @param pThis The string cache instance.
765	* @param uHashLen The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
766	* @param cchString The real length.
767	* @param pchString The string.
768	* @param piFreeHashTabEntry Where to store the index insertion index if NULL
769	* is returned (same as what
770	* rtStrCacheFindEmptyHashTabEntry would return).
771	* @param pcCollisions Where to return a collision counter.
772	*/
773	static PRTSTRCACHEENTRY rtStrCacheLookUp(PRTSTRCACHEINT pThis, uint32_t uHashLen, uint32_t cchString, const char *pchString,
774	uint32_t piFreeHashTabEntry, uint32_t pcCollisions)
775	{
776	*piFreeHashTabEntry = UINT32_MAX;
777	*pcCollisions = 0;
778
779	uint16_t cchStringFirst = RT_UOFFSETOF(RTSTRCACHEENTRY, szString[cchString + 1]) < RTSTRCACHE_HEAP_THRESHOLD
780	? (uint16_t)cchString : RTSTRCACHEENTRY_BIG_LEN;
781	uint32_t iHash = uHashLen % pThis->cHashTab;
782	for (;;)
783	{
784	PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
785
786	/* Give up if NULL, but record the index for insertion. */
787	if (pEntry == NULL)
788	{
789	if (*piFreeHashTabEntry == UINT32_MAX)
790	*piFreeHashTabEntry = iHash;
791	return NULL;
792	}
793
794	if (pEntry != PRTSTRCACHEENTRY_NIL)
795	{
796	/* Compare. */
797	if ( pEntry->uHash == (uint16_t)uHashLen
798	&& pEntry->cchString == cchStringFirst)
799	{
800	if (pEntry->cchString != RTSTRCACHEENTRY_BIG_LEN)
801	{
802	if ( !memcmp(pEntry->szString, pchString, cchString)
803	&& pEntry->szString[cchString] == '\0')
804	return pEntry;
805	}
806	else
807	{
808	PRTSTRCACHEBIGENTRY pBigEntry = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core);
809	if ( pBigEntry->cchString == cchString
810	&& !memcmp(pBigEntry->Core.szString, pchString, cchString))
811	return &pBigEntry->Core;
812	}
813	}
814
815	if (*piFreeHashTabEntry == UINT32_MAX)
816	*pcCollisions += 1;
817	}
818	/* Record the first NIL index for insertion in case we don't get a hit. */
819	else if (*piFreeHashTabEntry == UINT32_MAX)
820	*piFreeHashTabEntry = iHash;
821
822	/* Advance. */
823	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
824	iHash %= pThis->cHashTab;
825	}
826	}
827
828
829	RTDECL(const char ) RTStrCacheEnterN(RTSTRCACHE hStrCache, const char pchString, size_t cchString)
830	{
831	PRTSTRCACHEINT pThis = hStrCache;
832	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
833
834
835	/*
836	* Calculate the hash and figure the exact string length, then look for an existing entry.
837	*/
838	uint32_t const uHash = sdbmN(pchString, cchString, &cchString);
839	uint32_t const uHashLen = RT_MAKE_U32(uHash, cchString);
840	AssertReturn(cchString < _1G, NULL);
841	uint32_t const cchString32 = (uint32_t)cchString;
842
843	RTCritSectEnter(&pThis->CritSect);
844	RTSTRCACHE_CHECK(pThis);
845
846	uint32_t cCollisions;
847	uint32_t iFreeHashTabEntry;
848	PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString32, pchString, &iFreeHashTabEntry, &cCollisions);
849	if (pEntry)
850	{
851	uint32_t cRefs = ASMAtomicIncU32(&pEntry->cRefs);
852	Assert(cRefs < UINT32_MAX / 2);
853	}
854	else
855	{
856	/*
857	* Allocate a new entry.
858	*/
859	uint32_t cbEntry = cchString32 + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
860	if (cbEntry >= RTSTRCACHE_HEAP_THRESHOLD)
861	pEntry = rtStrCacheAllocHeapEntry(pThis, uHash, pchString, cchString32);
862	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
863	else if (cbEntry >= RTSTRCACHE_MERGED_THRESHOLD_BIT)
864	pEntry = rtStrCacheAllocMergedEntry(pThis, uHash, pchString, cchString32, cbEntry);
865	#endif
866	else
867	pEntry = rtStrCacheAllocFixedEntry(pThis, uHash, pchString, cchString32,
868	rtStrCacheSelectFixedList(cbEntry));
869	if (!pEntry)
870	{
871	RTSTRCACHE_CHECK(pThis);
872	RTCritSectLeave(&pThis->CritSect);
873	return NULL;
874	}
875
876	/*
877	* Insert it into the hash table.
878	*/
879	if (pThis->cHashTab - pThis->cStrings < pThis->cHashTab / 2)
880	{
881	int rc = rtStrCacheGrowHashTab(pThis);
882	if (RT_SUCCESS(rc))
883	iFreeHashTabEntry = rtStrCacheFindEmptyHashTabEntry(pThis, uHashLen);
884	else if (pThis->cHashTab - pThis->cStrings <= pThis->cHashTab / 8) /* 12.5% full => error */
885	{
886	pThis->papHashTab[iFreeHashTabEntry] = pEntry;
887	pThis->cStrings++;
888	pThis->cHashInserts++;
889	pThis->cHashCollisions += cCollisions > 0;
890	pThis->cHashCollisions2 += cCollisions > 1;
891	pThis->cbStrings += cchString32 + 1;
892	RTStrCacheRelease(hStrCache, pEntry->szString);
893
894	RTSTRCACHE_CHECK(pThis);
895	RTCritSectLeave(&pThis->CritSect);
896	return NULL;
897	}
898	}
899
900	pThis->papHashTab[iFreeHashTabEntry] = pEntry;
901	pThis->cStrings++;
902	pThis->cHashInserts++;
903	pThis->cHashCollisions += cCollisions > 0;
904	pThis->cHashCollisions2 += cCollisions > 1;
905	pThis->cbStrings += cchString32 + 1;
906	Assert(pThis->cStrings < pThis->cHashTab && pThis->cStrings > 0);
907	}
908
909	RTSTRCACHE_CHECK(pThis);
910	RTCritSectLeave(&pThis->CritSect);
911	return pEntry->szString;
912	}
913	RT_EXPORT_SYMBOL(RTStrCacheEnterN);
914
915
916	RTDECL(const char ) RTStrCacheEnter(RTSTRCACHE hStrCache, const char psz)
917	{
918	return RTStrCacheEnterN(hStrCache, psz, strlen(psz));
919	}
920	RT_EXPORT_SYMBOL(RTStrCacheEnter);
921
922
923	static const char rtStrCacheEnterLowerWorker(PRTSTRCACHEINT pThis, const char pchString, size_t cchString)
924	{
925	/*
926	* Try use a dynamic heap buffer first.
927	*/
928	if (cchString < 512)
929	{
930	char pszStackBuf = (char )alloca(cchString + 1);
931	if (pszStackBuf)
932	{
933	memcpy(pszStackBuf, pchString, cchString);
934	pszStackBuf[cchString] = '\0';
935	RTStrToLower(pszStackBuf);
936	return RTStrCacheEnterN(pThis, pszStackBuf, cchString);
937	}
938	}
939
940	/*
941	* Fall back on heap.
942	*/
943	char pszHeapBuf = (char )RTMemTmpAlloc(cchString + 1);
944	if (!pszHeapBuf)
945	return NULL;
946	memcpy(pszHeapBuf, pchString, cchString);
947	pszHeapBuf[cchString] = '\0';
948	RTStrToLower(pszHeapBuf);
949	const char *pszRet = RTStrCacheEnterN(pThis, pszHeapBuf, cchString);
950	RTMemTmpFree(pszHeapBuf);
951	return pszRet;
952	}
953
954	RTDECL(const char ) RTStrCacheEnterLowerN(RTSTRCACHE hStrCache, const char pchString, size_t cchString)
955	{
956	PRTSTRCACHEINT pThis = hStrCache;
957	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
958	return rtStrCacheEnterLowerWorker(pThis, pchString, RTStrNLen(pchString, cchString));
959	}
960	RT_EXPORT_SYMBOL(RTStrCacheEnterLowerN);
961
962
963	RTDECL(const char ) RTStrCacheEnterLower(RTSTRCACHE hStrCache, const char psz)
964	{
965	PRTSTRCACHEINT pThis = hStrCache;
966	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
967	return rtStrCacheEnterLowerWorker(pThis, psz, strlen(psz));
968	}
969	RT_EXPORT_SYMBOL(RTStrCacheEnterLower);
970
971
972	RTDECL(uint32_t) RTStrCacheRetain(const char *psz)
973	{
974	AssertPtr(psz);
975
976	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
977	Assert(!((uintptr_t)pStr & 15) \|\| pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
978
979	uint32_t cRefs = ASMAtomicIncU32(&pStr->cRefs);
980	Assert(cRefs > 1);
981	Assert(cRefs < UINT32_MAX / 2);
982
983	return cRefs;
984	}
985	RT_EXPORT_SYMBOL(RTStrCacheRetain);
986
987
988	static uint32_t rtStrCacheFreeEntry(PRTSTRCACHEINT pThis, PRTSTRCACHEENTRY pStr)
989	{
990	RTCritSectEnter(&pThis->CritSect);
991	RTSTRCACHE_CHECK(pThis);
992
993	/* Remove it from the hash table. */
994	uint32_t cchString = pStr->cchString == RTSTRCACHEENTRY_BIG_LEN
995	? RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core)->cchString
996	: pStr->cchString;
997	uint32_t uHashLen = RT_MAKE_U32(pStr->uHash, cchString);
998	uint32_t iHash = uHashLen % pThis->cHashTab;
999	if (pThis->papHashTab[iHash] == pStr)
1000	pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
1001	else
1002	{
1003	do
1004	{
1005	AssertBreak(pThis->papHashTab[iHash] != NULL);
1006	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
1007	iHash %= pThis->cHashTab;
1008	} while (pThis->papHashTab[iHash] != pStr);
1009	if (RT_LIKELY(pThis->papHashTab[iHash] == pStr))
1010	pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
1011	else
1012	{
1013	AssertFailed();
1014	iHash = pThis->cHashTab;
1015	while (iHash-- > 0)
1016	if (pThis->papHashTab[iHash] == pStr)
1017	break;
1018	AssertMsgFailed(("iHash=%u cHashTab=%u\n", iHash, pThis->cHashTab));
1019	}
1020	}
1021
1022	pThis->cStrings--;
1023	pThis->cbStrings -= cchString;
1024	Assert(pThis->cStrings < pThis->cHashTab);
1025
1026	/* Free it. */
1027	if (pStr->cchString != RTSTRCACHEENTRY_BIG_LEN)
1028	{
1029	uint32_t const cbMin = pStr->cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
1030	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
1031	if (cbMin <= RTSTRCACHE_MAX_FIXED)
1032	#endif
1033	{
1034	/*
1035	* No merging, just add it to the list.
1036	*/
1037	uint32_t const iFreeList = rtStrCacheSelectFixedList(cbMin);
1038	ASMCompilerBarrier();
1039	PRTSTRCACHEFREE pFreeStr = (PRTSTRCACHEFREE)pStr;
1040	pFreeStr->cbFree = cbMin;
1041	pFreeStr->uZero = 0;
1042	pFreeStr->pNext = pThis->apFreeLists[iFreeList];
1043	pThis->apFreeLists[iFreeList] = pFreeStr;
1044	}
1045	#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
1046	else
1047	{
1048	/*
1049	* Complicated mode, we merge with adjecent nodes.
1050	*/
1051	ASMCompilerBarrier();
1052	PRTSTRCACHEFREEMERGE pFreeStr = (PRTSTRCACHEFREEMERGE)pStr;
1053	pFreeStr->cbFree = RT_ALIGN_32(cbMin, sizeof(*pFreeStr));
1054	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_MAIN;
1055	pFreeStr->pMain = NULL;
1056	RTListInit(&pFreeStr->ListEntry);
1057
1058	/*
1059	* Merge with previous?
1060	* (Reading one block back is safe because there is always the
1061	* RTSTRCACHECHUNK structure at the head of each memory chunk.)
1062	*/
1063	uint32_t cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
1064	PRTSTRCACHEFREEMERGE pMain = pFreeStr - 1;
1065	if ( pMain->uMarker == RTSTRCACHEFREEMERGE_MAIN
1066	\|\| pMain->uMarker == RTSTRCACHEFREEMERGE_PART)
1067	{
1068	while (pMain->uMarker != RTSTRCACHEFREEMERGE_MAIN)
1069	pMain--;
1070	pMain->cbFree += pFreeStr->cbFree;
1071	}
1072	else
1073	{
1074	pMain = pFreeStr;
1075	pFreeStr++;
1076	cInternalBlocks--;
1077	}
1078
1079	/*
1080	* Mark internal blocks in the string we're freeing.
1081	*/
1082	while (cInternalBlocks-- > 0)
1083	{
1084	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
1085	pFreeStr->cbFree = 0;
1086	pFreeStr->pMain = pMain;
1087	RTListInit(&pFreeStr->ListEntry);
1088	pFreeStr++;
1089	}
1090
1091	/*
1092	* Merge with next? Limitation: We won't try cross page boundraries.
1093	* (pFreeStr points to the next first free enter after the string now.)
1094	*/
1095	if ( PAGE_ADDRESS(pFreeStr) == PAGE_ADDRESS(&pFreeStr[-1])
1096	&& pFreeStr->uMarker == RTSTRCACHEFREEMERGE_MAIN)
1097	{
1098	pMain->cbFree += pFreeStr->cbFree;
1099	cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
1100	Assert(cInternalBlocks > 0);
1101
1102	/* Update the main block we merge with. */
1103	pFreeStr->cbFree = 0;
1104	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
1105	RTListNodeRemove(&pFreeStr->ListEntry);
1106	RTListInit(&pFreeStr->ListEntry);
1107
1108	/* Change the internal blocks we merged in. */
1109	cInternalBlocks--;
1110	while (cInternalBlocks-- > 0)
1111	{
1112	pFreeStr++;
1113	pFreeStr->pMain = pMain;
1114	Assert(pFreeStr->uMarker == RTSTRCACHEFREEMERGE_PART);
1115	Assert(!pFreeStr->cbFree);
1116	}
1117	}
1118
1119	/*
1120	* Add/relink into the appropriate free list.
1121	*/
1122	rtStrCacheRelinkMerged(pThis, pMain);
1123	}
1124	#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
1125	RTSTRCACHE_CHECK(pThis);
1126	RTCritSectLeave(&pThis->CritSect);
1127	}
1128	else
1129	{
1130	/* Big string. */
1131	PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core);
1132	RTListNodeRemove(&pBigStr->ListEntry);
1133	pThis->cbBigEntries -= RT_ALIGN_32(RT_UOFFSETOF(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]),
1134	RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN);
1135
1136	RTSTRCACHE_CHECK(pThis);
1137	RTCritSectLeave(&pThis->CritSect);
1138
1139	RTMemFree(pBigStr);
1140	}
1141
1142	return 0;
1143	}
1144
1145	RTDECL(uint32_t) RTStrCacheRelease(RTSTRCACHE hStrCache, const char *psz)
1146	{
1147	if (!psz)
1148	return 0;
1149
1150	PRTSTRCACHEINT pThis = hStrCache;
1151	RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
1152
1153	AssertPtr(psz);
1154	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1155	Assert(!((uintptr_t)pStr & 15) \|\| pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
1156
1157	/*
1158	* Drop a reference and maybe free the entry.
1159	*/
1160	uint32_t cRefs = ASMAtomicDecU32(&pStr->cRefs);
1161	Assert(cRefs < UINT32_MAX / 2);
1162	if (!cRefs)
1163	return rtStrCacheFreeEntry(pThis, pStr);
1164
1165	return cRefs;
1166	}
1167	RT_EXPORT_SYMBOL(RTStrCacheRelease);
1168
1169
1170	RTDECL(size_t) RTStrCacheLength(const char *psz)
1171	{
1172	if (!psz)
1173	return 0;
1174
1175	AssertPtr(psz);
1176	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1177	if (pStr->cchString == RTSTRCACHEENTRY_BIG_LEN)
1178	{
1179	PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(psz, RTSTRCACHEBIGENTRY, Core.szString);
1180	return pBigStr->cchString;
1181	}
1182	Assert(!((uintptr_t)pStr & 15));
1183	return pStr->cchString;
1184	}
1185	RT_EXPORT_SYMBOL(RTStrCacheLength);
1186
1187
1188	RTDECL(bool) RTStrCacheIsRealImpl(void)
1189	{
1190	return true;
1191	}
1192	RT_EXPORT_SYMBOL(RTStrCacheIsRealImpl);
1193
1194
1195	RTDECL(uint32_t) RTStrCacheGetStats(RTSTRCACHE hStrCache, size_t pcbStrings, size_t pcbChunks, size_t *pcbBigEntries,
1196	uint32_t pcHashCollisions, uint32_t pcHashCollisions2, uint32_t *pcHashInserts,
1197	uint32_t *pcRehashes)
1198	{
1199	PRTSTRCACHEINT pThis = hStrCache;
1200	RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
1201
1202	RTCritSectEnter(&pThis->CritSect);
1203
1204	if (pcbStrings)
1205	*pcbStrings = pThis->cbStrings;
1206	if (pcbChunks)
1207	*pcbChunks = pThis->cbChunks;
1208	if (pcbBigEntries)
1209	*pcbBigEntries = pThis->cbBigEntries;
1210	if (pcHashCollisions)
1211	*pcHashCollisions = pThis->cHashCollisions;
1212	if (pcHashCollisions2)
1213	*pcHashCollisions2 = pThis->cHashCollisions2;
1214	if (pcHashInserts)
1215	*pcHashInserts = pThis->cHashInserts;
1216	if (pcRehashes)
1217	*pcRehashes = pThis->cRehashes;
1218	uint32_t cStrings = pThis->cStrings;
1219
1220	RTCritSectLeave(&pThis->CritSect);
1221	return cStrings;
1222	}
1223	RT_EXPORT_SYMBOL(RTStrCacheRelease);
1224

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

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

Download in other formats: