Branch data 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 : :
24 : : #include "rtl/instance.hxx"
25 : : #include "rtl/crc.h"
26 : : #include "rtl/memory.h"
27 : : #include <tools/solar.h>
28 : : #include <tools/debug.hxx>
29 : : #include <tools/string.hxx>
30 : : #include <tools/urlobj.hxx>
31 : :
32 : : /*========================================================================
33 : : *
34 : : * INetURLHistory internals.
35 : : *
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 : : /*
45 : : * INetURLHistoryHint implementation.
46 : : */
47 [ - + ][ + - ]: 1850 : IMPL_PTRHINT (INetURLHistoryHint, const INetURLObject);
[ # # ]
48 : :
49 : : /*========================================================================
50 : : *
51 : : * INetURLHistory_Impl interface.
52 : : *
53 : : *======================================================================*/
54 : : class INetURLHistory_Impl
55 : : {
56 : : /** head_entry.
57 : : */
58 : : struct head_entry
59 : : {
60 : : /** Representation.
61 : : */
62 : : sal_uInt32 m_nMagic;
63 : : sal_uInt16 m_nNext;
64 : : sal_uInt16 m_nMBZ;
65 : :
66 : : /** Initialization.
67 : : */
68 : 84 : void initialize (void)
69 : : {
70 : 84 : m_nMagic = INETHIST_MAGIC_HEAD;
71 : 84 : m_nNext = 0;
72 : 84 : m_nMBZ = 0;
73 : 84 : }
74 : : };
75 : :
76 : : /** hash_entry.
77 : : */
78 : : struct hash_entry
79 : : {
80 : : /** Representation.
81 : : */
82 : : sal_uInt32 m_nHash;
83 : : sal_uInt16 m_nLru;
84 : : sal_uInt16 m_nMBZ;
85 : :
86 : : /** Initialization.
87 : : */
88 : 86016 : void initialize (sal_uInt16 nLru, sal_uInt32 nHash = 0)
89 : : {
90 : 86016 : m_nHash = nHash;
91 : 86016 : m_nLru = nLru;
92 : 86016 : m_nMBZ = 0;
93 : 86016 : }
94 : :
95 : : /** Comparison.
96 : : */
97 : : sal_Bool operator== (const hash_entry &rOther) const
98 : : {
99 : : return (m_nHash == rOther.m_nHash);
100 : : }
101 : : sal_Bool operator< (const hash_entry &rOther) const
102 : : {
103 : : return (m_nHash < rOther.m_nHash);
104 : : }
105 : :
106 : 11661 : sal_Bool operator== (sal_uInt32 nHash) const
107 : : {
108 : 11661 : return (m_nHash == nHash);
109 : : }
110 : 10630 : sal_Bool operator< (sal_uInt32 nHash) const
111 : : {
112 : 10630 : return (m_nHash < nHash);
113 : : }
114 : : };
115 : :
116 : : /** lru_entry.
117 : : */
118 : : struct lru_entry
119 : : {
120 : : /** Representation.
121 : : */
122 : : sal_uInt32 m_nHash;
123 : : sal_uInt16 m_nNext;
124 : : sal_uInt16 m_nPrev;
125 : :
126 : : /** Initialization.
127 : : */
128 : 86016 : void initialize (sal_uInt16 nThis, sal_uInt32 nHash = 0)
129 : : {
130 : 86016 : m_nHash = nHash;
131 : 86016 : m_nNext = nThis;
132 : 86016 : m_nPrev = nThis;
133 : 86016 : }
134 : : };
135 : :
136 : : /** Representation.
137 : : */
138 : : head_entry m_aHead;
139 : : hash_entry m_pHash[INETHIST_SIZE_LIMIT];
140 : : lru_entry m_pList[INETHIST_SIZE_LIMIT];
141 : :
142 : : /** Initialization.
143 : : */
144 : : void initialize (void);
145 : :
146 : : /** capacity.
147 : : */
148 : 5880 : sal_uInt16 capacity (void) const
149 : : {
150 : 5880 : return (sal_uInt16)(INETHIST_SIZE_LIMIT);
151 : : }
152 : :
153 : : /** crc32.
154 : : */
155 : 1029 : sal_uInt32 crc32 (UniString const & rData) const
156 : : {
157 : 1029 : return rtl_crc32 (0, rData.GetBuffer(), rData.Len() * sizeof(sal_Unicode));
158 : : }
159 : :
160 : : /** find.
161 : : */
162 : : sal_uInt16 find (sal_uInt32 nHash) const;
163 : :
164 : : /** move.
165 : : */
166 : : void move (sal_uInt16 nSI, sal_uInt16 nDI);
167 : :
168 : : /** backlink.
169 : : */
170 : 86835 : void backlink (sal_uInt16 nThis, sal_uInt16 nTail)
171 : : {
172 : 86835 : register lru_entry &rThis = m_pList[nThis];
173 : 86835 : register lru_entry &rTail = m_pList[nTail];
174 : :
175 : 86835 : rTail.m_nNext = nThis;
176 : 86835 : rTail.m_nPrev = rThis.m_nPrev;
177 : 86835 : rThis.m_nPrev = nTail;
178 : 86835 : m_pList[rTail.m_nPrev].m_nNext = nTail;
179 : 86835 : }
180 : :
181 : : /** unlink.
182 : : */
183 : 903 : void unlink (sal_uInt16 nThis)
184 : : {
185 : 903 : register lru_entry &rThis = m_pList[nThis];
186 : :
187 : 903 : m_pList[rThis.m_nPrev].m_nNext = rThis.m_nNext;
188 : 903 : m_pList[rThis.m_nNext].m_nPrev = rThis.m_nPrev;
189 : 903 : rThis.m_nNext = nThis;
190 : 903 : rThis.m_nPrev = nThis;
191 : 903 : }
192 : :
193 : : /** Not implemented.
194 : : */
195 : : INetURLHistory_Impl (const INetURLHistory_Impl&);
196 : : INetURLHistory_Impl& operator= (const INetURLHistory_Impl&);
197 : :
198 : : public:
199 : : INetURLHistory_Impl (void);
200 : : ~INetURLHistory_Impl (void);
201 : :
202 : : /** putUrl/queryUrl.
203 : : */
204 : : void putUrl (const String &rUrl);
205 : : sal_Bool queryUrl (const String &rUrl);
206 : : };
207 : :
208 : : /*========================================================================
209 : : *
210 : : * INetURLHistory_Impl implementation.
211 : : *
212 : : *======================================================================*/
213 : : /*
214 : : * INetURLHistory_Impl.
215 : : */
216 : 84 : INetURLHistory_Impl::INetURLHistory_Impl (void)
217 : : {
218 : 84 : initialize();
219 : 84 : }
220 : :
221 : : /*
222 : : * ~INetURLHistory_Impl.
223 : : */
224 : 84 : INetURLHistory_Impl::~INetURLHistory_Impl (void)
225 : : {
226 : 84 : }
227 : :
228 : : /*
229 : : * initialize.
230 : : */
231 : 84 : void INetURLHistory_Impl::initialize (void)
232 : : {
233 : 84 : m_aHead.initialize();
234 : :
235 : 84 : sal_uInt16 i, n = capacity();
236 [ + + ]: 86100 : for (i = 0; i < n; i++)
237 : 86016 : m_pHash[i].initialize(i);
238 [ + + ]: 86100 : for (i = 0; i < n; i++)
239 : 86016 : m_pList[i].initialize(i);
240 [ + + ]: 86016 : for (i = 1; i < n; i++)
241 : 85932 : backlink (m_aHead.m_nNext, i);
242 : 84 : }
243 : :
244 : : /*
245 : : * find.
246 : : */
247 : 1932 : sal_uInt16 INetURLHistory_Impl::find (sal_uInt32 nHash) const
248 : : {
249 : 1932 : sal_uInt16 l = 0;
250 : 1932 : sal_uInt16 r = capacity() - 1;
251 : 1932 : sal_uInt16 c = capacity();
252 : :
253 [ + + ][ + - ]: 11659 : while ((l < r) && (r < c))
[ + + ]
254 : : {
255 : 10632 : sal_uInt16 m = (l + r) / 2;
256 [ + + ]: 10632 : if (m_pHash[m] == nHash)
257 : 905 : return m;
258 : :
259 [ + + ]: 9727 : if (m_pHash[m] < nHash)
260 : 8641 : l = m + 1;
261 : : else
262 : 1086 : r = m - 1;
263 : : }
264 : 1932 : return l;
265 : : }
266 : :
267 : : /*
268 : : * move.
269 : : */
270 : 903 : void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI)
271 : : {
272 : 903 : hash_entry e = m_pHash[nSI];
273 [ + - ]: 903 : if (nSI < nDI)
274 : : {
275 : : // shift left.
276 : : rtl_moveMemory (
277 : 903 : &m_pHash[nSI ],
278 : 903 : &m_pHash[nSI + 1],
279 [ + - ]: 903 : (nDI - nSI) * sizeof(hash_entry));
280 : : }
281 [ - + ]: 903 : if (nSI > nDI)
282 : : {
283 : : // shift right.
284 : : rtl_moveMemory (
285 : 0 : &m_pHash[nDI + 1],
286 : 0 : &m_pHash[nDI ],
287 [ # # ]: 0 : (nSI - nDI) * sizeof(hash_entry));
288 : : }
289 : 903 : m_pHash[nDI] = e;
290 : 903 : }
291 : :
292 : : /*
293 : : * putUrl.
294 : : */
295 : 905 : void INetURLHistory_Impl::putUrl (const String &rUrl)
296 : : {
297 : 905 : sal_uInt32 h = crc32 (rUrl);
298 : 905 : sal_uInt16 k = find (h);
299 [ + + ][ + + ]: 905 : if ((k < capacity()) && (m_pHash[k] == h))
[ + - ]
300 : : {
301 : : // Cache hit.
302 : 2 : sal_uInt16 nMRU = m_pHash[k].m_nLru;
303 [ - + ]: 2 : if (nMRU != m_aHead.m_nNext)
304 : : {
305 : : // Update LRU chain.
306 : 0 : unlink (nMRU);
307 : 0 : backlink (m_aHead.m_nNext, nMRU);
308 : :
309 : : // Rotate LRU chain.
310 : 0 : m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
311 : : }
312 : : }
313 : : else
314 : : {
315 : : // Cache miss. Obtain least recently used.
316 : 903 : sal_uInt16 nLRU = m_pList[m_aHead.m_nNext].m_nPrev;
317 : :
318 : 903 : sal_uInt16 nSI = find (m_pList[nLRU].m_nHash);
319 [ + - ]: 903 : if (!(nLRU == m_pHash[nSI].m_nLru))
320 : : {
321 : : // Update LRU chain.
322 : 903 : nLRU = m_pHash[nSI].m_nLru;
323 : 903 : unlink (nLRU);
324 : 903 : backlink (m_aHead.m_nNext, nLRU);
325 : : }
326 : :
327 : : // Rotate LRU chain.
328 : 903 : m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
329 : :
330 : : // Check source and destination.
331 [ + - ]: 903 : sal_uInt16 nDI = std::min (k, sal_uInt16(capacity() - 1));
332 [ + - ]: 903 : if (nSI < nDI)
333 : : {
334 [ + + ]: 903 : if (!(m_pHash[nDI] < h))
335 : 451 : nDI -= 1;
336 : : }
337 [ - + ]: 903 : if (nDI < nSI)
338 : : {
339 [ # # ]: 0 : if (m_pHash[nDI] < h)
340 : 0 : nDI += 1;
341 : : }
342 : :
343 : : // Assign data.
344 : 903 : m_pList[m_aHead.m_nNext].m_nHash = m_pHash[nSI].m_nHash = h;
345 [ + - ]: 903 : move (nSI, nDI);
346 : : }
347 : 905 : }
348 : :
349 : : /*
350 : : * queryUrl.
351 : : */
352 : 124 : sal_Bool INetURLHistory_Impl::queryUrl (const String &rUrl)
353 : : {
354 : 124 : sal_uInt32 h = crc32 (rUrl);
355 : 124 : sal_uInt16 k = find (h);
356 [ - + ][ - + ]: 124 : if ((k < capacity()) && (m_pHash[k] == h))
[ + - ]
357 : : {
358 : : // Cache hit.
359 : 0 : return sal_True;
360 : : }
361 : : else
362 : : {
363 : : // Cache miss.
364 : 124 : return sal_False;
365 : : }
366 : : }
367 : :
368 : : /*========================================================================
369 : : *
370 : : * INetURLHistory::StaticInstance implementation.
371 : : *
372 : : *======================================================================*/
373 : 84 : INetURLHistory * INetURLHistory::StaticInstance::operator ()()
374 : : {
375 [ + - ][ + - ]: 84 : static INetURLHistory g_aInstance;
[ + - ][ # # ]
376 : 84 : return &g_aInstance;
377 : : }
378 : :
379 : : /*========================================================================
380 : : *
381 : : * INetURLHistory implementation.
382 : : *
383 : : *======================================================================*/
384 : : /*
385 : : * INetURLHistory.
386 : : */
387 [ + - ][ + - ]: 84 : INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
388 : : {
389 : 84 : }
390 : :
391 : : /*
392 : : * ~INetURLHistory.
393 : : */
394 : 84 : INetURLHistory::~INetURLHistory()
395 : : {
396 [ + - ]: 84 : DELETEZ (m_pImpl);
397 [ - + ]: 84 : }
398 : :
399 : : /*
400 : : * GetOrCreate.
401 : : */
402 : 1192 : INetURLHistory* INetURLHistory::GetOrCreate()
403 : : {
404 : : return rtl_Instance<
405 : : INetURLHistory, StaticInstance,
406 : : osl::MutexGuard, osl::GetGlobalMutex >::create (
407 [ + - ]: 1192 : StaticInstance(), osl::GetGlobalMutex());
408 : : }
409 : :
410 : : /*
411 : : * NormalizeUrl_Impl.
412 : : */
413 : 1029 : void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl)
414 : : {
415 [ + - + - : 1029 : switch (rUrl.GetProtocol())
- ]
416 : : {
417 : : case INET_PROT_FILE:
418 [ - + ]: 905 : if (!rUrl.IsCaseSensitive())
419 : : {
420 [ # # ][ # # ]: 0 : String aPath (rUrl.GetURLPath(INetURLObject::NO_DECODE));
421 [ # # ]: 0 : aPath.ToLowerAscii();
422 [ # # ][ # # ]: 0 : rUrl.SetURLPath (aPath, INetURLObject::NOT_CANONIC);
[ # # ]
423 : : }
424 : 905 : break;
425 : :
426 : : case INET_PROT_FTP:
427 [ # # ]: 0 : if (!rUrl.HasPort())
428 : 0 : rUrl.SetPort (INETHIST_DEF_FTP_PORT);
429 : 0 : break;
430 : :
431 : : case INET_PROT_HTTP:
432 [ + - ]: 124 : if (!rUrl.HasPort())
433 : 124 : rUrl.SetPort (INETHIST_DEF_HTTP_PORT);
434 [ - + ]: 124 : if (!rUrl.HasURLPath())
435 [ # # ]: 0 : rUrl.SetURLPath (rtl::OString("/"));
436 : 124 : break;
437 : :
438 : : case INET_PROT_HTTPS:
439 [ # # ]: 0 : if (!rUrl.HasPort())
440 : 0 : rUrl.SetPort (INETHIST_DEF_HTTPS_PORT);
441 [ # # ]: 0 : if (!rUrl.HasURLPath())
442 [ # # ]: 0 : rUrl.SetURLPath (rtl::OString("/"));
443 : 0 : break;
444 : :
445 : : default:
446 : 0 : break;
447 : : }
448 : 1029 : }
449 : :
450 : : /*
451 : : * PutUrl_Impl.
452 : : */
453 : 905 : void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl)
454 : : {
455 : : DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation");
456 [ + - ]: 905 : if (m_pImpl)
457 : : {
458 [ + - ]: 905 : INetURLObject aHistUrl (rUrl);
459 [ + - ]: 905 : NormalizeUrl_Impl (aHistUrl);
460 : :
461 [ + - ][ + - ]: 905 : m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
[ + - ][ + - ]
462 [ + - ][ + - ]: 905 : Broadcast (INetURLHistoryHint (&rUrl));
[ + - ]
463 : :
464 [ + - ][ - + ]: 905 : if (aHistUrl.HasMark())
465 : : {
466 : : aHistUrl.SetURL (aHistUrl.GetURLNoMark(INetURLObject::NO_DECODE),
467 [ # # ][ # # ]: 0 : INetURLObject::NOT_CANONIC);
468 : :
469 [ # # ][ # # ]: 0 : m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
[ # # ][ # # ]
470 [ # # ][ # # ]: 0 : Broadcast (INetURLHistoryHint (&aHistUrl));
[ # # ]
471 [ + - ]: 905 : }
472 : : }
473 : 905 : }
474 : :
475 : : /*
476 : : * QueryUrl_Impl.
477 : : */
478 : 124 : sal_Bool INetURLHistory::QueryUrl_Impl (const INetURLObject &rUrl)
479 : : {
480 : : DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation");
481 [ + - ]: 124 : if (m_pImpl)
482 : : {
483 [ + - ]: 124 : INetURLObject aHistUrl (rUrl);
484 [ + - ]: 124 : NormalizeUrl_Impl (aHistUrl);
485 : :
486 [ + - ][ + - ]: 124 : return m_pImpl->queryUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
[ + - ][ + - ]
487 : : }
488 : 124 : return sal_False;
489 : : }
490 : :
491 : :
492 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
