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