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