| /************************************************************** |
| * |
| * 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 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| * |
| *************************************************************/ |
| |
| |
| |
| // MARKER(update_precomp.py): autogen include statement, do not remove |
| #include "precompiled_svl.hxx" |
| #include <svl/inethist.hxx> |
| |
| #ifndef INCLUDED_ALGORITHM |
| #include <algorithm> |
| #define INCLUDED_ALGORITHM |
| #endif |
| #include "rtl/instance.hxx" |
| #include "rtl/crc.h" |
| #include "rtl/memory.h" |
| #include <tools/solar.h> |
| #include <tools/debug.hxx> |
| #include <tools/string.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 |
| |
| /* |
| * INetURLHistoryHint implementation. |
| */ |
| IMPL_PTRHINT (INetURLHistoryHint, const INetURLObject); |
| |
| /*======================================================================== |
| * |
| * INetURLHistory_Impl interface. |
| * |
| *======================================================================*/ |
| class INetURLHistory_Impl |
| { |
| /** head_entry. |
| */ |
| struct head_entry |
| { |
| /** Representation. |
| */ |
| sal_uInt32 m_nMagic; |
| sal_uInt16 m_nNext; |
| sal_uInt16 m_nMBZ; |
| |
| /** Initialization. |
| */ |
| void initialize (void) |
| { |
| m_nMagic = INETHIST_MAGIC_HEAD; |
| m_nNext = 0; |
| m_nMBZ = 0; |
| } |
| }; |
| |
| /** hash_entry. |
| */ |
| struct hash_entry |
| { |
| /** Representation. |
| */ |
| sal_uInt32 m_nHash; |
| sal_uInt16 m_nLru; |
| sal_uInt16 m_nMBZ; |
| |
| /** Initialization. |
| */ |
| void initialize (sal_uInt16 nLru, sal_uInt32 nHash = 0) |
| { |
| m_nHash = nHash; |
| m_nLru = nLru; |
| m_nMBZ = 0; |
| } |
| |
| /** Comparison. |
| */ |
| sal_Bool operator== (const hash_entry &rOther) const |
| { |
| return (m_nHash == rOther.m_nHash); |
| } |
| sal_Bool operator< (const hash_entry &rOther) const |
| { |
| return (m_nHash < rOther.m_nHash); |
| } |
| |
| sal_Bool operator== (sal_uInt32 nHash) const |
| { |
| return (m_nHash == nHash); |
| } |
| sal_Bool operator< (sal_uInt32 nHash) const |
| { |
| return (m_nHash < nHash); |
| } |
| }; |
| |
| /** lru_entry. |
| */ |
| struct lru_entry |
| { |
| /** Representation. |
| */ |
| sal_uInt32 m_nHash; |
| sal_uInt16 m_nNext; |
| sal_uInt16 m_nPrev; |
| |
| /** Initialization. |
| */ |
| void initialize (sal_uInt16 nThis, sal_uInt32 nHash = 0) |
| { |
| m_nHash = nHash; |
| 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 (void); |
| |
| void downheap (hash_entry a[], sal_uInt16 n, sal_uInt16 k); |
| void heapsort (hash_entry a[], sal_uInt16 n); |
| |
| /** capacity. |
| */ |
| sal_uInt16 capacity (void) const |
| { |
| return (sal_uInt16)(INETHIST_SIZE_LIMIT); |
| } |
| |
| /** crc32. |
| */ |
| sal_uInt32 crc32 (UniString const & rData) const |
| { |
| return rtl_crc32 (0, rData.GetBuffer(), rData.Len() * sizeof(sal_Unicode)); |
| } |
| |
| /** find. |
| */ |
| sal_uInt16 find (sal_uInt32 nHash) const; |
| |
| /** move. |
| */ |
| void move (sal_uInt16 nSI, sal_uInt16 nDI); |
| |
| /** backlink. |
| */ |
| void backlink (sal_uInt16 nThis, sal_uInt16 nTail) |
| { |
| register lru_entry &rThis = m_pList[nThis]; |
| register 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; |
| } |
| |
| /** unlink. |
| */ |
| void unlink (sal_uInt16 nThis) |
| { |
| register 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; |
| } |
| |
| /** Not implemented. |
| */ |
| INetURLHistory_Impl (const INetURLHistory_Impl&); |
| INetURLHistory_Impl& operator= (const INetURLHistory_Impl&); |
| |
| public: |
| INetURLHistory_Impl (void); |
| ~INetURLHistory_Impl (void); |
| |
| /** putUrl/queryUrl. |
| */ |
| void putUrl (const String &rUrl); |
| sal_Bool queryUrl (const String &rUrl); |
| }; |
| |
| /*======================================================================== |
| * |
| * INetURLHistory_Impl implementation. |
| * |
| *======================================================================*/ |
| /* |
| * INetURLHistory_Impl. |
| */ |
| INetURLHistory_Impl::INetURLHistory_Impl (void) |
| { |
| initialize(); |
| } |
| |
| /* |
| * ~INetURLHistory_Impl. |
| */ |
| INetURLHistory_Impl::~INetURLHistory_Impl (void) |
| { |
| } |
| |
| /* |
| * initialize. |
| */ |
| void INetURLHistory_Impl::initialize (void) |
| { |
| 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); |
| } |
| |
| /* |
| * downheap. |
| */ |
| void INetURLHistory_Impl::downheap (hash_entry a[], sal_uInt16 n, sal_uInt16 k) |
| { |
| hash_entry h = a[k]; |
| while (k < n / 2) |
| { |
| sal_uInt16 i = k + k + 1; |
| if (((i + 1) < n) && (a[i] < a[i + 1])) i++; |
| if (!(h < a[i])) break; |
| a[k] = a[i]; |
| k = i; |
| } |
| a[k] = h; |
| } |
| |
| /* |
| * heapsort. |
| */ |
| void INetURLHistory_Impl::heapsort (hash_entry a[], sal_uInt16 n) |
| { |
| hash_entry h; |
| |
| for (sal_uInt16 k = (n - 1) / 2 + 1; k > 0; k--) |
| downheap (a, n, k - 1); |
| |
| while (n > 0) |
| { |
| h = a[0 ]; |
| a[0 ] = a[n - 1]; |
| a[n - 1] = h; |
| downheap (a, --n, 0); |
| } |
| } |
| |
| /* |
| * find. |
| */ |
| 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; |
| } |
| |
| /* |
| * move. |
| */ |
| void INetURLHistory_Impl::move (sal_uInt16 nSI, sal_uInt16 nDI) |
| { |
| hash_entry e = m_pHash[nSI]; |
| if (nSI < nDI) |
| { |
| // shift left. |
| rtl_moveMemory ( |
| &m_pHash[nSI ], |
| &m_pHash[nSI + 1], |
| (nDI - nSI) * sizeof(hash_entry)); |
| } |
| if (nSI > nDI) |
| { |
| // shift right. |
| rtl_moveMemory ( |
| &m_pHash[nDI + 1], |
| &m_pHash[nDI ], |
| (nSI - nDI) * sizeof(hash_entry)); |
| } |
| m_pHash[nDI] = e; |
| } |
| |
| /* |
| * putUrl. |
| */ |
| void INetURLHistory_Impl::putUrl (const String &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) |
| { |
| if (!(m_pHash[nDI] < h)) |
| nDI -= 1; |
| } |
| if (nDI < nSI) |
| { |
| if (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); |
| } |
| } |
| |
| /* |
| * queryUrl. |
| */ |
| sal_Bool INetURLHistory_Impl::queryUrl (const String &rUrl) |
| { |
| sal_uInt32 h = crc32 (rUrl); |
| sal_uInt16 k = find (h); |
| if ((k < capacity()) && (m_pHash[k] == h)) |
| { |
| // Cache hit. |
| return sal_True; |
| } |
| else |
| { |
| // Cache miss. |
| return sal_False; |
| } |
| } |
| |
| /*======================================================================== |
| * |
| * INetURLHistory::StaticInstance implementation. |
| * |
| *======================================================================*/ |
| INetURLHistory * INetURLHistory::StaticInstance::operator ()() |
| { |
| static INetURLHistory g_aInstance; |
| return &g_aInstance; |
| } |
| |
| /*======================================================================== |
| * |
| * INetURLHistory implementation. |
| * |
| *======================================================================*/ |
| /* |
| * INetURLHistory. |
| */ |
| INetURLHistory::INetURLHistory() : m_pImpl (new INetURLHistory_Impl()) |
| { |
| } |
| |
| /* |
| * ~INetURLHistory. |
| */ |
| INetURLHistory::~INetURLHistory() |
| { |
| DELETEZ (m_pImpl); |
| } |
| |
| /* |
| * GetOrCreate. |
| */ |
| INetURLHistory* INetURLHistory::GetOrCreate() |
| { |
| return rtl_Instance< |
| INetURLHistory, StaticInstance, |
| osl::MutexGuard, osl::GetGlobalMutex >::create ( |
| StaticInstance(), osl::GetGlobalMutex()); |
| } |
| |
| /* |
| * NormalizeUrl_Impl. |
| */ |
| void INetURLHistory::NormalizeUrl_Impl (INetURLObject &rUrl) |
| { |
| switch (rUrl.GetProtocol()) |
| { |
| case INET_PROT_FILE: |
| if (!rUrl.IsCaseSensitive()) |
| { |
| String aPath (rUrl.GetURLPath(INetURLObject::NO_DECODE)); |
| aPath.ToLowerAscii(); |
| rUrl.SetURLPath (aPath, INetURLObject::NOT_CANONIC); |
| } |
| break; |
| |
| case INET_PROT_FTP: |
| if (!rUrl.HasPort()) |
| rUrl.SetPort (INETHIST_DEF_FTP_PORT); |
| break; |
| |
| case INET_PROT_HTTP: |
| if (!rUrl.HasPort()) |
| rUrl.SetPort (INETHIST_DEF_HTTP_PORT); |
| if (!rUrl.HasURLPath()) |
| rUrl.SetURLPath ("/"); |
| break; |
| |
| case INET_PROT_HTTPS: |
| if (!rUrl.HasPort()) |
| rUrl.SetPort (INETHIST_DEF_HTTPS_PORT); |
| if (!rUrl.HasURLPath()) |
| rUrl.SetURLPath ("/"); |
| break; |
| |
| default: |
| break; |
| } |
| } |
| |
| /* |
| * PutUrl_Impl. |
| */ |
| void INetURLHistory::PutUrl_Impl (const INetURLObject &rUrl) |
| { |
| DBG_ASSERT (m_pImpl, "PutUrl_Impl(): no Implementation"); |
| if (m_pImpl) |
| { |
| INetURLObject aHistUrl (rUrl); |
| NormalizeUrl_Impl (aHistUrl); |
| |
| m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE)); |
| Broadcast (INetURLHistoryHint (&rUrl)); |
| |
| if (aHistUrl.HasMark()) |
| { |
| aHistUrl.SetURL (aHistUrl.GetURLNoMark(INetURLObject::NO_DECODE), |
| INetURLObject::NOT_CANONIC); |
| |
| m_pImpl->putUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE)); |
| Broadcast (INetURLHistoryHint (&aHistUrl)); |
| } |
| } |
| } |
| |
| /* |
| * QueryUrl_Impl. |
| */ |
| sal_Bool INetURLHistory::QueryUrl_Impl (const INetURLObject &rUrl) |
| { |
| DBG_ASSERT (m_pImpl, "QueryUrl_Impl(): no Implementation"); |
| if (m_pImpl) |
| { |
| INetURLObject aHistUrl (rUrl); |
| NormalizeUrl_Impl (aHistUrl); |
| |
| return m_pImpl->queryUrl (aHistUrl.GetMainURL(INetURLObject::NO_DECODE)); |
| } |
| return sal_False; |
| } |
| |
| |