1 files changed, 561 insertions, 0 deletions
diff --git a/store/source/storcach.cxx b/store/source/storcach.cxx
new file mode 100644
index 000000000000..f0e216575277
--- /dev/null
+++ b/store/source/storcach.cxx
@@ -0,0 +1,561 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2000, 2010 Oracle and/or its affiliates.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+// MARKER(update_precomp.py): autogen include statement, do not remove
+#include "precompiled_store.hxx"
+
+#include "storcach.hxx"
+
+#include "sal/types.h"
+#include "rtl/alloc.h"
+#include "osl/diagnose.h"
+
+#include "store/types.h"
+#include "object.hxx"
+#include "storbase.hxx"
+
+#ifndef INCLUDED_STDDEF_H
+#include <stddef.h>
+#define INCLUDED_STDDEF_H
+#endif
+
+using namespace store;
+
+/*========================================================================
+ *
+ * PageCache (non-virtual interface) implementation.
+ *
+ *======================================================================*/
+
+storeError PageCache::lookupPageAt (PageHolder & rxPage, sal_uInt32 nOffset)
+{
+    OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::lookupPageAt(): invalid Offset");
+    if (nOffset == STORE_PAGE_NULL)
+        return store_E_CantSeek;
+
+    return lookupPageAt_Impl (rxPage, nOffset);
+}
+
+storeError PageCache::insertPageAt (PageHolder const & rxPage, sal_uInt32 nOffset)
+{
+    // [SECURITY:ValInput]
+    PageData const * pagedata = rxPage.get();
+    OSL_PRECOND(!(pagedata == 0), "store::PageCache::insertPageAt(): invalid Page");
+    if (pagedata == 0)
+        return store_E_InvalidParameter;
+
+    sal_uInt32 const offset = pagedata->location();
+    OSL_PRECOND(!(nOffset != offset), "store::PageCache::insertPageAt(): inconsistent Offset");
+    if (nOffset != offset)
+        return store_E_InvalidParameter;
+
+    OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::insertPageAt(): invalid Offset");
+    if (nOffset == STORE_PAGE_NULL)
+        return store_E_CantSeek;
+
+    return insertPageAt_Impl (rxPage, nOffset);
+}
+
+storeError PageCache::updatePageAt (PageHolder const & rxPage, sal_uInt32 nOffset)
+{
+    // [SECURITY:ValInput]
+    PageData const * pagedata = rxPage.get();
+    OSL_PRECOND(!(pagedata == 0), "store::PageCache::updatePageAt(): invalid Page");
+    if (pagedata == 0)
+        return store_E_InvalidParameter;
+
+    sal_uInt32 const offset = pagedata->location();
+    OSL_PRECOND(!(nOffset != offset), "store::PageCache::updatePageAt(): inconsistent Offset");
+    if (nOffset != offset)
+        return store_E_InvalidParameter;
+
+    OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::updatePageAt(): invalid Offset");
+    if (nOffset == STORE_PAGE_NULL)
+        return store_E_CantSeek;
+
+    return updatePageAt_Impl (rxPage, nOffset);
+}
+
+storeError PageCache::removePageAt (sal_uInt32 nOffset)
+{
+    OSL_PRECOND(!(nOffset == STORE_PAGE_NULL), "store::PageCache::removePageAt(): invalid Offset");
+    if (nOffset == STORE_PAGE_NULL)
+        return store_E_CantSeek;
+
+    return removePageAt_Impl (nOffset);
+}
+
+/*========================================================================
+ *
+ * Entry.
+ *
+ *======================================================================*/
+namespace
+{
+
+struct Entry
+{
+    /** Representation.
+     */
+    PageHolder m_xPage;
+    sal_uInt32 m_nOffset;
+    Entry *    m_pNext;
+
+    /** Allocation.
+     */
+    static void * operator new (size_t, void * p) { return p; }
+    static void   operator delete (void *, void *) {}
+
+    /** Construction.
+     */
+    explicit Entry (PageHolder const & rxPage = PageHolder(), sal_uInt32 nOffset = STORE_PAGE_NULL)
+        : m_xPage(rxPage), m_nOffset(nOffset), m_pNext(0)
+    {}
+
+    /** Destruction.
+     */
+    ~Entry() {}
+};
+
+} // namespace
+
+/*========================================================================
+ *
+ * EntryCache interface.
+ *
+ *======================================================================*/
+namespace
+{
+
+class EntryCache
+{
+    rtl_cache_type * m_entry_cache;
+
+public:
+    static EntryCache & get();
+
+    Entry * create (PageHolder const & rxPage, sal_uInt32 nOffset);
+
+    void destroy (Entry * entry);
+
+protected:
+    EntryCache();
+    ~EntryCache();
+};
+
+} // namespace
+
+/*========================================================================
+ *
+ * EntryCache implementation.
+ *
+ *======================================================================*/
+
+EntryCache & EntryCache::get()
+{
+    static EntryCache g_entry_cache;
+    return g_entry_cache;
+}
+
+EntryCache::EntryCache()
+{
+    m_entry_cache = rtl_cache_create (
+        "store_cache_entry_cache",
+        sizeof(Entry),
+        0, // objalign
+        0, // constructor
+        0, // destructor
+        0, // reclaim
+        0, // userarg
+        0, // default source
+        0  // flags
+        );
+}
+
+EntryCache::~EntryCache()
+{
+    rtl_cache_destroy (m_entry_cache), m_entry_cache = 0;
+}
+
+Entry * EntryCache::create (PageHolder const & rxPage, sal_uInt32 nOffset)
+{
+    void * pAddr = rtl_cache_alloc (m_entry_cache);
+    if (pAddr != 0)
+    {
+        // construct.
+        return new(pAddr) Entry (rxPage, nOffset);
+    }
+    return 0;
+}
+
+void EntryCache::destroy (Entry * entry)
+{
+    if (entry != 0)
+    {
+        // destruct.
+        entry->~Entry();
+
+        // return to cache.
+        rtl_cache_free (m_entry_cache, entry);
+    }
+}
+
+/*========================================================================
+ *
+ * highbit():= log2() + 1 (complexity O(1))
+ *
+ *======================================================================*/
+static int highbit(sal_Size n)
+{
+    register int k = 1;
+
+    if (n == 0)
+        return (0);
+#if SAL_TYPES_SIZEOFLONG == 8
+    if (n & 0xffffffff00000000ul)
+        k |= 32, n >>= 32;
+#endif
+    if (n & 0xffff0000)
+        k |= 16, n >>= 16;
+    if (n & 0xff00)
+        k |= 8, n >>= 8;
+    if (n & 0xf0)
+        k |= 4, n >>= 4;
+    if (n & 0x0c)
+        k |= 2, n >>= 2;
+    if (n & 0x02)
+        k++;
+
+    return (k);
+}
+
+/*========================================================================
+ *
+ * PageCache_Impl implementation.
+ *
+ *======================================================================*/
+namespace store
+{
+
+class PageCache_Impl :
+    public store::OStoreObject,
+    public store::PageCache
+{
+    /** Representation.
+     */
+    static size_t const theTableSize = 32;
+    STORE_STATIC_ASSERT(STORE_IMPL_ISP2(theTableSize));
+
+    Entry **     m_hash_table;
+    Entry *      m_hash_table_0[theTableSize];
+    size_t       m_hash_size;
+    size_t       m_hash_shift;
+    size_t const m_page_shift;
+
+    size_t       m_hash_entries; // total number of entries in table.
+    size_t       m_nHit;
+    size_t       m_nMissed;
+
+    inline int hash_Impl(sal_uInt32 a, size_t s, size_t q, size_t m)
+    {
+        return ((((a) + ((a) >> (s)) + ((a) >> ((s) << 1))) >> (q)) & (m));
+    }
+    inline int hash_index_Impl (sal_uInt32 nOffset)
+    {
+        return hash_Impl(nOffset, m_hash_shift, m_page_shift, m_hash_size - 1);
+    }
+
+    Entry * lookup_Impl (Entry * entry, sal_uInt32 nOffset);
+    void rescale_Impl (sal_Size new_size);
+
+    /** PageCache Implementation.
+     */
+    virtual storeError lookupPageAt_Impl (
+        PageHolder & rxPage,
+        sal_uInt32   nOffset);
+
+    virtual storeError insertPageAt_Impl (
+        PageHolder const & rxPage,
+        sal_uInt32         nOffset);
+
+    virtual storeError updatePageAt_Impl (
+        PageHolder const & rxPage,
+        sal_uInt32         nOffset);
+
+    virtual storeError removePageAt_Impl (
+        sal_uInt32 nOffset);
+
+    /** Not implemented.
+     */
+    PageCache_Impl (PageCache_Impl const &);
+    PageCache_Impl & operator= (PageCache_Impl const &);
+
+public:
+    /** Construction.
+     */
+    explicit PageCache_Impl (sal_uInt16 nPageSize);
+
+    /** Delegate multiple inherited IReference.
+     */
+    virtual oslInterlockedCount SAL_CALL acquire();
+    virtual oslInterlockedCount SAL_CALL release();
+
+protected:
+    /** Destruction.
+     */
+    virtual ~PageCache_Impl (void);
+};
+
+} // namespace store
+
+PageCache_Impl::PageCache_Impl (sal_uInt16 nPageSize)
+    : m_hash_table   (m_hash_table_0),
+      m_hash_size    (theTableSize),
+      m_hash_shift   (highbit(m_hash_size) - 1),
+      m_page_shift   (highbit(nPageSize) - 1),
+      m_hash_entries (0),
+      m_nHit         (0),
+      m_nMissed      (0)
+{
+    static size_t const theSize = sizeof(m_hash_table_0) / sizeof(m_hash_table_0[0]);
+    STORE_STATIC_ASSERT(theSize == theTableSize);
+    memset(m_hash_table_0, 0, sizeof(m_hash_table_0));
+}
+
+PageCache_Impl::~PageCache_Impl()
+{
+    double s_x = 0.0, s_xx = 0.0;
+    sal_Size i, n = m_hash_size;
+    for (i = 0; i < n; i++)
+    {
+        int x = 0;
+        Entry * entry = m_hash_table[i];
+        while (entry != 0)
+        {
+            m_hash_table[i] = entry->m_pNext, entry->m_pNext = 0;
+            EntryCache::get().destroy (entry);
+            entry = m_hash_table[i];
+            x += 1;
+        }
+        s_x  += double(x);
+        s_xx += double(x) * double(x);
+    }
+    double ave = s_x / double(n);
+    OSL_TRACE("ave hash chain length: %g", ave);
+    (void) ave;
+
+    if (m_hash_table != m_hash_table_0)
+    {
+        rtl_freeMemory (m_hash_table);
+        m_hash_table = m_hash_table_0;
+        m_hash_size  = theTableSize;
+        m_hash_shift = highbit(m_hash_size) - 1;
+    }
+    OSL_TRACE("Hits: %u, Misses: %u", m_nHit, m_nMissed);
+}
+
+oslInterlockedCount PageCache_Impl::acquire()
+{
+    return OStoreObject::acquire();
+}
+
+oslInterlockedCount PageCache_Impl::release()
+{
+    return OStoreObject::release();
+}
+
+void PageCache_Impl::rescale_Impl (sal_Size new_size)
+{
+    sal_Size new_bytes = new_size * sizeof(Entry*);
+    Entry ** new_table = (Entry**)(rtl_allocateMemory(new_bytes));
+
+    if (new_table != 0)
+    {
+        Entry ** old_table = m_hash_table;
+        sal_Size old_size  = m_hash_size;
+
+        OSL_TRACE("ave chain length: %u, total entries: %u [old_size: %u, new_size: %u]",
+                  m_hash_entries >> m_hash_shift, m_hash_entries, old_size, new_size);
+
+        memset (new_table, 0, new_bytes);
+
+        m_hash_table = new_table;
+        m_hash_size  = new_size;
+        m_hash_shift = highbit(m_hash_size) - 1;
+
+        sal_Size i;
+        for (i = 0; i < old_size; i++)
+        {
+            Entry * curr = old_table[i];
+            while (curr != 0)
+            {
+                Entry * next = curr->m_pNext;
+                int index = hash_index_Impl(curr->m_nOffset);
+                curr->m_pNext = m_hash_table[index], m_hash_table[index] = curr;
+                curr = next;
+            }
+            old_table[i] = 0;
+        }
+        if (old_table != m_hash_table_0)
+        {
+            //
+            rtl_freeMemory (old_table);
+        }
+    }
+}
+
+Entry * PageCache_Impl::lookup_Impl (Entry * entry, sal_uInt32 nOffset)
+{
+    register int lookups = 0;
+    while (entry != 0)
+    {
+        if (entry->m_nOffset == nOffset)
+            break;
+
+        lookups += 1;
+        entry = entry->m_pNext;
+    }
+    if (lookups > 2)
+    {
+        sal_Size new_size = m_hash_size, ave = m_hash_entries >> m_hash_shift;
+        for (; ave > 4; new_size *= 2, ave /= 2)
+            continue;
+        if (new_size != m_hash_size)
+            rescale_Impl (new_size);
+    }
+    return entry;
+}
+
+storeError PageCache_Impl::lookupPageAt_Impl (
+    PageHolder & rxPage,
+    sal_uInt32   nOffset)
+{
+    int index = hash_index_Impl(nOffset);
+    Entry const * entry = lookup_Impl (m_hash_table[index], nOffset);
+    if (entry != 0)
+    {
+        // Existing entry.
+        rxPage = entry->m_xPage;
+
+        // Update stats and leave.
+        m_nHit += 1;
+        return store_E_None;
+    }
+
+    // Cache miss. Update stats and leave.
+    m_nMissed += 1;
+    return store_E_NotExists;
+}
+
+storeError PageCache_Impl::insertPageAt_Impl (
+    PageHolder const & rxPage,
+    sal_uInt32         nOffset)
+{
+    Entry * entry = EntryCache::get().create (rxPage, nOffset);
+    if (entry != 0)
+    {
+        // Insert new entry.
+        int index = hash_index_Impl(nOffset);
+        entry->m_pNext = m_hash_table[index], m_hash_table[index] = entry;
+
+        // Update stats and leave.
+        m_hash_entries += 1;
+        return store_E_None;
+    }
+    return store_E_OutOfMemory;
+}
+
+storeError PageCache_Impl::updatePageAt_Impl (
+    PageHolder const & rxPage,
+    sal_uInt32         nOffset)
+{
+    int index = hash_index_Impl(nOffset);
+    Entry *  entry  = lookup_Impl (m_hash_table[index], nOffset);
+    if (entry != 0)
+    {
+        // Update existing entry.
+        entry->m_xPage = rxPage;
+
+        // Update stats and leave. // m_nUpdHit += 1;
+        return store_E_None;
+    }
+    return insertPageAt_Impl (rxPage, nOffset);
+}
+
+storeError PageCache_Impl::removePageAt_Impl (
+    sal_uInt32 nOffset)
+{
+    Entry ** ppEntry = &(m_hash_table[hash_index_Impl(nOffset)]);
+    while (*ppEntry != 0)
+    {
+        if ((*ppEntry)->m_nOffset == nOffset)
+        {
+            // Existing entry.
+            Entry * entry = (*ppEntry);
+
+            // Dequeue and destroy entry.
+            (*ppEntry) = entry->m_pNext, entry->m_pNext = 0;
+            EntryCache::get().destroy (entry);
+
+            // Update stats and leave.
+            m_hash_entries -= 1;
+            return store_E_None;
+        }
+        ppEntry = &((*ppEntry)->m_pNext);
+    }
+    return store_E_NotExists;
+}
+
+/*========================================================================
+ *
+ * Old OStorePageCache implementation.
+ *
+ * (two-way association (sorted address array, LRU chain)).
+ * (external OStorePageData representation).
+ *
+ *======================================================================*/
+
+/*========================================================================
+ *
+ * PageCache factory implementation.
+ *
+ *======================================================================*/
+namespace store {
+
+storeError
+PageCache_createInstance (
+    rtl::Reference< store::PageCache > & rxCache,
+    sal_uInt16                           nPageSize)
+{
+    rxCache = new PageCache_Impl (nPageSize);
+    if (!rxCache.is())
+        return store_E_OutOfMemory;
+
+    return store_E_None;
+}
+
+} // namespace store