eyedb: HIdx.h Source File

00001 /* 
00002    EyeDB Object Database Management System
00003    Copyright (C) 1994-2008 SYSRA
00004    
00005    EyeDB is free software; you can redistribute it and/or
00006    modify it under the terms of the GNU Lesser General Public
00007    License as published by the Free Software Foundation; either
00008    version 2.1 of the License, or (at your option) any later version.
00009    
00010    EyeDB is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013    Lesser General Public License for more details.
00014    
00015    You should have received a copy of the GNU Lesser General Public
00016    License along with this library; if not, write to the Free Software
00017    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA 
00018 */
00019 
00020 /*
00021    Author: Eric Viara <viara@sysra.com>
00022 */
00023 
00024 
00025 #ifndef _eyedbsm_HIdx_
00026 #define _eyedbsm_HIdx_
00027 
00028 #include <stdio.h>
00029 #include <stdlib.h>
00030 #include <eyedblib/machtypes.h>
00031 #include <eyedbsm/Idx.h>
00032 #include <vector>
00033 #include <map>
00034 
00035 namespace eyedblib {
00036   class ThreadPool;
00037   class ThreadPerformer;
00038 }
00039 
00040 #define HAS_ALLOC_BUFFER
00041 
00042 namespace eyedbsm {
00043 
00049   class HIdxCursor;
00050 
00051   static const int HIdxImplHintsCount = 8;
00052   static const unsigned int HIdxDataVarSize = ~0U;
00053 
00058   class HIdx : public Idx {
00059 
00060     friend class HIdxCursor;
00061 
00062 #ifdef HAS_ALLOC_BUFFER
00063     AllocBuffer insert_buffer;
00064     AllocBuffer makeobj_buffer;
00065 #endif
00066 
00067   public: /* conceptually private */
00068     class CellHeader;
00069     class CListObjHeader;
00070     class CListHeader;
00071 
00072   public:
00073     enum HIdxKeyType {
00074       stringType = 1,
00075       dataType
00076     };
00077 
00078 
00079     struct _Idx {
00080       unsigned int idxtype;
00081       unsigned int object_count;
00082       unsigned int mag_order;
00083       unsigned int key_count;
00084       short dspid;
00085       unsigned int keytype;
00086       unsigned int keysz;
00087       unsigned int datasz;
00088       unsigned int offset;
00089       int impl_hints[HIdxImplHintsCount];
00090       void trace(FILE *fd = stdout) const;
00091       std::string toString() const;
00092     };
00093 
00094   public: //@@@@ A.W just try to cure
00095     struct _Idx hidx;
00096   private:
00097     unsigned int mask;
00098     Boolean pow2;
00099     Boolean uextend;
00100     Boolean data_grouped_by_key;
00101     unsigned int data_grouped_sizeof;
00102     Oid treeoid;
00103     Status stat;
00104     DbHandle *dbh;
00105     int bsize;
00106     hash_key_t hash_key;
00107     void *hash_data;
00108     int version;
00109     Boolean nocopy;
00110 
00111     class HKey {
00112       const void *key;
00113       HIdx *hidx;
00114       bool _garbage;
00115 
00116     public:
00117 
00118       HKey(HIdx *hidx, const void *key, bool copy = false);
00119       HKey(const HKey &);
00120       HKey& operator=(const HKey &);
00121 
00122       int operator<(const HKey &okey) const {
00123         return hidx->cmp(key, okey.key, 0) < 0 ? 1 : 0;
00124       }
00125 
00126       const void *getKey() const {return key;}
00127 
00128       void garbage() {
00129         if (_garbage) {
00130           free((char *)key);
00131           key = 0;
00132         }
00133       }
00134 
00135       ~HKey() {
00136         garbage();
00137       }
00138     };
00139 
00140     friend class HKey;
00141    
00142     std::map<HKey, std::vector<const void *> > cache_map;
00143 
00144     static void *copy_key(const void *, unsigned int, Boolean, Boolean *state = 0);
00145     Status dumpMemoryMap(const CListHeader &, const char *msg = "", FILE *fd = stdout);
00146 
00147     Status readCellHeader(int off, const Oid &, CellHeader &) const;
00148     Status writeCellHeader(int off, const Oid &, const CellHeader &) const;
00149     Status readCListObjHeader(const Oid &, CListObjHeader &) const;
00150     Status writeCListObjHeader(const Oid &, const CListObjHeader &) const;
00151     Status readCListHeader(unsigned int k, CListHeader &chd) const;
00152     Status writeCListHeader(unsigned int k, const CListHeader &chd) const;
00153     Status readCListHeaders(CListHeader *&chds) const;
00154     Status writeCListHeaders(const CListHeader *chds) const;
00155 
00156     Status insertCell(int offset, unsigned int size, CListObjHeader &h,
00157                       const Oid &koid) const;
00158     Status suppressCell(int offset, CListObjHeader &h, const Oid &koid) const;
00159     Status get_key(unsigned int &, const void *, unsigned int * = 0) const;
00160     int cmp(const void *, const void *, unsigned char) const;
00161     Status count_manage(DbHandle *dbh, int inc);
00162     Status getCell(unsigned int size, CListHeader &chd, unsigned int chd_k,
00163                    Oid &koid, CListObjHeader &h, int &offset, CellHeader &o);
00164     Status insert_realize(CListHeader &chd, unsigned int chd_k, const void *key,
00165                           unsigned int size, const void *xdata,
00166                           const Oid &koid, CListObjHeader &h, int offset,
00167                           CellHeader &o, unsigned int datasz);
00168     Status insert_perform(const void *key, std::vector<const void *> &xdata_v, unsigned int datasz);
00169     Status insert_perform(const void *key, const void *xdata, unsigned int datasz);
00170     Status remove_perform(const void *key, const void *xdata, unsigned int datasz, Boolean *found, unsigned char **prdata, unsigned int *pdatacnt, int *found_idx, unsigned int incr_alloc);
00171     Status remove_realize(CListHeader *chd, unsigned int chd_key,
00172                           const char *, const char *, const char *,
00173                           const CellHeader *, const Oid *);
00174     Status search_realize(const void *key, unsigned int *found_cnt, Boolean found_any, void * data);
00175     Status getObjectToExtend(unsigned int size, CListHeader &chd, unsigned int chd_k,
00176                              Oid &koid, CListObjHeader &h, int &offset,
00177                              CellHeader &o, Boolean &found);
00178     Status extendObject(CListHeader &chd, unsigned int chd_k, const Oid &koid,
00179                         CListObjHeader &h, Boolean &extended);
00180     Status extendObject(unsigned int size, CListHeader &chd, unsigned int chd_k, Oid &koid,
00181                         CListObjHeader &h, int &offset, CellHeader &o,
00182                         Boolean &extended);
00183     Boolean candidateForExtension(const CListObjHeader &);
00184     Status makeObject(CListHeader &chd, unsigned int chd_k, Oid &koid, int &offset,
00185                       CListObjHeader &h, CellHeader &o, unsigned int objsize);
00186     static bool inFreeList(const CListObjHeader &h, const CListHeader &chd, const Oid &koid);
00187     Status insertObjectInFreeList(CListHeader &chd, unsigned int chd_k, CListObjHeader &h,
00188                                   const Oid &koid);
00189     Status suppressObjectFromFreeList(CListHeader &chd, unsigned int chd_k, CListObjHeader &h,
00190                                       const Oid &koid);
00191     Status suppressObjectFromList(CListHeader &chd, unsigned int chd_k, CListObjHeader &h,
00192                                   const Oid &koid);
00193     Status replaceObjectInList(CListHeader &chd, unsigned int chd_k, CListObjHeader &h,
00194                                const Oid &koid, const Oid &nkoid);
00195     Status modifyObjectSize(int osize, int nsize, const Oid &koid, 
00196                             Oid &nkoid);
00197     Status headPrint(FILE *, int, Oid *, int&) const;
00198     Status getEntryCount(Oid *, unsigned int& ) const;
00199     Status getHashObjectBusySize(const Oid *koid, unsigned int &busysize,
00200                                  unsigned int &count, unsigned int size = 0) const;
00201     static Status get_def_string_hash_key(const void *key, unsigned int len,
00202                                           void *, unsigned int &);
00203     static Status get_def_nstring_hash_key(const void *key, unsigned int len,
00204                                            void *, unsigned int &);
00205     static Status get_def_rawdata_hash_key(const void *key, unsigned int len,
00206                                            void *, unsigned int &);
00207     static Status get_def_int16data_hash_key(const void *key,
00208                                              unsigned int len, void *, unsigned int &);
00209     static Status get_def_int32data_hash_key(const void *key,
00210                                              unsigned int len, void *, unsigned int &);
00211     static Status get_def_int64data_hash_key(const void *key,
00212                                              unsigned int len, void *, unsigned int &);
00213     static Status get_def_oiddata_hash_key(const void *key, unsigned int len,
00214                                            void *, unsigned int &);
00215     static Status get_def_float32data_hash_key(const void *key,
00216                                                unsigned int len,
00217                                                void *, unsigned int &);
00218     static Status get_def_float64data_hash_key(const void *key,
00219                                                unsigned int len,
00220                                                void *, unsigned int &);
00221 
00222     Status get_string_hash_key(const void *key, unsigned int len, unsigned int &) const;
00223     Status get_rawdata_hash_key(const void *key, unsigned int len, unsigned int &) const;
00224     void printCellHeader(const HIdx::CellHeader *o, int offset) const;
00225     void checkCellHeader(int offset, const Oid *koid) const;
00226     void printCListObjHeader(const HIdx::CListObjHeader *h) const;
00227     void checkCListObjHeader(const Oid *koid) const;
00228     void checkChain(const Oid *koid) const;
00229     void checkChain(const CListHeader *chd, const std::string &msg) const;
00230 
00231     void set_hash_key();
00232     Status destroy_r();
00233     Status copy_realize(Idx *) const;
00234     void init(DbHandle *, unsigned int keytype, unsigned int keysz,
00235               unsigned int offset,
00236               unsigned int datasz, short dspid,
00237               int mag_order, int key_count,
00238               const int *impl_hints,
00239               unsigned int impl_hints_cnt);
00240     KeyType keytype;
00241     Status collapse_realize(short dspid, HIdx *idx_n);
00242     Status h2x_datacnt_cpy(unsigned char *rdata, const unsigned int *pdatacnt) const;
00243     Status x2h_datacnt_cpy(unsigned int *pdatacnt, const unsigned char *pdata) const;
00244 
00245   public:
00246 
00247     enum Hints {
00248       IniSize_Hints,
00249       IniObjCnt_Hints,
00250       XCoef_Hints,
00251       SzMax_Hints,
00252       DataGroupedByKey_Hints
00253     };
00254 
00255     static const unsigned int MaxKeys;
00256     static const unsigned int VarSize;
00257     static const unsigned int MagorderKeycountCoef;
00258 
00270     HIdx(DbHandle *vh, KeyType type,
00271          unsigned int datasz, short dspid,
00272          int magorder, int key_count = 0,
00273          const int *impl_hints = 0,
00274          unsigned int impl_hints_cnt = 0);
00275 
00284     HIdx(DbHandle *vh, const Oid *poid,
00285          hash_key_t hash_key = 0,
00286          void *hash_data = 0,
00287          Boolean (*precmp)(void const * p, void const * q,
00288                            KeyType const * type, int & r) = 0);
00289 
00296     void open(hash_key_t hash_key = 0,
00297               void *hash_data = 0,
00298               Boolean (*precmp)(void const * p, void const * q,
00299                                 KeyType const * type, int & r) = 0);
00300 
00305     unsigned int getCount() const;
00306 
00311     short getDefaultDspid() const;
00312 
00317     void setDefaultDspid(short dspid);
00318 
00325     Status getObjects(Oid *&oids, unsigned int &cnt) const;
00326 
00331     virtual HIdx *asHIdx() {return this;}
00332 
00337     const KeyType & getKeyType() const {return keytype;}
00338 
00343     const HIdx::_Idx & getIdx() const {return hidx;}
00344 
00345     ~HIdx();
00346   
00353     Status insert(const void *key, const void *data);
00354 
00362     Status insert(const void *key, const void *data, unsigned int datasz);
00363 
00370     Status insert(const void *key, std::vector<const void *> &data_v);
00371 
00378     Status insert_cache(const void *key, const void *data);
00379 
00386     Status insert_cache(const void *key, std::vector<const void *> &data_v);
00387 
00392     Status flush_cache(bool insert_data = true);
00393 
00401     Status remove(const void *key, const void *data, Boolean *found = 0);
00402 
00411     Status remove(const void *key, const void *data, unsigned int datasz, Boolean *found = 0);
00412 
00420     Status search(const void *key, unsigned int *found_cnt);
00421 
00429     Status searchAny(const void *key, Boolean *found, void *data = 0);
00430 
00435     Status destroy();
00436 
00442     Status printStat(FILE *fd = stdout) const;
00443 
00449     Status dumpMemoryMap(FILE *fd = stdout);
00450 
00455     Oid const& oid() const {return treeoid;}
00456 
00461     Boolean isDataGroupedByKey() const {return data_grouped_by_key;}
00462 
00467     bool isDataVarSize() const {return hidx.datasz == HIdxDataVarSize;}
00468 
00473     unsigned int getDataGroupedSizeof() const {return data_grouped_sizeof;}
00474 
00479     Status status() const {return stat;}
00480 
00485     unsigned int getKeyCount() const {return hidx.key_count;}
00486 
00491     Status collapse();
00492 
00506     Status copy(HIdx *&idx_n, int key_count, int mag_order = 0,
00507                 short dspid = DefaultDspid,
00508                 const int *impl_hints = 0, unsigned int impl_hints_cnt = 0,
00509                 hash_key_t _hash_key = 0,
00510                 void *_hash_data = 0,
00511                 KeyType *ktype = 0) const;
00512 
00518     static unsigned int getMagOrder(unsigned int keycount);
00519 
00525     static unsigned int getKeyCount(unsigned int magorder);
00526 
00532     Status getStats(std::string& stats) const;
00533 
00534     struct Stats {
00535       _Idx idx;
00536       struct Entry {
00537         unsigned int object_count;
00538         unsigned int hash_object_count;
00539         unsigned int hash_object_size;
00540         unsigned int hash_object_busy_size;
00541       } *entries;
00542       unsigned int min_objects_per_entry;
00543       unsigned int max_objects_per_entry;
00544       unsigned int total_object_count;
00545       unsigned int total_hash_object_count;
00546       unsigned int total_hash_object_size;
00547       unsigned int total_hash_object_busy_size;
00548       unsigned int busy_key_count;
00549       unsigned int free_key_count;
00550 
00551       Stats();
00552       ~Stats();
00553       void trace(Boolean full = True, FILE *fd = stdout) const;
00554       std::string toString(Boolean full = True) const;
00555     };
00556 
00562     Status getStats(HIdx::Stats &stats) const;
00563 
00569     Status move(short dspid, eyedbsm::Oid &newoid,
00570                 hash_key_t hash_key = 0,
00571                 void *hash_data = 0);
00572 
00586     Status reimplementToHash(Oid &newoid, int key_count, int mag_order = 0,
00587                              short dspid = DefaultDspid,
00588                              const int *impl_hints = 0,
00589                              unsigned int impl_hints_cnt = 0,
00590                              hash_key_t hash_key = 0,
00591                              void *hash_data = 0,
00592                              KeyType *ktype = 0);
00593 
00601     Status reimplementToBTree(Oid &newoid, int degree = 0,
00602                               short dspid = DefaultDspid);
00603 
00615     Status simulate(HIdx::Stats &stats, int key_count,
00616                     int mag_order = 0,
00617                     const int *impl_hints = 0,
00618                     unsigned int impl_hints_cnt = 0,
00619                     hash_key_t hash_key = 0,
00620                     void *hash_data = 0) const;
00621 
00622   public: /* conceptually private */
00623     struct CellHeader {
00624     public:
00625       eyedblib::uint32 free:1, size:31;
00626       eyedblib::int32 cell_free_prev, cell_free_next;
00627     };
00628 
00629     struct CListObjHeader {
00630     public:
00631       unsigned int size;
00632       eyedblib::uint16 free_cnt, alloc_cnt;
00633       eyedblib::uint32 free_whole;
00634       eyedblib::int32 cell_free_first;
00635       Oid clobj_free_prev, clobj_free_next;
00636       Oid clobj_prev, clobj_next;
00637     };
00638   
00639     struct CListHeader {
00640     public:
00641       Oid clobj_first, clobj_last;
00642       Oid clobj_free_first;
00643     };
00644   };
00645 
00649   class HIdxCursor : public IdxCursor {
00650 
00651     const HIdx *idx;
00652     void *skey, *ekey;
00653     Boolean sexcl, eexcl;
00654     static const char defaultSKey[];
00655     char *sdata, *edata, *cur;
00656     unsigned int datacnt, idata;
00657     unsigned int jumpsize;
00658     Boolean nocopy;
00659     Boolean data_tofree;
00660     Status read(Boolean& end);
00661     Boolean equal;
00662     unsigned int k_cur, k_end;
00663     int cmp_realize(const void *, const void *, Boolean, unsigned char) const;
00664     int cmp(const void *) const;
00665     Oid koid;
00666     Boolean state;
00667     Boolean (*user_cmp)(const void *key, void *cmp_arg);
00668     void *cmp_arg;
00669     void append_next(void *data, Idx::Key *key, unsigned int n, DataBuffer *dataBuffer);
00670 
00671     void init(DbHandle *);
00672 
00673     // parallel management
00674     unsigned int perf_cnt, perf_end_cnt;
00675     Boolean master, slave;
00676     class LinkList;
00677     Boolean parallelInit(int thread_cnt);
00678     eyedblib::ThreadPerformer **perfs;
00679     HIdxCursor **perf_curs;
00680     LinkList *list;
00681     LinkList **lists;
00682     eyedblib::ThreadPool *thrpool;
00683     HIdxCursor(const HIdx *,
00684                unsigned int k_start,
00685                unsigned int k_end,
00686                const void *,
00687                const void *,
00688                Boolean,
00689                Boolean,
00690                Boolean (*user_cmp)(const void *, void *),
00691                void *cmp_arg,
00692                LinkList *);
00693 
00694     Status next(Boolean *found, unsigned int *found_cnt, void *data, Idx::Key *key, DataBuffer *dataBuffer);
00695 
00696   public:
00708     HIdxCursor(const HIdx *idx,
00709                const void *skey = 0,
00710                const void *ekey = defaultSKey,
00711                Boolean sexcl = False,
00712                Boolean eexcl = False,
00713                Boolean (*user_cmp)(const void *key, void *cmp_arg) = 0,
00714                void *cmp_arg = 0,
00715                int thread_cnt = 0);
00716 
00724     Status next(Boolean *found, void *data = 0, Idx::Key *key = 0);
00725 
00733     Status next(Boolean *found, DataBuffer &data, Idx::Key *key = 0);
00734 
00741     // note: can be only used on data_grouped_by_key index
00742     Status next(unsigned int *found_cnt, Idx::Key *key = 0);
00743 
00744     ~HIdxCursor();
00745   };
00746 
00751 };
00752 
00753 #endif