svtools/source/misc1/inethist.cxx

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