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/crc.h>
  26 #include <tools/debug.hxx>
  27 #include <tools/urlobj.hxx>
  28
  29 /*
  30  * INetURLHistory internals.
  31  */
  32 #define INETHIST_DEF_FTP_PORT    21
  33 #define INETHIST_DEF_HTTP_PORT   80
  34 #define INETHIST_DEF_HTTPS_PORT 443
  35
  36 #define INETHIST_SIZE_LIMIT   1024
  37 #define INETHIST_MAGIC_HEAD   0x484D4849UL
  38
  39 class INetURLHistory_Impl
  40 {
  41     struct head_entry
  42     {
  43         /** Representation.
  44         */
  45         sal_uInt32 m_nMagic;
  46         sal_uInt16 m_nNext;
  47
  48         /** Initialization.
  49         */
  50         void initialize()
  51         {
  52             m_nMagic = INETHIST_MAGIC_HEAD;
  53             m_nNext  = 0;
  54         }
  55     };
  56
  57     struct hash_entry
  58     {
  59         /** Representation.
  60         */
  61         sal_uInt32 m_nHash;
  62         sal_uInt16 m_nLru;
  63
  64         /** Initialization.
  65         */
  66         void initialize (sal_uInt16 nLru)
  67         {
  68             m_nHash = 0;
  69             m_nLru  = nLru;
  70         }
  71
  72         /** Comparison.
  73         */
  74         bool operator== (sal_uInt32 nHash) const
  75         {
  76             return (m_nHash == nHash);
  77         }
  78         bool operator< (sal_uInt32 nHash) const
  79         {
  80             return (m_nHash < nHash);
  81         }
  82     };
  83
  84     struct lru_entry
  85     {
  86         /** Representation.
  87         */
  88         sal_uInt32 m_nHash;
  89         sal_uInt16 m_nNext;
  90         sal_uInt16 m_nPrev;
  91
  92         /** Initialization.
  93         */
  94         void initialize (sal_uInt16 nThis)
  95         {
  96             m_nHash = 0;
  97             m_nNext = nThis;
  98             m_nPrev = nThis;
  99         }
 100     };
 101
 102     /** Representation.
 103     */
 104     head_entry m_aHead;
 105     hash_entry m_pHash[INETHIST_SIZE_LIMIT];
 106     lru_entry  m_pList[INETHIST_SIZE_LIMIT];
 107
 108     /** Initialization.
 109     */
 110     void initialize();
 111
 112     static sal_uInt16 capacity()
 113     {
 114         return sal_uInt16(INETHIST_SIZE_LIMIT);
 115     }
 116
 117     static sal_uInt32 crc32 (OUString const & rData)
 118     {
 119         return rtl_crc32 (0, rData.getStr(), rData.getLength() * sizeof(sal_Unicode));
 120     }
 121
 122     sal_uInt16 find (sal_uInt32 nHash) const;
 123
 124     void move (sal_uInt16 nSI, sal_uInt16 nDI);
 125
 126     void backlink (sal_uInt16 nThis, sal_uInt16 nTail)
 127     {
 128         lru_entry &rThis = m_pList[nThis];
 129         lru_entry &rTail = m_pList[nTail];
 130
 131         rTail.m_nNext = nThis;
 132         rTail.m_nPrev = rThis.m_nPrev;
 133         rThis.m_nPrev = nTail;
 134         m_pList[rTail.m_nPrev].m_nNext = nTail;
 135     }
 136
 137     void unlink (sal_uInt16 nThis)
 138     {
 139         lru_entry &rThis = m_pList[nThis];
 140
 141         m_pList[rThis.m_nPrev].m_nNext = rThis.m_nNext;
 142         m_pList[rThis.m_nNext].m_nPrev = rThis.m_nPrev;
 143         rThis.m_nNext = nThis;
 144         rThis.m_nPrev = nThis;
 145     }
 146
 147 public:
 148     INetURLHistory_Impl();
 149     INetURLHistory_Impl(const INetURLHistory_Impl&) = delete;
 150     INetURLHistory_Impl& operator=(const INetURLHistory_Impl&) = delete;
 151
 152     /** putUrl/queryUrl.
 153     */
 154     void putUrl   (const OUString &rUrl);
 155     bool queryUrl (const OUString &rUrl) const;
 156 };
 157
 158 INetURLHistory_Impl::INetURLHistory_Impl()
 159 {
 160     initialize();
 161 }
 162
 163 void INetURLHistory_Impl::initialize()
 164 {
 165     m_aHead.initialize();
 166
 167     sal_uInt16 i, n = capacity();
 168     for (i = 0; i < n; i++)
 169         m_pHash[i].initialize(i);
 170     for (i = 0; i < n; i++)
 171         m_pList[i].initialize(i);
 172     for (i = 1; i < n; i++)
 173         backlink (m_aHead.m_nNext, i);
 174 }
 175
 176 sal_uInt16 INetURLHistory_Impl::find (sal_uInt32 nHash) const
 177 {
 178     sal_uInt16 l = 0;
 179     sal_uInt16 r = capacity() - 1;
 180     sal_uInt16 c = capacity();
 181
 182     while ((l < r) && (r < c))
 183     {
 184         sal_uInt16 m = ((l + r) / 2) & 0xFFFF;
 185         if (m_pHash[m] == nHash)
 186             return m;
 187
 188         if (m_pHash[m] < nHash)
 189             l = m + 1;
 190         else
 191             r = m - 1;
 192     }
 193     return l;
 194 }
 195
 196 void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI)
 197 {
 198     hash_entry e = m_pHash[nSI];
 199     if (nSI < nDI)
 200     {
 201         // shift left.
 202         memmove (
 203             &m_pHash[nSI    ],
 204             &m_pHash[nSI + 1],
 205             (nDI - nSI) * sizeof(hash_entry));
 206     }
 207     if (nSI > nDI)
 208     {
 209         // shift right.
 210         memmove (
 211             &m_pHash[nDI + 1],
 212             &m_pHash[nDI    ],
 213             (nSI - nDI) * sizeof(hash_entry));
 214     }
 215     m_pHash[nDI] = e;
 216 }
 217
 218 void INetURLHistory_Impl::putUrl (const OUString &rUrl)
 219 {
 220     sal_uInt32 h = crc32 (rUrl);
 221     sal_uInt16 k = find (h);
 222     if ((k < capacity()) && (m_pHash[k] == h))
 223     {
 224         // Cache hit.
 225         sal_uInt16 nMRU = m_pHash[k].m_nLru;
 226         if (nMRU != m_aHead.m_nNext)
 227         {
 228             // Update LRU chain.
 229             unlink (nMRU);
 230             backlink (m_aHead.m_nNext, nMRU);
 231
 232             // Rotate LRU chain.
 233             m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
 234         }
 235     }
 236     else
 237     {
 238         // Cache miss. Obtain least recently used.
 239         sal_uInt16 nLRU = m_pList[m_aHead.m_nNext].m_nPrev;
 240
 241         sal_uInt16 nSI = find (m_pList[nLRU].m_nHash);
 242         if (nLRU != m_pHash[nSI].m_nLru)
 243         {
 244             // Update LRU chain.
 245             nLRU = m_pHash[nSI].m_nLru;
 246             unlink (nLRU);
 247             backlink (m_aHead.m_nNext, nLRU);
 248         }
 249
 250         // Rotate LRU chain.
 251         m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
 252
 253         // Check source and destination.
 254         sal_uInt16 nDI = std::min (k, sal_uInt16(capacity() - 1));
 255         if (nSI < nDI && !(m_pHash[nDI] < h))
 256             nDI -= 1;
 257         if (nDI < nSI && m_pHash[nDI] < h)
 258             nDI += 1;
 259
 260         // Assign data.
 261         m_pList[m_aHead.m_nNext].m_nHash = m_pHash[nSI].m_nHash = h;
 262         move (nSI, nDI);
 263     }
 264 }
 265
 266 bool INetURLHistory_Impl::queryUrl (const OUString &rUrl) const
 267 {
 268     sal_uInt32 h = crc32 (rUrl);
 269     sal_uInt16 k = find (h);
 270     // true if cache hit
 271     return (k < capacity()) && (m_pHash[k] == h);
 272 }
 273
 274 INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
 275 {
 276 }
 277
 278 INetURLHistory::~INetURLHistory()
 279 {
 280 }
 281
 282 /*
 283  * GetOrCreate.
 284  */
 285 INetURLHistory* INetURLHistory::GetOrCreate()
 286 {
 287     static INetURLHistory instance;
 288     return &instance;
 289 }
 290
 291 void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl)
 292 {
 293     switch (rUrl.GetProtocol())
 294     {
 295         case INetProtocol::File:
 296             if (!INetURLObject::IsCaseSensitive())
 297             {
 298                 OUString aPath (rUrl.GetURLPath(INetURLObject::DecodeMechanism::NONE).toAsciiLowerCase());
 299                 rUrl.SetURLPath (aPath, INetURLObject::EncodeMechanism::NotCanonical);
 300             }
 301             break;
 302
 303         case INetProtocol::Ftp:
 304             if (!rUrl.HasPort())
 305                 rUrl.SetPort (INETHIST_DEF_FTP_PORT);
 306             break;
 307
 308         case INetProtocol::Http:
 309             if (!rUrl.HasPort())
 310                 rUrl.SetPort (INETHIST_DEF_HTTP_PORT);
 311             if (!rUrl.HasURLPath())
 312                 rUrl.SetURLPath(u"/");
 313             break;
 314
 315         case INetProtocol::Https:
 316             if (!rUrl.HasPort())
 317                 rUrl.SetPort (INETHIST_DEF_HTTPS_PORT);
 318             if (!rUrl.HasURLPath())
 319                 rUrl.SetURLPath(u"/");
 320             break;
 321
 322         default:
 323             break;
 324     }
 325 }
 326
 327 void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl)
 328 {
 329     DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation");
 330     if (!m_pImpl)
 331         return;
 332
 333     INetURLObject aHistUrl (rUrl);
 334     NormalizeUrl_Impl (aHistUrl);
 335
 336     m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::DecodeMechanism::NONE));
 337     Broadcast (INetURLHistoryHint (&rUrl));
 338
 339     if (aHistUrl.HasMark())
 340     {
 341         aHistUrl.SetURL (aHistUrl.GetURLNoMark(INetURLObject::DecodeMechanism::NONE),
 342                          INetURLObject::EncodeMechanism::NotCanonical);
 343
 344         m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::DecodeMechanism::NONE));
 345         Broadcast (INetURLHistoryHint (&aHistUrl));
 346     }
 347 }
 348
 349 bool INetURLHistory::QueryUrl(std::u16string_view rUrl) const
 350 {
 351     INetProtocol eProto = INetURLObject::CompareProtocolScheme (rUrl);
 352     if (!QueryProtocol (eProto))
 353         return false;
 354     return QueryUrl_Impl( INetURLObject(rUrl) );
 355 }
 356
 357
 358 bool INetURLHistory::QueryUrl_Impl (INetURLObject rUrl) const
 359 {
 360     DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation");
 361     if (m_pImpl)
 362     {
 363         NormalizeUrl_Impl (rUrl);
 364
 365         return m_pImpl->queryUrl (rUrl.GetMainURL(INetURLObject::DecodeMechanism::NONE));
 366     }
 367     return false;
 368 }
 369
 370
 371 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */