Attachment #69752 for issue #78496

View | Details | Raw Unified | Return to issue 78496
Collapse All | Expand All




 ************************************************************************/

// MARKER(update_precomp.py): autogen include statement, do not remove
#if 0
#include "precompiled_sal.hxx"
#include "rtl/allocator.hxx"
#endif

#include "hash.h"
#include "strimp.h"
#include <osl/diagnose.h>

#if 0

#include <hash_set>


    getHashTable()->erase(pString);
}

#endif

// --------------------------- start here ---------------------------

struct StringHashTableImpl {
    sal_uInt32    nEntries;
    sal_uInt32    nSize;
    rtl_uString **pData;
};

typedef StringHashTableImpl StringHashTable;

extern "C" {

// Only for use in the implementation
StringHashTable *rtl_str_hash_new (sal_uInt32 nSize);
void rtl_str_hash_free (StringHashTable *pHash);

}

StringHashTable *
getHashTable ()
{
    static StringHashTable *pInternPool = NULL;
    if (pInternPool == NULL) {
        static StringHashTable* pHash = rtl_str_hash_new(1024);
        pInternPool = pHash;
    }
    return pInternPool;
}

extern "C" {

// Better / smaller / faster hash set ....

// TODO: add bottom bit-set list terminator to string list

static sal_uInt32
getNextSize (sal_uInt32 nSize)
{
    // Sedgewick - Algorithms in C P577.
    static const sal_uInt32 nPrimes[] = { 1021, 2039, 4093, 8191, 16381, 32749,
                                          65521, 131071,262139, 524287, 1048573,
                                          2097143, 4194301, 8388593, 16777213,
                                          33554393, 67108859, 134217689 };
    #define NUM_PRIMES (sizeof (nPrimes)/ sizeof (nPrimes[0]))
    for (sal_uInt32 i = 0; i < NUM_PRIMES; i++)
    {
        if (nPrimes[i] > nSize)
            return nPrimes[i];
    }
    return nSize * 2;
}

static sal_uInt32
hashString (rtl_uString *pString)
{
    return (sal_uInt32) rtl_ustr_hashCode_WithLength (pString->buffer,
                                                      pString->length);
}

StringHashTable *
rtl_str_hash_new (sal_uInt32 nSize)
{
    StringHashTable *pHash = (StringHashTable *)malloc (sizeof (StringHashTable));

    pHash->nEntries = 0;
    pHash->nSize = getNextSize (nSize);
    pHash->pData = (rtl_uString **) calloc (sizeof (rtl_uString *), pHash->nSize);

    return pHash;
}

void
rtl_str_hash_free (StringHashTable *pHash)
{
    if (!pHash)
        return;
    if (pHash->pData)
        free (pHash->pData);
    free (pHash);
}

static void
rtl_str_hash_insert_nonequal (StringHashTable   *pHash,
                              rtl_uString       *pString)
{
    sal_uInt32  nHash = hashString (pString);
    sal_uInt32  n;
    rtl_uString *pHashStr;

    n = nHash % pHash->nSize;
    while ((pHashStr = pHash->pData[n]) != NULL) {
        n++;
        if (n >= pHash->nSize)
            n = 0;
    }
    pHash->pData[n] = pString;
}

static void
rtl_str_hash_resize (sal_uInt32        nNewSize)
{
    sal_uInt32 i;
    StringHashTable *pNewHash;
    StringHashTable *pHash = getHashTable();

    OSL_ASSERT (nNewSize > pHash->nEntries);

    pNewHash = rtl_str_hash_new (nNewSize);

    for (i = 0; i < pHash->nSize; i++)
    {
        if (pHash->pData[i] != NULL)
            rtl_str_hash_insert_nonequal (pNewHash, pHash->pData[i]);
    }
    pNewHash->nEntries = pHash->nEntries;
    free (pHash->pData);
    *pHash = *pNewHash;
    pNewHash->pData = NULL;
    rtl_str_hash_free (pNewHash);
}

static int
compareEqual (rtl_uString *pStringA, rtl_uString *pStringB)
{
    if (pStringA == pStringB)
        return 1;
    if (pStringA->length != pStringB->length)
        return 0;
    return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
                                         pStringB->buffer, pStringB->length);
}


rtl_uString *
rtl_str_hash_intern (rtl_uString       *pString,
                     int                can_return)
{
    sal_uInt32  nHash = hashString (pString);
    sal_uInt32  n;
    rtl_uString *pHashStr;
    
    StringHashTable *pHash = getHashTable();

    // Should we resize ?
    if (pHash->nEntries >= pHash->nSize/2)
        rtl_str_hash_resize (getNextSize(pHash->nSize));

    n = nHash % pHash->nSize;
    while ((pHashStr = pHash->pData[n]) != NULL) {
        if (compareEqual (pHashStr, pString))
        {
            rtl_uString_acquire (pHashStr);
            return pHashStr;
        }
        n++;
        if (n >= pHash->nSize)
            n = 0;
    }

    if (!can_return)
    {
        rtl_uString *pCopy = NULL;
        rtl_uString_newFromString( &pCopy, pString );
        pString = pCopy;
        if (!pString)
            return NULL;
    }

    if (!SAL_STRING_IS_STATIC (pString))
        pString->refCount |= SAL_STRING_INTERN_FLAG;
    pHash->pData[n] = pString;
    pHash->nEntries++;

    return pString;
}

