Bdb packages | Design docs | Source docs | Guidelines | Recent releases
	Search | Site Map .

                 

---

/BdbBitMap/BdbBMIndexQueryAPI.cc

Go to the documentation of this file.

// ------------------------------------------------------------------------------
// File:
//      BdbBMIndexQueryAPI.cc
//
// Description:
//      Transient abstract class implmeenting an API to the BitMap index structure.
//      The API is used to access events using index structure. The access 
//      is read-only via (subset of) SQL query.
//
// Environment:
//      Software developed for the BaBar Detector at the SLAC B-Factory
//
// Author List:
//      Jacek Becla, Igor Gaponenko           Original Authors
//
// Copyright Information:
//      Copyright (C) 1997-98      Stanford Linear Accelerator Center
//
// ------------------------------------------------------------------------------

// -------------------------
// -- This Class's Header --
// -------------------------

#ifndef BDBBMINDEXQUERYAPI_HH
#include "BdbBitMap/BdbBMIndexQueryAPI.hh"
#endif

// ---------------------------------
// -- Collaborating Class Headers --
// ---------------------------------

#include "BdbApplication/BdbApplication.hh"

#include "BdbAccess/BdbDbTreeSingleton.hh"

#include "BdbClustering/BdbEvsHdrClusteringHint.hh"
#include "BdbClustering/BdbSimpleClusteringHint.hh"

#include "BdbTrees/BdbDbRegistrator.hh"

#include "AbsEvent/AbsEvent.hh"

#include "BdbEvent/BdbEvent.hh"

#include "BdbEventStore/BdbCollection.hh"
#include "BdbEventStore/BdbEventStore.hh"
#include "BdbEventStore/BdbTreeNodeCollectionIterator.hh"
#include "BdbEventStore/BdbEventStoreIterator.hh"
#include "BdbEventStore/BdbTreeCollection.hh"
#include "BdbEventStore/BdbVectorCollection.hh"

#include "BdbIndexing/BdbIndexingErrors.hh"
#include "BdbIndexing/BdbAbsIndexAPI.hh"
#include "BdbIndexing/BdbQuery.hh"
#include "BdbIndexing/BdbQueryDescr.hh"
#include "BdbIndexing/BdbQueryEstimation.hh"

#include "BdbBitMap/BdbBMDimension.hh"
#include "BdbBitMap/BdbBMBin.hh"

// -----------------------
// -- Local definitions --
// -----------------------

static const d_ULong BITS_31_30 = 0x80000000 | 0x40000000 ;
static const d_ULong BITS_31    = 0x80000000 ;
static const d_ULong BITS_30    = 0x40000000 ;
static const d_ULong BITS_29_00 = 0x3FFFFFFF ;

// ----------------------
// -- Static functions --
// ----------------------

inline d_Boolean IS_COMPRESSED(d_ULong value)
{
    return BITS_31 == ( BITS_31 & value ) ;
}

inline d_Boolean IS_EMPTY(d_ULong value)
{
    return ! ( BITS_29_00 & value ) ;
}

/**  
 **  Constructor. Used for accessing existing index structure.
 **  Requires a read transaction.
 **/

BdbBMIndexQueryAPI::BdbBMIndexQueryAPI() :
BdbAbsIndexQueryAPI("IndexRegistry",
                                        "BitMapIndexStructure")
{}

/**  
 **  Destructor
 **/

BdbBMIndexQueryAPI::~BdbBMIndexQueryAPI()
{}

/**
 **  Report error condition
 **/

void
BdbBMIndexQueryAPI::error(const char* message) const
{
    cout << "BdbBitMap[Events]::error " << message << "." << endl ;
}

/**
 **  Get a persistent reference to the implementation-specific
 **  index structure.
 **/

BdbStatus
BdbBMIndexQueryAPI::lookupIndexStructure(BdbHandle(BdbContObj)& contH,
                                         BdbRef(BdbAbsIndexStructure)& indexRef)
{
        BdbStatus status ;
    BdbRef(BdbBMIndexStructure) bmRef ;

  // Look up an object by its name in the namespace
  // container.

    status = bmRef.lookupObj(contH, getIndexStructureName(), BdbcRead) ;
    if( BdbcSuccess != status ) {
        error(" locate index structure") ;
        return status ;
    }

  // Load some essential information on the database:
  //
  //  - the compression flag (used by vector operations)
  //  - the number of events (used by vector operation NOT for
  //    the correct vector allignment).

    _compressed = bmRef->isCompressed() ;
    _events     = bmRef->getNumEvents() ;

    // Initialize the number of events

  // Return a reference to the structure.

    indexRef = bmRef ;

    return BdbcSuccess ;
}


// ----------------------------------------------------------------------
// -- Execute "trial" query request. Return result of query estimation --
// -- into supplied object.                                            --
// ----------------------------------------------------------------------


BdbStatus
BdbBMIndexQueryAPI::estimate(BdbQueryDescr& descr,
                             BdbQueryEstimation& estimation)
{
    BdbStatus status ;

  // Build the mask (vector) of selected events based on
  // given query description.

    ooVArray(d_ULong) result ;

    status = select(result, descr) ;
    if ( BdbcSuccess != status ) {
        return status ;
    }

  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  - - - - - - - - - - - -
  //  Make some estimations on the query results.
  //
  //  <IMPLEMENTED> (1) In case of the totatl number of the selected events this
  //                    require to count "1" in both compressed and non-compressed
  //                    vectors.
  //  <NOT APPLIED> (2) In case of number of "physical" DBs we have to use the
  //  <NOT APPLIED> (3) There are no ideas what to do with the number of tapes, since we
  //                    don't know for the moment how the files are located on HPSS.
  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  - - - - - - - - - - - -

    BdbRef(BdbBMIndexStructure) indexRef = getBMIndexRef() ;

    estimation.setTotalNumEvents(indexRef->getNumEvents()) ;
    estimation.setNumEvents(estimateNumEvents(result)) ;

    return BdbcSuccess ;
}


