NumericIndex.h

Go to the documentation of this file.

#ifndef OSMSCOUT_NUMERICINDEX_H
#define OSMSCOUT_NUMERICINDEX_H
 
/*
  This source is part of the libosmscout library
  Copyright (C) 2009  Tim Teulings
 
  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.
 
  This library 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 for more details.
 
  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
*/
 
#include <mutex>
#include <vector>
 
#include <osmscout/util/Cache.h>
#include <osmscout/log/Logger.h>
#include <osmscout/util/Number.h>
#include <osmscout/util/String.h>
 
#include <osmscout/io/File.h>
#include <osmscout/io/FileScanner.h>
 
namespace osmscout {

  template <class N>
  class NumericIndex
  {
  private:
    struct Entry
    {
      N          startId;
      FileOffset fileOffset;
    };
 
    struct Page
    {
      std::vector<Entry> entries;
 
      inline bool IndexIsValid(size_t index) const
      {
        return index<entries.size();
      }
    };
 
    using PageRef         = std::shared_ptr<Page>;
    using PageCache       = Cache<N, PageRef>;
    using PageSimpleCache = std::unordered_map<N, PageRef>;

    struct NumericIndexCacheValueSizer : public PageCache::ValueSizer
    {
      size_t GetSize(const PageRef& value) const
      {
        return sizeof(value)+sizeof(Page)+sizeof(Entry)*value->entries.size();
      }
    };
 
  private:
    std::string                         filepart;             
    std::string                         filename;             
 
    mutable FileScanner                  scanner;             
 
    size_t                               cacheSize;           
    uint32_t                             pageSize=0;          
    uint32_t                             levels=0;            
    std::vector<uint32_t>                pageCounts;          
    char                                 *buffer=nullptr;     
 
    PageRef                              root;                
    size_t                               simpleCacheMaxLevel; 
    mutable std::vector<PageSimpleCache> simplePageCache;     
    mutable std::vector<PageCache>       pageCaches;          
 
    mutable std::mutex                   accessMutex;         
 
  private:
    size_t GetPageIndex(const Page& page, N id) const;
    void ReadPage(FileOffset offset, PageRef& page) const;
    void InitializeCache();
 
  public:
    NumericIndex(const std::string& filename,
                 size_t cacheSize);
    virtual ~NumericIndex();
 
    bool Open(const std::string& path,
              bool memoryMapped);
    bool Close();
 
    bool IsOpen() const;
 
    bool GetOffset(const N& id, FileOffset& offset) const;
 
    template<typename IteratorIn>
    bool GetOffsets(IteratorIn begin,
                    IteratorIn end,
                    size_t size,
                    std::vector<FileOffset>& offsets) const;
 
    void DumpStatistics() const;
  };
 
  template <class N>
  NumericIndex<N>::NumericIndex(const std::string& filename,
                                size_t cacheSize)
   : filepart(filename),
     cacheSize(cacheSize)
  {
    // no code
  }
 
  template <class N>
  NumericIndex<N>::~NumericIndex()
  {
    Close();
 
    delete [] buffer;
  }

  template <class N>
  inline size_t NumericIndex<N>::GetPageIndex(const Page& page, N id) const
  {
    size_t size=page.entries.size();
 
    //std::cout << "Lookup in page: " << page.entries[0].startId << " " << id << " " << page.entries[page.entries.size()-1].startId << std::endl;
 
    if (size>0) {
      size_t left=0;
      size_t right=size-1;
 
      while (left<=right) {
        size_t mid=(left+right)/2;
 
        if (page.entries[mid].startId<=id &&
            (mid+1>=size || page.entries[mid+1].startId>id)) {
          return mid;
        }
 
        if (page.entries[mid].startId<id) {
          left=mid+1;
        }
        else {
          if (mid==0) {
            return size;
          }
 
          right=mid-1;
        }
      }
    }
 
    return size;
  }
 
