summaryrefslogtreecommitdiffstats
path: root/src/VBox/Runtime/common/string/strcache.cpp
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-06 03:01:46 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-06 03:01:46 +0000
commitf8fe689a81f906d1b91bb3220acde2a4ecb14c5b (patch)
tree26484e9d7e2c67806c2d1760196ff01aaa858e8c /src/VBox/Runtime/common/string/strcache.cpp
parentInitial commit. (diff)
downloadvirtualbox-f8fe689a81f906d1b91bb3220acde2a4ecb14c5b.tar.xz
virtualbox-f8fe689a81f906d1b91bb3220acde2a4ecb14c5b.zip
Adding upstream version 6.0.4-dfsg.upstream/6.0.4-dfsgupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/VBox/Runtime/common/string/strcache.cpp')
-rw-r--r--src/VBox/Runtime/common/string/strcache.cpp1229
1 files changed, 1229 insertions, 0 deletions
diff --git a/src/VBox/Runtime/common/string/strcache.cpp b/src/VBox/Runtime/common/string/strcache.cpp
new file mode 100644
index 00000000..451b7986
--- /dev/null
+++ b/src/VBox/Runtime/common/string/strcache.cpp
@@ -0,0 +1,1229 @@
+/* $Id: strcache.cpp $ */
+/** @file
+ * IPRT - String Cache.
+ */
+
+/*
+ * Copyright (C) 2009-2019 Oracle Corporation
+ *
+ * This file is part of VirtualBox Open Source Edition (OSE), as
+ * available from http://www.virtualbox.org. This file is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU
+ * General Public License (GPL) as published by the Free Software
+ * Foundation, in version 2 as it comes in the "COPYING" file of the
+ * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
+ * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+
+/*********************************************************************************************************************************
+* Header Files *
+*********************************************************************************************************************************/
+#include <iprt/strcache.h>
+#include "internal/iprt.h"
+
+#include <iprt/alloca.h>
+#include <iprt/asm.h>
+#include <iprt/assert.h>
+#include <iprt/critsect.h>
+#include <iprt/errcore.h>
+#include <iprt/list.h>
+#include <iprt/mem.h>
+#include <iprt/once.h>
+#include <iprt/param.h>
+#include <iprt/string.h>
+
+#include "internal/strhash.h"
+#include "internal/magics.h"
+
+
+/*********************************************************************************************************************************
+* Defined Constants And Macros *
+*********************************************************************************************************************************/
+/** Special NIL pointer for the hash table. It differs from NULL in that it is
+ * a valid hash table entry when doing a lookup. */
+#define PRTSTRCACHEENTRY_NIL ((PRTSTRCACHEENTRY)~(uintptr_t)1)
+
+/** Calcuates the increment when handling a collision.
+ * The current formula makes sure it's always odd so we cannot possibly end
+ * up a cyclic loop with an even sized table. It also takes more bits from
+ * the length part. */
+#define RTSTRCACHE_COLLISION_INCR(uHashLen) ( ((uHashLen >> 8) | 1) )
+
+/** The initial hash table size. Must be power of two. */
+#define RTSTRCACHE_INITIAL_HASH_SIZE 512
+/** The hash table growth factor. */
+#define RTSTRCACHE_HASH_GROW_FACTOR 4
+
+/**
+ * The RTSTRCACHEENTRY size threshold at which we stop using our own allocator
+ * and switch to the application heap, expressed as a power of two.
+ *
+ * Using a 1KB as a reasonable limit here.
+ */
+#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+# define RTSTRCACHE_HEAP_THRESHOLD_BIT 10
+#else
+# define RTSTRCACHE_HEAP_THRESHOLD_BIT 9
+#endif
+/** The RTSTRCACHE_HEAP_THRESHOLD_BIT as a byte limit. */
+#define RTSTRCACHE_HEAP_THRESHOLD RT_BIT_32(RTSTRCACHE_HEAP_THRESHOLD_BIT)
+/** Big (heap) entry size alignment. */
+#define RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN 16
+
+#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+/**
+ * The RTSTRCACHEENTRY size threshold at which we start using the merge free
+ * list for allocations, expressed as a power of two.
+ */
+# define RTSTRCACHE_MERGED_THRESHOLD_BIT 6
+
+/** The number of bytes (power of two) that the merged allocation lists should
+ * be grown by. Must be much greater than RTSTRCACHE_MERGED_THRESHOLD. */
+# define RTSTRCACHE_MERGED_GROW_SIZE _32K
+#endif
+
+/** The number of bytes (power of two) that the fixed allocation lists should
+ * be grown by. */
+#define RTSTRCACHE_FIXED_GROW_SIZE _32K
+
+/** The number of fixed sized lists. */
+#define RTSTRCACHE_NUM_OF_FIXED_SIZES 12
+
+
+/** Validates a string cache handle, translating RTSTRCACHE_DEFAULT when found,
+ * and returns rc if not valid. */
+#define RTSTRCACHE_VALID_RETURN_RC(pStrCache, rc) \
+ do { \
+ if ((pStrCache) == RTSTRCACHE_DEFAULT) \
+ { \
+ int rcOnce = RTOnce(&g_rtStrCacheOnce, rtStrCacheInitDefault, NULL); \
+ if (RT_FAILURE(rcOnce)) \
+ return (rc); \
+ (pStrCache) = g_hrtStrCacheDefault; \
+ } \
+ else \
+ { \
+ AssertPtrReturn((pStrCache), (rc)); \
+ AssertReturn((pStrCache)->u32Magic == RTSTRCACHE_MAGIC, (rc)); \
+ } \
+ } while (0)
+
+
+
+/*********************************************************************************************************************************
+* Structures and Typedefs *
+*********************************************************************************************************************************/
+/**
+ * String cache entry.
+ */
+typedef struct RTSTRCACHEENTRY
+{
+ /** The number of references. */
+ uint32_t volatile cRefs;
+ /** The lower 16-bit hash value. */
+ uint16_t uHash;
+ /** The string length (excluding the terminator).
+ * If this is set to RTSTRCACHEENTRY_BIG_LEN, this is a BIG entry
+ * (RTSTRCACHEBIGENTRY). */
+ uint16_t cchString;
+ /** The string. */
+ char szString[8];
+} RTSTRCACHEENTRY;
+AssertCompileSize(RTSTRCACHEENTRY, 16);
+/** Pointer to a string cache entry. */
+typedef RTSTRCACHEENTRY *PRTSTRCACHEENTRY;
+/** Pointer to a const string cache entry. */
+typedef RTSTRCACHEENTRY *PCRTSTRCACHEENTRY;
+
+/** RTSTCACHEENTRY::cchString value for big cache entries. */
+#define RTSTRCACHEENTRY_BIG_LEN UINT16_MAX
+
+/**
+ * Big string cache entry.
+ *
+ * These are allocated individually from the application heap.
+ */
+typedef struct RTSTRCACHEBIGENTRY
+{
+ /** List entry. */
+ RTLISTNODE ListEntry;
+ /** The string length. */
+ uint32_t cchString;
+ /** The full hash value / padding. */
+ uint32_t uHash;
+ /** The core entry. */
+ RTSTRCACHEENTRY Core;
+} RTSTRCACHEBIGENTRY;
+AssertCompileSize(RTSTRCACHEENTRY, 16);
+/** Pointer to a big string cache entry. */
+typedef RTSTRCACHEBIGENTRY *PRTSTRCACHEBIGENTRY;
+/** Pointer to a const big string cache entry. */
+typedef RTSTRCACHEBIGENTRY *PCRTSTRCACHEBIGENTRY;
+
+
+/**
+ * A free string cache entry.
+ */
+typedef struct RTSTRCACHEFREE
+{
+ /** Zero value indicating that it's a free entry (no refs, no hash). */
+ uint32_t uZero;
+ /** Number of free bytes. Only used for > 32 byte allocations. */
+ uint32_t cbFree;
+ /** Pointer to the next free item. */
+ struct RTSTRCACHEFREE *pNext;
+} RTSTRCACHEFREE;
+AssertCompileSize(RTSTRCACHEENTRY, 16);
+AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, cRefs, RTSTRCACHEFREE, uZero);
+AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, szString, RTSTRCACHEFREE, pNext);
+/** Pointer to a free string cache entry. */
+typedef RTSTRCACHEFREE *PRTSTRCACHEFREE;
+
+#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+
+/**
+ * A free string cache entry with merging.
+ *
+ * This differs from RTSTRCACHEFREE only in having a back pointer for more
+ * efficient list management (doubly vs. singly linked lists).
+ */
+typedef struct RTSTRCACHEFREEMERGE
+{
+ /** Marker that indicates what kind of entry this is, either . */
+ uint32_t uMarker;
+ /** Number of free bytes. Only used for > 32 byte allocations. */
+ uint32_t cbFree;
+ /** Pointer to the main node. NULL for main nodes. */
+ struct RTSTRCACHEFREEMERGE *pMain;
+ /** The free list entry. */
+ RTLISTNODE ListEntry;
+ /** Pads the size up to the minimum allocation unit for the merge list.
+ * This both defines the minimum allocation unit and simplifies pointer
+ * manipulation during merging and splitting. */
+ uint8_t abPadding[ARCH_BITS == 32 ? 44 : 32];
+} RTSTRCACHEFREEMERGE;
+AssertCompileSize(RTSTRCACHEFREEMERGE, RT_BIT_32(RTSTRCACHE_MERGED_THRESHOLD_BIT));
+/** Pointer to a free cache string in the merge list. */
+typedef RTSTRCACHEFREEMERGE *PRTSTRCACHEFREEMERGE;
+
+/** RTSTRCACHEFREEMERGE::uMarker value indicating that it's the real free chunk
+ * header. Must be something that's invalid UTF-8 for both little and big
+ * endian system. */
+# define RTSTRCACHEFREEMERGE_MAIN UINT32_C(0xfffffff1)
+/** RTSTRCACHEFREEMERGE::uMarker value indicating that it's part of a larger
+ * chunk of free memory. Must be something that's invalid UTF-8 for both little
+ * and big endian system. */
+# define RTSTRCACHEFREEMERGE_PART UINT32_C(0xfffffff2)
+
+#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
+
+/**
+ * Tracking structure chunk of memory used by the 16 byte or 32 byte
+ * allocations.
+ *
+ * This occupies the first entry in the chunk.
+ */
+typedef struct RTSTRCACHECHUNK
+{
+ /** The size of the chunk. */
+ size_t cb;
+ /** Pointer to the next chunk. */
+ struct RTSTRCACHECHUNK *pNext;
+} RTSTRCACHECHUNK;
+AssertCompile(sizeof(RTSTRCACHECHUNK) <= sizeof(RTSTRCACHEENTRY));
+/** Pointer to the chunk tracking structure. */
+typedef RTSTRCACHECHUNK *PRTSTRCACHECHUNK;
+
+
+/**
+ * Cache instance data.
+ */
+typedef struct RTSTRCACHEINT
+{
+ /** The string cache magic (RTSTRCACHE_MAGIC). */
+ uint32_t u32Magic;
+ /** Ref counter for the cache handle. */
+ uint32_t volatile cRefs;
+ /** The number of strings currently entered in the cache. */
+ uint32_t cStrings;
+ /** The size of the hash table. */
+ uint32_t cHashTab;
+ /** Pointer to the hash table. */
+ PRTSTRCACHEENTRY *papHashTab;
+ /** Free list for allocations of the sizes defined by g_acbFixedLists. */
+ PRTSTRCACHEFREE apFreeLists[RTSTRCACHE_NUM_OF_FIXED_SIZES];
+#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+ /** Free lists based on */
+ RTLISTANCHOR aMergedFreeLists[RTSTRCACHE_HEAP_THRESHOLD_BIT - RTSTRCACHE_MERGED_THRESHOLD_BIT + 1];
+#endif
+ /** List of allocated memory chunks. */
+ PRTSTRCACHECHUNK pChunkList;
+ /** List of big cache entries. */
+ RTLISTANCHOR BigEntryList;
+
+ /** @name Statistics
+ * @{ */
+ /** The total size of all chunks. */
+ size_t cbChunks;
+ /** The total length of all the strings, terminators included. */
+ size_t cbStrings;
+ /** The total size of all the big entries. */
+ size_t cbBigEntries;
+ /** Hash collisions. */
+ uint32_t cHashCollisions;
+ /** Secondary hash collisions. */
+ uint32_t cHashCollisions2;
+ /** The number of inserts to compare cHashCollisions to. */
+ uint32_t cHashInserts;
+ /** The number of rehashes. */
+ uint32_t cRehashes;
+ /** @} */
+
+ /** Critical section protecting the cache structures. */
+ RTCRITSECT CritSect;
+} RTSTRCACHEINT;
+/** Pointer to a cache instance. */
+typedef RTSTRCACHEINT *PRTSTRCACHEINT;
+
+
+
+/*********************************************************************************************************************************
+* Global Variables *
+*********************************************************************************************************************************/
+/** The entry sizes of the fixed lists (RTSTRCACHEINT::apFreeLists). */
+static const uint32_t g_acbFixedLists[RTSTRCACHE_NUM_OF_FIXED_SIZES] =
+{
+ 16, 32, 48, 64, 96, 128, 192, 256, 320, 384, 448, 512
+};
+
+/** Init once for the default string cache. */
+static RTONCE g_rtStrCacheOnce = RTONCE_INITIALIZER;
+/** The default string cache. */
+static RTSTRCACHE g_hrtStrCacheDefault = NIL_RTSTRCACHE;
+
+
+/** @callback_method_impl{FNRTONCE, Initializes g_hrtStrCacheDefault} */
+static DECLCALLBACK(int) rtStrCacheInitDefault(void *pvUser)
+{
+ NOREF(pvUser);
+ return RTStrCacheCreate(&g_hrtStrCacheDefault, "Default");
+}
+
+
+RTDECL(int) RTStrCacheCreate(PRTSTRCACHE phStrCache, const char *pszName)
+{
+ int rc = VERR_NO_MEMORY;
+ PRTSTRCACHEINT pThis = (PRTSTRCACHEINT)RTMemAllocZ(sizeof(*pThis));
+ if (pThis)
+ {
+ pThis->cHashTab = RTSTRCACHE_INITIAL_HASH_SIZE;
+ pThis->papHashTab = (PRTSTRCACHEENTRY*)RTMemAllocZ(sizeof(pThis->papHashTab[0]) * pThis->cHashTab);
+ if (pThis->papHashTab)
+ {
+ rc = RTCritSectInit(&pThis->CritSect);
+ if (RT_SUCCESS(rc))
+ {
+ RTListInit(&pThis->BigEntryList);
+#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+ for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
+ RTListInit(&pThis->aMergedFreeLists[i]);
+#endif
+ pThis->cRefs = 1;
+ pThis->u32Magic = RTSTRCACHE_MAGIC;
+
+ *phStrCache = pThis;
+ return VINF_SUCCESS;
+ }
+ RTMemFree(pThis->papHashTab);
+ }
+ RTMemFree(pThis);
+ }
+
+ RT_NOREF_PV(pszName);
+ return rc;
+}
+RT_EXPORT_SYMBOL(RTStrCacheCreate);
+
+
+RTDECL(int) RTStrCacheDestroy(RTSTRCACHE hStrCache)
+{
+ if ( hStrCache == NIL_RTSTRCACHE
+ || hStrCache == RTSTRCACHE_DEFAULT)
+ return VINF_SUCCESS;
+
+ PRTSTRCACHEINT pThis = hStrCache;
+ RTSTRCACHE_VALID_RETURN_RC(pThis, VERR_INVALID_HANDLE);
+
+ /*
+ * Invalidate it. Enter the crit sect just to be on the safe side.
+ */
+ AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTSTRCACHE_MAGIC_DEAD, RTSTRCACHE_MAGIC), VERR_INVALID_HANDLE);
+ RTCritSectEnter(&pThis->CritSect);
+ Assert(pThis->cRefs == 1);
+
+ PRTSTRCACHECHUNK pChunk;
+ while ((pChunk = pThis->pChunkList) != NULL)
+ {
+ pThis->pChunkList = pChunk->pNext;
+ RTMemPageFree(pChunk, pChunk->cb);
+ }
+
+ RTMemFree(pThis->papHashTab);
+ pThis->papHashTab = NULL;
+ pThis->cHashTab = 0;
+
+ PRTSTRCACHEBIGENTRY pCur, pNext;
+ RTListForEachSafe(&pThis->BigEntryList, pCur, pNext, RTSTRCACHEBIGENTRY, ListEntry)
+ {
+ RTMemFree(pCur);
+ }
+
+ RTCritSectLeave(&pThis->CritSect);
+ RTCritSectDelete(&pThis->CritSect);
+
+ RTMemFree(pThis);
+ return VINF_SUCCESS;
+}
+RT_EXPORT_SYMBOL(RTStrCacheDestroy);
+
+
+/**
+ * Selects the fixed free list index for a given minimum entry size.
+ *
+ * @returns Free list index.
+ * @param cbMin Minimum entry size.
+ */
+DECLINLINE(uint32_t) rtStrCacheSelectFixedList(uint32_t cbMin)
+{
+ Assert(cbMin <= g_acbFixedLists[RT_ELEMENTS(g_acbFixedLists) - 1]);
+ unsigned i = 0;
+ while (cbMin > g_acbFixedLists[i])
+ i++;
+ return i;
+}
+
+
+#ifdef RT_STRICT
+# define RTSTRCACHE_CHECK(a_pThis) do { rtStrCacheCheck(pThis); } while (0)
+/**
+ * Internal cache check.
+ */
+static void rtStrCacheCheck(PRTSTRCACHEINT pThis)
+{
+# ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+ for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
+ {
+ PRTSTRCACHEFREEMERGE pFree;
+ RTListForEach(&pThis->aMergedFreeLists[i], pFree, RTSTRCACHEFREEMERGE, ListEntry)
+ {
+ Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
+ Assert(pFree->cbFree > 0);
+ Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
+ }
+ }
+# endif
+ RT_NOREF_PV(pThis);
+}
+#else
+# define RTSTRCACHE_CHECK(a_pThis) do { } while (0)
+#endif
+
+
+/**
+ * Finds the first empty hash table entry given a hash+length value.
+ *
+ * ASSUMES that the hash table isn't full.
+ *
+ * @returns Hash table index.
+ * @param pThis The string cache instance.
+ * @param uHashLen The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
+ */
+static uint32_t rtStrCacheFindEmptyHashTabEntry(PRTSTRCACHEINT pThis, uint32_t uHashLen)
+{
+ uint32_t iHash = uHashLen % pThis->cHashTab;
+ for (;;)
+ {
+ PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
+ if (pEntry == NULL || pEntry == PRTSTRCACHEENTRY_NIL)
+ return iHash;
+
+ /* Advance. */
+ iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
+ iHash %= pThis->cHashTab;
+ }
+}
+
+/**
+ * Grows the hash table.
+ *
+ * @returns vINF_SUCCESS or VERR_NO_MEMORY.
+ * @param pThis The string cache instance.
+ */
+static int rtStrCacheGrowHashTab(PRTSTRCACHEINT pThis)
+{
+ /*
+ * Allocate a new hash table two times the size of the old one.
+ */
+ uint32_t cNew = pThis->cHashTab * RTSTRCACHE_HASH_GROW_FACTOR;
+ PRTSTRCACHEENTRY *papNew = (PRTSTRCACHEENTRY *)RTMemAllocZ(sizeof(papNew[0]) * cNew);
+ if (papNew == NULL)
+ return VERR_NO_MEMORY;
+
+ /*
+ * Install the new table and move the items from the old table and into the new one.
+ */
+ PRTSTRCACHEENTRY *papOld = pThis->papHashTab;
+ uint32_t iOld = pThis->cHashTab;
+
+ pThis->papHashTab = papNew;
+ pThis->cHashTab = cNew;
+ pThis->cRehashes++;
+
+ while (iOld-- > 0)
+ {
+ PRTSTRCACHEENTRY pEntry = papOld[iOld];
+ if (pEntry != NULL && pEntry != PRTSTRCACHEENTRY_NIL)
+ {
+ uint32_t cchString = pEntry->cchString;
+ if (cchString == RTSTRCACHEENTRY_BIG_LEN)
+ cchString = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core)->cchString;
+
+ uint32_t iHash = rtStrCacheFindEmptyHashTabEntry(pThis, RT_MAKE_U32(pEntry->uHash, cchString));
+ pThis->papHashTab[iHash] = pEntry;
+ }
+ }
+
+ /*
+ * Free the old hash table.
+ */
+ RTMemFree(papOld);
+ return VINF_SUCCESS;
+}
+
+#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+
+/**
+ * Link/Relink into the free right list.
+ *
+ * @param pThis The string cache instance.
+ * @param pFree The free string entry.
+ */
+static void rtStrCacheRelinkMerged(PRTSTRCACHEINT pThis, PRTSTRCACHEFREEMERGE pFree)
+{
+ Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
+ Assert(pFree->cbFree > 0);
+ Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
+
+ if (!RTListIsEmpty(&pFree->ListEntry))
+ RTListNodeRemove(&pFree->ListEntry);
+
+ uint32_t iList = (ASMBitLastSetU32(pFree->cbFree) - 1) - RTSTRCACHE_MERGED_THRESHOLD_BIT;
+ if (iList >= RT_ELEMENTS(pThis->aMergedFreeLists))
+ iList = RT_ELEMENTS(pThis->aMergedFreeLists) - 1;
+
+ RTListPrepend(&pThis->aMergedFreeLists[iList], &pFree->ListEntry);
+}
+
+
+/**
+ * Allocate a cache entry from the merged free lists.
+ *
+ * @returns Pointer to the cache entry on success, NULL on allocation error.
+ * @param pThis The string cache instance.
+ * @param uHash The full hash of the string.
+ * @param pchString The string.
+ * @param cchString The string length.
+ * @param cbEntry The required entry size.
+ */
+static PRTSTRCACHEENTRY rtStrCacheAllocMergedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
+ const char *pchString, uint32_t cchString, uint32_t cbEntry)
+{
+ cbEntry = RT_ALIGN_32(cbEntry, sizeof(RTSTRCACHEFREEMERGE));
+ Assert(cbEntry > cchString);
+
+ /*
+ * Search the list heads first.
+ */
+ PRTSTRCACHEFREEMERGE pFree = NULL;
+
+ uint32_t iList = ASMBitLastSetU32(cbEntry) - 1;
+ if (!RT_IS_POWER_OF_TWO(cbEntry))
+ iList++;
+ iList -= RTSTRCACHE_MERGED_THRESHOLD_BIT;
+
+ while (iList < RT_ELEMENTS(pThis->aMergedFreeLists))
+ {
+ pFree = RTListGetFirst(&pThis->aMergedFreeLists[iList], RTSTRCACHEFREEMERGE, ListEntry);
+ if (pFree)
+ {
+ /*
+ * Found something. Should we we split it? We split from the end
+ * to avoid having to update all the sub entries.
+ */
+ Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
+ Assert(pFree->cbFree >= cbEntry);
+ Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
+
+ if (pFree->cbFree == cbEntry)
+ RTListNodeRemove(&pFree->ListEntry);
+ else
+ {
+ uint32_t cRemainder = (pFree->cbFree - cbEntry) / sizeof(*pFree);
+ PRTSTRCACHEFREEMERGE pRemainder = pFree;
+ pFree += cRemainder;
+
+ Assert((pRemainder->cbFree - cbEntry) == cRemainder * sizeof(*pFree));
+ pRemainder->cbFree = cRemainder * sizeof(*pFree);
+
+ rtStrCacheRelinkMerged(pThis, pRemainder);
+ }
+ break;
+ }
+ iList++;
+ }
+ if (!pFree)
+ {
+ /*
+ * Allocate a new block. (We could search the list below in some
+ * cases, but it's too much effort to write and execute).
+ */
+ size_t const cbChunk = RTSTRCACHE_MERGED_GROW_SIZE; AssertReturn(cbChunk > cbEntry * 2, NULL);
+ PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(cbChunk);
+ if (!pChunk)
+ return NULL;
+ pChunk->cb = cbChunk;
+ pChunk->pNext = pThis->pChunkList;
+ pThis->pChunkList = pChunk;
+ pThis->cbChunks += cbChunk;
+ AssertCompile(sizeof(*pChunk) <= sizeof(*pFree));
+
+ /*
+ * Get one node for the allocation at hand.
+ */
+ pFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pChunk + sizeof(*pFree));
+
+ /*
+ * Create a free block out of the remainder (always a reminder).
+ */
+ PRTSTRCACHEFREEMERGE pNewFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pFree + cbEntry);
+ pNewFree->uMarker = RTSTRCACHEFREEMERGE_MAIN;
+ pNewFree->cbFree = cbChunk - sizeof(*pNewFree) - cbEntry; Assert(pNewFree->cbFree < cbChunk && pNewFree->cbFree > 0);
+ pNewFree->pMain = NULL;
+ RTListInit(&pNewFree->ListEntry);
+
+ uint32_t iInternalBlock = pNewFree->cbFree / sizeof(*pNewFree);
+ while (iInternalBlock-- > 1)
+ {
+ pNewFree[iInternalBlock].uMarker = RTSTRCACHEFREEMERGE_PART;
+ pNewFree[iInternalBlock].cbFree = 0;
+ pNewFree[iInternalBlock].pMain = pNewFree;
+ }
+
+ rtStrCacheRelinkMerged(pThis, pNewFree);
+ }
+
+ /*
+ * Initialize the entry. We zero all bytes we don't use so they cannot
+ * accidentally be mistaken for a free entry.
+ */
+ ASMCompilerBarrier();
+ PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
+ pEntry->cRefs = 1;
+ pEntry->uHash = (uint16_t)uHash;
+ pEntry->cchString = (uint16_t)cchString;
+ memcpy(pEntry->szString, pchString, cchString);
+ RT_BZERO(&pEntry->szString[cchString], cbEntry - RT_UOFFSETOF(RTSTRCACHEENTRY, szString) - cchString);
+
+ RTSTRCACHE_CHECK(pThis);
+
+ return pEntry;
+}
+
+#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
+
+/**
+ * Allocate a cache entry from the heap.
+ *
+ * @returns Pointer to the cache entry on success, NULL on allocation error.
+ * @param pThis The string cache instance.
+ * @param uHash The full hash of the string.
+ * @param pchString The string.
+ * @param cchString The string length.
+ */
+static PRTSTRCACHEENTRY rtStrCacheAllocHeapEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
+ const char *pchString, uint32_t cchString)
+{
+ /*
+ * Allocate a heap block for storing the string. We do some size aligning
+ * here to encourage the heap to give us optimal alignment.
+ */
+ size_t cbEntry = RT_UOFFSETOF_DYN(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]);
+ PRTSTRCACHEBIGENTRY pBigEntry = (PRTSTRCACHEBIGENTRY)RTMemAlloc(RT_ALIGN_Z(cbEntry, RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN));
+ if (!pBigEntry)
+ return NULL;
+
+ /*
+ * Initialize the block.
+ */
+ RTListAppend(&pThis->BigEntryList, &pBigEntry->ListEntry);
+ pThis->cbBigEntries += cbEntry;
+ pBigEntry->cchString = cchString;
+ pBigEntry->uHash = uHash;
+ pBigEntry->Core.cRefs = 1;
+ pBigEntry->Core.uHash = (uint16_t)uHash;
+ pBigEntry->Core.cchString = RTSTRCACHEENTRY_BIG_LEN;
+ /* The following is to try avoid gcc warnings/errors regarding array bounds: */
+ char *pszDst = (char *)memcpy(pBigEntry->Core.szString, pchString, cchString);
+ pszDst[cchString] = '\0';
+ ASMCompilerBarrier();
+
+ return &pBigEntry->Core;
+}
+
+
+/**
+ * Allocate a cache entry from a fixed size free list.
+ *
+ * @returns Pointer to the cache entry on success, NULL on allocation error.
+ * @param pThis The string cache instance.
+ * @param uHash The full hash of the string.
+ * @param pchString The string.
+ * @param cchString The string length.
+ * @param iFreeList Which free list.
+ */
+static PRTSTRCACHEENTRY rtStrCacheAllocFixedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
+ const char *pchString, uint32_t cchString, uint32_t iFreeList)
+{
+ /*
+ * Get an entry from the free list. If empty, allocate another chunk of
+ * memory and split it up into free entries of the desired size.
+ */
+ PRTSTRCACHEFREE pFree = pThis->apFreeLists[iFreeList];
+ if (!pFree)
+ {
+ PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(RTSTRCACHE_FIXED_GROW_SIZE);
+ if (!pChunk)
+ return NULL;
+ pChunk->cb = RTSTRCACHE_FIXED_GROW_SIZE;
+ pChunk->pNext = pThis->pChunkList;
+ pThis->pChunkList = pChunk;
+ pThis->cbChunks += RTSTRCACHE_FIXED_GROW_SIZE;
+
+ PRTSTRCACHEFREE pPrev = NULL;
+ uint32_t const cbEntry = g_acbFixedLists[iFreeList];
+ uint32_t cLeft = RTSTRCACHE_FIXED_GROW_SIZE / cbEntry - 1;
+ pFree = (PRTSTRCACHEFREE)((uintptr_t)pChunk + cbEntry);
+
+ Assert(sizeof(*pChunk) <= cbEntry);
+ Assert(sizeof(*pFree) <= cbEntry);
+ Assert(cbEntry < RTSTRCACHE_FIXED_GROW_SIZE / 16);
+
+ while (cLeft-- > 0)
+ {
+ pFree->uZero = 0;
+ pFree->cbFree = cbEntry;
+ pFree->pNext = pPrev;
+ pPrev = pFree;
+ pFree = (PRTSTRCACHEFREE)((uintptr_t)pFree + cbEntry);
+ }
+
+ Assert(pPrev);
+ pThis->apFreeLists[iFreeList] = pFree = pPrev;
+ }
+
+ /*
+ * Unlink it.
+ */
+ pThis->apFreeLists[iFreeList] = pFree->pNext;
+ ASMCompilerBarrier();
+
+ /*
+ * Initialize the entry.
+ */
+ PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
+ pEntry->cRefs = 1;
+ pEntry->uHash = (uint16_t)uHash;
+ pEntry->cchString = (uint16_t)cchString;
+ memcpy(pEntry->szString, pchString, cchString);
+ pEntry->szString[cchString] = '\0';
+
+ return pEntry;
+}
+
+
+/**
+ * Looks up a string in the hash table.
+ *
+ * @returns Pointer to the string cache entry, NULL + piFreeHashTabEntry if not
+ * found.
+ * @param pThis The string cache instance.
+ * @param uHashLen The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
+ * @param cchString The real length.
+ * @param pchString The string.
+ * @param piFreeHashTabEntry Where to store the index insertion index if NULL
+ * is returned (same as what
+ * rtStrCacheFindEmptyHashTabEntry would return).
+ * @param pcCollisions Where to return a collision counter.
+ */
+static PRTSTRCACHEENTRY rtStrCacheLookUp(PRTSTRCACHEINT pThis, uint32_t uHashLen, uint32_t cchString, const char *pchString,
+ uint32_t *piFreeHashTabEntry, uint32_t *pcCollisions)
+{
+ *piFreeHashTabEntry = UINT32_MAX;
+ *pcCollisions = 0;
+
+ uint16_t cchStringFirst = RT_UOFFSETOF_DYN(RTSTRCACHEENTRY, szString[cchString + 1]) < RTSTRCACHE_HEAP_THRESHOLD
+ ? (uint16_t)cchString : RTSTRCACHEENTRY_BIG_LEN;
+ uint32_t iHash = uHashLen % pThis->cHashTab;
+ for (;;)
+ {
+ PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
+
+ /* Give up if NULL, but record the index for insertion. */
+ if (pEntry == NULL)
+ {
+ if (*piFreeHashTabEntry == UINT32_MAX)
+ *piFreeHashTabEntry = iHash;
+ return NULL;
+ }
+
+ if (pEntry != PRTSTRCACHEENTRY_NIL)
+ {
+ /* Compare. */
+ if ( pEntry->uHash == (uint16_t)uHashLen
+ && pEntry->cchString == cchStringFirst)
+ {
+ if (pEntry->cchString != RTSTRCACHEENTRY_BIG_LEN)
+ {
+ if ( !memcmp(pEntry->szString, pchString, cchString)
+ && pEntry->szString[cchString] == '\0')
+ return pEntry;
+ }
+ else
+ {
+ PRTSTRCACHEBIGENTRY pBigEntry = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core);
+ if ( pBigEntry->cchString == cchString
+ && !memcmp(pBigEntry->Core.szString, pchString, cchString))
+ return &pBigEntry->Core;
+ }
+ }
+
+ if (*piFreeHashTabEntry == UINT32_MAX)
+ *pcCollisions += 1;
+ }
+ /* Record the first NIL index for insertion in case we don't get a hit. */
+ else if (*piFreeHashTabEntry == UINT32_MAX)
+ *piFreeHashTabEntry = iHash;
+
+ /* Advance. */
+ iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
+ iHash %= pThis->cHashTab;
+ }
+}
+
+
+RTDECL(const char *) RTStrCacheEnterN(RTSTRCACHE hStrCache, const char *pchString, size_t cchString)
+{
+ PRTSTRCACHEINT pThis = hStrCache;
+ RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
+
+
+ /*
+ * Calculate the hash and figure the exact string length, then look for an existing entry.
+ */
+ uint32_t const uHash = sdbmN(pchString, cchString, &cchString);
+ uint32_t const uHashLen = RT_MAKE_U32(uHash, cchString);
+ AssertReturn(cchString < _1G, NULL);
+ uint32_t const cchString32 = (uint32_t)cchString;
+
+ RTCritSectEnter(&pThis->CritSect);
+ RTSTRCACHE_CHECK(pThis);
+
+ uint32_t cCollisions;
+ uint32_t iFreeHashTabEntry;
+ PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString32, pchString, &iFreeHashTabEntry, &cCollisions);
+ if (pEntry)
+ {
+ uint32_t cRefs = ASMAtomicIncU32(&pEntry->cRefs);
+ Assert(cRefs < UINT32_MAX / 2); NOREF(cRefs);
+ }
+ else
+ {
+ /*
+ * Allocate a new entry.
+ */
+ uint32_t cbEntry = cchString32 + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
+ if (cbEntry >= RTSTRCACHE_HEAP_THRESHOLD)
+ pEntry = rtStrCacheAllocHeapEntry(pThis, uHash, pchString, cchString32);
+#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+ else if (cbEntry >= RTSTRCACHE_MERGED_THRESHOLD_BIT)
+ pEntry = rtStrCacheAllocMergedEntry(pThis, uHash, pchString, cchString32, cbEntry);
+#endif
+ else
+ pEntry = rtStrCacheAllocFixedEntry(pThis, uHash, pchString, cchString32,
+ rtStrCacheSelectFixedList(cbEntry));
+ if (!pEntry)
+ {
+ RTSTRCACHE_CHECK(pThis);
+ RTCritSectLeave(&pThis->CritSect);
+ return NULL;
+ }
+
+ /*
+ * Insert it into the hash table.
+ */
+ if (pThis->cHashTab - pThis->cStrings < pThis->cHashTab / 2)
+ {
+ int rc = rtStrCacheGrowHashTab(pThis);
+ if (RT_SUCCESS(rc))
+ iFreeHashTabEntry = rtStrCacheFindEmptyHashTabEntry(pThis, uHashLen);
+ else if (pThis->cHashTab - pThis->cStrings <= pThis->cHashTab / 8) /* 12.5% full => error */
+ {
+ pThis->papHashTab[iFreeHashTabEntry] = pEntry;
+ pThis->cStrings++;
+ pThis->cHashInserts++;
+ pThis->cHashCollisions += cCollisions > 0;
+ pThis->cHashCollisions2 += cCollisions > 1;
+ pThis->cbStrings += cchString32 + 1;
+ RTStrCacheRelease(hStrCache, pEntry->szString);
+
+ RTSTRCACHE_CHECK(pThis);
+ RTCritSectLeave(&pThis->CritSect);
+ return NULL;
+ }
+ }
+
+ pThis->papHashTab[iFreeHashTabEntry] = pEntry;
+ pThis->cStrings++;
+ pThis->cHashInserts++;
+ pThis->cHashCollisions += cCollisions > 0;
+ pThis->cHashCollisions2 += cCollisions > 1;
+ pThis->cbStrings += cchString32 + 1;
+ Assert(pThis->cStrings < pThis->cHashTab && pThis->cStrings > 0);
+ }
+
+ RTSTRCACHE_CHECK(pThis);
+ RTCritSectLeave(&pThis->CritSect);
+ return pEntry->szString;
+}
+RT_EXPORT_SYMBOL(RTStrCacheEnterN);
+
+
+RTDECL(const char *) RTStrCacheEnter(RTSTRCACHE hStrCache, const char *psz)
+{
+ return RTStrCacheEnterN(hStrCache, psz, strlen(psz));
+}
+RT_EXPORT_SYMBOL(RTStrCacheEnter);
+
+
+static const char *rtStrCacheEnterLowerWorker(PRTSTRCACHEINT pThis, const char *pchString, size_t cchString)
+{
+ /*
+ * Try use a dynamic heap buffer first.
+ */
+ if (cchString < 512)
+ {
+ char *pszStackBuf = (char *)alloca(cchString + 1);
+ if (pszStackBuf)
+ {
+ memcpy(pszStackBuf, pchString, cchString);
+ pszStackBuf[cchString] = '\0';
+ RTStrToLower(pszStackBuf);
+ return RTStrCacheEnterN(pThis, pszStackBuf, cchString);
+ }
+ }
+
+ /*
+ * Fall back on heap.
+ */
+ char *pszHeapBuf = (char *)RTMemTmpAlloc(cchString + 1);
+ if (!pszHeapBuf)
+ return NULL;
+ memcpy(pszHeapBuf, pchString, cchString);
+ pszHeapBuf[cchString] = '\0';
+ RTStrToLower(pszHeapBuf);
+ const char *pszRet = RTStrCacheEnterN(pThis, pszHeapBuf, cchString);
+ RTMemTmpFree(pszHeapBuf);
+ return pszRet;
+}
+
+RTDECL(const char *) RTStrCacheEnterLowerN(RTSTRCACHE hStrCache, const char *pchString, size_t cchString)
+{
+ PRTSTRCACHEINT pThis = hStrCache;
+ RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
+ return rtStrCacheEnterLowerWorker(pThis, pchString, RTStrNLen(pchString, cchString));
+}
+RT_EXPORT_SYMBOL(RTStrCacheEnterLowerN);
+
+
+RTDECL(const char *) RTStrCacheEnterLower(RTSTRCACHE hStrCache, const char *psz)
+{
+ PRTSTRCACHEINT pThis = hStrCache;
+ RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
+ return rtStrCacheEnterLowerWorker(pThis, psz, strlen(psz));
+}
+RT_EXPORT_SYMBOL(RTStrCacheEnterLower);
+
+
+RTDECL(uint32_t) RTStrCacheRetain(const char *psz)
+{
+ AssertPtr(psz);
+
+ PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
+ Assert(!((uintptr_t)pStr & 15) || pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
+
+ uint32_t cRefs = ASMAtomicIncU32(&pStr->cRefs);
+ Assert(cRefs > 1);
+ Assert(cRefs < UINT32_MAX / 2);
+
+ return cRefs;
+}
+RT_EXPORT_SYMBOL(RTStrCacheRetain);
+
+
+static uint32_t rtStrCacheFreeEntry(PRTSTRCACHEINT pThis, PRTSTRCACHEENTRY pStr)
+{
+ RTCritSectEnter(&pThis->CritSect);
+ RTSTRCACHE_CHECK(pThis);
+
+ /* Remove it from the hash table. */
+ uint32_t cchString = pStr->cchString == RTSTRCACHEENTRY_BIG_LEN
+ ? RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core)->cchString
+ : pStr->cchString;
+ uint32_t uHashLen = RT_MAKE_U32(pStr->uHash, cchString);
+ uint32_t iHash = uHashLen % pThis->cHashTab;
+ if (pThis->papHashTab[iHash] == pStr)
+ pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
+ else
+ {
+ do
+ {
+ AssertBreak(pThis->papHashTab[iHash] != NULL);
+ iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
+ iHash %= pThis->cHashTab;
+ } while (pThis->papHashTab[iHash] != pStr);
+ if (RT_LIKELY(pThis->papHashTab[iHash] == pStr))
+ pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
+ else
+ {
+ AssertFailed();
+ iHash = pThis->cHashTab;
+ while (iHash-- > 0)
+ if (pThis->papHashTab[iHash] == pStr)
+ break;
+ AssertMsgFailed(("iHash=%u cHashTab=%u\n", iHash, pThis->cHashTab));
+ }
+ }
+
+ pThis->cStrings--;
+ pThis->cbStrings -= cchString;
+ Assert(pThis->cStrings < pThis->cHashTab);
+
+ /* Free it. */
+ if (pStr->cchString != RTSTRCACHEENTRY_BIG_LEN)
+ {
+ uint32_t const cbMin = pStr->cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
+#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+ if (cbMin <= RTSTRCACHE_MAX_FIXED)
+#endif
+ {
+ /*
+ * No merging, just add it to the list.
+ */
+ uint32_t const iFreeList = rtStrCacheSelectFixedList(cbMin);
+ ASMCompilerBarrier();
+ PRTSTRCACHEFREE pFreeStr = (PRTSTRCACHEFREE)pStr;
+ pFreeStr->cbFree = cbMin;
+ pFreeStr->uZero = 0;
+ pFreeStr->pNext = pThis->apFreeLists[iFreeList];
+ pThis->apFreeLists[iFreeList] = pFreeStr;
+ }
+#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
+ else
+ {
+ /*
+ * Complicated mode, we merge with adjecent nodes.
+ */
+ ASMCompilerBarrier();
+ PRTSTRCACHEFREEMERGE pFreeStr = (PRTSTRCACHEFREEMERGE)pStr;
+ pFreeStr->cbFree = RT_ALIGN_32(cbMin, sizeof(*pFreeStr));
+ pFreeStr->uMarker = RTSTRCACHEFREEMERGE_MAIN;
+ pFreeStr->pMain = NULL;
+ RTListInit(&pFreeStr->ListEntry);
+
+ /*
+ * Merge with previous?
+ * (Reading one block back is safe because there is always the
+ * RTSTRCACHECHUNK structure at the head of each memory chunk.)
+ */
+ uint32_t cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
+ PRTSTRCACHEFREEMERGE pMain = pFreeStr - 1;
+ if ( pMain->uMarker == RTSTRCACHEFREEMERGE_MAIN
+ || pMain->uMarker == RTSTRCACHEFREEMERGE_PART)
+ {
+ while (pMain->uMarker != RTSTRCACHEFREEMERGE_MAIN)
+ pMain--;
+ pMain->cbFree += pFreeStr->cbFree;
+ }
+ else
+ {
+ pMain = pFreeStr;
+ pFreeStr++;
+ cInternalBlocks--;
+ }
+
+ /*
+ * Mark internal blocks in the string we're freeing.
+ */
+ while (cInternalBlocks-- > 0)
+ {
+ pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
+ pFreeStr->cbFree = 0;
+ pFreeStr->pMain = pMain;
+ RTListInit(&pFreeStr->ListEntry);
+ pFreeStr++;
+ }
+
+ /*
+ * Merge with next? Limitation: We won't try cross page boundraries.
+ * (pFreeStr points to the next first free enter after the string now.)
+ */
+ if ( PAGE_ADDRESS(pFreeStr) == PAGE_ADDRESS(&pFreeStr[-1])
+ && pFreeStr->uMarker == RTSTRCACHEFREEMERGE_MAIN)
+ {
+ pMain->cbFree += pFreeStr->cbFree;
+ cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
+ Assert(cInternalBlocks > 0);
+
+ /* Update the main block we merge with. */
+ pFreeStr->cbFree = 0;
+ pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
+ RTListNodeRemove(&pFreeStr->ListEntry);
+ RTListInit(&pFreeStr->ListEntry);
+
+ /* Change the internal blocks we merged in. */
+ cInternalBlocks--;
+ while (cInternalBlocks-- > 0)
+ {
+ pFreeStr++;
+ pFreeStr->pMain = pMain;
+ Assert(pFreeStr->uMarker == RTSTRCACHEFREEMERGE_PART);
+ Assert(!pFreeStr->cbFree);
+ }
+ }
+
+ /*
+ * Add/relink into the appropriate free list.
+ */
+ rtStrCacheRelinkMerged(pThis, pMain);
+ }
+#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
+ RTSTRCACHE_CHECK(pThis);
+ RTCritSectLeave(&pThis->CritSect);
+ }
+ else
+ {
+ /* Big string. */
+ PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core);
+ RTListNodeRemove(&pBigStr->ListEntry);
+ pThis->cbBigEntries -= RT_ALIGN_32(RT_UOFFSETOF_DYN(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]),
+ RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN);
+
+ RTSTRCACHE_CHECK(pThis);
+ RTCritSectLeave(&pThis->CritSect);
+
+ RTMemFree(pBigStr);
+ }
+
+ return 0;
+}
+
+RTDECL(uint32_t) RTStrCacheRelease(RTSTRCACHE hStrCache, const char *psz)
+{
+ if (!psz)
+ return 0;
+
+ PRTSTRCACHEINT pThis = hStrCache;
+ RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
+
+ AssertPtr(psz);
+ PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
+ Assert(!((uintptr_t)pStr & 15) || pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
+
+ /*
+ * Drop a reference and maybe free the entry.
+ */
+ uint32_t cRefs = ASMAtomicDecU32(&pStr->cRefs);
+ Assert(cRefs < UINT32_MAX / 2);
+ if (!cRefs)
+ return rtStrCacheFreeEntry(pThis, pStr);
+
+ return cRefs;
+}
+RT_EXPORT_SYMBOL(RTStrCacheRelease);
+
+
+RTDECL(size_t) RTStrCacheLength(const char *psz)
+{
+ if (!psz)
+ return 0;
+
+ AssertPtr(psz);
+ PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
+ if (pStr->cchString == RTSTRCACHEENTRY_BIG_LEN)
+ {
+ PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(psz, RTSTRCACHEBIGENTRY, Core.szString);
+ return pBigStr->cchString;
+ }
+ Assert(!((uintptr_t)pStr & 15));
+ return pStr->cchString;
+}
+RT_EXPORT_SYMBOL(RTStrCacheLength);
+
+
+RTDECL(bool) RTStrCacheIsRealImpl(void)
+{
+ return true;
+}
+RT_EXPORT_SYMBOL(RTStrCacheIsRealImpl);
+
+
+RTDECL(uint32_t) RTStrCacheGetStats(RTSTRCACHE hStrCache, size_t *pcbStrings, size_t *pcbChunks, size_t *pcbBigEntries,
+ uint32_t *pcHashCollisions, uint32_t *pcHashCollisions2, uint32_t *pcHashInserts,
+ uint32_t *pcRehashes)
+{
+ PRTSTRCACHEINT pThis = hStrCache;
+ RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
+
+ RTCritSectEnter(&pThis->CritSect);
+
+ if (pcbStrings)
+ *pcbStrings = pThis->cbStrings;
+ if (pcbChunks)
+ *pcbChunks = pThis->cbChunks;
+ if (pcbBigEntries)
+ *pcbBigEntries = pThis->cbBigEntries;
+ if (pcHashCollisions)
+ *pcHashCollisions = pThis->cHashCollisions;
+ if (pcHashCollisions2)
+ *pcHashCollisions2 = pThis->cHashCollisions2;
+ if (pcHashInserts)
+ *pcHashInserts = pThis->cHashInserts;
+ if (pcRehashes)
+ *pcRehashes = pThis->cRehashes;
+ uint32_t cStrings = pThis->cStrings;
+
+ RTCritSectLeave(&pThis->CritSect);
+ return cStrings;
+}
+RT_EXPORT_SYMBOL(RTStrCacheRelease);
+