371 lines
9.1 KiB
C++
371 lines
9.1 KiB
C++
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
|
|
/*
|
|
* This file is part of the LibreOffice project.
|
|
*
|
|
* This Source Code Form is subject to the terms of the Mozilla Public
|
|
* License, v. 2.0. If a copy of the MPL was not distributed with this
|
|
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
|
|
*
|
|
* This file incorporates work covered by the following license notice:
|
|
*
|
|
* Licensed to the Apache Software Foundation (ASF) under one or more
|
|
* contributor license agreements. See the NOTICE file distributed
|
|
* with this work for additional information regarding copyright
|
|
* ownership. The ASF licenses this file to you under the Apache
|
|
* License, Version 2.0 (the "License"); you may not use this file
|
|
* except in compliance with the License. You may obtain a copy of
|
|
* the License at http://www.apache.org/licenses/LICENSE-2.0 .
|
|
*/
|
|
|
|
#include <svl/inethist.hxx>
|
|
|
|
#include <algorithm>
|
|
#include <string.h>
|
|
|
|
#include <rtl/crc.h>
|
|
#include <tools/debug.hxx>
|
|
#include <tools/urlobj.hxx>
|
|
|
|
/*
|
|
* INetURLHistory internals.
|
|
*/
|
|
#define INETHIST_DEF_FTP_PORT 21
|
|
#define INETHIST_DEF_HTTP_PORT 80
|
|
#define INETHIST_DEF_HTTPS_PORT 443
|
|
|
|
#define INETHIST_SIZE_LIMIT 1024
|
|
#define INETHIST_MAGIC_HEAD 0x484D4849UL
|
|
|
|
class INetURLHistory_Impl
|
|
{
|
|
struct head_entry
|
|
{
|
|
/** Representation.
|
|
*/
|
|
sal_uInt32 m_nMagic;
|
|
sal_uInt16 m_nNext;
|
|
|
|
/** Initialization.
|
|
*/
|
|
void initialize()
|
|
{
|
|
m_nMagic = INETHIST_MAGIC_HEAD;
|
|
m_nNext = 0;
|
|
}
|
|
};
|
|
|
|
struct hash_entry
|
|
{
|
|
/** Representation.
|
|
*/
|
|
sal_uInt32 m_nHash;
|
|
sal_uInt16 m_nLru;
|
|
|
|
/** Initialization.
|
|
*/
|
|
void initialize (sal_uInt16 nLru)
|
|
{
|
|
m_nHash = 0;
|
|
m_nLru = nLru;
|
|
}
|
|
|
|
/** Comparison.
|
|
*/
|
|
bool operator== (sal_uInt32 nHash) const
|
|
{
|
|
return (m_nHash == nHash);
|
|
}
|
|
bool operator< (sal_uInt32 nHash) const
|
|
{
|
|
return (m_nHash < nHash);
|
|
}
|
|
};
|
|
|
|
struct lru_entry
|
|
{
|
|
/** Representation.
|
|
*/
|
|
sal_uInt32 m_nHash;
|
|
sal_uInt16 m_nNext;
|
|
sal_uInt16 m_nPrev;
|
|
|
|
/** Initialization.
|
|
*/
|
|
void initialize (sal_uInt16 nThis)
|
|
{
|
|
m_nHash = 0;
|
|
m_nNext = nThis;
|
|
m_nPrev = nThis;
|
|
}
|
|
};
|
|
|
|
/** Representation.
|
|
*/
|
|
head_entry m_aHead;
|
|
hash_entry m_pHash[INETHIST_SIZE_LIMIT];
|
|
lru_entry m_pList[INETHIST_SIZE_LIMIT];
|
|
|
|
/** Initialization.
|
|
*/
|
|
void initialize();
|
|
|
|
static sal_uInt16 capacity()
|
|
{
|
|
return sal_uInt16(INETHIST_SIZE_LIMIT);
|
|
}
|
|
|
|
static sal_uInt32 crc32 (OUString const & rData)
|
|
{
|
|
return rtl_crc32 (0, rData.getStr(), rData.getLength() * sizeof(sal_Unicode));
|
|
}
|
|
|
|
sal_uInt16 find (sal_uInt32 nHash) const;
|
|
|
|
void move (sal_uInt16 nSI, sal_uInt16 nDI);
|
|
|
|
void backlink (sal_uInt16 nThis, sal_uInt16 nTail)
|
|
{
|
|
lru_entry &rThis = m_pList[nThis];
|
|
lru_entry &rTail = m_pList[nTail];
|
|
|
|
rTail.m_nNext = nThis;
|
|
rTail.m_nPrev = rThis.m_nPrev;
|
|
rThis.m_nPrev = nTail;
|
|
m_pList[rTail.m_nPrev].m_nNext = nTail;
|
|
}
|
|
|
|
void unlink (sal_uInt16 nThis)
|
|
{
|
|
lru_entry &rThis = m_pList[nThis];
|
|
|
|
m_pList[rThis.m_nPrev].m_nNext = rThis.m_nNext;
|
|
m_pList[rThis.m_nNext].m_nPrev = rThis.m_nPrev;
|
|
rThis.m_nNext = nThis;
|
|
rThis.m_nPrev = nThis;
|
|
}
|
|
|
|
public:
|
|
INetURLHistory_Impl();
|
|
INetURLHistory_Impl(const INetURLHistory_Impl&) = delete;
|
|
INetURLHistory_Impl& operator=(const INetURLHistory_Impl&) = delete;
|
|
|
|
/** putUrl/queryUrl.
|
|
*/
|
|
void putUrl (const OUString &rUrl);
|
|
bool queryUrl (const OUString &rUrl) const;
|
|
};
|
|
|
|
INetURLHistory_Impl::INetURLHistory_Impl()
|
|
{
|
|
initialize();
|
|
}
|
|
|
|
void INetURLHistory_Impl::initialize()
|
|
{
|
|
m_aHead.initialize();
|
|
|
|
sal_uInt16 i, n = capacity();
|
|
for (i = 0; i < n; i++)
|
|
m_pHash[i].initialize(i);
|
|
for (i = 0; i < n; i++)
|
|
m_pList[i].initialize(i);
|
|
for (i = 1; i < n; i++)
|
|
backlink (m_aHead.m_nNext, i);
|
|
}
|
|
|
|
sal_uInt16 INetURLHistory_Impl::find (sal_uInt32 nHash) const
|
|
{
|
|
sal_uInt16 l = 0;
|
|
sal_uInt16 r = capacity() - 1;
|
|
sal_uInt16 c = capacity();
|
|
|
|
while ((l < r) && (r < c))
|
|
{
|
|
sal_uInt16 m = ((l + r) / 2) & 0xFFFF;
|
|
if (m_pHash[m] == nHash)
|
|
return m;
|
|
|
|
if (m_pHash[m] < nHash)
|
|
l = m + 1;
|
|
else
|
|
r = m - 1;
|
|
}
|
|
return l;
|
|
}
|
|
|
|
void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI)
|
|
{
|
|
hash_entry e = m_pHash[nSI];
|
|
if (nSI < nDI)
|
|
{
|
|
// shift left.
|
|
memmove (
|
|
&m_pHash[nSI ],
|
|
&m_pHash[nSI + 1],
|
|
(nDI - nSI) * sizeof(hash_entry));
|
|
}
|
|
if (nSI > nDI)
|
|
{
|
|
// shift right.
|
|
memmove (
|
|
&m_pHash[nDI + 1],
|
|
&m_pHash[nDI ],
|
|
(nSI - nDI) * sizeof(hash_entry));
|
|
}
|
|
m_pHash[nDI] = e;
|
|
}
|
|
|
|
void INetURLHistory_Impl::putUrl (const OUString &rUrl)
|
|
{
|
|
sal_uInt32 h = crc32 (rUrl);
|
|
sal_uInt16 k = find (h);
|
|
if ((k < capacity()) && (m_pHash[k] == h))
|
|
{
|
|
// Cache hit.
|
|
sal_uInt16 nMRU = m_pHash[k].m_nLru;
|
|
if (nMRU != m_aHead.m_nNext)
|
|
{
|
|
// Update LRU chain.
|
|
unlink (nMRU);
|
|
backlink (m_aHead.m_nNext, nMRU);
|
|
|
|
// Rotate LRU chain.
|
|
m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
// Cache miss. Obtain least recently used.
|
|
sal_uInt16 nLRU = m_pList[m_aHead.m_nNext].m_nPrev;
|
|
|
|
sal_uInt16 nSI = find (m_pList[nLRU].m_nHash);
|
|
if (nLRU != m_pHash[nSI].m_nLru)
|
|
{
|
|
// Update LRU chain.
|
|
nLRU = m_pHash[nSI].m_nLru;
|
|
unlink (nLRU);
|
|
backlink (m_aHead.m_nNext, nLRU);
|
|
}
|
|
|
|
// Rotate LRU chain.
|
|
m_aHead.m_nNext = m_pList[m_aHead.m_nNext].m_nPrev;
|
|
|
|
// Check source and destination.
|
|
sal_uInt16 nDI = std::min (k, sal_uInt16(capacity() - 1));
|
|
if (nSI < nDI && !(m_pHash[nDI] < h))
|
|
nDI -= 1;
|
|
if (nDI < nSI && m_pHash[nDI] < h)
|
|
nDI += 1;
|
|
|
|
// Assign data.
|
|
m_pList[m_aHead.m_nNext].m_nHash = m_pHash[nSI].m_nHash = h;
|
|
move (nSI, nDI);
|
|
}
|
|
}
|
|
|
|
bool INetURLHistory_Impl::queryUrl (const OUString &rUrl) const
|
|
{
|
|
sal_uInt32 h = crc32 (rUrl);
|
|
sal_uInt16 k = find (h);
|
|
// true if cache hit
|
|
return (k < capacity()) && (m_pHash[k] == h);
|
|
}
|
|
|
|
INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl())
|
|
{
|
|
}
|
|
|
|
INetURLHistory::~INetURLHistory()
|
|
{
|
|
}
|
|
|
|
/*
|
|
* GetOrCreate.
|
|
*/
|
|
INetURLHistory* INetURLHistory::GetOrCreate()
|
|
{
|
|
static INetURLHistory instance;
|
|
return &instance;
|
|
}
|
|
|
|
void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl)
|
|
{
|
|
switch (rUrl.GetProtocol())
|
|
{
|
|
case INetProtocol::File:
|
|
if (!INetURLObject::IsCaseSensitive())
|
|
{
|
|
OUString aPath (rUrl.GetURLPath(INetURLObject::DecodeMechanism::NONE).toAsciiLowerCase());
|
|
rUrl.SetURLPath (aPath, INetURLObject::EncodeMechanism::NotCanonical);
|
|
}
|
|
break;
|
|
|
|
case INetProtocol::Ftp:
|
|
if (!rUrl.HasPort())
|
|
rUrl.SetPort (INETHIST_DEF_FTP_PORT);
|
|
break;
|
|
|
|
case INetProtocol::Http:
|
|
if (!rUrl.HasPort())
|
|
rUrl.SetPort (INETHIST_DEF_HTTP_PORT);
|
|
if (!rUrl.HasURLPath())
|
|
rUrl.SetURLPath(u"/");
|
|
break;
|
|
|
|
case INetProtocol::Https:
|
|
if (!rUrl.HasPort())
|
|
rUrl.SetPort (INETHIST_DEF_HTTPS_PORT);
|
|
if (!rUrl.HasURLPath())
|
|
rUrl.SetURLPath(u"/");
|
|
break;
|
|
|
|
default:
|
|
break;
|
|
}
|
|
}
|
|
|
|
void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl)
|
|
{
|
|
DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation");
|
|
if (!m_pImpl)
|
|
return;
|
|
|
|
INetURLObject aHistUrl (rUrl);
|
|
NormalizeUrl_Impl (aHistUrl);
|
|
|
|
m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::DecodeMechanism::NONE));
|
|
Broadcast (INetURLHistoryHint (&rUrl));
|
|
|
|
if (aHistUrl.HasMark())
|
|
{
|
|
aHistUrl.SetURL (aHistUrl.GetURLNoMark(INetURLObject::DecodeMechanism::NONE),
|
|
INetURLObject::EncodeMechanism::NotCanonical);
|
|
|
|
m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::DecodeMechanism::NONE));
|
|
Broadcast (INetURLHistoryHint (&aHistUrl));
|
|
}
|
|
}
|
|
|
|
bool INetURLHistory::QueryUrl(std::u16string_view rUrl) const
|
|
{
|
|
INetProtocol eProto = INetURLObject::CompareProtocolScheme (rUrl);
|
|
if (!QueryProtocol (eProto))
|
|
return false;
|
|
return QueryUrl_Impl( INetURLObject(rUrl) );
|
|
}
|
|
|
|
|
|
bool INetURLHistory::QueryUrl_Impl (INetURLObject rUrl) const
|
|
{
|
|
DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation");
|
|
if (m_pImpl)
|
|
{
|
|
NormalizeUrl_Impl (rUrl);
|
|
|
|
return m_pImpl->queryUrl (rUrl.GetMainURL(INetURLObject::DecodeMechanism::NONE));
|
|
}
|
|
return false;
|
|
}
|
|
|
|
|
|
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|