// -----------------------------------------------------------------------
// -- FRONT-END: Place results into specified by name events collection --
// -----------------------------------------------------------------------


BdbStatus
BdbBMIndexQueryAPI::execute(BdbQueryDescr& descr,
                            BdbQueryEstimation& estimation,
                            const char* collection)
{
    BdbStatus status ;

  // - - - - - - - - - - - - - - - - - - - - -
  // Initialize context: clustering hints, etc
  // - - - - - - - - - - - - - - - - - - - - -
  
    BdbEventStore* theStore = BdbEventStore::instance( ) ;

    BdbDbRegistrator registrator ;
    BdbDbTreeSingleton::instance()->setRegistrator(&registrator) ;

    BdbAbstractClusteringHint* theTreHint ;
    BdbAbstractClusteringHint* theVecHint ;

    theStore->configureClustering() ;

    if ( theStore->useFullClustering()) {
        theTreHint = new BdbEvsClusteringHint(*theStore) ;
        theVecHint = new BdbEvsClusteringHint(*theStore) ;
    } else {
        theTreHint = new BdbSimpleClusteringHint(*theStore) ;
        theVecHint = new BdbSimpleClusteringHint(*theStore) ;
    }
    theTreHint->setComponent("col") ;
    theVecHint->setComponent("col") ;

    theStore->configureClustering(theTreHint, theVecHint) ;

  // - - - - - - - - - - - - - - - - - - - - - - - -
  // Try to locate collection.  It should not exists
  // - - - - - - - - - - - - - - - - - - - - - - - -

    BdbCollection<BdbEvent> aCollection;
        
    status = theStore->collection( aCollection, collection );
    if ( BdbcSuccess == status ) {
        error("Can not execute the query. Specified output collection already exists.") ;
        return BdbcError ;
    }
    
  // - - - - - - - - - - -
  // Create new collection
  // - - - - - - - - - - -

    status = theStore->treeCollection(aCollection, collection);
    if ( BdbcSuccess != status ) {
        error("Can not execute the query. Failed to create specified output collection.") ;
        return status ;
    }
    aCollection.createDescription(aCollection.name()) ;

  // - - - - - - - - - - - - - - - - - - - - - - - - - - -
  // Go ahead and perform a real query. Place results into
  // specified collection.
  // - - - - - - - - - - - - - - - - - - - - - - - - - - -

    return ( status = execute(descr, estimation, aCollection)) ;
}


// ----------------------------------------------------------------------------
// -- FRONT-END: Place results into specified by reference events collection --
// ----------------------------------------------------------------------------


BdbStatus
BdbBMIndexQueryAPI::execute(BdbQueryDescr& descr,
                            BdbQueryEstimation& estimation,
                            BdbCollection<BdbEvent>& outputCollection)
{
    BdbStatus status ;

  // - - - - - - - - - - - - - - - - - - - - - - - - - -
  // Build the mask (vector) of selected events based on
  // given query description.
  // - - - - - - - - - - - - - - - - - - - - - - - - - -

    ooVArray(d_ULong) result ;

    status = select(result, descr) ;
    if ( BdbcSuccess != status ) {
        return status ;
    }
    
  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  //  Make some estimations on the query results.
  //
  //    <IMPLEMENTED> (1) In case of the totatl number of the selected events this
  //                      require to count "1" in both compressed and non-compressed
  //                      vectors.
  //    <NOT APPLIED> (2) In case of number of "physical" DBs we have to use the
  //    <NOT APPLIED> (3) There are no ideas what to do with the number of tapes, since
  //                      we don't know for the moment how the files are located on HPSS
  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    BdbRef(BdbBMIndexStructure) indexRef = getBMIndexRef() ;

    estimation.setTotalNumEvents(indexRef->getNumEvents()) ;
    estimation.setNumEvents(estimateNumEvents(result)) ;

  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  // Locate the name of the original events collection
  //
  // NOTE: The current implementation allows to execute queries
  //       if the index was built from a real events collection
  //       rather then from just a plain text file.
  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    const char* target = indexRef->getTarget() ;

    if ( strncmp(target, "COLLECTION:", strlen("COLLECTION:"))) {
        error("Can not execute query. The index was not built from an event collection.") ;
        return BdbcError ;
    }

    int   inputCollectionNameLength = strlen(target) - strlen("COLLECTION:") ;
    char* inputCollectionName = new char[inputCollectionNameLength + 1] ;
    
    strcpy(inputCollectionName, &target[strlen(target) - inputCollectionNameLength]) ;

  // - - - - - - - - - - - - - - - - - - - - - - - - -
  // Open input collection and set up events iterator
  // - - - - - - - - - - - - - - - - - - - - - - - - -
  
    BdbEventStore* theStore = BdbEventStore::instance( ) ;
  
    BdbCollection<BdbEvent> inputCollection;
        
    status = theStore->collection( inputCollection, inputCollectionName );
    if ( BdbcSuccess != status ) {
        error("Can not execute the query. Original events collection does not exists.") ;        
        return status ;
    }
    BdbCollectionIterator<BdbEvent> inputCollectionItr(inputCollection) ;

  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  // Now we will translate the selected events (defined by their relative
  // position in the bit string) into real references.
  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   
    BdbHandle(BdbEvent) theEvent ;
    
    d_ULong nElems = result.size() ;
    d_ULong eventNumber = 0 ;

    d_ULong i ;
    d_ULong j ;

    for ( i = 0 ; i < nElems ; i++ ) {

        d_ULong value = result[i] ;

        if ( IS_COMPRESSED(value)) {
            if ( value & BITS_30 ) {

              // Take into account all "1"-s.

                d_ULong elements = BITS_29_00 & value ;

                for ( j = 0 ; j < elements ; j++ ) {

                    status = inputCollectionItr.next(theEvent) ;
                    if ( BdbcSuccess != status ) {

                        error("1: Unable to proceed with query execution.") ;
                        error("2: Failed to fetch next event reference from original collection.") ;
                        error("3: This might be because the index does not match the original collection.") ;

                        return status ;
                    }

                    status = outputCollection.add(theEvent) ;
                    if ( BdbcSuccess != status ) {
                        error("1: Unable to proceed with query execution.") ;
                        error("2: Failed to add next event reference to the output collection.") ;
                            
                        return status ;
                    }
                    eventNumber++ ;
                }
            } else {

              // Skip "0"-es.
              
                d_ULong eventsToSkeep = BITS_29_00 & value ;
                
                for ( j = 0 ; j < eventsToSkeep ; j++ ) {

                    status = inputCollectionItr.next(theEvent) ;
                    if ( BdbcSuccess != status ) {

                        error("1: Unable to proceed with query execution.") ;
                        error("2: Failed to fetch next event reference from original collection.") ;
                        error("3: This might be because the index does not match the original collection.") ;

                        return status ;
                    }
                }
                
                eventNumber += eventsToSkeep ;
            }
        } else {

          // Go along the bits and find all "1"-s.

            for ( j = 0 ; j < 30 ; j++ ) {
                if (( 1 << j ) & ( BITS_29_00 & value )) {

                    status = inputCollectionItr.next(theEvent) ;
                    if ( BdbcSuccess != status ) {

                        error("1: Unable to proceed with query execution.") ;
                        error("2: Failed to fetch next event reference from original collection.") ;
                        error("3: This might be because the index does not match the original collection.") ;

                        return status ;
                    }

                    status = outputCollection.add(theEvent) ;
                    if ( BdbcSuccess != status ) {
                        error("1: Unable to proceed with query execution.") ;
                        error("2: Failed to add next event reference to the output collection.") ;
                            
                        return status ;
                    }
                }
                eventNumber++ ;
            }
        }
    }

  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  // Copy collection description (TAGs profile) from the original
  // colection to the output one.
  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    BdbHandle(HepExplorableDescr) expDescr ;
    
    status = inputCollection.description(expDescr) ;
    if ( BdbcSuccess != status ) {
        error("Unable to get a description for input collection") ;
        return status ;
    }
    
    status = outputCollection.setDescription(expDescr) ;
    if ( BdbcSuccess != status ) {
        error("Unable to set a description for output collection") ;
        return status ;
    }

    return BdbcSuccess ;
}