  template <class N>
  inline void NumericIndex<N>::ReadPage(FileOffset offset, PageRef& page) const
  {
    if (!page) {
      page=std::make_shared<Page>();
    }
    else {
      page->entries.clear();
    }
 
    page->entries.reserve(pageSize/4);
 
    scanner.SetPos(offset);
 
    scanner.Read(buffer,
                 pageSize);
 
    size_t     currentPos=0;
    N          prevId=0;
    FileOffset prefFileOffset=0;
 
    //std::cout << "Page: " << offset << std::endl;
 
    while (currentPos<pageSize &&
           buffer[currentPos]!=0) {
      unsigned int idBytes;
      unsigned int fileOffsetBytes;
      N            curId;
      FileOffset   curFileOffset;
      Entry        entry;
 
      idBytes=DecodeNumber(&buffer[currentPos],
                           curId);
 
      currentPos+=idBytes;
 
      fileOffsetBytes=DecodeNumber(&buffer[currentPos],
                                   curFileOffset);
 
      currentPos+=fileOffsetBytes;
 
      entry.startId=prevId+curId;
      entry.fileOffset=prefFileOffset+curFileOffset;
 
      //std::cout << "- " << entry.startId << " " << idBytes << " " << entry.fileOffset << " " << fileOffsetBytes << std::endl;
 
      prevId=entry.startId;
      prefFileOffset=entry.fileOffset;
 
      page->entries.push_back(entry);
    }
  }
 
  template <class N>
  void NumericIndex<N>::InitializeCache()
  {
    size_t currentCacheSize=cacheSize; // Available free space in cache
    size_t requiredCacheSize=0;        // Space needed for caching everything
 
    for (const auto count : pageCounts) {
      requiredCacheSize+=count;
    }
 
    if (requiredCacheSize>cacheSize) {
      log.Warn() << "Warning: Index " << filepart << " has cache size " << cacheSize<< ", but requires cache size " << requiredCacheSize << " to load index completely into cache!";
    }
 
    simpleCacheMaxLevel=0;
    for (size_t level=1; level<pageCounts.size(); level++) {
      size_t resultingCacheSize; // Cache size we actually use for this level
 
      simplePageCache.push_back(PageSimpleCache());
 
      if (pageCounts[level]>currentCacheSize) {
        resultingCacheSize=currentCacheSize;
        currentCacheSize=0;
 
        pageCaches.push_back(PageCache(resultingCacheSize));
      }
      else {
        resultingCacheSize=pageCounts[level];
        currentCacheSize-=pageCounts[level];
 
        simpleCacheMaxLevel=level;
 
        pageCaches.push_back(PageCache(0));
      }
    }
  }
 
  template <class N>
  bool NumericIndex<N>::Open(const std::string& path,
                             bool memoryMapped)
  {
    filename=AppendFileToDir(path,filepart);
 
    try {
      scanner.Open(filename,
                   FileScanner::FastRandom,
                   memoryMapped);
 
      pageSize=scanner.ReadUInt32Number();                  // Size of one index page
      /*uint32_t entries=*/scanner.ReadUInt32Number();                   // Number of entries in data file
 
      levels=scanner.ReadUInt32();                    // Number of levels
      pageCounts.resize(levels);
 
      FileOffset lastLevelPageStart=scanner.ReadFileOffset();    // Start of top level index page
      FileOffset indexPageCountsOffset=scanner.ReadFileOffset(); // Start of list of sizes of index levels
 
      scanner.SetPos(indexPageCountsOffset);
      for (size_t level=0; level<levels; level++) {
        pageCounts[level]=scanner.ReadUInt32Number();
      }
 
      delete [] buffer;
      buffer=new char[pageSize];
 
      //std::cout << "Index " << filename << ": " << entries << " entries to index, " << levels << " levels, pageSize " << pageSize << ", cache size " << cacheSize << std::endl;
 
      ReadPage(lastLevelPageStart,root);
 
      InitializeCache();
    }
    catch (IOException& e) {
      log.Error() << e.GetDescription();
      scanner.CloseFailsafe();
      return false;
    }
 
    return !scanner.HasError();
  }
 
  template <class N>
  bool NumericIndex<N>::Close()
  {
    try {
      if (scanner.IsOpen()) {
        scanner.Close();
      }
    }
    catch (IOException& e) {
      log.Error() << e.GetDescription();
      scanner.CloseFailsafe();
      return false;
    }
 
    return true;
  }
 
  template <class N>
  bool NumericIndex<N>::IsOpen() const
  {
    return scanner.IsOpen();
  }

  template <class N>
  bool NumericIndex<N>::GetOffset(const N& id,
                                  FileOffset& offset) const
  {
    try
    {
      std::lock_guard<std::mutex> lock(accessMutex);
 
      //std::cout << "Looking up " << id << " in index...." << std::endl;
 
      size_t                      r=GetPageIndex(*root,id);
      PageRef                     pageRef;
 
      if (!root->IndexIsValid(r)) {
        //std::cerr << "Id " << id << " not found in root index, " << root->entries.front().startId << "-" << root->entries.back().startId << std::endl;
        return false;
      }
 
      const Entry& rootEntry=root->entries[r];
 
      //std::cout << "Root entry index: " << r << " " << rootEntry.startId << " " << rootEntry.fileOffset << std::endl;
 
      offset=rootEntry.fileOffset;
 
      N startId=rootEntry.startId;
      for (size_t level=0; level+2<=levels; level++) {
        //std::cout << "Level " << level << "/" << levels << std::endl;
        if (level<=simpleCacheMaxLevel) {
          auto cacheRef=simplePageCache[level].find(startId);
 
          if (cacheRef==simplePageCache[level].end()) {
            pageRef=nullptr; // Make sure, that we allocate a new page and not reuse an old one
 
            ReadPage(offset,pageRef);
 
            simplePageCache[level].emplace(startId,pageRef);
          }
          else {
            pageRef=cacheRef->second;
          }
        }
        else {
          typename PageCache::CacheRef cacheRef;
 
          if (!pageCaches[level].GetEntry(startId,cacheRef)) {
            typename PageCache::CacheEntry cacheEntry(startId);
 
            cacheRef=pageCaches[level].SetEntry(cacheEntry);
 
            ReadPage(offset,cacheRef->value);
          }
 
          pageRef=cacheRef->value;
        }
 
        Page& page=*pageRef;
 
        size_t i=GetPageIndex(page,id);
 
        if (!page.IndexIsValid(i)) {
          //std::cerr << "Id " << id << " not found in index level " << level+2 << "!" << std::endl;
          return false;
        }
 
        const Entry& entry=page.entries[i];
 
        //std::cout << "Sub entry index: " << i << " " << entry.startId << " " << entry.fileOffset << std::endl;
 
        startId=entry.startId;
        offset=entry.fileOffset;
      }
 
      if (startId!=id) {
        //std::cerr << "Id " << id << " not found in leaf index level (" << levels << " levels)" << std::endl;
      }
 
      return startId==id;
    }
    catch (IOException& e) {
      log.Error() << e.GetDescription();
      return false;
    }
  }

  template <class N>
  template<typename IteratorIn>
  bool NumericIndex<N>::GetOffsets(IteratorIn begin,
                                   IteratorIn end,
                                   size_t size,
                                   std::vector<FileOffset>& offsets) const
  {
    offsets.clear();
    offsets.reserve(size);
 
    for (IteratorIn idIter=begin; idIter!=end; ++idIter) {
      FileOffset offset;
 
      if (GetOffset(*idIter,
                    offset)) {
        offsets.push_back(offset);
      }
    }
 
    return true;
  }
 
  template <class N>
  void NumericIndex<N>::DumpStatistics() const
  {
    size_t memory=0;
    size_t pages=0;
 
    pages+=1;
    memory+=root->entries.size()*sizeof(Entry);
 
 
    for (size_t i=0; i<pageCaches.size(); i++) {
      pages+=pageCaches[i].GetSize();
      memory+=sizeof(pageCaches[i])+pageCaches[i].GetMemory(NumericIndexCacheValueSizer());
    }
 
    log.Info() << "Index " << filepart << ": " << pages << " pages, memory " << memory;
  }
}
 
#endif