void
rtl_str_hash_remove (rtl_uString       *pString)
{
    sal_uInt32   n;
    sal_uInt32   nHash = hashString (pString);
    rtl_uString *pHashStr;

    StringHashTable *pHash = getHashTable();

    n = nHash % pHash->nSize;
    while ((pHashStr = pHash->pData[n]) != NULL) {
        if (compareEqual (pHashStr, pString))
            break;
        n++;
        if (n >= pHash->nSize)
            n = 0;
    }
    OSL_ASSERT (pHash->pData[n] != 0);
    if (pHash->pData[n] == NULL)
        return;

    pHash->pData[n++] = NULL;
    pHash->nEntries--;

    if (n >= pHash->nSize)
        n = 0;

    while ((pHashStr = pHash->pData[n]) != NULL) {
        pHash->pData[n] = NULL;
        // FIXME: rather unsophisticated and N^2 in chain-length, but robust.
        rtl_str_hash_insert_nonequal (pHash, pHashStr);
        n++;
        if (n >= pHash->nSize)
            n = 0;
    }
    // FIXME: Should we down-size ?
}


}

Return to issue 78496

Lines 26-37 Link Here

(-)sal/rtl/source/hash.cxx (+221 lines)
26	************************************************************************/	26	************************************************************************/
27		27
28	// MARKER(update_precomp.py): autogen include statement, do not remove	28	// MARKER(update_precomp.py): autogen include statement, do not remove
		29	#if 0
29	#include "precompiled_sal.hxx"	30	#include "precompiled_sal.hxx"
30	#include "rtl/allocator.hxx"	31	#include "rtl/allocator.hxx"
		32	#endif
31		33
32	#include "hash.h"	34	#include "hash.h"
33	#include "strimp.h"	35	#include "strimp.h"
		36	#include <osl/diagnose.h>
34		37
		38	#if 0