// ------------------------------------------------------------
// -- Test method. It brakes through the regular interface   --
// -- allowing to obtain the bit-map implementation specific --
// -- results of the query execution.                        --
// ------------------------------------------------------------


BdbStatus
BdbBMIndexQueryAPI::execute(const BdbQueryDescr& descr,
                            BdbQueryEstimation& estimation,
                            ooVArray(d_ULong)& result)
{
    BdbStatus status ;

  // Build the mask (vector) of selected events based on
  // given query description.

    status = select(result, descr) ;
    if ( BdbcSuccess != status ) {
        return status ;
    }

  // Make some estimations on the query results.
  //
  // <IMPLEMENTED> (1) In case of the totatl number of the selected events this
  //                   require to count "1" in both compressed and non-compressed
  //                   vectors.
  // <NOT APPLIED> (2) In case of number of "physical" DBs we have to use the
  // <NOT APPLIED> (3) There are no ideas what to do with the number of tapes, since we
  //                   don't know for the moment how the files are located on HPSS.

    estimation.setNumEvents(estimateNumEvents(result)) ;

    return BdbcSuccess ;
}

/**-----------------------------------------------------------
 ** This helper functions perform an actual processing of the
 ** given request. On return it fills up a bit vector
 ** with the compression information on the selected events.
 **-----------------------------------------------------------
 **/

BdbStatus
BdbBMIndexQueryAPI::select(ooVArray(d_ULong)& result, const BdbQueryDescr& descr)
{

  // Check if the given structure is initialized.

    if ( ! descr.isInitialized()) {
        error("- the wrong structure has been passed for selection.") ;
        return BdbcError ;
    }

  // Start from the root node in the tree.

    return nextNode(result, descr.getHead()) ;
}

BdbStatus
BdbBMIndexQueryAPI::nextNode(ooVArray(d_ULong)& result, const BdbQueryNode* node)
{
    BdbStatus status ;
    ooVArray(d_ULong) left ;
    ooVArray(d_ULong) right ;

  // Check zero reference to the node was passed.
  // This should be treated as a error.

    if ( node == (BdbQueryNode*) 0 ) {
        error("- inconsistent query description. Unexpected NULL pointer.") ;
        return BdbcError ;
    }

  // Process this node.

    if ( node->isLogical()) {

        switch ( node->getLogicalOperation()) {

        case BdbQueryNode::LOP_NOT :

            status = nextNode(left, node->getLeft()) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }

            status = NOT(result, left) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }

            break ;

        case BdbQueryNode::LOP_AND :

            status = nextNode(left, node->getLeft()) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }
            status = nextNode(right, node->getRight()) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }

            status = AND(result, left, right) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }

            break ;

        case BdbQueryNode::LOP_OR :

            status = nextNode(left, node->getLeft()) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }
            status = nextNode(right, node->getRight()) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }

            status = OR(result, left, right) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }

            break ;
        }
    } else {

        status = endNode(result, node) ;
        if ( BdbcSuccess != status ) {
            return status ;
        }
    }

    return BdbcSuccess ;
}

