|
|
//+---------------------------------------------------------------------------
//
// Microsoft Windows
// Copyright (C) Microsoft Corporation, 1991 - 2000.
//
// File: MCURSOR.CXX
//
// Contents: Merge Cursor
//
// Classes: CMergeCursor
//
// History: 06-May-91 BartoszM Created
//
// widHeap keyHeap
//
//----------------------------------------------------------------------------
#include <pch.cxx>
#pragma hdrstop
#include <curstk.hxx>
#include "mcursor.hxx"
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::CMergeCursor, public
//
// Synopsis: Create a cursor that merges a number of cursors.
//
// Arguments: [cCursor] -- count of cursors
// [aCursor] -- array of pointers to cursors
//
// History: 06-May-91 BartoszM Created
// 24-Jan-92 AmyA Modified to take CKeyCurArray as a
// parameter.
//
// Notes: The cursors and the array will be deleted by destructor.
// Leaves widHeap empty.
//
//----------------------------------------------------------------------------
CMergeCursor::CMergeCursor( CKeyCurStack & stkCursor ): _keyHeap (), _widHeap ( stkCursor.Count() ){ _widMax = 0; // not valid
// Two step construction of the heap.
// We have to make sure that all cursors have a valid key
int cCursor = stkCursor.Count(); int count = 0;
// remove empty cursors. GetKey() can fail; don't leak cursors.
for ( int i = 0; i < cCursor; i++ ) { CKeyCursor *pCur = stkCursor.Get( i );
Win4Assert( 0 != pCur );
if ( 0 == pCur->GetKey() ) stkCursor.Free( i ); else count++; }
XArray<CKeyCursor *> aCursor( count );
for ( count = 0, i = 0; i < cCursor; i++ ) { CKeyCursor *pCur = stkCursor.Get( i );
if ( 0 != pCur ) aCursor[ count++ ] = pCur; }
delete [] stkCursor.AcqStack(); _keyHeap.MakeHeap ( count, aCursor.Acquire() );
if ( !_keyHeap.IsEmpty() ) { _iid = _keyHeap.Top()->IndexId(); _pid = _keyHeap.Top()->Pid(); }
ciDebugOut(( DEB_ITRACE, "merge cursor has %d cursors\n", count ));} //CMergeCursor
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::GetKey, public
//
// Synopsis: Get current key.
//
// History: 06-May-91 BartoszM Created
//
// Notes: Does not replenish widHeap
// Current key is defined as:
// 1. cur key of all cursors in widHeap, or,
// 2. if widHeap empty, cur key of Top of key heap
// (and cur key of all cursors in keyHeap with
// the same cur key).
//
//----------------------------------------------------------------------------
const CKeyBuf * CMergeCursor::GetKey(){ if ( _widHeap.IsEmpty() ) { if ( _keyHeap.IsEmpty() ) return 0;
return _keyHeap.Top()->GetKey(); }
return _widHeap.Top()->GetKey();}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::WorkId, public
//
// Synopsis: Get current work id.
//
// History: 06-May-91 BartoszM Created
//
// Notes: Current wid is defined as:
// 1. Cur wid of Top of widHeap (and cur wid of all
// cursors in widHeap with the same wid-- however,
// NextWid should not increment the others, since
// they correspond to different index id's), or,
// 2. if widHeap empty: replenish it
//
//----------------------------------------------------------------------------
WORKID CMergeCursor::WorkId(){ if ( _widHeap.IsEmpty() && !ReplenishWid() ) return widInvalid;
return _widHeap.Top()->WorkId();}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::Occurrence, public
//
// Synopsis: Get current occurrence.
//
// History: 06-May-91 BartoszM Created
//
// Notes: Current occurrence is defined as:
// 1. cur occ of Top of widHeap, or,
// 2. if widHeap empty, replenish it.
//
//----------------------------------------------------------------------------
OCCURRENCE CMergeCursor::Occurrence(){ if ( _widHeap.IsEmpty() && !ReplenishWid() ) return OCC_INVALID;
return _widHeap.Top()->Occurrence();}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::GetNextKey, public
//
// Synopsis: Move to next key
//
// Returns: Target key or NULL if no more keys
//
// History: 06-May-91 BartoszM Created
//
// Effects: Updates _iid _pid to the ones of the keyHeap top
//
// Notes: 1. Increment and move to keyHeap all cursors
// from widHeap, or,
// 2. if widHeap empty, increment and reheap all
// cursors in keyHeap with the same cur key
// as the Top.
//
//----------------------------------------------------------------------------
const CKeyBuf * CMergeCursor::GetNextKey(){ if ( ! _widHeap.IsEmpty() ) { // move widHeap to keyHeap advancing all cursors
CKeyCursor * cur; while ( ( cur = _widHeap.RemoveBottom() ) != 0 ) { if ( cur->GetNextKey() == 0 ) { delete cur; } else { _keyHeap.Add ( cur ); } } } else if ( !_keyHeap.IsEmpty() ) { // widHeap was empty. Advance all cursors
// with the lowest key.
CKeyBuf key = *_keyHeap.Top()->GetKey(); do { if ( _keyHeap.Top()->GetNextKey() == 0 ) { delete _keyHeap.RemoveTop(); if ( _keyHeap.IsEmpty () ) return 0; } else { _keyHeap.Reheap(); }
} while ( AreEqual(&key, _keyHeap.Top()->GetKey()) ); } else return 0;
if ( _keyHeap.IsEmpty() ) return 0;
CKeyCursor* cur = _keyHeap.Top(); _pid = cur->Pid(); _iid = cur->IndexId(); return cur->GetKey();}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::NextWorkId, public
//
// Synopsis: Move to next work id
//
// Returns: Target work id or widInvalid if no more wid's for current key
//
// Effects: Updates _iid to the one of the widHeap top
//
//
// History: 06-May-91 BartoszM Created
//
// Notes: The same work id may be returned multiple times,
// corresponding to multiple indexes.
// 1. Increment Top of widHeap and reheap, or,
// 2. if widHeap empty, replenish it
//
//----------------------------------------------------------------------------
WORKID CMergeCursor::NextWorkId(){ if ( _widHeap.IsEmpty() && !ReplenishWid() ) return widInvalid;
_widHeap.Top()->NextWorkId();
_widHeap.Reheap();
CKeyCursor* cur = _widHeap.Top(); _iid = cur->IndexId(); return cur->WorkId();}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::NextOccurrence, public
//
// Synopsis: Move to next occurrence
//
// Returns: Target occurrence or OCC_INVALID if no more occurrences
// for current (wid, index id) combination.
//
// History: 06-May-91 BartoszM Created
//
// Notes: 1. Increment Top of widHeap (do not reheap!), or,
// 2. if widHeap empty, replenish it
//
//----------------------------------------------------------------------------
OCCURRENCE CMergeCursor::NextOccurrence(){ if ( _widHeap.IsEmpty() && !ReplenishWid() ) return OCC_INVALID;
return _widHeap.Top()->NextOccurrence();}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::MaxOccurrence
//
// Synopsis: Returns max occurrence of current wid
//
// History: 20-Jun-96 SitaramR Created
//
//----------------------------------------------------------------------------
OCCURRENCE CMergeCursor::MaxOccurrence(){ if ( _widHeap.IsEmpty() ) return OCC_INVALID;
return _widHeap.Top()->MaxOccurrence();}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::WorkIdCount, public
//
// Synopsis: return wid count
//
// History: 21-Jun-91 BartoszM Created
//
// Notes: 1. Sum up wid count of all cursors in widHeap, or,
// 2. if widHeap empty, replenish it
//
//----------------------------------------------------------------------------
ULONG CMergeCursor::WorkIdCount(){ // Sum up all wid counts for the same key.
// move all cursors with the same key to wid heap
if (_widHeap.IsEmpty() && !ReplenishWid()) { return 0; }
int count = _widHeap.Count(); ULONG widCount = 0; CKeyCursor **curVec = _widHeap.GetVector(); while ( --count >= 0 ) widCount += curVec[count]->WorkIdCount(); // ciDebugOut (( DEB_ITRACE, "merge : wid count %ld\n", widCount ));
return widCount;}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::OccurrenceCount, public
//
// Synopsis: return occurrence count
//
// History: 21-Jun-91 BartoszM Created
//
// Notes: 1. Return occ count of Top of widHeap
// Occ counts of other cursors with the
// same wid do not count! They will
// be returned after NextWorkId is called
// 2. if widHeap empty, replenish it
//
//----------------------------------------------------------------------------
ULONG CMergeCursor::OccurrenceCount(){
if ( _widHeap.IsEmpty() && !ReplenishWid() ) { return 0; }
return _widHeap.Top()->OccurrenceCount();}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::HitCount, public
//
// Synopsis: return occurrence count
//
// History: 27-Feb-92 AmyA Created
//
// Notes: see notes for OccurrenceCount().
//
//----------------------------------------------------------------------------
ULONG CMergeCursor::HitCount(){ return OccurrenceCount();}
//+---------------------------------------------------------------------------
//
// Member: CMergeCursor::ReplenishWid, protected
//
// Synopsis: Replenish the wid heap
//
// Returns: TRUE if successful, FALSE if key heap exhausted
//
// Effects: Updates _iid to the ones of the widHeap top
//
// History: 06-May-91 BartoszM Created
//
//----------------------------------------------------------------------------
BOOL CMergeCursor::ReplenishWid(){
if ( _keyHeap.IsEmpty() ) { return FALSE; }
// Move all cursors with the lowest key
// to widHeap
CKeyBuf key = *(_keyHeap.Top()->GetKey()); do { CKeyCursor* cur = _keyHeap.RemoveTop(); _widHeap.Add ( cur ); } while ( !_keyHeap.IsEmpty() && AreEqual( &key, _keyHeap.Top()->GetKey()) );
_iid = _widHeap.Top()->IndexId(); return TRUE;}
//
// Remove RefillStream() and FreeStream() once NTFS supports
// sparse file operations on parts of a file when other parts
// of the file are mapped. This won't happen any time soon.
//
void CMergeCursor::FreeStream(){ ULONG cCursors = _keyHeap.Count(); CKeyCursor **aCursors = _keyHeap.GetVector();
ciDebugOut(( DEB_ITRACE, "free key heap has %d cursors\n", cCursors ));
for ( ULONG i = 0; i < cCursors; i++ ) aCursors[ i ]->FreeStream();
cCursors = _widHeap.Count(); aCursors = _widHeap.GetVector();
ciDebugOut(( DEB_ITRACE, "free wid heap has %d cursors\n", cCursors ));
for ( i = 0; i < cCursors; i++ ) aCursors[ i ]->FreeStream();} //FreeStream
void CMergeCursor::RefillStream(){ ULONG cCursors = _keyHeap.Count(); CKeyCursor **aCursors = _keyHeap.GetVector();
ciDebugOut(( DEB_ITRACE, "refill key heap has %d cursors\n", cCursors ));
for ( ULONG i = 0; i < cCursors; i++ ) aCursors[ i ]->RefillStream();
cCursors = _widHeap.Count(); aCursors = _widHeap.GetVector();
ciDebugOut(( DEB_ITRACE, "refill wid heap has %d cursors\n", cCursors ));
for ( i = 0; i < cCursors; i++ ) aCursors[ i ]->RefillStream();} //FreeStream
|
