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 "rtl/instance.hxx"
26 : #include "rtl/crc.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 656 : 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 8 : void initialize (void)
69 : {
70 8 : m_nMagic = INETHIST_MAGIC_HEAD;
71 8 : m_nNext = 0;
72 8 : m_nMBZ = 0;
73 8 : }
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 8192 : void initialize (sal_uInt16 nLru, sal_uInt32 nHash = 0)
89 : {
90 8192 : m_nHash = nHash;
91 8192 : m_nLru = nLru;
92 8192 : m_nMBZ = 0;
93 8192 : }
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 2729 : sal_Bool operator== (sal_uInt32 nHash) const
107 : {
108 2729 : return (m_nHash == nHash);
109 : }
110 2486 : sal_Bool operator< (sal_uInt32 nHash) const
111 : {
112 2486 : 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 8192 : void initialize (sal_uInt16 nThis, sal_uInt32 nHash = 0)
129 : {
130 8192 : m_nHash = nHash;
131 8192 : m_nNext = nThis;
132 8192 : m_nPrev = nThis;
133 8192 : }
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 1442 : sal_uInt16 capacity (void) const
149 : {
150 1442 : return (sal_uInt16)(INETHIST_SIZE_LIMIT);
151 : }
152 :
153 : /** crc32.
154 : */
155 243 : sal_uInt32 crc32 (UniString const & rData) const
156 : {
157 243 : 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 8419 : void backlink (sal_uInt16 nThis, sal_uInt16 nTail)
171 : {
172 8419 : register lru_entry &rThis = m_pList[nThis];
173 8419 : register lru_entry &rTail = m_pList[nTail];
174 :
175 8419 : rTail.m_nNext = nThis;
176 8419 : rTail.m_nPrev = rThis.m_nPrev;
177 8419 : rThis.m_nPrev = nTail;
178 8419 : m_pList[rTail.m_nPrev].m_nNext = nTail;
179 8419 : }
180 :
181 : /** unlink.
182 : */
183 235 : void unlink (sal_uInt16 nThis)
184 : {
185 235 : register lru_entry &rThis = m_pList[nThis];
186 :
187 235 : m_pList[rThis.m_nPrev].m_nNext = rThis.m_nNext;
188 235 : m_pList[rThis.m_nNext].m_nPrev = rThis.m_nPrev;
189 235 : rThis.m_nNext = nThis;
190 235 : rThis.m_nPrev = nThis;
191 235 : }
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 8 : INetURLHistory_Impl::INetURLHistory_Impl (void)
217 : {
218 8 : initialize();
219 8 : }
220 :
221 : /*
222 : * ~INetURLHistory_Impl.
223 : */
224 8 : INetURLHistory_Impl::~INetURLHistory_Impl (void)
225 : {
226 8 : }
227 :
228 : /*
229 : * initialize.
230 : */
231 8 : void INetURLHistory_Impl::initialize (void)
232 : {
233 8 : m_aHead.initialize();
234 :
235 8 : sal_uInt16 i, n = capacity();
236 8200 : for (i = 0; i < n; i++)
237 8192 : m_pHash[i].initialize(i);
238 8200 : for (i = 0; i < n; i++)
239 8192 : m_pList[i].initialize(i);
240 8192 : for (i = 1; i < n; i++)
241 8184 : backlink (m_aHead.m_nNext, i);
242 8 : }
243 :
244 : /*
245 : * find.
246 : */
247 478 : sal_uInt16 INetURLHistory_Impl::find (sal_uInt32 nHash) const
248 : {
249 478 : sal_uInt16 l = 0;
250 478 : sal_uInt16 r = capacity() - 1;
251 478 : sal_uInt16 c = capacity();
252 :
253 3207 : while ((l < r) && (r < c))
254 : {
255 2486 : sal_uInt16 m = (l + r) / 2;
256 2486 : if (m_pHash[m] == nHash)
257 235 : return m;
258 :
259 2251 : if (m_pHash[m] < nHash)
260 1878 : l = m + 1;
261 : else
262 373 : r = m - 1;
263 : }
264 243 : return l;
265 : }
266 :
267 : /*
268 : * move.
269 : */
270 235 : void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI)
271 : {
272 235 : hash_entry e = m_pHash[nSI];
273 235 : if (nSI < nDI)
274 : {
275 : // shift left.
276 : memmove (
277 235 : &m_pHash[nSI ],
278 235 : &m_pHash[nSI + 1],
279 705 : (nDI - nSI) * sizeof(hash_entry));
280 : }
281 235 : if (nSI > nDI)
282 : {
283 : // shift right.
284 : memmove (
285 0 : &m_pHash[nDI + 1],
286 0 : &m_pHash[nDI ],
287 0 : (nSI - nDI) * sizeof(hash_entry));
288 : }
289 235 : m_pHash[nDI] = e;
290 235 : }
291 :
292 : /*
293 : * putUrl.
294 : */
295 235 : void INetURLHistory_Impl::putUrl (const String &rUrl)
296 : {
297 235 : sal_uInt32 h = crc32 (rUrl);
298 235 : sal_uInt16 k = find (h);
299 235 : if ((k < capacity()) && (m_pHash[k] == h))
300 : {
301 : // Cache hit.
302 0 : sal_uInt16 nMRU = m_pHash[k].m_nLru;
303 0 : 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 235 : sal_uInt16 nLRU = m_pList[m_aHead.m_nNext].m_nPrev;
317 :
318 235 : sal_uInt16 nSI = find (m_pList[nLRU].m_nHash);
319 235 : if (!(nLRU == m_pHash[nSI].m_nLru))
320 : {
321 : // Update LRU chain.
322 235 : nLRU = m_pHash[nSI].m_nLru;
323 235 : unlink (nLRU);
324 235 : backlink (m_aHead.m_nNext, nLRU);
325 : }
326 :
327 : // Rotate LRU chain.
328 235 : m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
329 :
330 : // Check source and destination.
331 235 : sal_uInt16 nDI = std::min (k, sal_uInt16(capacity() - 1));
332 235 : if (nSI < nDI)
333 : {
334 235 : if (!(m_pHash[nDI] < h))
335 129 : nDI -= 1;
336 : }
337 235 : if (nDI < nSI)
338 : {
339 0 : if (m_pHash[nDI] < h)
340 0 : nDI += 1;
341 : }
342 :
343 : // Assign data.
344 235 : m_pList[m_aHead.m_nNext].m_nHash = m_pHash[nSI].m_nHash = h;
345 235 : move (nSI, nDI);
346 : }
347 235 : }
348 :
349 : /*
350 : * queryUrl.
351 : */
352 8 : sal_Bool INetURLHistory_Impl::queryUrl (const String &rUrl)
353 : {
354 8 : sal_uInt32 h = crc32 (rUrl);
355 8 : sal_uInt16 k = find (h);
356 8 : if ((k < capacity()) && (m_pHash[k] == h))
357 : {
358 : // Cache hit.
359 0 : return sal_True;
360 : }
361 : else
362 : {
363 : // Cache miss.
364 8 : return sal_False;
365 : }
366 : }
367 :
368 : /*========================================================================
369 : *
370 : * INetURLHistory::StaticInstance implementation.
371 : *
372 : *======================================================================*/
373 8 : INetURLHistory * INetURLHistory::StaticInstance::operator ()()
374 : {
375 8 : static INetURLHistory g_aInstance;
376 8 : return &g_aInstance;
377 : }
378 :
379 : /*========================================================================
380 : *
381 : * INetURLHistory implementation.
382 : *
383 : *======================================================================*/
384 : /*
385 : * INetURLHistory.
386 : */
387 8 : INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
388 : {
389 8 : }
390 :
391 : /*
392 : * ~INetURLHistory.
393 : */
394 16 : INetURLHistory::~INetURLHistory()
395 : {
396 8 : DELETEZ (m_pImpl);
397 8 : }
398 :
399 : /*
400 : * GetOrCreate.
401 : */
402 253 : INetURLHistory* INetURLHistory::GetOrCreate()
403 : {
404 : return rtl_Instance<
405 : INetURLHistory, StaticInstance,
406 : osl::MutexGuard, osl::GetGlobalMutex >::create (
407 253 : StaticInstance(), osl::GetGlobalMutex());
408 : }
409 :
410 : /*
411 : * NormalizeUrl_Impl.
412 : */
413 243 : void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl)
414 : {
415 243 : switch (rUrl.GetProtocol())
416 : {
417 : case INET_PROT_FILE:
418 235 : 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 235 : 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 8 : if (!rUrl.HasPort())
433 8 : rUrl.SetPort (INETHIST_DEF_HTTP_PORT);
434 8 : if (!rUrl.HasURLPath())
435 0 : rUrl.SetURLPath (rtl::OString("/"));
436 8 : 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 243 : }
449 :
450 : /*
451 : * PutUrl_Impl.
452 : */
453 235 : void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl)
454 : {
455 : DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation");
456 235 : if (m_pImpl)
457 : {
458 235 : INetURLObject aHistUrl (rUrl);
459 235 : NormalizeUrl_Impl (aHistUrl);
460 :
461 235 : m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
462 235 : Broadcast (INetURLHistoryHint (&rUrl));
463 :
464 235 : 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 235 : }
472 : }
473 235 : }
474 :
475 : /*
476 : * QueryUrl_Impl.
477 : */
478 8 : sal_Bool INetURLHistory::QueryUrl_Impl (const INetURLObject &rUrl)
479 : {
480 : DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation");
481 8 : if (m_pImpl)
482 : {
483 8 : INetURLObject aHistUrl (rUrl);
484 8 : NormalizeUrl_Impl (aHistUrl);
485 :
486 8 : return m_pImpl->queryUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
487 : }
488 0 : return sal_False;
489 : }
490 :
491 :
492 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