35		39
36	#include <hash_set>	40	#include <hash_set>
37		41
Lines 110-113 rtl_str_hash_remove (rtl_uString *pString) Link Here
110	getHashTable()->erase(pString);	114	getHashTable()->erase(pString);
111	}	115	}
112		116
		117	#endif
		118
		119	// --------------------------- start here ---------------------------
		120
		121	struct StringHashTableImpl {
		122	sal_uInt32 nEntries;
		123	sal_uInt32 nSize;
		124	rtl_uString **pData;
		125	};
		126
		127	typedef StringHashTableImpl StringHashTable;
		128
		129	extern "C" {
		130
		131	// Only for use in the implementation
		132	StringHashTable *rtl_str_hash_new (sal_uInt32 nSize);
		133	void rtl_str_hash_free (StringHashTable *pHash);
		134
		135	}
		136
		137	StringHashTable *
		138	getHashTable ()
		139	{
		140	static StringHashTable *pInternPool = NULL;
		141	if (pInternPool == NULL) {
		142	static StringHashTable* pHash = rtl_str_hash_new(1024);
		143	pInternPool = pHash;
		144	}
		145	return pInternPool;
		146	}
		147
		148	extern "C" {
		149
		150	// Better / smaller / faster hash set ....
		151
		152	// TODO: add bottom bit-set list terminator to string list
		153
		154	static sal_uInt32
		155	getNextSize (sal_uInt32 nSize)
		156	{
		157	// Sedgewick - Algorithms in C P577.
		158	static const sal_uInt32 nPrimes[] = { 1021, 2039, 4093, 8191, 16381, 32749,
		159	65521, 131071,262139, 524287, 1048573,
		160	2097143, 4194301, 8388593, 16777213,
		161	33554393, 67108859, 134217689 };
		162	#define NUM_PRIMES (sizeof (nPrimes)/ sizeof (nPrimes[0]))
		163	for (sal_uInt32 i = 0; i < NUM_PRIMES; i++)
		164	{
		165	if (nPrimes[i] > nSize)
		166	return nPrimes[i];
		167	}
		168	return nSize * 2;
		169	}
		170
		171	static sal_uInt32
		172	hashString (rtl_uString *pString)
		173	{
		174	return (sal_uInt32) rtl_ustr_hashCode_WithLength (pString->buffer,
		175	pString->length);
		176	}
		177
		178	StringHashTable *
		179	rtl_str_hash_new (sal_uInt32 nSize)
		180	{
181	StringHashTable pHash = (StringHashTable )malloc (sizeof (StringHashTable));
182
183	pHash->nEntries = 0;
184	pHash->nSize = getNextSize (nSize);
185	pHash->pData = (rtl_uString *) calloc (sizeof (rtl_uString ), pHash->nSize);
186
187	return pHash;
188	}
189
190	void
191	rtl_str_hash_free (StringHashTable *pHash)
192	{
193	if (!pHash)
194	return;
195	if (pHash->pData)
196	free (pHash->pData);
197	free (pHash);
198	}
199
200	static void
201	rtl_str_hash_insert_nonequal (StringHashTable *pHash,
202	rtl_uString *pString)
203	{
204	sal_uInt32 nHash = hashString (pString);
205	sal_uInt32 n;
206	rtl_uString *pHashStr;
207
208	n = nHash % pHash->nSize;
209	while ((pHashStr = pHash->pData[n]) != NULL) {
210	n++;
211	if (n >= pHash->nSize)
212	n = 0;
213	}
214	pHash->pData[n] = pString;
215	}
216
217	static void
218	rtl_str_hash_resize (sal_uInt32 nNewSize)
219	{
220	sal_uInt32 i;
221	StringHashTable *pNewHash;
222	StringHashTable *pHash = getHashTable();
223
224	OSL_ASSERT (nNewSize > pHash->nEntries);
225
226	pNewHash = rtl_str_hash_new (nNewSize);
227
228	for (i = 0; i < pHash->nSize; i++)
229	{
230	if (pHash->pData[i] != NULL)
231	rtl_str_hash_insert_nonequal (pNewHash, pHash->pData[i]);
232	}
233	pNewHash->nEntries = pHash->nEntries;
234	free (pHash->pData);
235	pHash = pNewHash;
236	pNewHash->pData = NULL;
237	rtl_str_hash_free (pNewHash);
238	}
239
240	static int
241	compareEqual (rtl_uString pStringA, rtl_uString pStringB)
242	{
243	if (pStringA == pStringB)
244	return 1;
245	if (pStringA->length != pStringB->length)
246	return 0;
247	return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
248	pStringB->buffer, pStringB->length);
249	}
250
251
252	rtl_uString *
253	rtl_str_hash_intern (rtl_uString *pString,
254	int can_return)
255	{
256	sal_uInt32 nHash = hashString (pString);
257	sal_uInt32 n;
258	rtl_uString *pHashStr;
259
260	StringHashTable *pHash = getHashTable();
261
262	// Should we resize ?
263	if (pHash->nEntries >= pHash->nSize/2)
264	rtl_str_hash_resize (getNextSize(pHash->nSize));
265
266	n = nHash % pHash->nSize;
267	while ((pHashStr = pHash->pData[n]) != NULL) {
268	if (compareEqual (pHashStr, pString))
269	{
270	rtl_uString_acquire (pHashStr);
271	return pHashStr;
272	}
273	n++;
274	if (n >= pHash->nSize)
275	n = 0;
276	}
277
278	if (!can_return)
279	{
280	rtl_uString *pCopy = NULL;
281	rtl_uString_newFromString( &pCopy, pString );
282	pString = pCopy;
283	if (!pString)
284	return NULL;
285	}
286
287	if (!SAL_STRING_IS_STATIC (pString))
288	pString->refCount \|= SAL_STRING_INTERN_FLAG;
289	pHash->pData[n] = pString;
290	pHash->nEntries++;
291
292	return pString;
293	}
294
295	void
296	rtl_str_hash_remove (rtl_uString *pString)
297	{
298	sal_uInt32 n;
299	sal_uInt32 nHash = hashString (pString);
300	rtl_uString *pHashStr;
301
302	StringHashTable *pHash = getHashTable();
303
304	n = nHash % pHash->nSize;
305	while ((pHashStr = pHash->pData[n]) != NULL) {
306	if (compareEqual (pHashStr, pString))
307	break;
308	n++;
309	if (n >= pHash->nSize)
310	n = 0;
311	}
312	OSL_ASSERT (pHash->pData[n] != 0);
313	if (pHash->pData[n] == NULL)
314	return;
315
316	pHash->pData[n++] = NULL;
317	pHash->nEntries--;
318
319	if (n >= pHash->nSize)
320	n = 0;
321
322	while ((pHashStr = pHash->pData[n]) != NULL) {
323	pHash->pData[n] = NULL;
324	// FIXME: rather unsophisticated and N^2 in chain-length, but robust.
325	rtl_str_hash_insert_nonequal (pHash, pHashStr);
326	n++;
327	if (n >= pHash->nSize)
328	n = 0;
329	}
330	// FIXME: Should we down-size ?
331	}
332
333
113	}	334	}