xref: /aoo42x/main/svl/source/misc/inethist.cxx (revision 40df464e)
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 		*/
76 		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 		*/
96 		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 		*/
105 		sal_Bool operator== (const hash_entry &rOther) const
106 		{
107 			return (m_nHash == rOther.m_nHash);
108 		}
109 		sal_Bool operator< (const hash_entry &rOther) const
110 		{
111 			return (m_nHash < rOther.m_nHash);
112 		}
113 
114 		sal_Bool operator== (sal_uInt32 nHash) const
115 		{
116 			return (m_nHash == nHash);
117 		}
118 		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 		*/
136 		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 	*/
159 	sal_uInt16 capacity (void) const
160 	{
161 		return (sal_uInt16)(INETHIST_SIZE_LIMIT);
162 	}
163 
164 	/** crc32.
165 	*/
166 	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 	*/
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 	*/
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  */
227 INetURLHistory_Impl::INetURLHistory_Impl (void)
228 {
229 	initialize();
230 }
231 
232 /*
233  * ~INetURLHistory_Impl.
234  */
235 INetURLHistory_Impl::~INetURLHistory_Impl (void)
236 {
237 }
238 
239 /*
240  * initialize.
241  */
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  */
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  */
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  */
294 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  */
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  */
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  */
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  *======================================================================*/
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  */
434 INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
435 {
436 }
437 
438 /*
439  * ~INetURLHistory.
440  */
441 INetURLHistory::~INetURLHistory()
442 {
443 	DELETEZ (m_pImpl);
444 }
445 
446 /*
447  * GetOrCreate.
448  */
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  */
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  */
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  */
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