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