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