BdbStatus
BdbBMIndexQueryAPI::endNode(ooVArray(d_ULong)& result, const BdbQueryNode* node)
{
    BdbStatus status ;
    d_ULong i ;

  // Take the specified range and calculate the bins
  // that must be OR-ed.

    const char* dimName = node->getName() ;

  // STEP I: Pre-load the following information:
  //
  //  - the reference to the persistent index structure
  //  - reference to the persistent dimension
  //  - the number of events in the database
  //  - the number of bins
  //  - an array of references to the persistent bins

    d_ULong nEvents ;
    d_ULong nBins ;

    BdbRef(BdbBMIndexStructure) indexRef ;
    BdbRef(BdbBMDimension)      dimRef ;
    ooVArray(BdbRef(BdbBMBin))  binRef ;

    indexRef = getBMIndexRef() ;

    status = indexRef->getDimension(dimName, dimRef) ;
    if ( BdbcSuccess != status ) {
        cout << "BdbBMIndexQuery::endNode() - unknown attribute name: "
             << dimName << endl ;
        return status ;
    }

    nEvents = indexRef->getNumEvents() ;
    nBins   = dimRef->getNumBins() ;

    status = binRef.resize(nBins) ;
    if ( BdbcSuccess != status ) {
        cout << "BdbBMIndexQuery::endNode() - failed to resize ooVArray." << endl ;
        return status ;
    }

    for ( i = 0 ; i < nBins ; i++ ) {

        status = dimRef->getBin(i, binRef[i]) ;
        if ( BdbcSuccess != status ) {
          cout << "BdbBMIndexQuery::endNode() - failed to load persistent BdbBMBin object." << endl ;
          return status ;
        }
    }

  // STEP II: Find out a range of bins to be OR-ed together
  //          in order to meet the selection criteria.

    d_ULong from ;     // The bin number to start WITH.
    d_ULong to ;       // The bin number to finish BEFORE.

    d_Float minVal ;   // Minumum range of the query.
    d_Float maxVal ;   // Maxumum range of the query.

    minVal = node->getMinVal() ;
    maxVal = node->getMaxVal() ;

    if ( ! node->isMinDefined()) {
        from = 0 ;
    } else {

        while ( true ) {

            if ( minVal <  dimRef->getMinValue()) {
                from = 0 ;
                break ; // Less then dimension's minimum.
            }

            if ( minVal >= dimRef->getMaxValue()) {
                from = nBins -1 ;
                break ; // More or equal then dimension's maximum.
            }

            d_Boolean from_is_found = false ;

            for ( i = 0 ; i < nBins ; i++ ) {

                if (( minVal >= binRef[i]->getMinValue()) &&
                    ( minVal <  binRef[i]->getMaxValue())) {

                    from = i ;

                    from_is_found = true ;

                    break ;
                }
            }

            if ( ! from_is_found ) {
                cout << "BdbBMIndexQuery::endNode() - internal bug #1." << endl ;
                return BdbcError ;
            }

            break ;     // Within dimension.
        }
    }

    if ( ! node->isMaxDefined()) {
        to = nBins  ;
    } else {

        while ( true ) {

            if ( maxVal <  dimRef->getMinValue()) {
                to = 1 ;
                break ; // Less then dimension's minimum.
            }

            if ( maxVal >= dimRef->getMaxValue()) {
                to = nBins ;
                break ; // More or equal then dimension's maximum.
            }

            d_Boolean to_is_found = false ;

            for ( i = 0 ; i < nBins ; i++ ) {

                if (( maxVal >= binRef[i]->getMinValue()) &&
                    ( maxVal <  binRef[i]->getMaxValue())) {

                    to = i + 1 ;

                    to_is_found = true ;

                    break ;
                }
            }

            if ( ! to_is_found ) {
                cout << "BdbBMIndexQuery::endNode() - internal bug #2." << endl ;
                return BdbcError ;
            }

            break ;     // Within dimension.
        }
    }

    if ( from >= to ) {
        cout << "BdbBMIndexQuery::endNode() - wrong range for attribute: "
             << dimName << endl ;
        return BdbcError ;
    }

  // STEP III: The final action is to go through the selected
  //           bit strings and to "OR" them together.

    ooVArray(d_ULong) tmp ;

    status = ZERO(tmp, nEvents) ;
    if ( BdbcSuccess != status ) {
        cout << "BdbBMIndexQuery::endNode() - error to create temporary bit vector." << endl ;
        return status ;
    }

    for ( i = from ; i < to ; i++ ) {

        result.resize(0) ;  // If we don't do it, the vector length
                            // will increase after each OR.

        status = OR(result, tmp, binRef[i]->getBits()) ;
        if ( BdbcSuccess != status ) {
          cout << "BdbBMIndexQuery::endNode() - operation OR failed for bit vectors." << endl ;
          return status ;
        }
        tmp = result ;  // Save the result for the next operation.
    }

    return BdbcSuccess ;
}

/**-------------------------------------------------------------------
 **  Bit strings operations. Are used by the query estimator
 **  and executor.
 **  All the operations are based on existing arrays.
 **  The output of the vectors is compressed or not depending
 ** on the state of the persistent index structure.
 **
 ** NOTE: (1) The max number of elements (either compressed or not)
 **           is limited by 30 bits, or 10^30.
 **           This is general limitation of all the vector algorithms.
 **
 **       (2) The implementation of the OR, AND operations for the
 **           compressed vetors is not so efficient as it could be.
 **           The situation will be improved in further versions.
 **-------------------------------------------------------------------
 **/

