include/Cache/CacheEngine.hpp

Go to the documentation of this file.

#ifndef hpp_CPP_CacheEngine_CPP_hpp
#define hpp_CPP_CacheEngine_CPP_hpp

// We need types
#include "../Types/Types.hpp"
// We need AVL trees too for fast index
#include "../Tree/Avl.hpp"
// We need containers too for item groups
#include "../Containers/Container.hpp"
// We need strings too
#include "../Strings/Strings.hpp"
// We need time declaration
#include <time.h>
// We need platform specific lock mechanism
#include "../Platform/Platform.hpp"


namespace Cache
{
    typedef time_t CacheTime;
    typedef PlatformSpecific::FastLock Lock;

    class Item
    {
        // Types
    public:
        enum DocumentType
        {
            Unknown     =   0x00000000,     
            XML         =   0x00000001,     
            HTML        =   0x00000002,     
            JPEGImage   =   0x00000003,     
            PNGImage    =   0x00000004,     
            GIFImage    =   0x00000005,     
            Stylesheet  =   0x00000006,     
            ScriptFile  =   0x00000007,     
        };
        enum Status
        {
            Unset               = 0,    
            WaitingFetching     = 1,    
            Ready               = 2,    

            FetchingError       = -1,    
            BadURI              = -2,    
        };

        typedef void (*DeleteDataFnc)(void *);    

        // Members
    private:    
        const Strings::FastString   URL;
        CacheTime                   timestamp;
        DocumentType            type;
        void *                  data;
        uint32                  size;
        Status                  status;
        DeleteDataFnc           deleteFunction;
        
    public:    
        volatile Lock           lock;

        // The default deletion functions
    public:    
        template <typename T>
            static void DeleteDeleter(T * ptr) { delete ptr; }
        template <typename T>
            static void ArrayDeleteDeleter(T * ptr) { delete[] ptr; }
        static void FreeDeleter(void * ptr) { free(ptr); }
        static void NoDeleter(void * ptr) { }
        static void PODBlockDeleter(void * ptr) { delete[] (char*)ptr; }

        // Interface used when single threaded
    public:        
        inline static CacheTime Now() { return (CacheTime)time(NULL); }
        inline void setData(const DocumentType _type, void * _data, const uint32 _size, const DeleteDataFnc _deleter = &PODBlockDeleter) { type = _type; data = _data; size = _size; deleteFunction = _deleter; }
        inline void setStatus(const Status _status) { status = _status; }
        inline const void * getData() const { return data; }
        inline const uint32 getDataSize() const { return size; }
        inline const DocumentType getDocumentType() const { return type; }
        inline const Strings::FastString & getDocumentURL() const { return URL; }
        inline const CacheTime getTimestamp() const { return timestamp; }
        inline const Status getStatus() const { return status; }

        inline bool fetchingError() const { return status < 0; }

        inline void deleteData() { if (deleteFunction) (*deleteFunction)(data); data = 0; size = 0; type = Unknown; deleteFunction = 0; }
        inline void Suicide() { deleteData(); delete this; }
    
        // Interface used when multithreaded
    public:
        inline void setData(const DocumentType _type, void * _data, const uint32 _size, const DeleteDataFnc _deleter = &PODBlockDeleter) volatile { PlatformSpecific::LockingObjPtr<Item>(*this, lock)->setData(_type, _data, _size, _deleter); }
        inline void setStatus(const Status _status) volatile { PlatformSpecific::LockingObjPtr<Item>(*this, lock)->setStatus(_status); }
        inline const void * getData() volatile const { return PlatformSpecific::LockingConstObjPtr<Item>(*this, lock)->getData(); }
        inline const uint32 getDataSize() volatile const { return PlatformSpecific::LockingConstObjPtr<Item>(*this, lock)->getDataSize(); }
        inline const DocumentType getDocumentType() const volatile  { return PlatformSpecific::LockingConstObjPtr<Item>(*this, lock)->getDocumentType(); }
        inline const Strings::FastString & getDocumentURL() const volatile  { return *const_cast<const Strings::FastString*>(&URL); }
        inline const CacheTime getTimestamp() const volatile  { return PlatformSpecific::LockingConstObjPtr<Item>(*this, lock)->getTimestamp(); }
        inline const Status getStatus() const volatile { return PlatformSpecific::LockingConstObjPtr<Item>(*this, lock)->getStatus(); }

