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