BdbStatus
BdbBMIndexQueryAPI::NOT(ooVArray(d_ULong)& out,
                        const ooVArray(d_ULong)& in)
{
    BdbStatus status ;
    d_ULong i ;
    d_ULong nBits ;

  // (Re-)allocate output vector of the same
  // size as the input one.

    nBits = in.size() ;

    status = out.resize(nBits) ;
    if ( BdbcSuccess != status ) {
        error("- vector resize.") ;
        return status ;
    }

  // Perform NOT for each element depending
  // on the compressing method.

  // DEBUG:    cout << endl ;
  // DEBUG:    cout << "BdbBMIndexQueryAPI::NOT num30 " << nBits << endl ;

    if ( isCompressed()) {

        for ( i = 0 ; i < nBits ; i++ ) {

            d_ULong value  = in[i] ;

            if ( IS_COMPRESSED(value)) {

                out[i] = BITS_31 | ( BITS_30 & ( ~value )) | ( BITS_29_00 & value ) ;

            } else {

                out[i] = BITS_29_00 & ( ~value ) ;

            }

            d_ULong value1 = value ;
            d_ULong value2 = out[i] ;

  // DEBUG:            cout << endl ;
  // DEBUG:            cout << "                       value1: (31) (30) (29..0) = "
  // DEBUG:                 << ( BITS_31 == ( BITS_31 & value1 )) << " "
  // DEBUG:                 << ( BITS_30 == ( BITS_30 & value1 )) << " "
  // DEBUG:                 << ( BITS_29_00 & value1 ) << endl
  // DEBUG:                 << "                       value2: (31) (30) (29..0) = "
  // DEBUG:                 << ( BITS_31 == ( BITS_31 & value2 )) << " "
  // DEBUG:                 << ( BITS_30 == ( BITS_30 & value2 )) << " "
  // DEBUG:                 << ( BITS_29_00 & value2 ) << endl ;

        }

    } else {

      // The most significant two (31,30) bits
      // are zero-ed.

        for ( i = 0 ; i < nBits ; i++ ) {
            out[i] = BITS_29_00 & ( ~in[i] ) ;
        }
    }

  // Make a "last word alignment correction", by suppressing all meaningles
  // fantom "1" in the last word.
  // As it's might be seen from the code below, this kind of correction
  // is only done, when the last word is uncompressed and contains
  // less then 30 meaningfull bits.
  //
  // NOTE: The correction mechanism is based on an idea of a "magic
  //       quantum" of 30 events.

    d_ULong rem30 = getNumEvents() % 30 ;

    if ( rem30 && nBits ) {

      // DEBUG:     cout << endl ;
      // DEBUG:     cout << "BdbBMIndexQueryAPI::NOT rem30 " << rem30 << endl ;

        if ( ! IS_COMPRESSED(out[nBits-1])) {

          // Make a proper mask in order to enable the meaningfull
          // bits only.

            d_ULong bits29_00 = 0 ;

            for ( i = 0 ; i < rem30 ; i++ ) {
                bits29_00 = ( 1 << i ) | bits29_00 ;
            }

            d_ULong value1 = out[nBits-1] ;

            out[nBits-1] = bits29_00 & out[nBits-1] ;

            d_ULong value2 = out[nBits-1];

          // DEBUG:            cout << endl ;
          // DEBUG:            cout << "                       value1: (31) (30) (29..0) = "
          // DEBUG:                 << ( BITS_31 == ( BITS_31 & value1 )) << " "
          // DEBUG:                 << ( BITS_30 == ( BITS_30 & value1 )) << " "
          // DEBUG:                 << ( BITS_29_00 & value1 ) << endl
          // DEBUG:                 << "                       value2: (31) (30) (29..0) = "
          // DEBUG:                 << ( BITS_31 == ( BITS_31 & value2 )) << " "
          // DEBUG:                 << ( BITS_30 == ( BITS_30 & value2 )) << " "
          // DEBUG:                 << ( BITS_29_00 & value2 ) << endl ;

        }
    }

    return BdbcSuccess ;
}

BdbStatus
BdbBMIndexQueryAPI::AND(ooVArray(d_ULong)& out,
                        const ooVArray(d_ULong)& in1,
                        const ooVArray(d_ULong)& in2)
{
    BdbStatus status ;
    d_ULong i ;
    d_ULong size1 = in1.size() ;
    d_ULong size2 = in2.size() ;

  // Perform AND depending
  // on the compressing method.

    if ( isCompressed()) {

        CompressionContext context(out) ;

        d_ULong num30 = getNumEvents() / 30 ;
        d_ULong rem30 = getNumEvents() % 30 ;

        d_ULong next1 = 0 ;
        d_ULong next2 = 0 ;

      // First we perform operation on "full" 30-bits words.

        d_ULong value1 ;
        d_ULong value2 ;

        d_ULong p1 ;
        d_ULong p2 ;

        d_Boolean empty1 = true ;
        d_Boolean empty2 = true ;

        for ( i = 0 ; i < num30 ; i++ ) {

          // Load the next (compressed/un-compressed) words
          // if nessesary.
          // Advance the "next" indexes as well.
          //
          // NOTE: indirect checking for the vectors consistency
          //       is done before to load next portion of data.

            if ( empty1 ) {

                if ( next1 >= size1 ) {
                    error("- input vectors are inconsistent.") ;
                    return BdbcError ;
                }

                value1 = in1[next1++] ;
            }

            if ( empty2 ) {

                if ( next2 >= size1 ) {
                    error("- input vectors are inconsistent.") ;
                    return BdbcError ;
                }

                value2 = in2[next2++] ;
            }

          // Get next portion of 30 bits depending
          // on whether the input word is compressed or not.
          // Update "empty" flag if desired.

            if ( IS_COMPRESSED(value1)) {

                p1 = GET_30(value1) ;
                empty1 = IS_EMPTY(value1) ;

            } else {

                p1 = value1 ;
                empty1 = true ;

            }

            if ( IS_COMPRESSED(value2)) {

                p2 = GET_30(value2) ;
                empty2 = IS_EMPTY(value2) ;

            } else {

                p2 = value2 ;
                empty2 = true ;

            }

          // Perform the operation on the values.
          // Save the results in the output vector.

            status = context.compress(p1 & p2, 0) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }

        }

      // Then we perform operation on the last word having less
      // then 30 usefull bits if desired, of course.
      // Save results in output vector.

        if ( rem30 ) {

          // Check if both vectors have the same length.

            if (( next1 >= size1 ) || ( next2 >= size2 )) {
                error("- input vectors are inconsistent.") ;
                return BdbcError ;
            }

            status = context.compress(in1[next1] & in2[next2], rem30) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }
        }

      // Synchronize the context.

        status = context.synchronize() ;
        if ( BdbcSuccess != status ) {
            return status ;
        }

    } else {

      // Check if both vectors have the same length.

        if ( size1 != size2 ) {
            error("- vectors have different length.") ;
            return BdbcError ;
        }

      // (Re-)allocate output vector of the same
      // size as the input ones.

         status = out.resize(size1) ;
        if ( BdbcSuccess != status ) {
            error("- vector resize.") ;
            return status ;
        }

        for ( i = 0 ; i < size1 ; i++ ) {
            out[i] = in1[i] & in2[i] ;
        }
    }

    return BdbcSuccess ;
}

