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