LCOV - code coverage report
Current view: top level - libreoffice/svl/source/misc - inethist.cxx (source / functions) Hit Total Coverage
Test: libreoffice_filtered.info Lines: 132 160 82.5 %
Date: 2012-12-27 Functions: 28 32 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       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 <tools/solar.h>
      28             : #include <tools/debug.hxx>
      29             : #include <tools/string.hxx>
      30             : #include <tools/urlobj.hxx>
      31             : 
      32             : /*========================================================================
      33             :  *
      34             :  * INetURLHistory internals.
      35             :  *
      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             : /*
      45             :  * INetURLHistoryHint implementation.
      46             :  */
      47         656 : IMPL_PTRHINT (INetURLHistoryHint, const INetURLObject);
      48             : 
      49             : /*========================================================================
      50             :  *
      51             :  * INetURLHistory_Impl interface.
      52             :  *
      53             :  *======================================================================*/
      54             : class INetURLHistory_Impl
      55             : {
      56             :     /** head_entry.
      57             :     */
      58             :     struct head_entry
      59             :     {
      60             :         /** Representation.
      61             :         */
      62             :         sal_uInt32 m_nMagic;
      63             :         sal_uInt16 m_nNext;
      64             :         sal_uInt16 m_nMBZ;
      65             : 
      66             :         /** Initialization.
      67             :         */
      68           8 :         void initialize (void)
      69             :         {
      70           8 :             m_nMagic = INETHIST_MAGIC_HEAD;
      71           8 :             m_nNext  = 0;
      72           8 :             m_nMBZ   = 0;
      73           8 :         }
      74             :     };
      75             : 
      76             :     /** hash_entry.
      77             :     */
      78             :     struct hash_entry
      79             :     {
      80             :         /** Representation.
      81             :         */
      82             :         sal_uInt32 m_nHash;
      83             :         sal_uInt16 m_nLru;
      84             :         sal_uInt16 m_nMBZ;
      85             : 
      86             :         /** Initialization.
      87             :         */
      88        8192 :         void initialize (sal_uInt16 nLru, sal_uInt32 nHash = 0)
      89             :         {
      90        8192 :             m_nHash = nHash;
      91        8192 :             m_nLru  = nLru;
      92        8192 :             m_nMBZ  = 0;
      93        8192 :         }
      94             : 
      95             :         /** Comparison.
      96             :         */
      97             :         sal_Bool operator== (const hash_entry &rOther) const
      98             :         {
      99             :             return (m_nHash == rOther.m_nHash);
     100             :         }
     101             :         sal_Bool operator< (const hash_entry &rOther) const
     102             :         {
     103             :             return (m_nHash < rOther.m_nHash);
     104             :         }
     105             : 
     106        2729 :         sal_Bool operator== (sal_uInt32 nHash) const
     107             :         {
     108        2729 :             return (m_nHash == nHash);
     109             :         }
     110        2486 :         sal_Bool operator< (sal_uInt32 nHash) const
     111             :         {
     112        2486 :             return (m_nHash < nHash);
     113             :         }
     114             :     };
     115             : 
     116             :     /** lru_entry.
     117             :     */
     118             :     struct lru_entry
     119             :     {
     120             :         /** Representation.
     121             :         */
     122             :         sal_uInt32 m_nHash;
     123             :         sal_uInt16 m_nNext;
     124             :         sal_uInt16 m_nPrev;
     125             : 
     126             :         /** Initialization.
     127             :         */
     128        8192 :         void initialize (sal_uInt16 nThis, sal_uInt32 nHash = 0)
     129             :         {
     130        8192 :             m_nHash = nHash;
     131        8192 :             m_nNext = nThis;
     132        8192 :             m_nPrev = nThis;
     133        8192 :         }
     134             :     };
     135             : 
     136             :     /** Representation.
     137             :     */
     138             :     head_entry m_aHead;
     139             :     hash_entry m_pHash[INETHIST_SIZE_LIMIT];
     140             :     lru_entry  m_pList[INETHIST_SIZE_LIMIT];
     141             : 
     142             :     /** Initialization.
     143             :     */
     144             :     void initialize (void);
     145             : 
     146             :     /** capacity.
     147             :     */
     148        1442 :     sal_uInt16 capacity (void) const
     149             :     {
     150        1442 :         return (sal_uInt16)(INETHIST_SIZE_LIMIT);
     151             :     }
     152             : 
     153             :     /** crc32.
     154             :     */
     155         243 :     sal_uInt32 crc32 (UniString const & rData) const
     156             :     {
     157         243 :         return rtl_crc32 (0, rData.GetBuffer(), rData.Len() * sizeof(sal_Unicode));
     158             :     }
     159             : 
     160             :     /** find.
     161             :     */
     162             :     sal_uInt16 find (sal_uInt32 nHash) const;
     163             : 
     164             :     /** move.
     165             :     */
     166             :     void move (sal_uInt16 nSI, sal_uInt16 nDI);
     167             : 
     168             :     /** backlink.
     169             :     */
     170        8419 :     void backlink (sal_uInt16 nThis, sal_uInt16 nTail)
     171             :     {
     172        8419 :         register lru_entry &rThis = m_pList[nThis];
     173        8419 :         register lru_entry &rTail = m_pList[nTail];
     174             : 
     175        8419 :         rTail.m_nNext = nThis;
     176        8419 :         rTail.m_nPrev = rThis.m_nPrev;
     177        8419 :         rThis.m_nPrev = nTail;
     178        8419 :         m_pList[rTail.m_nPrev].m_nNext = nTail;
     179        8419 :     }
     180             : 
     181             :     /** unlink.
     182             :     */
     183         235 :     void unlink (sal_uInt16 nThis)
     184             :     {
     185         235 :         register lru_entry &rThis = m_pList[nThis];
     186             : 
     187         235 :         m_pList[rThis.m_nPrev].m_nNext = rThis.m_nNext;
     188         235 :         m_pList[rThis.m_nNext].m_nPrev = rThis.m_nPrev;
     189         235 :         rThis.m_nNext = nThis;
     190         235 :         rThis.m_nPrev = nThis;
     191         235 :     }
     192             : 
     193             :     /** Not implemented.
     194             :     */
     195             :     INetURLHistory_Impl (const INetURLHistory_Impl&);
     196             :     INetURLHistory_Impl& operator= (const INetURLHistory_Impl&);
     197             : 
     198             : public:
     199             :     INetURLHistory_Impl (void);
     200             :     ~INetURLHistory_Impl (void);
     201             : 
     202             :     /** putUrl/queryUrl.
     203             :     */
     204             :     void putUrl   (const String &rUrl);
     205             :     sal_Bool queryUrl (const String &rUrl);
     206             : };
     207             : 
     208             : /*========================================================================
     209             :  *
     210             :  * INetURLHistory_Impl implementation.
     211             :  *
     212             :  *======================================================================*/
     213             : /*
     214             :  * INetURLHistory_Impl.
     215             :  */
     216           8 : INetURLHistory_Impl::INetURLHistory_Impl (void)
     217             : {
     218           8 :     initialize();
     219           8 : }
     220             : 
     221             : /*
     222             :  * ~INetURLHistory_Impl.
     223             :  */
     224           8 : INetURLHistory_Impl::~INetURLHistory_Impl (void)
     225             : {
     226           8 : }
     227             : 
     228             : /*
     229             :  * initialize.
     230             :  */
     231           8 : void INetURLHistory_Impl::initialize (void)
     232             : {
     233           8 :     m_aHead.initialize();
     234             : 
     235           8 :     sal_uInt16 i, n = capacity();
     236        8200 :     for (i = 0; i < n; i++)
     237        8192 :         m_pHash[i].initialize(i);
     238        8200 :     for (i = 0; i < n; i++)
     239        8192 :         m_pList[i].initialize(i);
     240        8192 :     for (i = 1; i < n; i++)
     241        8184 :         backlink (m_aHead.m_nNext, i);
     242           8 : }
     243             : 
     244             : /*
     245             :  * find.
     246             :  */
     247         478 : sal_uInt16 INetURLHistory_Impl::find (sal_uInt32 nHash) const
     248             : {
     249         478 :     sal_uInt16 l = 0;
     250         478 :     sal_uInt16 r = capacity() - 1;
     251         478 :     sal_uInt16 c = capacity();
     252             : 
     253        3207 :     while ((l < r) && (r < c))
     254             :     {
     255        2486 :         sal_uInt16 m = (l + r) / 2;
     256        2486 :         if (m_pHash[m] == nHash)
     257         235 :             return m;
     258             : 
     259        2251 :         if (m_pHash[m] < nHash)
     260        1878 :             l = m + 1;
     261             :         else
     262         373 :             r = m - 1;
     263             :     }
     264         243 :     return l;
     265             : }
     266             : 
     267             : /*
     268             :  * move.
     269             :  */
     270         235 : void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI)
     271             : {
     272         235 :     hash_entry e = m_pHash[nSI];
     273         235 :     if (nSI < nDI)
     274             :     {
     275             :         // shift left.
     276             :         memmove (
     277         235 :             &m_pHash[nSI    ],
     278         235 :             &m_pHash[nSI + 1],
     279         705 :             (nDI - nSI) * sizeof(hash_entry));
     280             :     }
     281         235 :     if (nSI > nDI)
     282             :     {
     283             :         // shift right.
     284             :         memmove (
     285           0 :             &m_pHash[nDI + 1],
     286           0 :             &m_pHash[nDI    ],
     287           0 :             (nSI - nDI) * sizeof(hash_entry));
     288             :     }
     289         235 :     m_pHash[nDI] = e;
     290         235 : }
     291             : 
     292             : /*
     293             :  * putUrl.
     294             :  */
     295         235 : void INetURLHistory_Impl::putUrl (const String &rUrl)
     296             : {
     297         235 :     sal_uInt32 h = crc32 (rUrl);
     298         235 :     sal_uInt16 k = find (h);
     299         235 :     if ((k < capacity()) && (m_pHash[k] == h))
     300             :     {
     301             :         // Cache hit.
     302           0 :         sal_uInt16 nMRU = m_pHash[k].m_nLru;
     303           0 :         if (nMRU != m_aHead.m_nNext)
     304             :         {
     305             :             // Update LRU chain.
     306           0 :             unlink (nMRU);
     307           0 :             backlink (m_aHead.m_nNext, nMRU);
     308             : 
     309             :             // Rotate LRU chain.
     310           0 :             m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
     311             :         }
     312             :     }
     313             :     else
     314             :     {
     315             :         // Cache miss. Obtain least recently used.
     316         235 :         sal_uInt16 nLRU = m_pList[m_aHead.m_nNext].m_nPrev;
     317             : 
     318         235 :         sal_uInt16 nSI = find (m_pList[nLRU].m_nHash);
     319         235 :         if (!(nLRU == m_pHash[nSI].m_nLru))
     320             :         {
     321             :             // Update LRU chain.
     322         235 :             nLRU = m_pHash[nSI].m_nLru;
     323         235 :             unlink (nLRU);
     324         235 :             backlink (m_aHead.m_nNext, nLRU);
     325             :         }
     326             : 
     327             :         // Rotate LRU chain.
     328         235 :         m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
     329             : 
     330             :         // Check source and destination.
     331         235 :         sal_uInt16 nDI = std::min (k, sal_uInt16(capacity() - 1));
     332         235 :         if (nSI < nDI)
     333             :         {
     334         235 :             if (!(m_pHash[nDI] < h))
     335         129 :                 nDI -= 1;
     336             :         }
     337         235 :         if (nDI < nSI)
     338             :         {
     339           0 :             if (m_pHash[nDI] < h)
     340           0 :                 nDI += 1;
     341             :         }
     342             : 
     343             :         // Assign data.
     344         235 :         m_pList[m_aHead.m_nNext].m_nHash = m_pHash[nSI].m_nHash = h;
     345         235 :         move (nSI, nDI);
     346             :     }
     347         235 : }
     348             : 
     349             : /*
     350             :  * queryUrl.
     351             :  */
     352           8 : sal_Bool INetURLHistory_Impl::queryUrl (const String &rUrl)
     353             : {
     354           8 :     sal_uInt32 h = crc32 (rUrl);
     355           8 :     sal_uInt16 k = find (h);
     356           8 :     if ((k < capacity()) && (m_pHash[k] == h))
     357             :     {
     358             :         // Cache hit.
     359           0 :         return sal_True;
     360             :     }
     361             :     else
     362             :     {
     363             :         // Cache miss.
     364           8 :         return sal_False;
     365             :     }
     366             : }
     367             : 
     368             : /*========================================================================
     369             :  *
     370             :  * INetURLHistory::StaticInstance implementation.
     371             :  *
     372             :  *======================================================================*/
     373           8 : INetURLHistory * INetURLHistory::StaticInstance::operator ()()
     374             : {
     375           8 :     static INetURLHistory g_aInstance;
     376           8 :     return &g_aInstance;
     377             : }
     378             : 
     379             : /*========================================================================
     380             :  *
     381             :  * INetURLHistory implementation.
     382             :  *
     383             :  *======================================================================*/
     384             : /*
     385             :  * INetURLHistory.
     386             :  */
     387           8 : INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
     388             : {
     389           8 : }
     390             : 
     391             : /*
     392             :  * ~INetURLHistory.
     393             :  */
     394          16 : INetURLHistory::~INetURLHistory()
     395             : {
     396           8 :     DELETEZ (m_pImpl);
     397           8 : }
     398             : 
     399             : /*
     400             :  * GetOrCreate.
     401             :  */
     402         253 : INetURLHistory* INetURLHistory::GetOrCreate()
     403             : {
     404             :     return rtl_Instance<
     405             :         INetURLHistory, StaticInstance,
     406             :         osl::MutexGuard, osl::GetGlobalMutex >::create (
     407         253 :             StaticInstance(), osl::GetGlobalMutex());
     408             : }
     409             : 
     410             : /*
     411             :  * NormalizeUrl_Impl.
     412             :  */
     413         243 : void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl)
     414             : {
     415         243 :     switch (rUrl.GetProtocol())
     416             :     {
     417             :         case INET_PROT_FILE:
     418         235 :             if (!rUrl.IsCaseSensitive())
     419             :             {
     420           0 :                 String aPath (rUrl.GetURLPath(INetURLObject::NO_DECODE));
     421           0 :                 aPath.ToLowerAscii();
     422           0 :                 rUrl.SetURLPath (aPath, INetURLObject::NOT_CANONIC);
     423             :             }
     424         235 :             break;
     425             : 
     426             :         case INET_PROT_FTP:
     427           0 :             if (!rUrl.HasPort())
     428           0 :                 rUrl.SetPort (INETHIST_DEF_FTP_PORT);
     429           0 :             break;
     430             : 
     431             :         case INET_PROT_HTTP:
     432           8 :             if (!rUrl.HasPort())
     433           8 :                 rUrl.SetPort (INETHIST_DEF_HTTP_PORT);
     434           8 :             if (!rUrl.HasURLPath())
     435           0 :                 rUrl.SetURLPath (rtl::OString("/"));
     436           8 :             break;
     437             : 
     438             :         case INET_PROT_HTTPS:
     439           0 :             if (!rUrl.HasPort())
     440           0 :                 rUrl.SetPort (INETHIST_DEF_HTTPS_PORT);
     441           0 :             if (!rUrl.HasURLPath())
     442           0 :                 rUrl.SetURLPath (rtl::OString("/"));
     443           0 :             break;
     444             : 
     445             :         default:
     446           0 :             break;
     447             :     }
     448         243 : }
     449             : 
     450             : /*
     451             :  * PutUrl_Impl.
     452             :  */
     453         235 : void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl)
     454             : {
     455             :     DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation");
     456         235 :     if (m_pImpl)
     457             :     {
     458         235 :         INetURLObject aHistUrl (rUrl);
     459         235 :         NormalizeUrl_Impl (aHistUrl);
     460             : 
     461         235 :         m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
     462         235 :         Broadcast (INetURLHistoryHint (&rUrl));
     463             : 
     464         235 :         if (aHistUrl.HasMark())
     465             :         {
     466             :             aHistUrl.SetURL (aHistUrl.GetURLNoMark(INetURLObject::NO_DECODE),
     467           0 :                              INetURLObject::NOT_CANONIC);
     468             : 
     469           0 :             m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
     470           0 :             Broadcast (INetURLHistoryHint (&aHistUrl));
     471         235 :         }
     472             :     }
     473         235 : }
     474             : 
     475             : /*
     476             :  * QueryUrl_Impl.
     477             :  */
     478           8 : sal_Bool INetURLHistory::QueryUrl_Impl (const INetURLObject &rUrl)
     479             : {
     480             :     DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation");
     481           8 :     if (m_pImpl)
     482             :     {
     483           8 :         INetURLObject aHistUrl (rUrl);
     484           8 :         NormalizeUrl_Impl (aHistUrl);
     485             : 
     486           8 :         return m_pImpl->queryUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE));
     487             :     }
     488           0 :     return sal_False;
     489             : }
     490             : 
     491             : 
     492             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10