svl/source/misc/inethist.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <svl/inethist.hxx>
  21
  22 #include <algorithm>
  23 #include <string.h>
  24
  25 #include <rtl/instance.hxx>
  26 #include <rtl/crc.h>
  27 #include <osl/getglobalmutex.hxx>
  28 #include <tools/solar.h>
  29 #include <tools/debug.hxx>
  30 #include <tools/urlobj.hxx>
  31
  32 /*
  33  * INetURLHistory internals.
  34  */
  35 #define INETHIST_DEF_FTP_PORT    21
  36 #define INETHIST_DEF_HTTP_PORT   80
  37 #define INETHIST_DEF_HTTPS_PORT 443
  38
  39 #define INETHIST_SIZE_LIMIT   1024
  40 #define INETHIST_MAGIC_HEAD   0x484D4849UL
  41
  42 class INetURLHistory_Impl
  43 {
  44     struct head_entry
  45     {
  46         /** Representation.
  47         */
  48         sal_uInt32 m_nMagic;
  49         sal_uInt16 m_nNext;
  50
  51         /** Initialization.
  52         */
  53         void initialize()
  54         {
  55             m_nMagic = INETHIST_MAGIC_HEAD;
  56             m_nNext  = 0;
  57         }
  58     };
  59
  60     struct hash_entry
  61     {
  62         /** Representation.
  63         */
  64         sal_uInt32 m_nHash;
  65         sal_uInt16 m_nLru;
  66
  67         /** Initialization.
  68         */
  69         void initialize (sal_uInt16 nLru)
  70         {
  71             m_nHash = 0;
  72             m_nLru  = nLru;
  73         }
  74
  75         /** Comparison.
  76         */
  77         bool operator== (sal_uInt32 nHash) const
  78         {
  79             return (m_nHash == nHash);
  80         }
  81         bool operator< (sal_uInt32 nHash) const
  82         {
  83             return (m_nHash < nHash);
  84         }
  85     };
  86
  87     struct lru_entry
  88     {
  89         /** Representation.
  90         */
  91         sal_uInt32 m_nHash;
  92         sal_uInt16 m_nNext;
  93         sal_uInt16 m_nPrev;
  94
  95         /** Initialization.
  96         */
  97         void initialize (sal_uInt16 nThis)
  98         {
  99             m_nHash = 0;
 100             m_nNext = nThis;
 101             m_nPrev = nThis;
 102         }
 103     };
 104
 105     /** Representation.
 106     */
 107     head_entry m_aHead;
 108     hash_entry m_pHash[INETHIST_SIZE_LIMIT];
 109     lru_entry  m_pList[INETHIST_SIZE_LIMIT];
 110
 111     /** Initialization.
 112     */
 113     void initialize();
 114
 115     static sal_uInt16 capacity()
 116     {
 117         return sal_uInt16(INETHIST_SIZE_LIMIT);
 118     }
 119
 120     static sal_uInt32 crc32 (OUString const & rData)
 121     {
 122         return rtl_crc32 (0, rData.getStr(), rData.getLength() * sizeof(sal_Unicode));
 123     }
 124
 125     sal_uInt16 find (sal_uInt32 nHash) const;
 126
 127     void move (sal_uInt16 nSI, sal_uInt16 nDI);
 128
 129     void backlink (sal_uInt16 nThis, sal_uInt16 nTail)
 130     {
 131         lru_entry &rThis = m_pList[nThis];
 132         lru_entry &rTail = m_pList[nTail];
 133
 134         rTail.m_nNext = nThis;
 135         rTail.m_nPrev = rThis.m_nPrev;
 136         rThis.m_nPrev = nTail;
 137         m_pList[rTail.m_nPrev].m_nNext = nTail;
 138     }
 139
 140     void unlink (sal_uInt16 nThis)
 141     {
 142         lru_entry &rThis = m_pList[nThis];
 143
 144         m_pList[rThis.m_nPrev].m_nNext = rThis.m_nNext;
 145         m_pList[rThis.m_nNext].m_nPrev = rThis.m_nPrev;
 146         rThis.m_nNext = nThis;
 147         rThis.m_nPrev = nThis;
 148     }
 149
 150 public:
 151     INetURLHistory_Impl();
 152     INetURLHistory_Impl(const INetURLHistory_Impl&) = delete;
 153     INetURLHistory_Impl& operator=(const INetURLHistory_Impl&) = delete;
 154
 155     /** putUrl/queryUrl.
 156     */
 157     void putUrl   (const OUString &rUrl);
 158     bool queryUrl (const OUString &rUrl) const;
 159 };
 160
 161 INetURLHistory_Impl::INetURLHistory_Impl()
 162 {
 163     initialize();
 164 }
 165
 166 void INetURLHistory_Impl::initialize()
 167 {
 168     m_aHead.initialize();
 169
 170     sal_uInt16 i, n = capacity();
 171     for (i = 0; i < n; i++)
 172         m_pHash[i].initialize(i);
 173     for (i = 0; i < n; i++)
 174         m_pList[i].initialize(i);
 175     for (i = 1; i < n; i++)
 176         backlink (m_aHead.m_nNext, i);
 177 }
 178
 179 sal_uInt16 INetURLHistory_Impl::find (sal_uInt32 nHash) const
 180 {
 181     sal_uInt16 l = 0;
 182     sal_uInt16 r = capacity() - 1;
 183     sal_uInt16 c = capacity();
 184
 185     while ((l < r) && (r < c))
 186     {
 187         sal_uInt16 m = (l + r) / 2;
 188         if (m_pHash[m] == nHash)
 189             return m;
 190
 191         if (m_pHash[m] < nHash)
 192             l = m + 1;
 193         else
 194             r = m - 1;
 195     }
 196     return l;
 197 }
 198
 199 void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI)
 200 {
 201     hash_entry e = m_pHash[nSI];
 202     if (nSI < nDI)
 203     {
 204         // shift left.
 205         memmove (
 206             &m_pHash[nSI    ],
 207             &m_pHash[nSI + 1],
 208             (nDI - nSI) * sizeof(hash_entry));
 209     }
 210     if (nSI > nDI)
 211     {
 212         // shift right.
 213         memmove (
 214             &m_pHash[nDI + 1],
 215             &m_pHash[nDI    ],
 216             (nSI - nDI) * sizeof(hash_entry));
 217     }
 218     m_pHash[nDI] = e;
 219 }
 220
 221 void INetURLHistory_Impl::putUrl (const OUString &rUrl)
 222 {
 223     sal_uInt32 h = crc32 (rUrl);
 224     sal_uInt16 k = find (h);
 225     if ((k < capacity()) && (m_pHash[k] == h))
 226     {
 227         // Cache hit.
 228         sal_uInt16 nMRU = m_pHash[k].m_nLru;
 229         if (nMRU != m_aHead.m_nNext)
 230         {
 231             // Update LRU chain.
 232             unlink (nMRU);
 233             backlink (m_aHead.m_nNext, nMRU);
 234
 235             // Rotate LRU chain.
 236             m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
 237         }
 238     }
 239     else
 240     {
 241         // Cache miss. Obtain least recently used.
 242         sal_uInt16 nLRU = m_pList[m_aHead.m_nNext].m_nPrev;
 243
 244         sal_uInt16 nSI = find (m_pList[nLRU].m_nHash);
 245         if (nLRU != m_pHash[nSI].m_nLru)
 246         {
 247             // Update LRU chain.
 248             nLRU = m_pHash[nSI].m_nLru;
 249             unlink (nLRU);
 250             backlink (m_aHead.m_nNext, nLRU);
 251         }
 252
 253         // Rotate LRU chain.
 254         m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
 255
 256         // Check source and destination.
 257         sal_uInt16 nDI = std::min (k, sal_uInt16(capacity() - 1));
 258         if (nSI < nDI)
 259         {
 260             if (!(m_pHash[nDI] < h))
 261                 nDI -= 1;
 262         }
 263         if (nDI < nSI)
 264         {
 265             if (m_pHash[nDI] < h)
 266                 nDI += 1;
 267         }
 268
 269         // Assign data.
 270         m_pList[m_aHead.m_nNext].m_nHash = m_pHash[nSI].m_nHash = h;
 271         move (nSI, nDI);
 272     }
 273 }
 274
 275 bool INetURLHistory_Impl::queryUrl (const OUString &rUrl) const
 276 {
 277     sal_uInt32 h = crc32 (rUrl);
 278     sal_uInt16 k = find (h);
 279     // true if cache hit
 280     return (k < capacity()) && (m_pHash[k] == h);
 281 }
 282
 283 /*
 284  * INetURLHistory::StaticInstance implementation.
 285  */
 286 INetURLHistory * INetURLHistory::StaticInstance::operator ()()
 287 {
 288     static INetURLHistory g_aInstance;
 289     return &g_aInstance;
 290 }
 291
 292 INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
 293 {
 294 }
 295
 296 INetURLHistory::~INetURLHistory()
 297 {
 298 }
 299
 300 /*
 301  * GetOrCreate.
 302  */
 303 INetURLHistory* INetURLHistory::GetOrCreate()
 304 {
 305     return rtl_Instance<
 306         INetURLHistory, StaticInstance,
 307         osl::MutexGuard, osl::GetGlobalMutex >::create (
 308             StaticInstance(), osl::GetGlobalMutex());
 309 }
 310
 311 void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl)
 312 {
 313     switch (rUrl.GetProtocol())
 314     {
 315         case INetProtocol::File:
 316             if (!INetURLObject::IsCaseSensitive())
 317             {
 318                 OUString aPath (rUrl.GetURLPath(INetURLObject::DecodeMechanism::NONE).toAsciiLowerCase());
 319                 rUrl.SetURLPath (aPath, INetURLObject::EncodeMechanism::NotCanonical);
 320             }
 321             break;
 322
 323         case INetProtocol::Ftp:
 324             if (!rUrl.HasPort())
 325                 rUrl.SetPort (INETHIST_DEF_FTP_PORT);
 326             break;
 327
 328         case INetProtocol::Http:
 329             if (!rUrl.HasPort())
 330                 rUrl.SetPort (INETHIST_DEF_HTTP_PORT);
 331             if (!rUrl.HasURLPath())
 332                 rUrl.SetURLPath("/");
 333             break;
 334
 335         case INetProtocol::Https:
 336             if (!rUrl.HasPort())
 337                 rUrl.SetPort (INETHIST_DEF_HTTPS_PORT);
 338             if (!rUrl.HasURLPath())
 339                 rUrl.SetURLPath("/");
 340             break;
 341
 342         default:
 343             break;
 344     }
 345 }
 346
 347 void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl)
 348 {
 349     DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation");
 350     if (!m_pImpl)
 351         return;
 352
 353     INetURLObject aHistUrl (rUrl);
 354     NormalizeUrl_Impl (aHistUrl);
 355
 356     m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::DecodeMechanism::NONE));
 357     Broadcast (INetURLHistoryHint (&rUrl));
 358
 359     if (aHistUrl.HasMark())
 360     {
 361         aHistUrl.SetURL (aHistUrl.GetURLNoMark(INetURLObject::DecodeMechanism::NONE),
 362                          INetURLObject::EncodeMechanism::NotCanonical);
 363
 364         m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::DecodeMechanism::NONE));
 365         Broadcast (INetURLHistoryHint (&aHistUrl));
 366     }
 367 }
 368
 369 bool INetURLHistory::QueryUrl_Impl (const INetURLObject &rUrl)
 370 {
 371     DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation");
 372     if (m_pImpl)
 373     {
 374         INetURLObject aHistUrl (rUrl);
 375         NormalizeUrl_Impl (aHistUrl);
 376
 377         return m_pImpl->queryUrl (aHistUrl.GetMainURL(INetURLObject::DecodeMechanism::NONE));
 378     }
 379     return false;
 380 }
 381
 382
 383 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */