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