BdbStatus
BdbBMIndexQueryAPI::OR(ooVArray(d_ULong)& out,
                       const ooVArray(d_ULong)& in1,
                       const ooVArray(d_ULong)& in2)
{
    BdbStatus status ;
    d_ULong i ;
    d_ULong size1 = in1.size() ;
    d_ULong size2 = in2.size() ;

  // Perform OR depending
  // on the compressing method.

    if ( isCompressed()) {

        CompressionContext context(out) ;

        d_ULong num30 = getNumEvents() / 30 ;
        d_ULong rem30 = getNumEvents() % 30 ;

      // DEBUG:        cout << "BdbBMIndexQueryAPI::OR" << endl
      // DEBUG:             << "    num30 = " << num30  << endl
      // DEBUG:             << "    rem30 = " << rem30  << endl
      // DEBUG:             << "    size1 = " << size1  << endl
      // DEBUG:             << "    size2 = " << size2  << endl ;

        d_ULong next1 = 0 ;
        d_ULong next2 = 0 ;

      // First we perform operation on "full" 30-bits words.

        d_ULong value1 ;
        d_ULong value2 ;

        d_ULong p1 ;
        d_ULong p2 ;

        d_Boolean empty1 = true ;
        d_Boolean empty2 = true ;

        for ( i = 0 ; i < num30 ; i++ ) {

          // Load the next (compressed/un-compressed) words
          // if nessesary.
          // Advance the "next" indexes as well.
          //
          // NOTE: indirect checking for the vectors consistency
          //       is done before to load next portion of data.

            if ( empty1 ) {

                if ( next1 >= size1 ) {
                    error("- input vectors are inconsistent.") ;

                    cout << "BdbBMIndexQueryAPI::OR" << endl
                         << "    i     = " << i      << endl
                         << "    next1 = " << next1  << endl ;

                    return BdbcError ;
                }

                value1 = in1[next1++] ;
            }

            if ( empty2 ) {

                if ( next2 >= size2 ) {
                    error("- input vectors are inconsistent.") ;

                    cout << "BdbBMIndexQueryAPI::OR" << endl
                         << "    i     = " << i      << endl
                         << "    next2 = " << next2  << endl ;

                    return BdbcError ;
                }

                value2 = in2[next2++] ;
            }

          // DEBUG:            cout << endl ;
          // DEBUG:            cout << "BdbBMIndexQueryAPI::OR num30" << endl
          // DEBUG:                 << "                       value1: (31) (30) (29..0) = "
          // DEBUG:                 << ( BITS_31 == ( BITS_31 & value1 )) << " "
          // DEBUG:                 << ( BITS_30 == ( BITS_30 & value1 )) << " "
          // DEBUG:                 << ( BITS_29_00 & value1 ) << endl
          // DEBUG:                 << "                       value2: (31) (30) (29..0) = "
          // DEBUG:                 << ( BITS_31 == ( BITS_31 & value2 )) << " "
          // DEBUG:                 << ( BITS_30 == ( BITS_30 & value2 )) << " "
          // DEBUG:                 << ( BITS_29_00 & value2 ) << endl ;

          // Get next portion of 30 bits depending
          // on whether the input word is compressed or not.
          // Update "empty" flag if desired.

            if ( IS_COMPRESSED(value1)) {

                p1 = GET_30(value1) ;
                empty1 = IS_EMPTY(value1) ;

            } else {

                p1 = value1 ;
                empty1 = true ;

            }

            if ( IS_COMPRESSED(value2)) {

                p2 = GET_30(value2) ;
                empty2 = IS_EMPTY(value2) ;

            } else {

                p2 = value2 ;
                empty2 = true ;

            }

          // DEBUG:            cout << endl
          // DEBUG:                 << "                       value1: (31) (30) (29..0) = "
          // DEBUG:                 << ( BITS_31 == ( BITS_31 & value1 )) << " "
          // DEBUG:                 << ( BITS_30 == ( BITS_30 & value1 )) << " "
          // DEBUG:                 << ( BITS_29_00 & value1 ) << endl
          // DEBUG:                 << "                       value2: (31) (30) (29..0) = "
          // DEBUG:                 << ( BITS_31 == ( BITS_31 & value2 )) << " "
          // DEBUG:                 << ( BITS_30 == ( BITS_30 & value2 )) << " "
          // DEBUG:                 << ( BITS_29_00 & value2 ) << endl ;

          // Perform the operation on the values.
          // Save the results in the output vector.

            status = context.compress(p1 | p2, 0) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }

        }

      // Then we perform operation on the last word having less
      // then 30 usefull bits if desired, of course.
      // Save results in output vector.

        if ( rem30 ) {

          // Check if both vectors have the same length.

            if (( next1 >= size1 ) || ( next2 >= size2 )) {
                error("- input vectors are inconsistent.") ;
                return BdbcError ;
            }

          // DEBUG:            d_ULong value1 = in1[next1] ;
          // DEBUG:            d_ULong value2 = in2[next2] ;
          // DEBUG:
          // DEBUG:            cout << endl ;
          // DEBUG:            cout << "BdbBMIndexQueryAPI::OR rem30" << endl
          // DEBUG:                 << "                       value1: (31) (30) (29..0) = "
          // DEBUG:                 << ( BITS_31 == ( BITS_31 & value1 )) << " "
          // DEBUG:                 << ( BITS_30 == ( BITS_30 & value1 )) << " "
          // DEBUG:                 << ( BITS_29_00 & value1 ) << endl
          // DEBUG:                 << "                       value2: (31) (30) (29..0) = "
          // DEBUG:                 << ( BITS_31 == ( BITS_31 & value2 )) << " "
          // DEBUG:                 << ( BITS_30 == ( BITS_30 & value2 )) << " "
          // DEBUG:                 << ( BITS_29_00 & value2 ) << endl ;

            status = context.compress(in1[next1] | in2[next2], rem30) ;
            if ( BdbcSuccess != status ) {
                return status ;
            }
        }

      // Synchronize the context.

        status = context.synchronize() ;
        if ( BdbcSuccess != status ) {
            return status ;
        }

    } else {

      // Check if both vectors have the same length.

        if ( size1 != size2 ) {
            error("- vectors have different length.") ;
            return BdbcError ;
        }

      // (Re-)allocate output vector of the same
      // size as the input ones.

        status = out.resize(size1) ;
        if ( BdbcSuccess != status ) {
            error("- vector resize.") ;
            return status ;
        }

        for ( i = 0 ; i < size1 ; i++ ) {
            out[i] = in1[i] | in2[i] ;
        }
    }

    return BdbcSuccess ;
}

