[2582] | 1 | // ===================================================================
|
---|
| 2 | // $Id: $
|
---|
| 3 | //
|
---|
| 4 | // ktb.cpp
|
---|
| 5 | //
|
---|
| 6 | // KDB - trees for ray tracing, special version for SCCG 2006
|
---|
| 7 | //
|
---|
| 8 | // REPLACEMENT_STRING
|
---|
| 9 | //
|
---|
| 10 | // Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
|
---|
| 11 | // Initial coding by Vlasta Havran, 1998-2001.
|
---|
| 12 |
|
---|
| 13 | // GOLEM library
|
---|
| 14 | #include "ktb8b.h"
|
---|
| 15 | #include "Environment.h"
|
---|
| 16 |
|
---|
| 17 | // standard headers
|
---|
| 18 | #include <algorithm>
|
---|
| 19 |
|
---|
| 20 | namespace GtpVisibilityPreprocessor {
|
---|
| 21 |
|
---|
| 22 | // default constructor
|
---|
| 23 | CKTB8BNodeIterator::CKTB8BNodeIterator()
|
---|
| 24 | {
|
---|
| 25 |
|
---|
| 26 | }
|
---|
| 27 |
|
---|
| 28 | //-------------------------------------------------------------
|
---|
| 29 | // class CKTB8BNodeIterator .. implementation
|
---|
| 30 |
|
---|
| 31 | // test all objects in the leaf for intersection with ray
|
---|
| 32 | // and returns the pointer to closest one if exists
|
---|
| 33 | // and passing through parameter returns in tmax
|
---|
| 34 | int
|
---|
| 35 | CKTB8BNodeIterator::TestFullLeaf(const SimpleRay &ray, const SKTBNode *p)
|
---|
| 36 | {
|
---|
| 37 | ObjectContainer *list = GetObjList(p);
|
---|
| 38 | if (!list) // no object
|
---|
| 39 | return 0;
|
---|
| 40 | ObjectContainer::iterator sc_end = list->end();
|
---|
| 41 |
|
---|
| 42 | int intersected = 0;
|
---|
| 43 | // iterate the whole list and find out the nearest intersection
|
---|
| 44 | for (ObjectContainer::iterator sc = list->begin(); sc != sc_end; sc++) {
|
---|
| 45 | // if the intersection realy lies in the node
|
---|
| 46 | if ((*sc)->CastSimpleRay(ray)) {
|
---|
| 47 | intersected = 1;
|
---|
| 48 | }
|
---|
| 49 | } // for all objects
|
---|
| 50 |
|
---|
| 51 | return intersected;
|
---|
| 52 | }
|
---|
| 53 |
|
---|
| 54 | int
|
---|
| 55 | CKTB8BNodeIterator::TestFullLeaf(const SimpleRay &ray, const SKTBNode *p,
|
---|
| 56 | int indexRay)
|
---|
| 57 | {
|
---|
| 58 | ObjectContainer *list = GetObjList(p);
|
---|
| 59 | if (!list) // no object
|
---|
| 60 | return 0;
|
---|
| 61 | ObjectContainer::iterator sc_end = list->end();
|
---|
| 62 |
|
---|
| 63 | float tclosest = Limits::Infinity;
|
---|
| 64 | int intersected = 0;
|
---|
[2592] | 65 | indexRay += rayOffset;
|
---|
[2582] | 66 | // iterate the whole list and find out the nearest intersection
|
---|
| 67 | for (ObjectContainer::iterator sc = list->begin(); sc != sc_end; sc++) {
|
---|
| 68 | // if the intersection realy lies in the node
|
---|
| 69 | if ((*sc)->CastSimpleRay(ray, indexRay)) {
|
---|
| 70 | // update tclosest !!!!!!!!!!!!!!!!!!!!!!!!!!!!
|
---|
| 71 | // tclosest = ray.
|
---|
| 72 | intersected = 1;
|
---|
| 73 | }
|
---|
| 74 | } // for all objects
|
---|
| 75 |
|
---|
| 76 | return intersected;
|
---|
| 77 | }
|
---|
| 78 |
|
---|
| 79 | // test all objects in the leaf for intersection with ray
|
---|
| 80 | // and find any if exist .. returns this object, otherwise 0
|
---|
| 81 | int
|
---|
| 82 | CKTB8BNodeIterator::HitAnyObj(const SimpleRay &ray, const SKTBNode *p)
|
---|
| 83 | {
|
---|
| 84 | ObjectContainer *list = GetObjList(p);
|
---|
| 85 | if (!list) // no object
|
---|
| 86 | return 0;
|
---|
| 87 | ObjectContainer::iterator sc_end = list->end();
|
---|
| 88 |
|
---|
| 89 | float tclosest = Limits::Infinity;
|
---|
| 90 | int intersected = 0;
|
---|
| 91 | // iterate the whole list and find out the nearest intersection
|
---|
| 92 | for (ObjectContainer::iterator sc = list->begin(); sc != sc_end; sc++) {
|
---|
| 93 | Intersectable *is = (*sc);
|
---|
| 94 | // if the intersection realy lies in the node
|
---|
| 95 | if (is->CastSimpleRay(ray)) {
|
---|
| 96 | // update tclosest !!!!!!!!!!!!!!!!!!!!!!!!!!!!
|
---|
| 97 | // tclosest = ray.
|
---|
| 98 | return 1; // intersected
|
---|
| 99 | }
|
---|
| 100 | } // for all objects
|
---|
| 101 |
|
---|
| 102 | return 0;
|
---|
| 103 | }
|
---|
| 104 |
|
---|
| 105 | const CKTB8BNodeAbstract::SKTBNode*
|
---|
| 106 | CKTB8BNodeIterator::Locate(const Vector3 & /*position*/)
|
---|
| 107 | {
|
---|
| 108 | cerr << "Locate vector - Not yet implemented" << endl;
|
---|
| 109 | return (CKTB8BNodeAbstract::SKTBNode*)0;
|
---|
| 110 | }
|
---|
| 111 |
|
---|
| 112 |
|
---|
| 113 | // ---------------------------------------------------------------------
|
---|
| 114 | // Allocator for KTB tree
|
---|
| 115 |
|
---|
| 116 | // forget the content that is created by previous kd-tree construction
|
---|
| 117 | // or just init for the first use.
|
---|
| 118 | void
|
---|
| 119 | CKTB8BAllocMan::InitForConstructor()
|
---|
| 120 | {
|
---|
| 121 | #ifdef _KTB_CONSTR_STATS
|
---|
| 122 | _stats_interiorCount = 0;
|
---|
| 123 | _stats_bboxCount = 0;
|
---|
| 124 | _stats_leafNodeCount = 0;
|
---|
| 125 | _stats_emptyLeftNodeCount = 0;
|
---|
| 126 | // Aggregate statistics
|
---|
| 127 | _sumLeafDepth = 0;
|
---|
| 128 | _sumFullLeafDepth = 0;
|
---|
| 129 | // The count of object references in leaves
|
---|
| 130 | _sumObjectRefCount = 0;
|
---|
| 131 | // The maximum number of object references in a leaf
|
---|
| 132 | _maxObjectRefInLeaf = 0;
|
---|
| 133 | // surface areas
|
---|
| 134 | _sumSurfaceAreaLeaves = 0.f;
|
---|
| 135 | _sumSurfaceAreaMULcntLeaves = 0.f;
|
---|
| 136 | _sumSurfaceAreaInteriorNodes = 0.f;
|
---|
| 137 | #endif
|
---|
| 138 |
|
---|
| 139 | // This is the statistics
|
---|
| 140 | _currDepth = 0;
|
---|
| 141 | _maxDepth = -1;
|
---|
| 142 | InitPars();
|
---|
| 143 | }
|
---|
| 144 |
|
---|
| 145 | // init the stack of auxiliary variables from min to max
|
---|
| 146 | void
|
---|
| 147 | CKTB8BAllocMan::InitAux(int /*min*/, int /*maxD*/, int maxItemsAtOnce)
|
---|
| 148 | {
|
---|
| 149 | // The size of one entry
|
---|
| 150 | int sizeEntryV = sizeof(SKTBNode);
|
---|
| 151 | // The number of entries to be allocated at once in a block
|
---|
| 152 | // (=size of the block)
|
---|
| 153 | int numEntriesInBlock = 1024;
|
---|
| 154 | // the allignment
|
---|
| 155 | int allignEntrySizeV = sizeof(SKTBNode);
|
---|
| 156 | int allignBlockSizeV = 128;
|
---|
| 157 |
|
---|
| 158 | // Create an allocator in DFS order
|
---|
| 159 | alloc2 = new CAllocContinuous(sizeEntryV, numEntriesInBlock,
|
---|
| 160 | maxItemsAtOnce,
|
---|
| 161 | allignEntrySizeV,
|
---|
| 162 | allignBlockSizeV);
|
---|
| 163 | assert(alloc2);
|
---|
| 164 | // the first allocation is enabled by this command
|
---|
| 165 | alloc2->AllocNewBlock();
|
---|
| 166 | return;
|
---|
| 167 | }
|
---|
| 168 |
|
---|
| 169 | // Read some basic parameters from the environment file
|
---|
| 170 | void
|
---|
| 171 | CKTB8BAllocMan::InitPars()
|
---|
| 172 | {
|
---|
| 173 | Environment::GetSingleton()->GetIntValue("BSP.maxListLength",
|
---|
| 174 | maxListLength);
|
---|
| 175 | Environment::GetSingleton()->GetIntValue("BSP.maxDepthAllowed",
|
---|
| 176 | maxDepthAllowed);
|
---|
| 177 | }
|
---|
| 178 |
|
---|
| 179 | void
|
---|
| 180 | CKTB8BAllocMan::PostBuild()
|
---|
| 181 | {
|
---|
| 182 | // Here it can be some postprocessing of the tree, such as branches
|
---|
| 183 | // collapsing for the same content of leaves etc.
|
---|
| 184 | }
|
---|
| 185 |
|
---|
| 186 | void
|
---|
| 187 | CKTB8BAllocMan::Remove()
|
---|
| 188 | {
|
---|
| 189 | // Release the all memory by blocks, so all the interior nodes
|
---|
| 190 | // and leaves representations. This should be fast.
|
---|
| 191 | alloc2->ReleaseMemory();
|
---|
| 192 | }
|
---|
| 193 |
|
---|
| 194 |
|
---|
| 195 | // Create the representation of the interior node
|
---|
| 196 | SKTBNodeT*
|
---|
| 197 | CKTB8BAllocMan::AllocInteriorNode(int axis, float position,
|
---|
| 198 | int cntLeft, int cntRight)
|
---|
| 199 | {
|
---|
| 200 | #ifdef _DEBUG
|
---|
| 201 | nodeToLink = 0;
|
---|
| 202 | #endif
|
---|
| 203 |
|
---|
| 204 | #ifdef _KTB_CONSTR_STATS
|
---|
| 205 | _stats_interiorCount++;
|
---|
| 206 | #endif
|
---|
| 207 |
|
---|
| 208 | // Just to satisfy the compiler
|
---|
| 209 | cntLeft = cntLeft;
|
---|
| 210 | cntRight = cntRight;
|
---|
| 211 |
|
---|
| 212 | // Alloc a single node
|
---|
| 213 | SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(1));
|
---|
| 214 | nodeToLink = n;
|
---|
| 215 | if (n == 0) {
|
---|
| 216 | // we have to insert a special node that links only
|
---|
| 217 | nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
|
---|
| 218 | assert(nodeToLink);
|
---|
| 219 | nodeToLink->offset = CKTBAxes::EE_Link;
|
---|
| 220 | n = (SKTBNodeT*)(alloc2->NewEntryInNewBlock(1));
|
---|
| 221 | // This is the link
|
---|
| 222 | nodeToLink->linkedNode = n;
|
---|
| 223 | } // if n
|
---|
| 224 |
|
---|
| 225 | assert(n);
|
---|
| 226 | assert(nodeToLink);
|
---|
| 227 |
|
---|
| 228 | // Set the interior node
|
---|
| 229 | assert((axis >=0) && (axis < 3));
|
---|
| 230 | n->offset = axis;
|
---|
| 231 | n->splitPlane = position;
|
---|
| 232 |
|
---|
| 233 | #ifdef _DEBUG_ALLOCATION
|
---|
| 234 | cout << "AllocInterior node adr = " << (void*)n << endl;
|
---|
| 235 | #endif // _DEBUG_ALLOCATION
|
---|
| 236 | // Return the setupped node, but do not forget to
|
---|
| 237 | // use in the parent node to use nodeToLink !!!!
|
---|
| 238 | return n;
|
---|
| 239 | }
|
---|
| 240 |
|
---|
| 241 | // Create the representation of the interior node with box
|
---|
| 242 | SKTBNodeT*
|
---|
| 243 | CKTB8BAllocMan::AllocInteriorNodeWithBox(int axis, float position,
|
---|
| 244 | int cntLeft, int cntRight,
|
---|
[2592] | 245 | const SBBox &tsbox,
|
---|
| 246 | SKTBNodeT* prevMinBoxNode,
|
---|
[2582] | 247 | int depthStore)
|
---|
| 248 | {
|
---|
| 249 | #ifdef _DEBUG
|
---|
| 250 | nodeToLink = 0;
|
---|
| 251 | if ( (position < tsbox.Min(axis)) ||
|
---|
| 252 | (position > tsbox.Max(axis)) ) {
|
---|
| 253 | cerr << "Something wrong with the tree axis = " << axis;
|
---|
| 254 | cerr << " Min(axis) = " << tsbox.Min(axis)
|
---|
| 255 | << " splitValue = " << position
|
---|
| 256 | << " Max(axis) = " << tsbox.Max(axis) << endl;
|
---|
| 257 | abort();;
|
---|
| 258 | }
|
---|
| 259 | #endif
|
---|
| 260 |
|
---|
| 261 | #ifdef _KTB_CONSTR_STATS
|
---|
| 262 | _stats_interiorCount++;
|
---|
| 263 | _stats_minbboxCount++;
|
---|
| 264 | #endif
|
---|
| 265 |
|
---|
| 266 | // Just to satisfy the compiler
|
---|
| 267 | cntLeft = cntLeft;
|
---|
| 268 | cntRight = cntRight;
|
---|
| 269 |
|
---|
| 270 | #ifdef _SHORT_FORM_MINBOX
|
---|
| 271 | // Alloc two nodes = 2*8 Bytes = 16 Bytes
|
---|
| 272 | SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(2));
|
---|
| 273 | nodeToLink = n;
|
---|
| 274 | if (n == 0) {
|
---|
| 275 | // we have to insert a special node that links only
|
---|
| 276 | nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
|
---|
| 277 | assert(nodeToLink);
|
---|
| 278 | nodeToLink->offset = CKTBAxes::EE_Link;
|
---|
| 279 | n = (SKTBNodeT*)(alloc2->NewEntryInNewBlock(2));
|
---|
| 280 | // This is the link
|
---|
| 281 | nodeToLink->linkedNode = n;
|
---|
| 282 | } // if n
|
---|
| 283 |
|
---|
| 284 | assert(n);
|
---|
| 285 | assert(nodeToLink);
|
---|
| 286 |
|
---|
| 287 | // Set the interior node
|
---|
| 288 | assert((axis >=0) && (axis < 3));
|
---|
| 289 | n->offset = (int)CKTBAxes::EE_X_axisBox + axis;
|
---|
| 290 | n->splitPlane = position;
|
---|
| 291 |
|
---|
| 292 | // Set the box
|
---|
| 293 | // and the address to the parent min box node
|
---|
| 294 | (n+1)->parentBoxNode = prevMinBoxNode;
|
---|
| 295 |
|
---|
| 296 | // Here we simply allocate the box for the address
|
---|
| 297 | SBBox *badr = new SBBox;
|
---|
| 298 | assert(badr);
|
---|
| 299 | (n+1)->pointer = (unsigned char *)badr;
|
---|
| 300 |
|
---|
| 301 | // Note that we cannot store the depth here !
|
---|
| 302 | depthStore = depthStore; // to satisfy the compiler
|
---|
| 303 | #else // _SHORT_FORM_MINBOX
|
---|
| 304 | // Alloc two single nodes (16 Bytes) + box (24 Bytes) = 40 Bytes
|
---|
| 305 | SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(5));
|
---|
| 306 | nodeToLink = n;
|
---|
| 307 | if (n == 0) {
|
---|
| 308 | // we have to insert a special node that links only
|
---|
| 309 | nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
|
---|
| 310 | assert(nodeToLink);
|
---|
| 311 | nodeToLink->offset = CKTBAxes::EE_Link;
|
---|
| 312 | n = (SKTBNodeT*)(alloc2->NewEntryInNewBlock(5));
|
---|
| 313 | // This is the link
|
---|
| 314 | nodeToLink->linkedNode = n;
|
---|
| 315 | } // if n
|
---|
| 316 |
|
---|
| 317 | assert(n);
|
---|
| 318 | assert(nodeToLink);
|
---|
| 319 |
|
---|
| 320 | // Set the interior node
|
---|
| 321 | assert((axis >=0) && (axis < 3));
|
---|
| 322 | n->offset = (int)CKTBAxes::EE_X_axisBox + axis;
|
---|
| 323 | n->splitPlane = position;
|
---|
| 324 |
|
---|
| 325 | // Set the box itself
|
---|
| 326 | // and the address to the parent min box node
|
---|
| 327 | (n+1)->parentBoxNode = prevMinBoxNode;
|
---|
| 328 | // here we set the depth of the node (suited for debugging)
|
---|
| 329 | (n+1)->depth = depthStore;
|
---|
| 330 |
|
---|
| 331 | // This is not very nice, we use the address in already allocated
|
---|
| 332 | //item, but this saves memory of 4 Bytes, which allows allingment to 32 Bytes
|
---|
| 333 | //for this entry
|
---|
| 334 | SBBox *badr = (SBBox*)(((char*)n)+16);
|
---|
| 335 | #endif // _SHORT_FORM_MINBOX
|
---|
| 336 |
|
---|
| 337 | // and copy the box content from the function parameters
|
---|
| 338 | *(badr) = tsbox;
|
---|
| 339 |
|
---|
| 340 | #ifdef _DEBUG_ALLOCATION
|
---|
| 341 | cout << "AllocInterior node adr = " << (void*)n << endl;
|
---|
| 342 | #endif // _DEBUG_ALLOCATION
|
---|
| 343 | // Return the setupped node, but do not forget to
|
---|
| 344 | // use in the parent node to use nodeToLink !!!!
|
---|
| 345 | return n;
|
---|
| 346 | }
|
---|
| 347 |
|
---|
| 348 | // Set the pointers to children for the interior node
|
---|
| 349 | void
|
---|
| 350 | CKTB8BAllocMan::SetInteriorNodeLinks(SKTBNodeT *node,
|
---|
| 351 | SKTBNodeT *leftChild,
|
---|
| 352 | SKTBNodeT *rightChild)
|
---|
| 353 | {
|
---|
| 354 | leftChild = leftChild; // to satisfy the compiler
|
---|
| 355 |
|
---|
[2592] | 356 | #if 1
|
---|
| 357 | if (! ((node+1 == leftChild) || (node+2 == leftChild) ||
|
---|
| 358 | (node+5 == leftChild))) {
|
---|
| 359 |
|
---|
| 360 | cout << "Problem with left node linking " << endl;
|
---|
| 361 | }
|
---|
| 362 |
|
---|
| 363 | #endif
|
---|
[2582] | 364 | // Check on correctness of DFS order
|
---|
| 365 | assert( (node+1 == leftChild) || (node+2 == leftChild) || (node+5 == leftChild) );
|
---|
| 366 |
|
---|
| 367 | #ifdef _DEBUG_ALLOCATION
|
---|
| 368 | cout << "SetInteriorNode adr = " << (void*)node
|
---|
| 369 | << " right = " << (void*)rightChild << endl;
|
---|
| 370 | #endif
|
---|
| 371 |
|
---|
| 372 | #ifdef _DEBUG
|
---|
| 373 | // Check if last 3 bits of the address are really zero
|
---|
| 374 | // and hence they can be used for different purposes
|
---|
| 375 | if ( ( ((unsigned int)rightChild) & CKTBAxes::EE_Mask) != 0) {
|
---|
| 376 | // The bug in implementation of DFS order allocator or so
|
---|
| 377 | // This should never happen.
|
---|
| 378 | cerr << "cerr error, node is not 8Bytes aligned, it cannot be linked in DFS" << endl;
|
---|
| 379 | abort();;
|
---|
| 380 | }
|
---|
| 381 | #endif
|
---|
| 382 |
|
---|
| 383 | // Bitwise OR should work correctly
|
---|
| 384 | assert(node->offset <= CKTBAxes::EE_Z_axisBox);
|
---|
| 385 | //assert(node->offset >= 0);
|
---|
| 386 | //(unsigned long)node->offset |= (unsigned long)rightChild;
|
---|
| 387 | node->offset = node->offset | (unsigned int)rightChild;
|
---|
| 388 | #ifdef _DEBUG
|
---|
| 389 | // Compute right child
|
---|
| 390 | SKTBNodeT *p = GetRight(node);
|
---|
| 391 | if (p != rightChild) {
|
---|
| 392 | cerr << "Problem with implementation of setting right child" << endl;
|
---|
| 393 | abort();;
|
---|
| 394 | }
|
---|
| 395 | #endif
|
---|
| 396 |
|
---|
| 397 | return;
|
---|
| 398 | }
|
---|
| 399 |
|
---|
[2592] | 400 | // Set the pointers to children for the interior node
|
---|
| 401 | void
|
---|
| 402 | CKTB8BAllocMan::SetInteriorNodeLeft(SKTBNodeT *node,
|
---|
| 403 | SKTBNodeT *leftChild)
|
---|
| 404 | {
|
---|
| 405 | leftChild = leftChild; // to satisfy the compiler
|
---|
| 406 |
|
---|
| 407 | #if 1
|
---|
| 408 | if (! ((node+1 == leftChild) || (node+2 == leftChild) ||
|
---|
| 409 | (node+5 == leftChild))) {
|
---|
| 410 |
|
---|
| 411 | cout << "Problem with left node linking " << endl;
|
---|
| 412 | abort();
|
---|
| 413 | }
|
---|
| 414 |
|
---|
| 415 | #endif
|
---|
| 416 | // Check on correctness of DFS order
|
---|
| 417 | assert( (node+1 == leftChild) || (node+2 == leftChild) || (node+5 == leftChild) );
|
---|
| 418 |
|
---|
| 419 | // Nothing to do - left link is linked automatically
|
---|
| 420 | return;
|
---|
| 421 | }
|
---|
| 422 |
|
---|
| 423 | // Set the pointers to children for the interior node
|
---|
| 424 | void
|
---|
| 425 | CKTB8BAllocMan::SetInteriorNodeRight(SKTBNodeT *node,
|
---|
| 426 | SKTBNodeT *rightChild)
|
---|
| 427 | {
|
---|
| 428 | assert(node->offset <= CKTBAxes::EE_Z_axisBox);
|
---|
| 429 | //assert(node->offset >= 0);
|
---|
| 430 | //(unsigned long)node->offset |= (unsigned long)rightChild;
|
---|
| 431 | node->offset = node->offset | (unsigned int)rightChild;
|
---|
| 432 | #ifdef _DEBUG
|
---|
| 433 | // Compute right child
|
---|
| 434 | SKTBNodeT *p = GetRight(node);
|
---|
| 435 | if (p != rightChild) {
|
---|
| 436 | cerr << "Problem with implementation of setting right child" << endl;
|
---|
| 437 | abort();;
|
---|
| 438 | }
|
---|
| 439 | #endif
|
---|
| 440 |
|
---|
| 441 | return;
|
---|
| 442 | }
|
---|
| 443 |
|
---|
| 444 |
|
---|
[2582] | 445 | // Create the representation of the leaf. Note that possibly there
|
---|
| 446 | // can be special cases, such as 0, 1, 2, or 3 objects, or in general
|
---|
| 447 | // N objects.
|
---|
| 448 | SKTBNodeT*
|
---|
| 449 | CKTB8BAllocMan::AllocLeaf(int cntObjects)
|
---|
| 450 | {
|
---|
| 451 | #ifdef _DEBUG
|
---|
| 452 | nodeToLink = 0;
|
---|
| 453 | #endif
|
---|
| 454 |
|
---|
| 455 | #ifdef _KTB_CONSTR_STATS
|
---|
| 456 | _stats_leafNodeCount++;
|
---|
| 457 | _sumLeafDepth += _currDepth;
|
---|
| 458 | if (cntObjects) {
|
---|
| 459 | _sumFullLeafDepth += _currDepth;
|
---|
| 460 | // The count of object references in leaves
|
---|
| 461 | _sumObjectRefCount += cntObjects;
|
---|
| 462 | // The maximum number of object references in a leaf
|
---|
| 463 | if (cntObjects > _maxObjectRefInLeaf)
|
---|
| 464 | _maxObjectRefInLeaf = cntObjects;
|
---|
| 465 | }
|
---|
| 466 | else
|
---|
| 467 | _stats_emptyLeftNodeCount++;
|
---|
| 468 | #endif
|
---|
| 469 |
|
---|
| 470 | // Alloc a single node
|
---|
| 471 | SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(1));
|
---|
| 472 | nodeToLink = n;
|
---|
| 473 | if (n == 0) {
|
---|
| 474 | // we have to insert a special node that links only
|
---|
| 475 | n = nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
|
---|
| 476 | assert(nodeToLink);
|
---|
| 477 | // Allocate a new block for the next allocation
|
---|
| 478 | alloc2->AllocNewBlock();
|
---|
| 479 | } // if n
|
---|
| 480 |
|
---|
| 481 | n->offset = CKTBAxes::EE_Leaf;
|
---|
| 482 | n->objlist = 0;
|
---|
| 483 |
|
---|
| 484 | #ifdef _DEBUG_ALLOCATION
|
---|
| 485 | cout << "AllocLeaf adr = " << (void*)n << endl;
|
---|
| 486 | #endif
|
---|
| 487 |
|
---|
| 488 | // Return the node
|
---|
| 489 | return n;
|
---|
| 490 | }
|
---|
| 491 |
|
---|
| 492 | // if active node is empty, then is replaced by full leaf with
|
---|
| 493 | // the object list. In success returns 0, for failure returns 1.
|
---|
| 494 | // The object list is used as it is .. it is not copied !!
|
---|
| 495 | int
|
---|
| 496 | CKTB8BAllocMan::SetFullLeaf(SKTBNodeT *node, const ObjectContainer *objlist)
|
---|
| 497 | {
|
---|
| 498 | assert(node);
|
---|
| 499 | assert(IsLeaf_(node));
|
---|
| 500 |
|
---|
| 501 | #ifdef _DEBUG_ALLOCATION
|
---|
| 502 | cout << "SetFullLeaf adr = " << (void*)node << endl;
|
---|
| 503 | #endif
|
---|
| 504 |
|
---|
| 505 | if ( (objlist == NULL) ||
|
---|
| 506 | (objlist->size() == 0) ) {
|
---|
| 507 | node->objlist = 0;
|
---|
| 508 | }
|
---|
| 509 | else {
|
---|
| 510 | // Set the pointer to the list of objects
|
---|
| 511 | node->objlist = (ObjectContainer *) objlist;
|
---|
| 512 | }
|
---|
| 513 |
|
---|
| 514 | return 0;
|
---|
| 515 | }
|
---|
| 516 |
|
---|
| 517 | }
|
---|