        inline bool fetchingError() const volatile { return PlatformSpecific::LockingConstObjPtr<Item>(*this, lock)->fetchingError(); }
        
        inline void deleteData() volatile { PlatformSpecific::LockingObjPtr<Item>(*this, lock)->deleteData(); }
        inline void Suicide() volatile { PlatformSpecific::LockingObjPtr<Item>(*this, lock)->Suicide(); }

        // Construction / Destruction
    public:    
        Item(const Strings::FastString & _URL, const DocumentType & _type = Unknown, void * _data = 0, const uint32 _size = 0, const DeleteDataFnc _deleter = &PODBlockDeleter) 
            : URL(_URL), timestamp(Now()), type(_type), data(_data), size(_size), deleteFunction(_deleter), status(WaitingFetching) {}

        ~Item() { deleteData(); }
    };

    struct ItemComparator
    {
        inline static bool LessThan(const volatile Item & a, const volatile Item& b) { return (bool)(a.getDocumentURL() < b.getDocumentURL()); }
        inline static bool Equal(const volatile Item & a, const volatile Item & b) { return (bool)(a.getDocumentURL() == b.getDocumentURL()); }
    };

    class RequiredFetcherImplementation
    {
    public:
        virtual bool queueDocumentToFetch(volatile Item & item, void * opaque = 0) = 0;

        virtual uint32 isItemFetched(volatile Item & item) const = 0;
    };



    class Holder
    {
        // Type definition
    public:    
        typedef Container::PlainOldData<volatile Item *>::Array ItemGroup;
        typedef Container::NotConstructible<ItemGroup>::ChainedList ItemGroupList;

        // Members
    private:
        RequiredFetcherImplementation &     fetcher;
        typedef Tree::AVL::Tree<volatile Item *, Strings::FastString, ItemComparator, Tree::AVL::PointerDeletion<volatile Item *, Strings::FastString> > ItemTree;
        ItemTree                            items;
        typedef Tree::AVL::Tree<volatile Item *, CacheTime>  TimeTree;
        TimeTree                            timeIndex;
        const uint32                        maxAllowedSize;
        uint32                              currentSize;
        ItemGroupList                       itemGroupList;

        // Helpers
    private:
        volatile Item * addItemToCache(const Strings::FastString & URL)
        {
            // Make sure the item doesn't exist already
            ItemTree::IterT iter = items.searchFor(URL);
            if (iter.isValid()) return *iter;
            
            // Not found already, so allocate it
            volatile Item * item = new Item(URL);
            if (!item) return 0; 
            
            // Then store in the tree
            if (!timeIndex.insertObject(item, item->getTimestamp())) { delete item; return 0; }
            if (!items.insertObject(item, URL)) 
            { 
                timeIndex.Delete(item->getTimestamp());
                delete item; return 0; 
            }

            return item;
        }

        inline void removeItemFromCache(volatile Item * item, const bool clean = true)
        {
            if (item)
            {
                if (clean) item->deleteData();
                timeIndex.Delete(item->getTimestamp());
                items.Delete(item->getDocumentURL());
            }
        }

        inline void removeItemFromGroup(volatile Item * item, ItemGroup * group)
        {
            if (item && group) group->Remove(group->indexOf(item));
        }


        // Interface
    public:
        ItemGroup * addGroupFromRoot(const Strings::FastString & URL, void * opaque)
        {
            // Check if the group already exist
            ItemGroup * group = findRoot(URL);
            if (group) return group;
            else
            {
                // Create an item
                // Then add the item to the list too 
                volatile Item * item = addItemToCache(URL);

                // Ok, create one
                group = new ItemGroup;
                if (!group) { removeItemFromCache(item, false); return 0; }

                // Append the item
                group->Append(item);
                // And then fetch it
                if (!fetcher.queueDocumentToFetch(*item, opaque))
                    { removeItemFromCache(item); delete group; return 0; }

                if (!itemGroupList.Add(group))
                    { removeItemFromCache(item); delete group; return 0; }

                return group;
            }
        }

        ItemGroup * findRoot(const Strings::FastString & URL)
        {
            // This is stupid linear search
            ItemGroup * first = itemGroupList.parseList(true);
            while (first)
            {
                if (first->getSize() && first->getElementAtUncheckedPosition(0)->getDocumentURL() == URL) return first;
                first = itemGroupList.parseList();
            }
            return 0;
        }