BdbStatus
BdbBMIndexQueryAPI::ONE(ooVArray(d_ULong)& out,
    d_ULong elements)
{
    return ONE_OR_ZERO(out, elements, 1) ;
}

BdbStatus
BdbBMIndexQueryAPI::ZERO(ooVArray(d_ULong)& out,
    d_ULong elements)
{
    return ONE_OR_ZERO(out, elements, 0) ;
}

BdbStatus
BdbBMIndexQueryAPI::ONE_OR_ZERO(ooVArray(d_ULong)& out,
                                d_ULong elements,
                                d_ULong bit)
{
    BdbStatus status ;
    d_ULong i ;
    d_ULong vectorSize ;
    d_ULong num30 = (BITS_29_00 & elements) / 30 ;  // Use 30 bits only.
    d_ULong rem30 = (BITS_29_00 & elements) % 30 ;  // Use 30 bits only.

  // Create a bit vector with all the elements set either to "1" or to "0",
  // depending on the value of specified parameter.
  // The vector is created either compressed or not depending
  // on the status of the open database.

    if ( isCompressed()) {

      // COMPRESSED vectors.

        vectorSize = 1 ;
        if ( rem30 ) {
            vectorSize++ ;
        }

        status = out.resize(vectorSize) ;
        if ( BdbcSuccess != status ) {
            error("- vector resize.") ;
            return status ;
        }

      // Compress the first word of the vector.

        out[0] = ( BITS_31 | ( bit << 30 )) | ( 30 * num30 ) ;

      // Fill the second word of the vector by raw bit string if desired.

        if ( rem30 ) {

            out[1] = 0 ;

            for ( i = 0 ; i < rem30 ; i++ ) {
                out[1] = out[1] | ( bit << i ) ;
            }
        }

    } else {

      // NON-COMPRESSED vectors.

        vectorSize = num30 ;
        if ( rem30 ) {
            vectorSize++ ;
        }

        status = out.resize(vectorSize) ;
        if ( BdbcSuccess != status ) {
            error("- vector resize.") ;
            return status ;
        }

      // Fill the first complete words of the vector by
      // raw bit strings.

        for ( d_ULong j = 0 ; j < vectorSize - 1 ; j++ ) {

            out[j] = 0 ;

            for ( i = 0 ; i < 30 ; i++ ) {
                out[j] = out[j] | ( bit << i ) ;
            }

        }

      // Fill the last word of the vector by raw bit string if desired.

        if ( rem30 ) {

            out[vectorSize-1] = 0 ;

            for ( i = 0 ; i < rem30 ; i++ ) {
                out[vectorSize-1] = out[vectorSize-1] | ( bit << i ) ;
            }
        }
    }

    return BdbcSuccess ;
}

d_ULong
BdbBMIndexQueryAPI::GET_30(d_ULong& value)
{

  // Decrement input value by 30.

    value = ( BITS_31_30 & value ) | (( BITS_29_00 & value ) - 30 ) ;

  // Return the mask of "30-th" depending on the compressing
  // contents: "1" or "0".

    if ( BITS_30 == ( BITS_30 & value ))
        return BITS_29_00 ;
    else
        return 0 ;
}


/** ----------------------------------------------------------
 ** The following helper functions gather the query estimation
 ** statistics based on already done events pre-selections.
 ** ----------------------------------------------------------
 **/

d_ULong
BdbBMIndexQueryAPI::estimateNumEvents(const ooVArray(d_ULong)& in)
{
    d_ULong events = 0 ;
    d_ULong vectorSize = in.size() ;

  // DEBUG:    cout << endl ;
  // DEBUG:    cout << "BdbBMIndexQueryAPI::estimateNumEvents vectorSize = " << vectorSize << endl ;
  // DEBUG:
  // DEBUG:    cout << "1: events = " << events << endl ;

    for ( d_ULong i = 0 ; i < vectorSize ; i++ ) {

        d_ULong value = in[i] ;


      // DEBUG:        cout << endl ;
      // DEBUG:        cout << "                       value:  (31) (30) (29..0) = "
      // DEBUG:             << ( BITS_31 == ( BITS_31 & value )) << " "
      // DEBUG:             << ( BITS_30 == ( BITS_30 & value )) << " "
      // DEBUG:             << ( BITS_29_00 & value ) << endl ;

      // For compressed words, we take into account only those
      // words where the "1"-s were compressed.
      //
      // Otherwise we count each bit in a word. In this case
      // a small optimization is done in order to skip the completelly
      // "empty" (= 0) words.

        d_ULong mask = ( BITS_31_30 & value ) ;

        switch ( mask ) {

        case BITS_31_30:

            events = events + ( BITS_29_00 & value ) ;

          // DEBUG:            cout << "2: events = " << events << endl ;

            break ;

        case BITS_31:
        case BITS_30:

          // DEBUG:            cout << "x: value      = " << value << endl ;
          // DEBUG:            cout << "   mask       = " << mask  << endl ;
          // DEBUG:            cout << "   BITS_31_30 = " << BITS_31_30  << endl ;

            break ;

        default:

            if ( value ) {
                for ( d_ULong j = 0 ; j < 30 ; j++ ) {
                    if ( value & ( 1 << j )) {
                        events++ ;
                    }
                }
            }

          // DEBUG:            cout << "3: events = " << events << endl ;

            break ;
        }
    }

  // DEBUG:    cout << "4: events = " << events << endl ;

    return events ;
}

