Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : #include <svl/inethist.hxx>
21 :
22 : #include <algorithm>
23 : #include <string.h>
24 :
25 : #include <boost/noncopyable.hpp>
26 : #include <rtl/instance.hxx>
27 : #include <rtl/crc.h>
28 : #include <osl/diagnose.h>
29 : #include <osl/getglobalmutex.hxx>
30 : #include <tools/solar.h>
31 : #include <tools/debug.hxx>
32 : #include <tools/urlobj.hxx>
33 :
34 : /*
35 : * INetURLHistory internals.
36 : */
37 : #define INETHIST_DEF_FTP_PORT 21
38 : #define INETHIST_DEF_HTTP_PORT 80
39 : #define INETHIST_DEF_HTTPS_PORT 443
40 :
41 : #define INETHIST_SIZE_LIMIT 1024
42 : #define INETHIST_MAGIC_HEAD 0x484D4849UL
43 :
44 : class INetURLHistory_Impl: private boost::noncopyable
45 : {
46 : struct head_entry
47 : {
48 : /** Representation.
49 : */
50 : sal_uInt32 m_nMagic;
51 : sal_uInt16 m_nNext;
52 : sal_uInt16 m_nMBZ;
53 :
54 : /** Initialization.
55 : */
56 67 : void initialize()
57 : {
58 67 : m_nMagic = INETHIST_MAGIC_HEAD;
59 67 : m_nNext = 0;
60 67 : m_nMBZ = 0;
61 67 : }
62 : };
63 :
64 : struct hash_entry
65 : {
66 : /** Representation.
67 : */
68 : sal_uInt32 m_nHash;
69 : sal_uInt16 m_nLru;
70 : sal_uInt16 m_nMBZ;
71 :
72 : /** Initialization.
73 : */
74 68608 : void initialize (sal_uInt16 nLru, sal_uInt32 nHash = 0)
75 : {
76 68608 : m_nHash = nHash;
77 68608 : m_nLru = nLru;
78 68608 : m_nMBZ = 0;
79 68608 : }
80 :
81 : /** Comparison.
82 : */
83 44397 : bool operator== (sal_uInt32 nHash) const
84 : {
85 44397 : return (m_nHash == nHash);
86 : }
87 39931 : bool operator< (sal_uInt32 nHash) const
88 : {
89 39931 : return (m_nHash < nHash);
90 : }
91 : };
92 :
93 : struct lru_entry
94 : {
95 : /** Representation.
96 : */
97 : sal_uInt32 m_nHash;
98 : sal_uInt16 m_nNext;
99 : sal_uInt16 m_nPrev;
100 :
101 : /** Initialization.
102 : */
103 68608 : void initialize (sal_uInt16 nThis, sal_uInt32 nHash = 0)
104 : {
105 68608 : m_nHash = nHash;
106 68608 : m_nNext = nThis;
107 68608 : m_nPrev = nThis;
108 68608 : }
109 : };
110 :
111 : /** Representation.
112 : */
113 : head_entry m_aHead;
114 : hash_entry m_pHash[INETHIST_SIZE_LIMIT];
115 : lru_entry m_pList[INETHIST_SIZE_LIMIT];
116 :
117 : /** Initialization.
118 : */
119 : void initialize();
120 :
121 18181 : static sal_uInt16 capacity()
122 : {
123 18181 : return (sal_uInt16)(INETHIST_SIZE_LIMIT);
124 : }
125 :
126 4176 : static sal_uInt32 crc32 (OUString const & rData)
127 : {
128 4176 : return rtl_crc32 (0, rData.getStr(), rData.getLength() * sizeof(sal_Unicode));
129 : }
130 :
131 : sal_uInt16 find (sal_uInt32 nHash) const;
132 :
133 : void move (sal_uInt16 nSI, sal_uInt16 nDI);
134 :
135 70444 : void backlink (sal_uInt16 nThis, sal_uInt16 nTail)
136 : {
137 70444 : lru_entry &rThis = m_pList[nThis];
138 70444 : lru_entry &rTail = m_pList[nTail];
139 :
140 70444 : rTail.m_nNext = nThis;
141 70444 : rTail.m_nPrev = rThis.m_nPrev;
142 70444 : rThis.m_nPrev = nTail;
143 70444 : m_pList[rTail.m_nPrev].m_nNext = nTail;
144 70444 : }
145 :
146 1903 : void unlink (sal_uInt16 nThis)
147 : {
148 1903 : lru_entry &rThis = m_pList[nThis];
149 :
150 1903 : m_pList[rThis.m_nPrev].m_nNext = rThis.m_nNext;
151 1903 : m_pList[rThis.m_nNext].m_nPrev = rThis.m_nPrev;
152 1903 : rThis.m_nNext = nThis;
153 1903 : rThis.m_nPrev = nThis;
154 1903 : }
155 :
156 : public:
157 : INetURLHistory_Impl();
158 : ~INetURLHistory_Impl();
159 :
160 : /** putUrl/queryUrl.
161 : */
162 : void putUrl (const OUString &rUrl);
163 : bool queryUrl (const OUString &rUrl);
164 : };
165 :
166 67 : INetURLHistory_Impl::INetURLHistory_Impl()
167 : {
168 67 : initialize();
169 67 : }
170 :
171 67 : INetURLHistory_Impl::~INetURLHistory_Impl()
172 : {
173 67 : }
174 :
175 67 : void INetURLHistory_Impl::initialize()
176 : {
177 67 : m_aHead.initialize();
178 :
179 67 : sal_uInt16 i, n = capacity();
180 68675 : for (i = 0; i < n; i++)
181 68608 : m_pHash[i].initialize(i);
182 68675 : for (i = 0; i < n; i++)
183 68608 : m_pList[i].initialize(i);
184 68608 : for (i = 1; i < n; i++)
185 68541 : backlink (m_aHead.m_nNext, i);
186 67 : }
187 :
188 6038 : sal_uInt16 INetURLHistory_Impl::find (sal_uInt32 nHash) const
189 : {
190 6038 : sal_uInt16 l = 0;
191 6038 : sal_uInt16 r = capacity() - 1;
192 6038 : sal_uInt16 c = capacity();
193 :
194 50145 : while ((l < r) && (r < c))
195 : {
196 40221 : sal_uInt16 m = (l + r) / 2;
197 40221 : if (m_pHash[m] == nHash)
198 2152 : return m;
199 :
200 38069 : if (m_pHash[m] < nHash)
201 31336 : l = m + 1;
202 : else
203 6733 : r = m - 1;
204 : }
205 3886 : return l;
206 : }
207 :
208 1862 : void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI)
209 : {
210 1862 : hash_entry e = m_pHash[nSI];
211 1862 : if (nSI < nDI)
212 : {
213 : // shift left.
214 : memmove (
215 1862 : &m_pHash[nSI ],
216 1862 : &m_pHash[nSI + 1],
217 5586 : (nDI - nSI) * sizeof(hash_entry));
218 : }
219 1862 : if (nSI > nDI)
220 : {
221 : // shift right.
222 : memmove (
223 0 : &m_pHash[nDI + 1],
224 0 : &m_pHash[nDI ],
225 0 : (nSI - nDI) * sizeof(hash_entry));
226 : }
227 1862 : m_pHash[nDI] = e;
228 1862 : }
229 :
230 2442 : void INetURLHistory_Impl::putUrl (const OUString &rUrl)
231 : {
232 2442 : sal_uInt32 h = crc32 (rUrl);
233 2442 : sal_uInt16 k = find (h);
234 2442 : if ((k < capacity()) && (m_pHash[k] == h))
235 : {
236 : // Cache hit.
237 580 : sal_uInt16 nMRU = m_pHash[k].m_nLru;
238 580 : if (nMRU != m_aHead.m_nNext)
239 : {
240 : // Update LRU chain.
241 41 : unlink (nMRU);
242 41 : backlink (m_aHead.m_nNext, nMRU);
243 :
244 : // Rotate LRU chain.
245 41 : m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
246 : }
247 : }
248 : else
249 : {
250 : // Cache miss. Obtain least recently used.
251 1862 : sal_uInt16 nLRU = m_pList[m_aHead.m_nNext].m_nPrev;
252 :
253 1862 : sal_uInt16 nSI = find (m_pList[nLRU].m_nHash);
254 1862 : if (!(nLRU == m_pHash[nSI].m_nLru))
255 : {
256 : // Update LRU chain.
257 1862 : nLRU = m_pHash[nSI].m_nLru;
258 1862 : unlink (nLRU);
259 1862 : backlink (m_aHead.m_nNext, nLRU);
260 : }
261 :
262 : // Rotate LRU chain.
263 1862 : m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
264 :
265 : // Check source and destination.
266 1862 : sal_uInt16 nDI = std::min (k, sal_uInt16(capacity() - 1));
267 1862 : if (nSI < nDI)
268 : {
269 1862 : if (!(m_pHash[nDI] < h))
270 928 : nDI -= 1;
271 : }
272 1862 : if (nDI < nSI)
273 : {
274 0 : if (m_pHash[nDI] < h)
275 0 : nDI += 1;
276 : }
277 :
278 : // Assign data.
279 1862 : m_pList[m_aHead.m_nNext].m_nHash = m_pHash[nSI].m_nHash = h;
280 1862 : move (nSI, nDI);
281 : }
282 2442 : }
283 :
284 1734 : bool INetURLHistory_Impl::queryUrl (const OUString &rUrl)
285 : {
286 1734 : sal_uInt32 h = crc32 (rUrl);
287 1734 : sal_uInt16 k = find (h);
288 1734 : if ((k < capacity()) && (m_pHash[k] == h))
289 : {
290 : // Cache hit.
291 0 : return true;
292 : }
293 : else
294 : {
295 : // Cache miss.
296 1734 : return false;
297 : }
298 : }
299 :
300 : /*
301 : * INetURLHistory::StaticInstance implementation.
302 : */
303 67 : INetURLHistory * INetURLHistory::StaticInstance::operator ()()
304 : {
305 67 : static INetURLHistory g_aInstance;
306 67 : return &g_aInstance;
307 : }
308 :
309 67 : INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
310 : {
311 67 : }
312 :
313 134 : INetURLHistory::~INetURLHistory()
314 : {
315 67 : DELETEZ (m_pImpl);
316 67 : }
317 :
318 : /*
319 : * GetOrCreate.
320 : */
321 4612 : INetURLHistory* INetURLHistory::GetOrCreate()
322 : {
323 : return rtl_Instance<
324 : INetURLHistory, StaticInstance,
325 : osl::MutexGuard, osl::GetGlobalMutex >::create (
326 4612 : StaticInstance(), osl::GetGlobalMutex());
327 : }
328 :
329 4176 : void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl)
330 : {
331 4176 : switch (rUrl.GetProtocol())
332 : {
333 : case INetProtocol::File:
334 3644 : if (!INetURLObject::IsCaseSensitive())
335 : {
336 0 : OUString aPath (rUrl.GetURLPath(INetURLObject::NO_DECODE).toAsciiLowerCase());
337 0 : rUrl.SetURLPath (aPath, INetURLObject::NOT_CANONIC);
338 : }
339 3644 : break;
340 :
341 : case INetProtocol::Ftp:
342 0 : if (!rUrl.HasPort())
343 0 : rUrl.SetPort (INETHIST_DEF_FTP_PORT);
344 0 : break;
345 :
346 : case INetProtocol::Http:
347 529 : if (!rUrl.HasPort())
348 529 : rUrl.SetPort (INETHIST_DEF_HTTP_PORT);
349 529 : if (!rUrl.HasURLPath())
350 0 : rUrl.SetURLPath("/");
351 529 : break;
352 :
353 : case INetProtocol::Https:
354 3 : if (!rUrl.HasPort())
355 3 : rUrl.SetPort (INETHIST_DEF_HTTPS_PORT);
356 3 : if (!rUrl.HasURLPath())
357 0 : rUrl.SetURLPath("/");
358 3 : break;
359 :
360 : default:
361 0 : break;
362 : }
363 4176 : }
364 :
365 2442 : void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl)
366 : {
367 : DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation");
368 2442 : if (m_pImpl)
369 : {
370 2442 : INetURLObject aHistUrl (rUrl);
371 2442 : NormalizeUrl_Impl (aHistUrl);
372 :
373 2442 : m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
374 2442 : Broadcast (INetURLHistoryHint (&rUrl));
375 :
376 2442 : if (aHistUrl.HasMark())
377 : {
378 : aHistUrl.SetURL (aHistUrl.GetURLNoMark(INetURLObject::NO_DECODE),
379 0 : INetURLObject::NOT_CANONIC);
380 :
381 0 : m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
382 0 : Broadcast (INetURLHistoryHint (&aHistUrl));
383 2442 : }
384 : }
385 2442 : }
386 :
387 1734 : bool INetURLHistory::QueryUrl_Impl (const INetURLObject &rUrl)
388 : {
389 : DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation");
390 1734 : if (m_pImpl)
391 : {
392 1734 : INetURLObject aHistUrl (rUrl);
393 1734 : NormalizeUrl_Impl (aHistUrl);
394 :
395 1734 : return m_pImpl->queryUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
396 : }
397 0 : return false;
398 : }
399 :
400 :
401 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
