RTree.h

// -*- c++ -*-

#ifndef __RTREE_H__
#define __RTREE_H__

// tools
// #include <"tools/AVLTree.h"

// storage
#include "storage/FileAllocator.h"
#include "storage/Interval.h"

// When using the ArchiveDataTool to convert about 500 channels,
// 230MB of data, 102K directory file into an index, these were the
// results:
// Via NFS:
// M=3
// real    0m30.871s
// user    0m0.790s
// sys     0m2.030s
//  
// M=10
// real    0m23.944s
// user    0m0.830s
// sys     0m1.690s
//
// Local disk:
// No profiling, M=10
// real    0m17.148s
// user    0m0.700s
// sys     0m0.990s
//  
// No profiling, M=50
// real    0m3.402s  (!)
// user    0m1.290s
// sys     0m0.770s
//
// --> NFS is bad, small RTreeM values are bad.

class RTree
{
public:
    class Datablock
    {
    public:

        Datablock();
        
      virtual ~Datablock();

        virtual bool isValid() const = 0;
           
        const stdString &getDataFilename() const
        {
            LOG_ASSERT(isValid());
            return data_filename;
        }
        
        FileOffset getDataOffset() const
        {
            LOG_ASSERT(isValid());
            return data_offset;
        }
        
        virtual const Interval& getInterval() const = 0;
        
            virtual bool getNextChainedBlock() = 0;
            
        virtual bool getNextDatablock() = 0;

            virtual bool getPrevDatablock() = 0;
        
    protected:

      PROHIBIT_DEFAULT_COPY(Datablock);

      FileOffset data_offset;
        
      stdString  data_filename;
    };

    static const size_t anchor_size = 8;

    RTree(FileAllocator &fa, FileOffset anchor);
    
    void init(int M);

    void reattach();

    int getM() const
    {   return M; }
    
    Interval getInterval();

    Datablock *search(const epicsTime &start) const;

    Datablock *getFirstDatablock() const;
    
    Datablock *getLastDatablock() const; 
    
    class Node chooseLeaf(const Interval &range);
    
    bool insertDatablock(const Interval &range,
                         FileOffset data_offset,
                         const stdString &data_filename);
    
    size_t removeDatablock(const Interval &range,
                         FileOffset data_offset,
                         const stdString &data_filename);

    bool updateLastDatablock(const Interval &range,
                             FileOffset data_offset, stdString data_filename);
    
    void makeDot(const char *filename);

    bool selfTest(unsigned long &nodes, unsigned long &records);

private:
    PROHIBIT_DEFAULT_COPY(RTree);
    
    FileAllocator &fa;
    
    const FileOffset anchor;
    
    // FileOffset to the root = content of what's at anchor
    FileOffset root_offset;

    int M;
    
    // mutable AVLTree<Node> node_cache;
    mutable size_t cache_misses, cache_hits; 
    
    void make_node_dot(FILE *dot, FILE *f, FileOffset node_offset);

    bool getFirstRecord(class Node &node, int &record_index) const;

    bool getLastRecord(class Node &node, int &record_index) const;

    void split_record(Node &node, int idx, const epicsTime &cut);

    void adjust_tree(Node &node, Node *new_node);
    
    size_t removeDatablock(Node &node, const Interval &range,
                       FileOffset data_offset, const stdString &data_filename);
      
    size_t removeDatablock(Node &node, int record_index, const Interval &range,
                       FileOffset data_offset, const stdString &data_filename);
                       
    void remove_record(Node &node, int i);

    void condense_tree(Node &node);

    bool updateLast(const epicsTime &start,
                    const epicsTime &end, FileOffset ID);
};

#endif