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 : * INetURLHistory internals.
34 : */
35 : #define INETHIST_DEF_FTP_PORT 21
36 : #define INETHIST_DEF_HTTP_PORT 80
37 : #define INETHIST_DEF_HTTPS_PORT 443
38 :
39 : #define INETHIST_SIZE_LIMIT 1024
40 : #define INETHIST_MAGIC_HEAD 0x484D4849UL
41 :
42 : /*
43 : * INetURLHistoryHint implementation.
44 : */
45 7980 : IMPL_PTRHINT (INetURLHistoryHint, const INetURLObject);
46 :
47 : class INetURLHistory_Impl: private boost::noncopyable
48 : {
49 : struct head_entry
50 : {
51 : /** Representation.
52 : */
53 : sal_uInt32 m_nMagic;
54 : sal_uInt16 m_nNext;
55 : sal_uInt16 m_nMBZ;
56 :
57 : /** Initialization.
58 : */
59 100 : void initialize (void)
60 : {
61 100 : m_nMagic = INETHIST_MAGIC_HEAD;
62 100 : m_nNext = 0;
63 100 : m_nMBZ = 0;
64 100 : }
65 : };
66 :
67 : struct hash_entry
68 : {
69 : /** Representation.
70 : */
71 : sal_uInt32 m_nHash;
72 : sal_uInt16 m_nLru;
73 : sal_uInt16 m_nMBZ;
74 :
75 : /** Initialization.
76 : */
77 102400 : void initialize (sal_uInt16 nLru, sal_uInt32 nHash = 0)
78 : {
79 102400 : m_nHash = nHash;
80 102400 : m_nLru = nLru;
81 102400 : m_nMBZ = 0;
82 102400 : }
83 :
84 : /** Comparison.
85 : */
86 71112 : bool operator== (sal_uInt32 nHash) const
87 : {
88 71112 : return (m_nHash == nHash);
89 : }
90 63972 : bool operator< (sal_uInt32 nHash) const
91 : {
92 63972 : return (m_nHash < nHash);
93 : }
94 : };
95 :
96 : struct lru_entry
97 : {
98 : /** Representation.
99 : */
100 : sal_uInt32 m_nHash;
101 : sal_uInt16 m_nNext;
102 : sal_uInt16 m_nPrev;
103 :
104 : /** Initialization.
105 : */
106 102400 : void initialize (sal_uInt16 nThis, sal_uInt32 nHash = 0)
107 : {
108 102400 : m_nHash = nHash;
109 102400 : m_nNext = nThis;
110 102400 : m_nPrev = nThis;
111 102400 : }
112 : };
113 :
114 : /** Representation.
115 : */
116 : head_entry m_aHead;
117 : hash_entry m_pHash[INETHIST_SIZE_LIMIT];
118 : lru_entry m_pList[INETHIST_SIZE_LIMIT];
119 :
120 : /** Initialization.
121 : */
122 : void initialize (void);
123 :
124 29410 : sal_uInt16 capacity (void) const
125 : {
126 29410 : return (sal_uInt16)(INETHIST_SIZE_LIMIT);
127 : }
128 :
129 6710 : sal_uInt32 crc32 (OUString const & rData) const
130 : {
131 6710 : return rtl_crc32 (0, rData.getStr(), rData.getLength() * sizeof(sal_Unicode));
132 : }
133 :
134 : sal_uInt16 find (sal_uInt32 nHash) const;
135 :
136 : void move (sal_uInt16 nSI, sal_uInt16 nDI);
137 :
138 105380 : void backlink (sal_uInt16 nThis, sal_uInt16 nTail)
139 : {
140 105380 : lru_entry &rThis = m_pList[nThis];
141 105380 : lru_entry &rTail = m_pList[nTail];
142 :
143 105380 : rTail.m_nNext = nThis;
144 105380 : rTail.m_nPrev = rThis.m_nPrev;
145 105380 : rThis.m_nPrev = nTail;
146 105380 : m_pList[rTail.m_nPrev].m_nNext = nTail;
147 105380 : }
148 :
149 3080 : void unlink (sal_uInt16 nThis)
150 : {
151 3080 : lru_entry &rThis = m_pList[nThis];
152 :
153 3080 : m_pList[rThis.m_nPrev].m_nNext = rThis.m_nNext;
154 3080 : m_pList[rThis.m_nNext].m_nPrev = rThis.m_nPrev;
155 3080 : rThis.m_nNext = nThis;
156 3080 : rThis.m_nPrev = nThis;
157 3080 : }
158 :
159 : public:
160 : INetURLHistory_Impl (void);
161 : ~INetURLHistory_Impl (void);
162 :
163 : /** putUrl/queryUrl.
164 : */
165 : void putUrl (const OUString &rUrl);
166 : bool queryUrl (const OUString &rUrl);
167 : };
168 :
169 100 : INetURLHistory_Impl::INetURLHistory_Impl (void)
170 : {
171 100 : initialize();
172 100 : }
173 :
174 100 : INetURLHistory_Impl::~INetURLHistory_Impl (void)
175 : {
176 100 : }
177 :
178 100 : void INetURLHistory_Impl::initialize (void)
179 : {
180 100 : m_aHead.initialize();
181 :
182 100 : sal_uInt16 i, n = capacity();
183 102500 : for (i = 0; i < n; i++)
184 102400 : m_pHash[i].initialize(i);
185 102500 : for (i = 0; i < n; i++)
186 102400 : m_pList[i].initialize(i);
187 102400 : for (i = 1; i < n; i++)
188 102300 : backlink (m_aHead.m_nNext, i);
189 100 : }
190 :
191 9770 : sal_uInt16 INetURLHistory_Impl::find (sal_uInt32 nHash) const
192 : {
193 9770 : sal_uInt16 l = 0;
194 9770 : sal_uInt16 r = capacity() - 1;
195 9770 : sal_uInt16 c = capacity();
196 :
197 80452 : while ((l < r) && (r < c))
198 : {
199 64402 : sal_uInt16 m = (l + r) / 2;
200 64402 : if (m_pHash[m] == nHash)
201 3490 : return m;
202 :
203 60912 : if (m_pHash[m] < nHash)
204 49739 : l = m + 1;
205 : else
206 11173 : r = m - 1;
207 : }
208 6280 : return l;
209 : }
210 :
211 3060 : void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI)
212 : {
213 3060 : hash_entry e = m_pHash[nSI];
214 3060 : if (nSI < nDI)
215 : {
216 : // shift left.
217 : memmove (
218 3060 : &m_pHash[nSI ],
219 3060 : &m_pHash[nSI + 1],
220 9180 : (nDI - nSI) * sizeof(hash_entry));
221 : }
222 3060 : if (nSI > nDI)
223 : {
224 : // shift right.
225 : memmove (
226 0 : &m_pHash[nDI + 1],
227 0 : &m_pHash[nDI ],
228 0 : (nSI - nDI) * sizeof(hash_entry));
229 : }
230 3060 : m_pHash[nDI] = e;
231 3060 : }
232 :
233 3990 : void INetURLHistory_Impl::putUrl (const OUString &rUrl)
234 : {
235 3990 : sal_uInt32 h = crc32 (rUrl);
236 3990 : sal_uInt16 k = find (h);
237 3990 : if ((k < capacity()) && (m_pHash[k] == h))
238 : {
239 : // Cache hit.
240 930 : sal_uInt16 nMRU = m_pHash[k].m_nLru;
241 930 : if (nMRU != m_aHead.m_nNext)
242 : {
243 : // Update LRU chain.
244 20 : unlink (nMRU);
245 20 : backlink (m_aHead.m_nNext, nMRU);
246 :
247 : // Rotate LRU chain.
248 20 : m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
249 : }
250 : }
251 : else
252 : {
253 : // Cache miss. Obtain least recently used.
254 3060 : sal_uInt16 nLRU = m_pList[m_aHead.m_nNext].m_nPrev;
255 :
256 3060 : sal_uInt16 nSI = find (m_pList[nLRU].m_nHash);
257 3060 : if (!(nLRU == m_pHash[nSI].m_nLru))
258 : {
259 : // Update LRU chain.
260 3060 : nLRU = m_pHash[nSI].m_nLru;
261 3060 : unlink (nLRU);
262 3060 : backlink (m_aHead.m_nNext, nLRU);
263 : }
264 :
265 : // Rotate LRU chain.
266 3060 : m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
267 :
268 : // Check source and destination.
269 3060 : sal_uInt16 nDI = std::min (k, sal_uInt16(capacity() - 1));
270 3060 : if (nSI < nDI)
271 : {
272 3060 : if (!(m_pHash[nDI] < h))
273 1524 : nDI -= 1;
274 : }
275 3060 : if (nDI < nSI)
276 : {
277 0 : if (m_pHash[nDI] < h)
278 0 : nDI += 1;
279 : }
280 :
281 : // Assign data.
282 3060 : m_pList[m_aHead.m_nNext].m_nHash = m_pHash[nSI].m_nHash = h;
283 3060 : move (nSI, nDI);
284 : }
285 3990 : }
286 :
287 2720 : bool INetURLHistory_Impl::queryUrl (const OUString &rUrl)
288 : {
289 2720 : sal_uInt32 h = crc32 (rUrl);
290 2720 : sal_uInt16 k = find (h);
291 2720 : if ((k < capacity()) && (m_pHash[k] == h))
292 : {
293 : // Cache hit.
294 0 : return true;
295 : }
296 : else
297 : {
298 : // Cache miss.
299 2720 : return false;
300 : }
301 : }
302 :
303 : /*
304 : * INetURLHistory::StaticInstance implementation.
305 : */
306 100 : INetURLHistory * INetURLHistory::StaticInstance::operator ()()
307 : {
308 100 : static INetURLHistory g_aInstance;
309 100 : return &g_aInstance;
310 : }
311 :
312 100 : INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
313 : {
314 100 : }
315 :
316 200 : INetURLHistory::~INetURLHistory()
317 : {
318 100 : DELETEZ (m_pImpl);
319 100 : }
320 :
321 : /*
322 : * GetOrCreate.
323 : */
324 7468 : INetURLHistory* INetURLHistory::GetOrCreate()
325 : {
326 : return rtl_Instance<
327 : INetURLHistory, StaticInstance,
328 : osl::MutexGuard, osl::GetGlobalMutex >::create (
329 7468 : StaticInstance(), osl::GetGlobalMutex());
330 : }
331 :
332 6710 : void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl)
333 : {
334 6710 : switch (rUrl.GetProtocol())
335 : {
336 : case INET_PROT_FILE:
337 5924 : if (!rUrl.IsCaseSensitive())
338 : {
339 0 : OUString aPath (rUrl.GetURLPath(INetURLObject::NO_DECODE).toAsciiLowerCase());
340 0 : rUrl.SetURLPath (aPath, INetURLObject::NOT_CANONIC);
341 : }
342 5924 : break;
343 :
344 : case INET_PROT_FTP:
345 0 : if (!rUrl.HasPort())
346 0 : rUrl.SetPort (INETHIST_DEF_FTP_PORT);
347 0 : break;
348 :
349 : case INET_PROT_HTTP:
350 780 : if (!rUrl.HasPort())
351 780 : rUrl.SetPort (INETHIST_DEF_HTTP_PORT);
352 780 : if (!rUrl.HasURLPath())
353 0 : rUrl.SetURLPath("/");
354 780 : break;
355 :
356 : case INET_PROT_HTTPS:
357 6 : if (!rUrl.HasPort())
358 6 : rUrl.SetPort (INETHIST_DEF_HTTPS_PORT);
359 6 : if (!rUrl.HasURLPath())
360 0 : rUrl.SetURLPath("/");
361 6 : break;
362 :
363 : default:
364 0 : break;
365 : }
366 6710 : }
367 :
368 3990 : void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl)
369 : {
370 : DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation");
371 3990 : if (m_pImpl)
372 : {
373 3990 : INetURLObject aHistUrl (rUrl);
374 3990 : NormalizeUrl_Impl (aHistUrl);
375 :
376 3990 : m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
377 3990 : Broadcast (INetURLHistoryHint (&rUrl));
378 :
379 3990 : if (aHistUrl.HasMark())
380 : {
381 : aHistUrl.SetURL (aHistUrl.GetURLNoMark(INetURLObject::NO_DECODE),
382 0 : INetURLObject::NOT_CANONIC);
383 :
384 0 : m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
385 0 : Broadcast (INetURLHistoryHint (&aHistUrl));
386 3990 : }
387 : }
388 3990 : }
389 :
390 2720 : bool INetURLHistory::QueryUrl_Impl (const INetURLObject &rUrl)
391 : {
392 : DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation");
393 2720 : if (m_pImpl)
394 : {
395 2720 : INetURLObject aHistUrl (rUrl);
396 2720 : NormalizeUrl_Impl (aHistUrl);
397 :
398 2720 : return m_pImpl->queryUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
399 : }
400 0 : return false;
401 : }
402 :
403 :
404 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