        ItemGroup * findGroupFromItem(volatile Item * item)
        {
            if (!item) return 0;
            // This is stupid linear search
            ItemGroup * first = itemGroupList.parseList(true);
            while (first)
            {
                if (first->getSize())
                {
                    if (first->indexOf(item) != first->getSize()) return first;
                }
                first = itemGroupList.parseList();
            }
            return 0;
        }


        bool emptyCache(const uint32 size)
        {
            if (size > maxAllowedSize) return false;
            if (size == maxAllowedSize)
            {   // Clean the whole cache
                timeIndex.Clear();
                items.Clear();

                // Then clear the list
                itemGroupList.Free();
                currentSize = 0;
            }
            else
            {   // Need to find the oldest items
                while (((int32)maxAllowedSize - (int32)currentSize) < (int32)size)
                {
                    // Find the oldest item
                    TimeTree::IterT iter = timeIndex.searchExtreme(true);
                    if (!iter.isValid()) return false; // It's not possible to find an oldest item...

                    // First remove this item from every group first
                    volatile Item * item = *iter;
                    ItemGroup * group = findGroupFromItem(item);
                    while (group) 
                    {
                        removeItemFromGroup(item, group);
                        group = findGroupFromItem(item);
                    }

                    // Then remove this item, once for all
                    currentSize -= item->getDataSize();
                    removeItemFromCache(item);
                }
                // Ok, it's done !
            }
            return true;
        }

        bool addItemToGroup(const Strings::FastString & URL, ItemGroup * group)
        {
            if (!group) return false;
            // Create an item
            volatile Item * item = addItemToCache(URL);

            // Append the item
            group->Append(item);
            // And then fetch it
            if (!fetcher.queueDocumentToFetch(*item))
                { removeItemFromGroup(item, group); removeItemFromCache(item); return false; }

            return true;
        }

        inline volatile Item * findItemFromURL(const Strings::FastString & URL)
        {
            ItemTree::IterT iter = items.searchFor(URL); if (iter.isValid()) return *iter; else return 0;
        }

        const uint32 getFetchingAdvancement(const ItemGroup * group, bool booleanResult = false)
        {
            if (!group) return 0; // No documents
            // First, add cumulative sizes
            uint32 i = 0, size = 0;
            for (; i < group->getSize(); i++) size += group->getElementAtUncheckedPosition(i)->fetchingError() ? 0 : group->getElementAtUncheckedPosition(i)->getDataSize();
            if (!size) // No known size yet
            {
                // Either every document are fetched, either none of them is.
                if (booleanResult)
                {
                    for (i = 0; i < group->getSize(); i++) 
                    {
                        uint32 current = fetcher.isItemFetched(*group->getElementAtUncheckedPosition(i));
                        if (current == (uint32)-1) return 0;
                    }
                    return 100;
                } // Else, simply deduce percentage from the number of entirely fetched documents
                uint32 currentCount = 0;
                for (i = 0; i < group->getSize(); i++) 
                {
                    currentCount += fetcher.isItemFetched(*group->getElementAtUncheckedPosition(i)) != (uint32)-1;
                }
                return (currentCount * 100) / group->getSize();
            }
            else
            {   // Need to compute percentage here
                uint32 current = 0, count = 0;
                for (i = 0; i < group->getSize(); i++) 
                {
                    uint32 amountFetched = fetcher.isItemFetched(*group->getElementAtUncheckedPosition(i));
                    current += amountFetched == (uint32)-1 ? 0 : amountFetched;
                    count += amountFetched != (uint32)-1;
                }
                return booleanResult ? (count == group->getSize()) * 100 : (current * 100) / size;
            }
        }

        inline const bool entireGroupReady(const ItemGroup * group)
        {
            return getFetchingAdvancement(group, true) == 100;
        }

        inline const bool groupFetchingError(const ItemGroup * group)
        {
            if (!group || !group->getSize() || group->getElementAtUncheckedPosition(0)->fetchingError()) return true;
            return false;
        }

        // Construction
    public:
        Holder(RequiredFetcherImplementation & _fetcher, const uint32 maxSize = 33554432) : fetcher(_fetcher), currentSize(0), maxAllowedSize(maxSize) {}
        virtual ~Holder() { emptyCache(maxAllowedSize); }
    };
}

#endif

(C) An X-Ryl669 project 2007

This document describes Unlimited Zooming Interface source code. UZI stands for Unlimited Zooming Interface, and source code license is