diff options
Diffstat (limited to '')
| -rw-r--r-- | svl/source/misc/inethist.cxx | 371 |
1 files changed, 371 insertions, 0 deletions
diff --git a/svl/source/misc/inethist.cxx b/svl/source/misc/inethist.cxx new file mode 100644 index 000000000..dc25d6b0b --- /dev/null +++ b/svl/source/misc/inethist.cxx @@ -0,0 +1,371 @@ +/* -*- 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; + 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: */ |