150 lines
3.3 KiB
C++
150 lines
3.3 KiB
C++
//+---------------------------------------------------------------------------
|
|
//
|
|
// Microsoft Windows
|
|
// Copyright (C) Microsoft Corporation, 1991 - 2000.
|
|
//
|
|
// File: DIRTREE.CXX
|
|
//
|
|
// Contents: Directory Tree
|
|
//
|
|
// Classes: CDirTree
|
|
//
|
|
// History: 13-Aug-91 BartoszM Created
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
#include <pch.cxx>
|
|
#pragma hdrstop
|
|
|
|
#include <misc.hxx>
|
|
#include <dirtree.hxx>
|
|
|
|
void CDirTree::Init ( unsigned count )
|
|
{
|
|
//
|
|
// If we are rebuilding the directory tree, cleanup the old one
|
|
//
|
|
if (_count != 0)
|
|
{
|
|
delete _pKeys;
|
|
_pKeys = new CKeyArray(1);
|
|
}
|
|
|
|
ciAssert ( count > 0 );
|
|
_count = count;
|
|
|
|
// How many binary digits are needed
|
|
// to represent numbers from 0 to _count-1?
|
|
|
|
if ( _count > 1 )
|
|
_digits = Log2 ( _count - 1 );
|
|
else
|
|
_digits = 0;
|
|
|
|
_firstLeaf = 1 << _digits;
|
|
}
|
|
|
|
void CDirTree::Init ( CKeyArray& keys, unsigned count )
|
|
{
|
|
Init ( count );
|
|
for ( unsigned n = 1; n < count; n++)
|
|
{
|
|
ciAssert ( keys.Get(n).Pid() != pidAll );
|
|
_pKeys->Add ( Index(n), keys.Get(n) );
|
|
}
|
|
Done ( n );
|
|
}
|
|
|
|
void CDirTree::Add ( unsigned i, const CKeyBuf& key )
|
|
{
|
|
// skip the zerot'th key
|
|
if ( i == 0 )
|
|
return;
|
|
|
|
ciAssert ( &key != 0 );
|
|
ciAssert ( key.Pid() != pidAll );
|
|
|
|
_pKeys->Add ( Index(i), key);
|
|
}
|
|
|
|
unsigned CDirTree::Seek ( const CKey& key ) const
|
|
{
|
|
ciDebugOut (( DEB_PDIR, "CDirTree::Seek %.*ws pid %d\n",
|
|
key.StrLen(), key.GetStr(), key.Pid() ));
|
|
|
|
//----------------------------------------------------
|
|
// Notice: Make sure that pidAll is smaller
|
|
// than any other legal PID. If the search key
|
|
// has pidAll we want to be positioned at the beginning
|
|
// of the range.
|
|
//----------------------------------------------------
|
|
|
|
ciAssert ( pidAll == 0 );
|
|
|
|
for ( unsigned i = 1; i < _firstLeaf; )
|
|
{
|
|
ciDebugOut (( DEB_PDIR, "\tCompare with %.*ws pid %d ",
|
|
_pKeys->Get(i).StrLen(), _pKeys->Get(i).GetStr(), _pKeys->Get(i).Pid() ));
|
|
|
|
if ( key.Compare(_pKeys->Get(i)) < 0 )
|
|
{
|
|
ciDebugOut (( DEB_PDIR, "too big\n" ));
|
|
i = 2 * i;
|
|
}
|
|
else
|
|
{
|
|
ciDebugOut (( DEB_PDIR, "too small or equal\n" ));
|
|
i = 2 * i + 1;
|
|
}
|
|
}
|
|
|
|
return i - _firstLeaf;
|
|
}
|
|
|
|
// Decompose idx = (1, 2^digits - 1) in the following form
|
|
// idx = i * 2^n, where i is odd
|
|
// n counts the number of trailing zeros,
|
|
// i has (digits - n) digits
|
|
//
|
|
// level = digits - n
|
|
// is the level of the tree (root is level 1)
|
|
//
|
|
// i / 2 is the node number within this level
|
|
// it has (level-1) digits
|
|
|
|
unsigned CDirTree::Index( unsigned idx )
|
|
{
|
|
ciAssert (idx != 0);
|
|
|
|
unsigned i = idx;
|
|
unsigned n = 0;
|
|
|
|
while ( (i & 1) == 0 )
|
|
{
|
|
i >>= 1;
|
|
n++;
|
|
}
|
|
|
|
// n = number of trailing 0's
|
|
// i is odd
|
|
|
|
idx = (1 << (_digits - n - 1)) + (i >> 1);
|
|
|
|
ciAssert ( idx < _firstLeaf );
|
|
|
|
return idx;
|
|
}
|
|
|
|
void CDirTree::Done( unsigned i )
|
|
{
|
|
//
|
|
// This can be very expensive, since each key will allocate
|
|
// > 250 bytes and fill them with 0xff. But it's too late to do anything
|
|
// about it since the definition of max key is defined now that we've
|
|
// shipped.
|
|
//
|
|
|
|
for ( ; i < _firstLeaf; i++ )
|
|
_pKeys->FillMax(Index(i));
|
|
}
|