1 /**************************************************************
2 *
3 * Licensed to the Apache Software Foundation (ASF) under one
4 * or more contributor license agreements. See the NOTICE file
5 * distributed with this work for additional information
6 * regarding copyright ownership. The ASF licenses this file
7 * to you under the Apache License, Version 2.0 (the
8 * "License"); you may not use this file except in compliance
9 * with the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing,
14 * software distributed under the License is distributed on an
15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 * KIND, either express or implied. See the License for the
17 * specific language governing permissions and limitations
18 * under the License.
19 *
20 *************************************************************/
21
22
23
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_svl.hxx"
26 #include <svl/inethist.hxx>
27
28 #ifndef INCLUDED_ALGORITHM
29 #include <algorithm>
30 #define INCLUDED_ALGORITHM
31 #endif
32 #include "rtl/instance.hxx"
33 #include "rtl/crc.h"
34 #include "rtl/memory.h"
35 #include <tools/solar.h>
36 #include <tools/debug.hxx>
37 #include <tools/string.hxx>
38 #include <tools/urlobj.hxx>
39
40 /*========================================================================
41 *
42 * INetURLHistory internals.
43 *
44 *======================================================================*/
45 #define INETHIST_DEF_FTP_PORT 21
46 #define INETHIST_DEF_HTTP_PORT 80
47 #define INETHIST_DEF_HTTPS_PORT 443
48
49 #define INETHIST_SIZE_LIMIT 1024
50 #define INETHIST_MAGIC_HEAD 0x484D4849UL
51
52 /*
53 * INetURLHistoryHint implementation.
54 */
55 IMPL_PTRHINT (INetURLHistoryHint, const INetURLObject);
56
57 /*========================================================================
58 *
59 * INetURLHistory_Impl interface.
60 *
61 *======================================================================*/
62 class INetURLHistory_Impl
63 {
64 /** head_entry.
65 */
66 struct head_entry
67 {
68 /** Representation.
69 */
70 sal_uInt32 m_nMagic;
71 sal_uInt16 m_nNext;
72 sal_uInt16 m_nMBZ;
73
74 /** Initialization.
75 */
initializeINetURLHistory_Impl::head_entry76 void initialize (void)
77 {
78 m_nMagic = INETHIST_MAGIC_HEAD;
79 m_nNext = 0;
80 m_nMBZ = 0;
81 }
82 };
83
84 /** hash_entry.
85 */
86 struct hash_entry
87 {
88 /** Representation.
89 */
90 sal_uInt32 m_nHash;
91 sal_uInt16 m_nLru;
92 sal_uInt16 m_nMBZ;
93
94 /** Initialization.
95 */
initializeINetURLHistory_Impl::hash_entry96 void initialize (sal_uInt16 nLru, sal_uInt32 nHash = 0)
97 {
98 m_nHash = nHash;
99 m_nLru = nLru;
100 m_nMBZ = 0;
101 }
102
103 /** Comparison.
104 */
operator ==INetURLHistory_Impl::hash_entry105 sal_Bool operator== (const hash_entry &rOther) const
106 {
107 return (m_nHash == rOther.m_nHash);
108 }
operator <INetURLHistory_Impl::hash_entry109 sal_Bool operator< (const hash_entry &rOther) const
110 {
111 return (m_nHash < rOther.m_nHash);
112 }
113
operator ==INetURLHistory_Impl::hash_entry114 sal_Bool operator== (sal_uInt32 nHash) const
115 {
116 return (m_nHash == nHash);
117 }
operator <INetURLHistory_Impl::hash_entry118 sal_Bool operator< (sal_uInt32 nHash) const
119 {
120 return (m_nHash < nHash);
121 }
122 };
123
124 /** lru_entry.
125 */
126 struct lru_entry
127 {
128 /** Representation.
129 */
130 sal_uInt32 m_nHash;
131 sal_uInt16 m_nNext;
132 sal_uInt16 m_nPrev;
133
134 /** Initialization.
135 */
initializeINetURLHistory_Impl::lru_entry136 void initialize (sal_uInt16 nThis, sal_uInt32 nHash = 0)
137 {
138 m_nHash = nHash;
139 m_nNext = nThis;
140 m_nPrev = nThis;
141 }
142 };
143
144 /** Representation.
145 */
146 head_entry m_aHead;
147 hash_entry m_pHash[INETHIST_SIZE_LIMIT];
148 lru_entry m_pList[INETHIST_SIZE_LIMIT];
149
150 /** Initialization.
151 */
152 void initialize (void);
153
154 void downheap (hash_entry a[], sal_uInt16 n, sal_uInt16 k);
155 void heapsort (hash_entry a[], sal_uInt16 n);
156
157 /** capacity.
158 */
capacity(void) const159 sal_uInt16 capacity (void) const
160 {
161 return (sal_uInt16)(INETHIST_SIZE_LIMIT);
162 }
163
164 /** crc32.
165 */
crc32(UniString const & rData) const166 sal_uInt32 crc32 (UniString const & rData) const
167 {
168 return rtl_crc32 (0, rData.GetBuffer(), rData.Len() * sizeof(sal_Unicode));
169 }
170
171 /** find.
172 */
173 sal_uInt16 find (sal_uInt32 nHash) const;
174
175 /** move.
176 */
177 void move (sal_uInt16 nSI, sal_uInt16 nDI);
178
179 /** backlink.
180 */
backlink(sal_uInt16 nThis,sal_uInt16 nTail)181 void backlink (sal_uInt16 nThis, sal_uInt16 nTail)
182 {
183 register lru_entry &rThis = m_pList[nThis];
184 register lru_entry &rTail = m_pList[nTail];
185
186 rTail.m_nNext = nThis;
187 rTail.m_nPrev = rThis.m_nPrev;
188 rThis.m_nPrev = nTail;
189 m_pList[rTail.m_nPrev].m_nNext = nTail;
190 }
191
192 /** unlink.
193 */
unlink(sal_uInt16 nThis)194 void unlink (sal_uInt16 nThis)
195 {
196 register lru_entry &rThis = m_pList[nThis];
197
198 m_pList[rThis.m_nPrev].m_nNext = rThis.m_nNext;
199 m_pList[rThis.m_nNext].m_nPrev = rThis.m_nPrev;
200 rThis.m_nNext = nThis;
201 rThis.m_nPrev = nThis;
202 }
203
204 /** Not implemented.
205 */
206 INetURLHistory_Impl (const INetURLHistory_Impl&);
207 INetURLHistory_Impl& operator= (const INetURLHistory_Impl&);
208
209 public:
210 INetURLHistory_Impl (void);
211 ~INetURLHistory_Impl (void);
212
213 /** putUrl/queryUrl.
214 */
215 void putUrl (const String &rUrl);
216 sal_Bool queryUrl (const String &rUrl);
217 };
218
219 /*========================================================================
220 *
221 * INetURLHistory_Impl implementation.
222 *
223 *======================================================================*/
224 /*
225 * INetURLHistory_Impl.
226 */
INetURLHistory_Impl(void)227 INetURLHistory_Impl::INetURLHistory_Impl (void)
228 {
229 initialize();
230 }
231
232 /*
233 * ~INetURLHistory_Impl.
234 */
~INetURLHistory_Impl(void)235 INetURLHistory_Impl::~INetURLHistory_Impl (void)
236 {
237 }
238
239 /*
240 * initialize.
241 */
initialize(void)242 void INetURLHistory_Impl::initialize (void)
243 {
244 m_aHead.initialize();
245
246 sal_uInt16 i, n = capacity();
247 for (i = 0; i < n; i++)
248 m_pHash[i].initialize(i);
249 for (i = 0; i < n; i++)
250 m_pList[i].initialize(i);
251 for (i = 1; i < n; i++)
252 backlink (m_aHead.m_nNext, i);
253 }
254
255 /*
256 * downheap.
257 */
downheap(hash_entry a[],sal_uInt16 n,sal_uInt16 k)258 void INetURLHistory_Impl::downheap (hash_entry a[], sal_uInt16 n, sal_uInt16 k)
259 {
260 hash_entry h = a[k];
261 while (k < n / 2)
262 {
263 sal_uInt16 i = k + k + 1;
264 if (((i + 1) < n) && (a[i] < a[i + 1])) i++;
265 if (!(h < a[i])) break;
266 a[k] = a[i];
267 k = i;
268 }
269 a[k] = h;
270 }
271
272 /*
273 * heapsort.
274 */
heapsort(hash_entry a[],sal_uInt16 n)275 void INetURLHistory_Impl::heapsort (hash_entry a[], sal_uInt16 n)
276 {
277 hash_entry h;
278
279 for (sal_uInt16 k = (n - 1) / 2 + 1; k > 0; k--)
280 downheap (a, n, k - 1);
281
282 while (n > 0)
283 {
284 h = a[0 ];
285 a[0 ] = a[n - 1];
286 a[n - 1] = h;
287 downheap (a, --n, 0);
288 }
289 }
290
291 /*
292 * find.
293 */
find(sal_uInt32 nHash) const294 sal_uInt16 INetURLHistory_Impl::find (sal_uInt32 nHash) const
295 {
296 sal_uInt16 l = 0;
297 sal_uInt16 r = capacity() - 1;
298 sal_uInt16 c = capacity();
299
300 while ((l < r) && (r < c))
301 {
302 sal_uInt16 m = (l + r) / 2;
303 if (m_pHash[m] == nHash)
304 return m;
305
306 if (m_pHash[m] < nHash)
307 l = m + 1;
308 else
309 r = m - 1;
310 }
311 return l;
312 }
313
314 /*
315 * move.
316 */
move(sal_uInt16 nSI,sal_uInt16 nDI)317 void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI)
318 {
319 hash_entry e = m_pHash[nSI];
320 if (nSI < nDI)
321 {
322 // shift left.
323 rtl_moveMemory (
324 &m_pHash[nSI ],
325 &m_pHash[nSI + 1],
326 (nDI - nSI) * sizeof(hash_entry));
327 }
328 if (nSI > nDI)
329 {
330 // shift right.
331 rtl_moveMemory (
332 &m_pHash[nDI + 1],
333 &m_pHash[nDI ],
334 (nSI - nDI) * sizeof(hash_entry));
335 }
336 m_pHash[nDI] = e;
337 }
338
339 /*
340 * putUrl.
341 */
putUrl(const String & rUrl)342 void INetURLHistory_Impl::putUrl (const String &rUrl)
343 {
344 sal_uInt32 h = crc32 (rUrl);
345 sal_uInt16 k = find (h);
346 if ((k < capacity()) && (m_pHash[k] == h))
347 {
348 // Cache hit.
349 sal_uInt16 nMRU = m_pHash[k].m_nLru;
350 if (nMRU != m_aHead.m_nNext)
351 {
352 // Update LRU chain.
353 unlink (nMRU);
354 backlink (m_aHead.m_nNext, nMRU);
355
356 // Rotate LRU chain.
357 m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
358 }
359 }
360 else
361 {
362 // Cache miss. Obtain least recently used.
363 sal_uInt16 nLRU = m_pList[m_aHead.m_nNext].m_nPrev;
364
365 sal_uInt16 nSI = find (m_pList[nLRU].m_nHash);
366 if (!(nLRU == m_pHash[nSI].m_nLru))
367 {
368 // Update LRU chain.
369 nLRU = m_pHash[nSI].m_nLru;
370 unlink (nLRU);
371 backlink (m_aHead.m_nNext, nLRU);
372 }
373
374 // Rotate LRU chain.
375 m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
376
377 // Check source and destination.
378 sal_uInt16 nDI = std::min (k, sal_uInt16(capacity() - 1));
379 if (nSI < nDI)
380 {
381 if (!(m_pHash[nDI] < h))
382 nDI -= 1;
383 }
384 if (nDI < nSI)
385 {
386 if (m_pHash[nDI] < h)
387 nDI += 1;
388 }
389
390 // Assign data.
391 m_pList[m_aHead.m_nNext].m_nHash = m_pHash[nSI].m_nHash = h;
392 move (nSI, nDI);
393 }
394 }
395
396 /*
397 * queryUrl.
398 */
queryUrl(const String & rUrl)399 sal_Bool INetURLHistory_Impl::queryUrl (const String &rUrl)
400 {
401 sal_uInt32 h = crc32 (rUrl);
402 sal_uInt16 k = find (h);
403 if ((k < capacity()) && (m_pHash[k] == h))
404 {
405 // Cache hit.
406 return sal_True;
407 }
408 else
409 {
410 // Cache miss.
411 return sal_False;
412 }
413 }
414
415 /*========================================================================
416 *
417 * INetURLHistory::StaticInstance implementation.
418 *
419 *======================================================================*/
operator ()()420 INetURLHistory * INetURLHistory::StaticInstance::operator ()()
421 {
422 static INetURLHistory g_aInstance;
423 return &g_aInstance;
424 }
425
426 /*========================================================================
427 *
428 * INetURLHistory implementation.
429 *
430 *======================================================================*/
431 /*
432 * INetURLHistory.
433 */
INetURLHistory()434 INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
435 {
436 }
437
438 /*
439 * ~INetURLHistory.
440 */
~INetURLHistory()441 INetURLHistory::~INetURLHistory()
442 {
443 DELETEZ (m_pImpl);
444 }
445
446 /*
447 * GetOrCreate.
448 */
GetOrCreate()449 INetURLHistory* INetURLHistory::GetOrCreate()
450 {
451 return rtl_Instance<
452 INetURLHistory, StaticInstance,
453 osl::MutexGuard, osl::GetGlobalMutex >::create (
454 StaticInstance(), osl::GetGlobalMutex());
455 }
456
457 /*
458 * NormalizeUrl_Impl.
459 */
NormalizeUrl_Impl(INetURLObject & rUrl)460 void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl)
461 {
462 switch (rUrl.GetProtocol())
463 {
464 case INET_PROT_FILE:
465 if (!rUrl.IsCaseSensitive())
466 {
467 String aPath (rUrl.GetURLPath(INetURLObject::NO_DECODE));
468 aPath.ToLowerAscii();
469 rUrl.SetURLPath (aPath, INetURLObject::NOT_CANONIC);
470 }
471 break;
472
473 case INET_PROT_FTP:
474 if (!rUrl.HasPort())
475 rUrl.SetPort (INETHIST_DEF_FTP_PORT);
476 break;
477
478 case INET_PROT_HTTP:
479 if (!rUrl.HasPort())
480 rUrl.SetPort (INETHIST_DEF_HTTP_PORT);
481 if (!rUrl.HasURLPath())
482 rUrl.SetURLPath ("/");
483 break;
484
485 case INET_PROT_HTTPS:
486 if (!rUrl.HasPort())
487 rUrl.SetPort (INETHIST_DEF_HTTPS_PORT);
488 if (!rUrl.HasURLPath())
489 rUrl.SetURLPath ("/");
490 break;
491
492 default:
493 break;
494 }
495 }
496
497 /*
498 * PutUrl_Impl.
499 */
PutUrl_Impl(const INetURLObject & rUrl)500 void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl)
501 {
502 DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation");
503 if (m_pImpl)
504 {
505 INetURLObject aHistUrl (rUrl);
506 NormalizeUrl_Impl (aHistUrl);
507
508 m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
509 Broadcast (INetURLHistoryHint (&rUrl));
510
511 if (aHistUrl.HasMark())
512 {
513 aHistUrl.SetURL (aHistUrl.GetURLNoMark(INetURLObject::NO_DECODE),
514 INetURLObject::NOT_CANONIC);
515
516 m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
517 Broadcast (INetURLHistoryHint (&aHistUrl));
518 }
519 }
520 }
521
522 /*
523 * QueryUrl_Impl.
524 */
QueryUrl_Impl(const INetURLObject & rUrl)525 sal_Bool INetURLHistory::QueryUrl_Impl (const INetURLObject &rUrl)
526 {
527 DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation");
528 if (m_pImpl)
529 {
530 INetURLObject aHistUrl (rUrl);
531 NormalizeUrl_Impl (aHistUrl);
532
533 return m_pImpl->queryUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
534 }
535 return sal_False;
536 }
537
538
539