Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : : /*************************************************************************
3 : : *
4 : : * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 : : *
6 : : * Copyright 2000, 2010 Oracle and/or its affiliates.
7 : : *
8 : : * OpenOffice.org - a multi-platform office productivity suite
9 : : *
10 : : * This file is part of OpenOffice.org.
11 : : *
12 : : * OpenOffice.org is free software: you can redistribute it and/or modify
13 : : * it under the terms of the GNU Lesser General Public License version 3
14 : : * only, as published by the Free Software Foundation.
15 : : *
16 : : * OpenOffice.org is distributed in the hope that it will be useful,
17 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 : : * GNU Lesser General Public License version 3 for more details
20 : : * (a copy is included in the LICENSE file that accompanied this code).
21 : : *
22 : : * You should have received a copy of the GNU Lesser General Public License
23 : : * version 3 along with OpenOffice.org. If not, see
24 : : * <http://www.openoffice.org/license.html>
25 : : * for a copy of the LGPLv3 License.
26 : : *
27 : : ************************************************************************/
28 : :
29 : :
30 : : #include "hash.hxx"
31 : : #include "strimp.hxx"
32 : : #include <osl/diagnose.h>
33 : : #include <sal/macros.h>
34 : :
35 : : struct StringHashTableImpl {
36 : : sal_uInt32 nEntries;
37 : : sal_uInt32 nSize;
38 : : rtl_uString **pData;
39 : : };
40 : :
41 : : typedef StringHashTableImpl StringHashTable;
42 : :
43 : : // Only for use in the implementation
44 : : static StringHashTable *rtl_str_hash_new (sal_uInt32 nSize);
45 : : static void rtl_str_hash_free (StringHashTable *pHash);
46 : :
47 : : StringHashTable *
48 : 740139 : getHashTable ()
49 : : {
50 : : static StringHashTable *pInternPool = NULL;
51 [ + + ]: 740139 : if (pInternPool == NULL) {
52 [ + - ][ + - ]: 271 : static StringHashTable* pHash = rtl_str_hash_new(1024);
[ + - ][ # # ]
53 : 271 : pInternPool = pHash;
54 : : }
55 : 740139 : return pInternPool;
56 : : }
57 : :
58 : : // Better / smaller / faster hash set ....
59 : :
60 : : // TODO: add bottom bit-set list terminator to string list
61 : :
62 : : static sal_uInt32
63 : 511 : getNextSize (sal_uInt32 nSize)
64 : : {
65 : : // Sedgewick - Algorithms in C P577.
66 : : static const sal_uInt32 nPrimes[] = { 1021, 2039, 4093, 8191, 16381, 32749,
67 : : 65521, 131071,262139, 524287, 1048573,
68 : : 2097143, 4194301, 8388593, 16777213,
69 : : 33554393, 67108859, 134217689 };
70 : :
71 [ + - ]: 1614 : for (sal_uInt32 i = 0; i < SAL_N_ELEMENTS(nPrimes); i++)
72 : : {
73 [ + + ]: 1614 : if (nPrimes[i] > nSize)
74 : 511 : return nPrimes[i];
75 : : }
76 : 511 : return nSize * 2;
77 : : }
78 : :
79 : : static sal_uInt32
80 : 1085741 : hashString (rtl_uString *pString)
81 : : {
82 : : return (sal_uInt32) rtl_ustr_hashCode_WithLength (pString->buffer,
83 : 1085741 : pString->length);
84 : : }
85 : :
86 : : static StringHashTable *
87 : 391 : rtl_str_hash_new (sal_uInt32 nSize)
88 : : {
89 : 391 : StringHashTable *pHash = (StringHashTable *)malloc (sizeof (StringHashTable));
90 : :
91 : 391 : pHash->nEntries = 0;
92 : 391 : pHash->nSize = getNextSize (nSize);
93 : 391 : pHash->pData = (rtl_uString **) calloc (sizeof (rtl_uString *), pHash->nSize);
94 : :
95 : 391 : return pHash;
96 : : }
97 : :
98 : : static void
99 : 120 : rtl_str_hash_free (StringHashTable *pHash)
100 : : {
101 [ - + ]: 120 : if (!pHash)
102 : 120 : return;
103 [ - + ]: 120 : if (pHash->pData)
104 : 0 : free (pHash->pData);
105 : 120 : free (pHash);
106 : : }
107 : :
108 : : static void
109 : 345722 : rtl_str_hash_insert_nonequal (StringHashTable *pHash,
110 : : rtl_uString *pString)
111 : : {
112 : 345722 : sal_uInt32 nHash = hashString (pString);
113 : : sal_uInt32 n;
114 : :
115 : 345722 : n = nHash % pHash->nSize;
116 [ + + ]: 372886 : while (pHash->pData[n] != NULL) {
117 : 27164 : n++;
118 [ - + ]: 27164 : if (n >= pHash->nSize)
119 : 0 : n = 0;
120 : : }
121 : 345722 : pHash->pData[n] = pString;
122 : 345722 : }
123 : :
124 : : static void
125 : 120 : rtl_str_hash_resize (sal_uInt32 nNewSize)
126 : : {
127 : : sal_uInt32 i;
128 : : StringHashTable *pNewHash;
129 : 120 : StringHashTable *pHash = getHashTable();
130 : :
131 : : OSL_ASSERT (nNewSize > pHash->nEntries);
132 : :
133 : 120 : pNewHash = rtl_str_hash_new (nNewSize);
134 : :
135 [ + + ]: 601616 : for (i = 0; i < pHash->nSize; i++)
136 : : {
137 [ + + ]: 601496 : if (pHash->pData[i] != NULL)
138 : 300688 : rtl_str_hash_insert_nonequal (pNewHash, pHash->pData[i]);
139 : : }
140 : 120 : pNewHash->nEntries = pHash->nEntries;
141 : 120 : free (pHash->pData);
142 : 120 : *pHash = *pNewHash;
143 : 120 : pNewHash->pData = NULL;
144 : 120 : rtl_str_hash_free (pNewHash);
145 : 120 : }
146 : :
147 : : static int
148 : 583940 : compareEqual (rtl_uString *pStringA, rtl_uString *pStringB)
149 : : {
150 [ + + ]: 583940 : if (pStringA == pStringB)
151 : 332695 : return 1;
152 [ + + ]: 251245 : if (pStringA->length != pStringB->length)
153 : 167882 : return 0;
154 : : return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
155 : 583940 : pStringB->buffer, pStringB->length);
156 : : }
157 : :
158 : :
159 : : rtl_uString *
160 : 407324 : rtl_str_hash_intern (rtl_uString *pString,
161 : : int can_return)
162 : : {
163 : 407324 : sal_uInt32 nHash = hashString (pString);
164 : : sal_uInt32 n;
165 : : rtl_uString *pHashStr;
166 : :
167 : 407324 : StringHashTable *pHash = getHashTable();
168 : :
169 : : // Should we resize ?
170 [ + + ]: 407324 : if (pHash->nEntries >= pHash->nSize/2)
171 : 120 : rtl_str_hash_resize (getNextSize(pHash->nSize));
172 : :
173 : 407324 : n = nHash % pHash->nSize;
174 [ + + ]: 566578 : while ((pHashStr = pHash->pData[n]) != NULL) {
175 [ + + ]: 233034 : if (compareEqual (pHashStr, pString))
176 : : {
177 : 73780 : rtl_uString_acquire (pHashStr);
178 : 73780 : return pHashStr;
179 : : }
180 : 159254 : n++;
181 [ + + ]: 159254 : if (n >= pHash->nSize)
182 : 20 : n = 0;
183 : : }
184 : :
185 [ + + ]: 333544 : if (!can_return)
186 : : {
187 : 47603 : rtl_uString *pCopy = NULL;
188 : 47603 : rtl_uString_newFromString( &pCopy, pString );
189 : 47603 : pString = pCopy;
190 [ - + ]: 47603 : if (!pString)
191 : 47603 : return NULL;
192 : : }
193 : :
194 [ + - ]: 333544 : if (!SAL_STRING_IS_STATIC (pString))
195 : 333544 : pString->refCount |= SAL_STRING_INTERN_FLAG;
196 : 333544 : pHash->pData[n] = pString;
197 : 333544 : pHash->nEntries++;
198 : :
199 : 407324 : return pString;
200 : : }
201 : :
202 : : void
203 : 332695 : rtl_str_hash_remove (rtl_uString *pString)
204 : : {
205 : : sal_uInt32 n;
206 : 332695 : sal_uInt32 nHash = hashString (pString);
207 : : rtl_uString *pHashStr;
208 : :
209 : 332695 : StringHashTable *pHash = getHashTable();
210 : :
211 : 332695 : n = nHash % pHash->nSize;
212 [ + - ]: 350906 : while ((pHashStr = pHash->pData[n]) != NULL) {
213 [ + + ]: 350906 : if (compareEqual (pHashStr, pString))
214 : 332695 : break;
215 : 18211 : n++;
216 [ - + ]: 18211 : if (n >= pHash->nSize)
217 : 0 : n = 0;
218 : : }
219 : : OSL_ASSERT (pHash->pData[n] != 0);
220 [ - + ]: 332695 : if (pHash->pData[n] == NULL)
221 : 332695 : return;
222 : :
223 : 332695 : pHash->pData[n++] = NULL;
224 : 332695 : pHash->nEntries--;
225 : :
226 [ - + ]: 332695 : if (n >= pHash->nSize)
227 : 0 : n = 0;
228 : :
229 [ + + ]: 377729 : while ((pHashStr = pHash->pData[n]) != NULL) {
230 : 45034 : pHash->pData[n] = NULL;
231 : : // FIXME: rather unsophisticated and N^2 in chain-length, but robust.
232 : 45034 : rtl_str_hash_insert_nonequal (pHash, pHashStr);
233 : 45034 : n++;
234 [ - + ]: 45034 : if (n >= pHash->nSize)
235 : 0 : n = 0;
236 : : }
237 : : // FIXME: Should we down-size ?
238 : : }
239 : :
240 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