/**--------------------------
 **  Transaction management
 **--------------------------
 **/

void
BdbBMIndexQueryAPI::startUpdate( const char* theTag )
{
    BdbApplication* theApp = BdbApplication::instance( );
    theApp->startUpdate( "Indexing", theTag );
}

void
BdbBMIndexQueryAPI::startRead( const char* theTag )
{
    BdbApplication* theApp = BdbApplication::instance( );
    theApp->startRead( "Indexing", theTag );
}

void
BdbBMIndexQueryAPI::abort( )
{
    BdbApplication* theApp = BdbApplication::instance( );
    theApp->abort( "Indexing" );
}

void
BdbBMIndexQueryAPI::commit( )
{
    BdbApplication* theApp = BdbApplication::instance( );
    theApp->commit( "Indexing" );
}

/** -----------------------------------------------------------
 **  Implementation for the nested class of CompressionContext
 ** -----------------------------------------------------------
 **/

BdbBMIndexQueryAPI::CompressionContext::CompressionContext(ooVArray(d_ULong)& out) :
_isCompressing(false),
_out(out)
{
}

BdbBMIndexQueryAPI::CompressionContext::~CompressionContext()
{
    synchronize() ;
}

BdbStatus
BdbBMIndexQueryAPI::CompressionContext::compress(d_ULong value, d_ULong rem30)
{
    BdbStatus status ;

  // Is input value compressed ?

    if ( IS_COMPRESSED(value)) {

        if ( _isCompressing ) {

          // Are we compressing the same ("0" or "1")?

            if (((   _isZero ) && ( ! value ))
                               ||
                (( ! _isZero ) && (   value ))) {

              // Yes. We are already compressing the same.
              // Here we just update the compression counter.

              _counter += ( BITS_29_00 & value ) ;

            } else {

              // Since we were compressing "something" different,
              // first we have to flash it and then start
              // compressing new stuff.

                status = synchronize() ;
                if ( status != BdbcSuccess ) {
                    return status ;
                }

                _isCompressing = true ;
                _isZero        = ( BITS_30 != ( BITS_30 & value )) ;
                _counter       = ( BITS_29_00 & value ) ;

            }

        } else {

          // Start compressing new stuff.

            _isCompressing = true ;
            _isZero        = ( BITS_30 != ( BITS_30 & value )) ;
            _counter       = ( BITS_29_00 & value ) ;

        }

    } else {

      // Check if it's the last uncompleted word of the bit string,
      // having other then 30 "usefull" bits.
      // In this case we just flush the existing compression and flush
      // this last word as well.
      // Otherwise we will try to make a routine compression if possible.

        if ( rem30 ) {

            if ( _isCompressing ) {

                status = synchronize() ;
                if ( status != BdbcSuccess ) {
                    return status ;
                }
            }

          // Select meaningfull bits only.

            d_ULong usefull_bits = 0 ;

            for ( d_ULong i = 0 ; i < rem30 ; i++ ) {
              usefull_bits = ( 1 << i ) | usefull_bits ;
            }

            value = usefull_bits & value ;

          // Then imediatelly flash the new value.

            status = _out.extend(value) ;
            if ( status != BdbcSuccess ) {
                return status ;
            }

        } else {

          // Possible to compress this word?

            if (( BITS_29_00 == ( BITS_29_00 & value )) || ( ! value )) {

                if ( _isCompressing ) {

                  // Are we compressing the same ("0" or "1")?

                    if (((   _isZero ) && ( ! value ))
                                       ||
                        (( ! _isZero ) && (   value ))) {

                      // Yes. We are already compressing the same.
                      // Here we just update the compression counter.

                        _counter += 30 ;

                    } else {

                      // Since we were compressing "something" different,
                      // first we have to flash it and then start
                      // compressing new stuff.

                        status = synchronize() ;
                        if ( status != BdbcSuccess ) {
                            return status ;
                        }

                        _isCompressing = true ;
                        _isZero        = ! value ;
                        _counter       = 30 ;

                    }
                } else {

                  // Start compressing new stuff.

                    _isCompressing = true ;
                    _isZero        = ! value ;
                    _counter       = 30 ;

                }

            } else {

              //  Compressing is not possible.
              //  If we are already compressing somthing, we should
              //  flash compression buffer before to flush the temporary one.

                status = synchronize() ;
                if ( status != BdbcSuccess ) {
                    return status ;
                }

              // Then imediatelly flash the new value.

                status = _out.extend(value) ;
                if ( status != BdbcSuccess ) {
                    return status ;
                }
            }
        }
    }

  // DEBUG:    cout << "CompressionContext: value       = " << value
  //                << "  _counter = " << _counter << endl ;
  // DEBUG:    cout << "                    _out.size() =" << (d_ULong) _out.size() << endl ;

    return BdbcSuccess ;
}

BdbStatus
BdbBMIndexQueryAPI::CompressionContext::synchronize()
{
    BdbStatus status ;

  //  If we are already compressing somthing, we should
  //  flash compression buffer.

    if ( _isCompressing ) {

        if ( _isZero ) {
            _counter = BITS_31    | _counter ;
        } else {
            _counter = BITS_31_30 | _counter ;
        }

        status = _out.extend(_counter) ;
        if ( status != BdbcSuccess ) {
            return status ;
        }

        _isCompressing = false ;
    }

    return BdbcSuccess ;
}

/////////////////
// End Of File //
/////////////////

 

---

BaBar Public Site | SLAC | News | Links | Who's Who | Contact Us

Page Owner: Jacek Becla
Last Update: October 04, 2002