Source/System/State/Shader/Base/OSGShaderCacheTree.inl

   1 /*---------------------------------------------------------------------------*\
   2  *                                OpenSG                                     *
   3  *                                                                           *
   4  *                                                                           *
   5  *             Copyright (C) 2000-2002 by the OpenSG Forum                   *
   6  *                                                                           *
   7  *                            www.opensg.org                                 *
   8  *                                                                           *
   9  *   contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de          *
  10  *                                                                           *
  11 \*---------------------------------------------------------------------------*/
  12 /*---------------------------------------------------------------------------*\
  13  *                                License                                    *
  14  *                                                                           *
  15  * This library is free software; you can redistribute it and/or modify it   *
  16  * under the terms of the GNU Library General Public License as published    *
  17  * by the Free Software Foundation, version 2.                               *
  18  *                                                                           *
  19  * This library is distributed in the hope that it will be useful, but       *
  20  * WITHOUT ANY WARRANTY; without even the implied warranty of                *
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
  22  * Library General Public License for more details.                          *
  23  *                                                                           *
  24  * You should have received a copy of the GNU Library General Public         *
  25  * License along with this library; if not, write to the Free Software       *
  26  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
  27  *                                                                           *
  28 \*---------------------------------------------------------------------------*/
  29 /*---------------------------------------------------------------------------*\
  30  *                                Changes                                    *
  31  *                                                                           *
  32  *                                                                           *
  33  *                                                                           *
  34  *                                                                           *
  35  *                                                                           *
  36  *                                                                           *
  37 \*---------------------------------------------------------------------------*/
  38
  39 OSG_BEGIN_NAMESPACE
  40
  41 /*---------------------------------------------------------------------------*/
  42 /*---------------------------------------------------------------------------*/
  43
  44 template<class ObjectT> inline
  45 ObjectT *ShaderVectorCache<ObjectT>::find(const IdStore &vIds)
  46 {
  47     typename ObjectStore::const_iterator sIt =
  48         std::lower_bound(_vObjectStore.begin(),
  49                          _vObjectStore.end  (),
  50                           vIds);
  51
  52     if(sIt == _vObjectStore.end())
  53     {
  54         return NULL;
  55     }
  56
  57     if(sIt->first != vIds)
  58     {
  59         return NULL;
  60     }
  61
  62     return sIt->second;
  63 }
  64
  65 template<class ObjectT> inline
  66 bool ShaderVectorCache<ObjectT>::add (const IdStore &vIds,
  67                                             ObjectT *pObject)
  68 {
  69     bool returnValue = false;
  70
  71     typename ObjectStore::iterator sIt = std::lower_bound(_vObjectStore.begin(),
  72                                                           _vObjectStore.end  (),
  73                                                            vIds               );
  74
  75
  76     if(sIt == _vObjectStore.end())
  77     {
  78         _vObjectStore.push_back(StoreElement(vIds, pObject));
  79
  80         returnValue = true;
  81     }
  82     else if(sIt->first != vIds)
  83     {
  84         _vObjectStore.insert(sIt, StoreElement(vIds, pObject));
  85
  86         returnValue = true;
  87     }
  88
  89     return returnValue;
  90 }
  91
  92 template<class ObjectT> inline
  93 void ShaderVectorCache<ObjectT>::sub(UInt32 uiIdx)
  94 {
  95     typename ObjectStore::      iterator sIt  = _vObjectStore.begin();
  96     typename ObjectStore::const_iterator sEnd = _vObjectStore.end  ();
  97
  98
  99     while(sIt != sEnd)
 100     {
 101         IdStore::const_iterator idIt  = std::find(sIt->first.begin(),
 102                                                   sIt->first.end  (),
 103                                                   uiIdx);
 104
 105         if(idIt != sIt->first.end())
 106         {
 107             sIt  = _vObjectStore.erase(sIt);
 108             sEnd = _vObjectStore.end();
 109         }
 110         else
 111         {
 112             ++sIt;
 113         }
 114     }
 115 }
 116
 117 template<class ObjectT> inline
 118 void ShaderVectorCache<ObjectT>::dumpDot(const Char8 *szFilename)
 119 {
 120 }
 121
 122 template<class ObjectT>
 123 template <typename ElemDestFunc> inline
 124 void ShaderVectorCache<ObjectT>::destroy(ElemDestFunc destFunc)
 125 {
 126 #ifndef OSG_SHC_REF_CLEANUP
 127     typename ObjectStore::      iterator sIt  = _vObjectStore.begin();
 128     typename ObjectStore::const_iterator sEnd = _vObjectStore.end  ();
 129
 130     for(; sIt != sEnd; ++sIt)
 131     {
 132         (destFunc)(sIt->second);
 133
 134         sIt->second = NULL;
 135     }
 136 #endif
 137
 138 }
 139
 140 template<class ObjectT> inline
 141 ShaderVectorCache<ObjectT>::ShaderVectorCache(void) :
 142     _vObjectStore()
 143 {
 144 }
 145
 146 template<class ObjectT> inline
 147 ShaderVectorCache<ObjectT>::~ShaderVectorCache(void)
 148 {
 149 }
 150
 151
 152
 153 /*---------------------------------------------------------------------------*/
 154 /*---------------------------------------------------------------------------*/
 155
 156 template<class ObjectT> inline
 157 ObjectT *ShaderMapCache<ObjectT>::find(const IdStore &vIds)
 158 {
 159     typename ObjectStore::const_iterator sIt = _vObjectStore.find(vIds);
 160
 161     if(sIt == _vObjectStore.end())
 162     {
 163         return NULL;
 164     }
 165
 166     return sIt->second;
 167 }
 168
 169 template<class ObjectT> inline
 170 bool ShaderMapCache<ObjectT>::add (const IdStore &vIds,
 171                                          ObjectT *pObject)
 172 {
 173     bool returnValue = false;
 174
 175     typename ObjectStore::iterator sIt = _vObjectStore.lower_bound(vIds);
 176
 177
 178     if(sIt == _vObjectStore.end() || sIt->first != vIds)
 179     {
 180         _vObjectStore.insert(sIt, std::make_pair(vIds, pObject));
 181
 182         returnValue = true;
 183     }
 184
 185     return returnValue;
 186 }
 187
 188 template<class ObjectT> inline
 189 void ShaderMapCache<ObjectT>::sub(UInt32 uiIdx)
 190 {
 191     typename ObjectStore::      iterator sIt  = _vObjectStore.begin();
 192     typename ObjectStore::const_iterator sEnd = _vObjectStore.end  ();
 193
 194     std::vector<IdStore> vDestKeys;
 195
 196     while(sIt != sEnd)
 197     {
 198         IdStore::const_iterator idIt  = std::find(sIt->first.begin(),
 199                                                   sIt->first.end  (),
 200                                                   uiIdx);
 201
 202         if(idIt != sIt->first.end())
 203         {
 204             vDestKeys.push_back(sIt->first);
 205         }
 206
 207         ++sIt;
 208     }
 209
 210     std::vector<IdStore>::const_iterator kIt  = vDestKeys.begin();
 211     std::vector<IdStore>::const_iterator kEnd = vDestKeys.end  ();
 212
 213     for(; kIt != kEnd; ++kIt)
 214     {
 215         _vObjectStore.erase(*kIt);
 216     }
 217 }
 218
 219 template<class ObjectT> inline
 220 void ShaderMapCache<ObjectT>::dumpDot(const Char8 *szFilename)
 221 {
 222 }
 223
 224 template<class ObjectT>
 225 template <typename ElemDestFunc> inline
 226 void ShaderMapCache<ObjectT>::destroy(ElemDestFunc destFunc)
 227 {
 228 #ifndef OSG_SHC_REF_CLEANUP
 229     typename ObjectStore::      iterator sIt  = _vObjectStore.begin();
 230     typename ObjectStore::const_iterator sEnd = _vObjectStore.end  ();
 231
 232     for(; sIt != sEnd; ++sIt)
 233     {
 234         (destFunc)(sIt->second);
 235
 236         sIt->second = NULL;
 237     }
 238 #endif
 239
 240 }
 241
 242 template<class ObjectT> inline
 243 ShaderMapCache<ObjectT>::ShaderMapCache(void) :
 244     _vObjectStore()
 245 {
 246 }
 247
 248 template<class ObjectT> inline
 249 ShaderMapCache<ObjectT>::~ShaderMapCache(void)
 250 {
 251 }
 252
 253
 254
 255 /*---------------------------------------------------------------------------*/
 256 /*---------------------------------------------------------------------------*/
 257
 258
 259 #if defined(WIN32) || defined(__APPLE__) || \
 260     defined(__GXX_EXPERIMENTAL_CXX0X__)
 261 template<class ObjectT, UInt32 LevelBits>
 262 const Real32 ShaderCacheTreeV0<ObjectT, LevelBits>::LevelFactor =
 263                                                            1.f / (LevelBits);
 264 #endif
 265
 266 template<class ObjectT, UInt32 LevelBits> inline
 267 ShaderCacheTreeV0<ObjectT, LevelBits>::TreeNode::TreeNode(void) :
 268 #ifdef OSG_DEBUG
 269     _uiNodeId(0   ),
 270 #endif
 271     _pObject (NULL),
 272     _pPrev   (NULL),
 273     _pNext   (NULL)
 274 {
 275     memset(&(_vChildren[0]), 0, LevelSize * sizeof(TreeNode *));
 276 }
 277
 278 template<class ObjectT, UInt32 LevelBits> inline
 279 ShaderCacheTreeV0<ObjectT, LevelBits>::TreeNode::~TreeNode(void)
 280 {
 281     _pObject  = NULL;
 282     _pPrev    = NULL;
 283     _pNext    = NULL;
 284 }
 285
 286 template<class ObjectT, UInt32 LevelBits> inline
 287 void ShaderCacheTreeV0<ObjectT, LevelBits>::TreeNode::clear(void)
 288 {
 289     _pObject  = NULL;
 290     _pPrev    = NULL;
 291     _pNext    = NULL;
 292
 293     memset(&(_vChildren[0]), 0, LevelSize * sizeof(TreeNode *));
 294 }
 295
 296
 297 static UInt16 IdxToBits[9] =
 298 {
 299     0x0000,
 300
 301     0x0001,
 302     0x0002,
 303     0x0004,
 304     0x0008,
 305
 306     0x0010,
 307     0x0020,
 308     0x0040,
 309     0x0080
 310 };
 311
 312 template<class ObjectT, UInt32 LevelBits> inline
 313 ObjectT *ShaderCacheTreeV0<ObjectT, LevelBits>::find(const IdStore &vIds)
 314 {
 315     if(vIds.size() < 1)
 316         return NULL;
 317
 318     ObjectT *returnValue = NULL;
 319
 320     IdType uiStartId     = vIds[0] - 1;
 321     IdType uiStartLevel  = IdType(uiStartId * LevelFactor);
 322
 323     UInt32 uiCurrId      = 0;
 324     UInt32 uiLastId      = vIds.size();
 325
 326
 327     if(uiStartLevel >= _vLevelEntries.size())
 328     {
 329         uiStartLevel = _vLevelEntries.size() - 1;
 330     }
 331
 332
 333     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
 334     UInt32    uiCurrBits = 0x0000;
 335     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
 336
 337     if(pCurrNode == NULL)
 338         return NULL;
 339
 340     for(; uiCurrId < uiLastId; ++uiCurrId)
 341     {
 342         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
 343
 344         if(uiCurrIdx <= LevelBits)
 345         {
 346             uiCurrBits |= IdxToBits[uiCurrIdx];
 347
 348             continue;
 349         }
 350         else
 351         {
 352             pCurrNode = pCurrNode->_vChildren[uiCurrBits];
 353
 354             if(pCurrNode == NULL)
 355             {
 356                 break;
 357             }
 358
 359             uiCurrBits  = 0x0000;
 360
 361             uiLevelSub += LevelBits;
 362             uiCurrIdx  -= LevelBits;
 363
 364             while(uiCurrIdx > LevelBits)
 365             {
 366                 pCurrNode = pCurrNode->_vChildren[0];
 367
 368                 if(pCurrNode == NULL)
 369                 {
 370                     break;
 371                 }
 372                 uiLevelSub += LevelBits;
 373                 uiCurrIdx  -= LevelBits;
 374             }
 375
 376             if(pCurrNode == NULL)
 377             {
 378                 break;
 379             }
 380
 381             uiCurrBits |= IdxToBits[uiCurrIdx];
 382         }
 383     }
 384
 385     if(pCurrNode != NULL)
 386     {
 387         pCurrNode = pCurrNode->_vChildren[uiCurrBits];
 388
 389         if(pCurrNode != NULL)
 390         {
 391             returnValue = pCurrNode->_pObject;
 392         }
 393     }
 394
 395     return returnValue;
 396 }
 397
 398
 399 template<class ObjectT, UInt32 LevelBits> inline
 400 bool ShaderCacheTreeV0<ObjectT, LevelBits>::add(const IdStore &vIds,
 401                                                       ObjectT *pObject)
 402 {
 403     bool returnValue = false;
 404
 405     if(vIds.size() < 1)
 406         return returnValue;
 407
 408     IdType uiStartId    = vIds[0] - 1;
 409
 410     IdType uiStartLevel = IdType(uiStartId * LevelFactor);
 411
 412     UInt32 uiCurrId     = 0;
 413     UInt32 uiLastId     = vIds.size();
 414
 415
 416     if(uiStartLevel >= _vLevelEntries.size())
 417     {
 418         uiStartLevel = _vLevelEntries.size() - 1;
 419     }
 420
 421     UInt32 uiLevelSub   = (uiStartLevel * LevelBits);
 422
 423     TreeNode *pCurrNode = _vLevelEntries[uiStartLevel];
 424     TreeNode *pNextNode = NULL;
 425
 426     UInt32 uiCurrBits = 0x0000;
 427
 428     for(; uiCurrId < uiLastId; ++uiCurrId)
 429     {
 430         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
 431
 432         if(uiCurrIdx <= LevelBits)
 433         {
 434             uiCurrBits |= IdxToBits[uiCurrIdx];
 435
 436             continue;
 437         }
 438         else
 439         {
 440             pNextNode = pCurrNode->_vChildren[uiCurrBits];
 441
 442             if(pNextNode == NULL)
 443             {
 444                 pNextNode = allocateNode();
 445
 446                 pCurrNode->_vChildren[uiCurrBits] = pNextNode;
 447
 448                 if(uiStartLevel == _vLevelEntries.size() - 1)
 449                 {
 450                     if(_vLevelEntries.back()->_vChildren[0] == NULL)
 451                     {
 452                         TreeNode *pTmpNode = allocateNode();
 453
 454                         _vLevelEntries.back()->_vChildren[0] = pTmpNode;
 455
 456                         _vLevelEntries.push_back(pTmpNode);
 457
 458                         pTmpNode->_pNext  = pNextNode;
 459                         pNextNode->_pPrev = pTmpNode;
 460                     }
 461                     else
 462                     {
 463                         _vLevelEntries.push_back(pNextNode);
 464                     }
 465                 }
 466                 else
 467                 {
 468                     pNextNode->_pNext =
 469                         _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext;
 470
 471                     if(pNextNode->_pNext != NULL)
 472                     {
 473                         pNextNode->_pNext->_pPrev = pNextNode;
 474                     }
 475
 476                     _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext =
 477                         pNextNode;
 478
 479                     pNextNode->_pPrev =
 480                         _vLevelEntries[uiStartLevel]->_vChildren[0];
 481                 }
 482             }
 483
 484             ++uiStartLevel;
 485
 486             uiCurrBits  = 0x0000;
 487
 488             pCurrNode   = pNextNode;
 489
 490             uiLevelSub += LevelBits;
 491             uiCurrIdx  -= LevelBits;
 492
 493             while(uiCurrIdx > LevelBits)
 494             {
 495                 if(pCurrNode->_vChildren[0] == NULL)
 496                 {
 497                     pNextNode = allocateNode();
 498
 499                     pCurrNode->_vChildren[0] = pNextNode;
 500
 501                     if(uiStartLevel == _vLevelEntries.size() - 1)
 502                     {
 503                         if(_vLevelEntries.back()->_vChildren[0] == NULL)
 504                         {
 505                             TreeNode *pTmpNode = allocateNode();
 506
 507                             _vLevelEntries.back()->_vChildren[0] = pTmpNode;
 508
 509                             _vLevelEntries.push_back(pTmpNode);
 510
 511                             pTmpNode->_pNext  = pNextNode;
 512                             pNextNode->_pPrev = pTmpNode;
 513                         }
 514                         else
 515                         {
 516                             _vLevelEntries.push_back(pNextNode);
 517                         }
 518                     }
 519                     else
 520                     {
 521                         pNextNode->_pNext =
 522                             _vLevelEntries[uiStartLevel]->
 523                                 _vChildren[0]->_pNext;
 524
 525                         if(pNextNode->_pNext != NULL)
 526                         {
 527                             pNextNode->_pNext->_pPrev = pNextNode;
 528                         }
 529
 530                         _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext=
 531                             pNextNode;
 532
 533                         pNextNode->_pPrev =
 534                             _vLevelEntries[uiStartLevel]->_vChildren[0];
 535                     }
 536                 }
 537
 538                 pCurrNode = pCurrNode->_vChildren[0];
 539
 540                 uiLevelSub += LevelBits;
 541                 uiCurrIdx  -= LevelBits;
 542                 ++uiStartLevel;
 543             }
 544
 545
 546
 547             uiCurrBits |= IdxToBits[uiCurrIdx];
 548        }
 549     }
 550
 551     if(pCurrNode != NULL)
 552     {
 553         TreeNode *pNextNode = pCurrNode->_vChildren[uiCurrBits];
 554
 555         if(pNextNode != NULL)
 556         {
 557             if(pNextNode->_pObject == NULL)
 558             {
 559                 pNextNode->_pObject = pObject;
 560
 561                 returnValue = true;
 562             }
 563             else
 564             {
 565                 OSG_ASSERT(pNextNode->_pObject == pObject);
 566             }
 567         }
 568         else
 569         {
 570             pNextNode = allocateNode();
 571
 572             pCurrNode->_vChildren[uiCurrBits] = pNextNode;
 573
 574             if(uiStartLevel == _vLevelEntries.size() - 1)
 575             {
 576                 if(uiCurrBits == 0)
 577                 {
 578                     OSG_ASSERT(false);
 579                     _vLevelEntries.push_back(pNextNode);
 580                 }
 581                 else
 582                 {
 583                     TreeNode *pTmpNode = allocateNode();
 584
 585                     _vLevelEntries.back()->_vChildren[0] = pTmpNode;
 586
 587                     _vLevelEntries.push_back(pTmpNode);
 588
 589                     pTmpNode->_pNext  = pNextNode;
 590                     pNextNode->_pPrev = pTmpNode;
 591                 }
 592             }
 593             else
 594             {
 595                 pNextNode->_pNext =
 596                     _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext;
 597
 598                 if(pNextNode->_pNext != NULL)
 599                 {
 600                     pNextNode->_pNext->_pPrev = pNextNode;
 601                 }
 602
 603                 _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext =
 604                     pNextNode;
 605
 606                 pNextNode->_pPrev =
 607                     _vLevelEntries[uiStartLevel]->_vChildren[0];
 608             }
 609
 610             pNextNode->_pObject = pObject;
 611
 612             returnValue = true;
 613         }
 614     }
 615
 616     return returnValue;
 617 }
 618
 619 template<class ObjectT, UInt32 LevelBits> inline
 620 void ShaderCacheTreeV0<ObjectT, LevelBits>::sub(UInt32 uiIdx)
 621 {
 622     IdType uiStartLevel  = IdType((uiIdx - 1) * LevelFactor);
 623
 624     if(uiStartLevel >= _vLevelEntries.size())
 625     {
 626         return;
 627     }
 628
 629     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
 630     UInt32    uiCurrIdx  = uiIdx - uiLevelSub;
 631     UInt32    uiCurrBits = IdxToBits[uiCurrIdx];
 632
 633     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
 634
 635     for(; pCurrNode != NULL; pCurrNode = pCurrNode->_pNext)
 636     {
 637         for(UInt32 i = 0; i < LevelSize; ++i)
 638         {
 639             TreeNode *pChild = pCurrNode->_vChildren[i];
 640
 641             if(0x0000 != (i & uiCurrBits) && pChild != NULL)
 642             {
 643                 if(pChild->_pNext == NULL)
 644                 {
 645                     pChild->_pPrev->_pNext = NULL;
 646                 }
 647                 else
 648                 {
 649                     pChild->_pPrev->_pNext = pChild->_pNext;
 650                     pChild->_pNext->_pPrev = pChild->_pPrev;
 651                 }
 652
 653                 pChild->_pPrev = NULL;
 654                 pChild->_pNext = NULL;
 655
 656                 eraseNode(pCurrNode->_vChildren[i]);
 657                 pCurrNode->_vChildren[i] = NULL;
 658             }
 659         }
 660     }
 661 }
 662
 663 template<class ObjectT, UInt32 LevelBits> inline
 664 void ShaderCacheTreeV0<ObjectT, LevelBits>::dumpDot(const Char8 *szFilename)
 665 {
 666     FILE *pOut = fopen(szFilename, "w");
 667
 668     if(pOut != NULL)
 669     {
 670         fprintf(pOut, "digraph structs\n");
 671         fprintf(pOut, "{\n");
 672         fprintf(pOut, "node [shape=record];\n");
 673
 674         std::vector<std::vector<TreeNode *> > vLevelStore;
 675
 676         dumpDotNode(_pRoot, pOut, vLevelStore, 0);
 677
 678 #ifdef OSG_DEBUG
 679         fprintf(pOut, "struct%d\n", 0);
 680         fprintf(pOut, "[\n");
 681         fprintf(pOut, "    label=\"");
 682
 683         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
 684         {
 685             if(_vLevelEntries[i] != NULL)
 686             {
 687                 fprintf(pOut, "<l%d> %d", i, i);
 688             }
 689             else
 690             {
 691                 fprintf(pOut, "<l%d> NIL", i);
 692             }
 693
 694             if(i == _vLevelEntries.size() - 1)
 695             {
 696                 fprintf(pOut, "\"\n");
 697             }
 698             else
 699             {
 700                 fprintf(pOut, "|");
 701             }
 702         }
 703
 704         fprintf(pOut, "]\n");
 705
 706
 707         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
 708         {
 709             if(_vLevelEntries[i] != NULL)
 710             {
 711                 fprintf(pOut, "struct%d:l%d -> struct%d:l%d;\n",
 712                         0, i,
 713                         _vLevelEntries[i]->_uiNodeId, 0);
 714             }
 715         }
 716
 717         for(UInt32 i = 0; i < vLevelStore.size(); ++i)
 718         {
 719             fprintf(pOut, "{ rank=same;");
 720
 721             for(UInt32 j = 0; j < vLevelStore[i].size(); ++j)
 722             {
 723                 TreeNode *pChild = vLevelStore[i][j];
 724
 725                 if(pChild != NULL)
 726                 {
 727                     fprintf(pOut, "\"struct%d\";",
 728                             pChild->_uiNodeId);
 729                 }
 730             }
 731
 732             fprintf(pOut, "}\n");
 733         }
 734 #endif
 735
 736         fprintf(pOut, "}\n");
 737         fclose(pOut);
 738     }
 739 }
 740
 741 template<class ObjectT, UInt32 LevelBits> inline
 742 void ShaderCacheTreeV0<ObjectT, LevelBits>::dumpDotNode(
 743     TreeNode                              *pNode,
 744     FILE                                  *pOut ,
 745     std::vector<std::vector<TreeNode *> > &vLevelStore,
 746     UInt32                                 uiLevel    )
 747 {
 748 #ifdef OSG_DEBUG
 749     if(pNode == NULL)
 750         return;
 751
 752     if(uiLevel == vLevelStore.size())
 753     {
 754         vLevelStore.push_back(std::vector<TreeNode *>());
 755     }
 756
 757     fprintf(pOut, "struct%d\n", pNode->_uiNodeId);
 758     fprintf(pOut, "[\n");
 759     fprintf(pOut, "    label=\"");
 760
 761     if(pNode->_pPrev != NULL)
 762     {
 763         fprintf(pOut, "<prev> P|");
 764     }
 765     else
 766     {
 767         fprintf(pOut, "<prev> P:NIL|");
 768     }
 769
 770     for(UInt32 i = 0; i < LevelSize; ++i)
 771     {
 772         if(pNode->_vChildren[i] != NULL)
 773         {
 774             fprintf(pOut, "<l%d> %d|", i, i);
 775         }
 776         else
 777         {
 778             fprintf(pOut, "<l%d> NIL|", i);
 779         }
 780     }
 781
 782     if(pNode->_pObject != NULL)
 783     {
 784         fprintf(pOut, "<val> VAL:Obj|");
 785     }
 786     else
 787     {
 788         fprintf(pOut, "<val> VAL:NIL|");
 789     }
 790
 791     if(pNode->_pNext != NULL)
 792     {
 793         fprintf(pOut, "<next> N\"\n");
 794     }
 795     else
 796     {
 797         fprintf(pOut, "<next> N:NIL\"\n");
 798     }
 799
 800     fprintf(pOut, "]\n");
 801
 802     for(UInt32 i = 0; i < LevelSize; ++i)
 803     {
 804         TreeNode *pChild = pNode->_vChildren[i];
 805
 806         if(pChild != NULL)
 807         {
 808             dumpDotNode(pChild, pOut, vLevelStore, uiLevel + 1);
 809
 810             fprintf(pOut, "struct%d:l%d -> struct%d:l%d;\n",
 811                     pNode ->_uiNodeId, i,
 812                     pChild->_uiNodeId, UInt32(LevelSize/2));
 813         }
 814     }
 815
 816     if(pNode->_pNext != NULL)
 817     {
 818         fprintf(pOut, "struct%d:next -> struct%d:prev;\n",
 819                 pNode ->_uiNodeId,
 820                 pNode->_pNext->_uiNodeId);
 821     }
 822     if(pNode->_pPrev != NULL)
 823     {
 824         fprintf(pOut, "struct%d:prev -> struct%d:next;\n",
 825                 pNode ->_uiNodeId,
 826                 pNode->_pPrev->_uiNodeId);
 827     }
 828
 829 #if 0
 830     fprintf(pOut, "{ rank=same;");
 831
 832     for(UInt32 i = 0; i < LevelSize; ++i)
 833     {
 834         TreeNode *pChild = pNode->_vChildren[i];
 835
 836         if(pChild != NULL)
 837         {
 838             fprintf(pOut, "\"struct%d\";",
 839                     pChild->_uiNodeId);
 840         }
 841
 842     }
 843
 844      fprintf(pOut, "}\n");
 845 #endif
 846
 847      vLevelStore[uiLevel].push_back(pNode);
 848
 849 #endif
 850 }
 851
 852 template<class ObjectT, UInt32 LevelBits> inline
 853 ShaderCacheTreeV0<ObjectT, LevelBits>::ShaderCacheTreeV0(void) :
 854 #ifdef OSG_DEBUG
 855     _uiNodeCount  (0   ),
 856 #endif
 857     _pRoot        (NULL),
 858     _vLevelEntries(    ),
 859     _qFreeElements(    )
 860 {
 861     _pRoot = allocateNode();
 862
 863     _vLevelEntries.push_back(_pRoot);
 864 }
 865
 866 template<class ObjectT, UInt32 LevelBits> inline
 867 ShaderCacheTreeV0<ObjectT, LevelBits>::~ShaderCacheTreeV0(void)
 868 {
 869     typename std::deque <TreeNode *>::const_iterator qIt  =
 870         _qFreeElements.begin();
 871
 872     typename std::deque <TreeNode *>::const_iterator qEnd =
 873         _qFreeElements.end();
 874
 875     for(; qIt != qEnd; ++qIt)
 876     {
 877         delete (*qIt);
 878     }
 879 }
 880
 881 template<class ObjectT, UInt32 LevelBits> inline
 882 typename ShaderCacheTreeV0<ObjectT, LevelBits>::TreeNode *
 883     ShaderCacheTreeV0<ObjectT, LevelBits>::allocateNode(void)
 884 {
 885     TreeNode *returnValue = NULL;
 886
 887     if(_qFreeElements.empty() == false)
 888     {
 889         returnValue = _qFreeElements.back();
 890
 891         _qFreeElements.pop_back();
 892
 893         returnValue->clear();
 894     }
 895     else
 896     {
 897         returnValue = new TreeNode();
 898
 899 #ifdef OSG_DEBUG
 900         returnValue->_uiNodeId = ++_uiNodeCount;
 901 #endif
 902     }
 903
 904 #ifdef OSG_DEBUG
 905     UInt64 rU = reinterpret_cast<UInt64>(returnValue);
 906
 907     OSG_ASSERT((rU & 0x0001) == 0x0000);
 908 #endif
 909
 910     return returnValue;
 911 }
 912
 913 template<class ObjectT, UInt32 LevelBits> inline
 914 void ShaderCacheTreeV0<ObjectT, LevelBits>::eraseNode(TreeNode *pNode)
 915 {
 916     for(UInt32 i = 0; i < LevelSize; ++i)
 917     {
 918         if(pNode->_vChildren[i] != NULL)
 919         {
 920             eraseNode(pNode->_vChildren[i]);
 921         }
 922     }
 923
 924     pNode->_pObject = NULL;
 925
 926     _qFreeElements.push_back(pNode);
 927 }
 928
 929 template<class ObjectT, UInt32 LevelBits>
 930 template <typename ElemDestFunc> inline
 931 void ShaderCacheTreeV0<ObjectT, LevelBits>::destroyNode(TreeNode     *pNode,
 932                                                         ElemDestFunc  destFunc)
 933 {
 934     if(pNode == NULL)
 935         return;
 936
 937     UInt32 uiChildStart = 0;
 938
 939     if(pNode->_pPrev == NULL)
 940         uiChildStart = 1;
 941
 942     for(UInt32 i = uiChildStart; i < LevelSize; ++i)
 943     {
 944         if(pNode->_vChildren[i] != NULL)
 945         {
 946             destroyNode(pNode->_vChildren[i], destFunc);
 947         }
 948     }
 949
 950     if(pNode->_pObject != NULL)
 951     {
 952 #ifndef OSG_SHC_REF_CLEANUP
 953         (destFunc)(pNode->_pObject);
 954 #endif
 955         pNode->_pObject = NULL;
 956     }
 957
 958     delete pNode;
 959 }
 960
 961 template<class ObjectT, UInt32 LevelBits>
 962 template <typename ElemDestFunc> inline
 963 void ShaderCacheTreeV0<ObjectT, LevelBits>::destroy(ElemDestFunc destFunc)
 964 {
 965     destroyNode(_pRoot, destFunc);
 966
 967     _vLevelEntries[0] = NULL;
 968
 969     _pRoot = NULL;
 970 }
 971
 972
 973
 974
 975
 976 /*---------------------------------------------------------------------------*/
 977 /*---------------------------------------------------------------------------*/
 978
 979
 980 template<typename Object1T, typename RefCountPol1,
 981          typename Object2T, typename RefCountPol2> inline
 982 VariantPtr<Object1T, RefCountPol1,
 983            Object2T, RefCountPol2>::VariantPtr(void)
 984 {
 985     _val._pObj1 = NULL;
 986 }
 987
 988 template<typename Object1T, typename RefCountPol1,
 989          typename Object2T, typename RefCountPol2> inline
 990 VariantPtr<Object1T, RefCountPol1,
 991            Object2T, RefCountPol2>::~VariantPtr(void)
 992 {
 993     if(_val._uiIntVal & UIMaskChoice)  //isObj1
 994     {
 995         _val._uiIntVal &= UIMaskPtr;
 996
 997         RefCountPol1::subRef(_val._pObj1);
 998     }
 999 }
1000
1001 template<typename Object1T, typename RefCountPol1,
1002          typename Object2T, typename RefCountPol2> inline
1003 Object1T *VariantPtr<Object1T, RefCountPol1,
1004                      Object2T, RefCountPol2>::asT1(void) const
1005 {
1006
1007     if(_val._uiIntVal & UIMaskChoice) //isObj1
1008     {
1009         MemberU returnValue = { _val._uiIntVal & UIMaskPtr };
1010
1011         return returnValue._pObj1;
1012     }
1013
1014     return NULL;
1015 }
1016
1017 template<typename Object1T, typename RefCountPol1,
1018          typename Object2T, typename RefCountPol2> inline
1019 Object2T *VariantPtr<Object1T, RefCountPol1,
1020                      Object2T, RefCountPol2>::asT2(void) const
1021 {
1022
1023     if(!(_val._uiIntVal & UIMaskChoice)) //!isObj1
1024         return _val._pObj2;
1025
1026     return NULL;
1027 }
1028
1029 template<typename Object1T, typename RefCountPol1,
1030          typename Object2T, typename RefCountPol2> inline
1031 void VariantPtr<Object1T, RefCountPol1,
1032                 Object2T, RefCountPol2>::setAsT1(Object1T * const rhs)
1033 {
1034     if(_val._uiIntVal & UIMaskChoice) //isObj1
1035     {
1036         _val._uiIntVal &= UIMaskPtr;
1037
1038         RefCountPol1::setRefd(_val._pObj1, rhs);
1039     }
1040     else
1041     {
1042         RefCountPol1::addRef(rhs);
1043
1044         _val._pObj1 = rhs;
1045     }
1046
1047     //isObj1
1048     _val._uiIntVal |= UIMaskChoice;
1049
1050 }
1051
1052 template<typename Object1T, typename RefCountPol1,
1053          typename Object2T, typename RefCountPol2> inline
1054 void VariantPtr<Object1T, RefCountPol1,
1055                 Object2T, RefCountPol2>::setAsT2(Object2T * const rhs)
1056 {
1057     if(_val._uiIntVal & UIMaskChoice) //isObj1
1058     {
1059         _val._uiIntVal &= UIMaskPtr;
1060
1061         RefCountPol1::subRef(_val._pObj1);
1062     }
1063
1064     _val._pObj2 = rhs;
1065 }
1066
1067
1068 template<typename Object1T, typename RefCountPol1,
1069          typename Object2T, typename RefCountPol2> inline
1070 void VariantPtr<Object1T, RefCountPol1,
1071                 Object2T, RefCountPol2>::operator =(Object1T * const rhs)
1072 {
1073     setAsT1(rhs);
1074 }
1075
1076 template<typename Object1T, typename RefCountPol1,
1077          typename Object2T, typename RefCountPol2> inline
1078 void VariantPtr<Object1T, RefCountPol1,
1079                 Object2T, RefCountPol2>::operator =(Object2T * const rhs)
1080 {
1081     setAsT2(rhs);
1082 }
1083
1084
1085 template<typename Object1T, typename RefCountPol1,
1086          typename Object2T, typename RefCountPol2> inline
1087 Object2T *VariantPtr<Object1T, RefCountPol1,
1088                      Object2T, RefCountPol2>::operator ->(void) const
1089 {
1090     return this->asT2();
1091 }
1092
1093
1094
1095
1096 /*---------------------------------------------------------------------------*/
1097 /*---------------------------------------------------------------------------*/
1098
1099 #if defined(WIN32) || defined(__APPLE__) || \
1100     defined(__GXX_EXPERIMENTAL_CXX0X__)
1101 template<class ObjectT, UInt32 LevelBits>
1102 const Real32 ShaderCacheTreeV1<ObjectT, LevelBits>::LevelFactor =
1103                                                             1.f / (LevelBits);
1104 #endif
1105
1106 template<class ObjectT, UInt32 LevelBits> inline
1107 ShaderCacheTreeV1<ObjectT, LevelBits>::TreeNode::TreeNode(void) :
1108 #ifdef OSG_DEBUG
1109     _uiNodeId(0   ),
1110 #endif
1111     _pObject (NULL),
1112     _pPrev   (NULL),
1113     _pNext   (NULL)
1114 {
1115 }
1116
1117 template<class ObjectT, UInt32 LevelBits> inline
1118 ShaderCacheTreeV1<ObjectT, LevelBits>::TreeNode::~TreeNode(void)
1119 {
1120     _pObject = NULL;
1121     _pPrev   = NULL;
1122     _pNext   = NULL;
1123
1124     for(UInt32 i = 0; i < LevelSize; ++i)
1125     {
1126         _vChildren[i].setAsT1(NULL);
1127     }
1128 }
1129
1130 template<class ObjectT, UInt32 LevelBits> inline
1131 void ShaderCacheTreeV1<ObjectT, LevelBits>::TreeNode::clear(void)
1132 {
1133     _pObject = NULL;
1134     _pPrev   = NULL;
1135     _pNext   = NULL;
1136
1137     for(UInt32 i = 0; i < LevelSize; ++i)
1138     {
1139         _vChildren[i].setAsT1(NULL);
1140     }
1141 }
1142
1143
1144
1145 template<class ObjectT, UInt32 LevelBits> inline
1146 ObjectT *ShaderCacheTreeV1<ObjectT, LevelBits>::find(const IdStore &vIds)
1147 {
1148     if(vIds.size() < 1)
1149         return NULL;
1150
1151     ObjectT *returnValue = NULL;
1152
1153     IdType uiStartId     = vIds[0] - 1;
1154     IdType uiStartLevel  = IdType(uiStartId * LevelFactor);
1155
1156     UInt32 uiCurrId      = 0;
1157     UInt32 uiLastId      = vIds.size();
1158
1159
1160     if(uiStartLevel >= _vLevelEntries.size())
1161     {
1162         uiStartLevel = _vLevelEntries.size() - 1;
1163     }
1164
1165
1166     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
1167     UInt32    uiCurrBits = 0x0000;
1168     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
1169
1170     if(pCurrNode == NULL)
1171         return;
1172
1173     for(; uiCurrId < uiLastId; ++uiCurrId)
1174     {
1175         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
1176
1177         if(uiCurrIdx <= LevelBits)
1178         {
1179             uiCurrBits |= IdxToBits[uiCurrIdx];
1180
1181             continue;
1182         }
1183         else
1184         {
1185             pCurrNode = pCurrNode->_vChildren[uiCurrBits].asT2();
1186
1187             if(pCurrNode == NULL)
1188             {
1189                 break;
1190             }
1191
1192             uiCurrBits  = 0x0000;
1193
1194             uiLevelSub += LevelBits;
1195             uiCurrIdx  -= LevelBits;
1196
1197             while(uiCurrIdx > LevelBits)
1198             {
1199                 pCurrNode = pCurrNode->_vChildren[0].asT2();
1200
1201                 if(pCurrNode == NULL)
1202                 {
1203                     break;
1204                 }
1205                 uiLevelSub += LevelBits;
1206                 uiCurrIdx  -= LevelBits;
1207             }
1208
1209             if(pCurrNode == NULL)
1210             {
1211                 break;
1212             }
1213
1214             uiCurrBits |= IdxToBits[uiCurrIdx];
1215         }
1216     }
1217
1218     if(pCurrNode != NULL)
1219     {
1220         TreeNode *pNext = pCurrNode->_vChildren[uiCurrBits].asT2();
1221
1222         if(pNext != NULL)
1223         {
1224             returnValue = pNext->_pObject;
1225         }
1226         else
1227         {
1228             returnValue = pCurrNode->_vChildren[uiCurrBits].asT1();
1229         }
1230     }
1231
1232     return returnValue;
1233 }
1234
1235
1236 template<class ObjectT, UInt32 LevelBits> inline
1237 bool ShaderCacheTreeV1<ObjectT, LevelBits>::add(const IdStore &vIds,
1238                                                       ObjectT *pObject)
1239 {
1240     bool returnValue = false;
1241
1242     if(vIds.size() < 1)
1243         return returnValue;
1244
1245     IdType uiStartId    = vIds[0] - 1;
1246
1247     IdType uiStartLevel = IdType(uiStartId * LevelFactor);
1248
1249     UInt32 uiCurrId     = 0;
1250     UInt32 uiLastId     = vIds.size();
1251
1252
1253     if(uiStartLevel >= _vLevelEntries.size())
1254     {
1255         uiStartLevel = _vLevelEntries.size() - 1;
1256     }
1257
1258     UInt32 uiLevelSub   = (uiStartLevel * LevelBits);
1259
1260     TreeNode *pCurrNode = _vLevelEntries[uiStartLevel];
1261     TreeNode *pNextNode = NULL;
1262
1263     UInt32 uiCurrBits = 0x0000;
1264
1265     for(; uiCurrId < uiLastId; ++uiCurrId)
1266     {
1267         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
1268
1269         if(uiCurrIdx <= LevelBits)
1270         {
1271             uiCurrBits |= IdxToBits[uiCurrIdx];
1272
1273             continue;
1274         }
1275         else
1276         {
1277             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
1278
1279             if(pNextNode == NULL)
1280             {
1281                 pNextNode = allocateNode();
1282
1283                 if(pCurrNode->_vChildren[uiCurrBits].asT1() != NULL)
1284                 {
1285                     pNextNode->_pObject =
1286                         pCurrNode->_vChildren[uiCurrBits].asT1();
1287                 }
1288
1289                 pCurrNode->_vChildren[uiCurrBits] = pNextNode;
1290
1291                 if(uiStartLevel == _vLevelEntries.size() - 1)
1292                 {
1293                     if(_vLevelEntries.back()->_vChildren[0].asT2() == NULL)
1294                     {
1295                         TreeNode *pTmpNode = allocateNode();
1296
1297                         _vLevelEntries.back()->_vChildren[0] = pTmpNode;
1298
1299                         _vLevelEntries.push_back(pTmpNode);
1300
1301                         pTmpNode->_pNext  = pNextNode;
1302                         pNextNode->_pPrev = pTmpNode;
1303                     }
1304                     else
1305                     {
1306                         _vLevelEntries.push_back(pNextNode);
1307                     }
1308                 }
1309                 else
1310                 {
1311                     pNextNode->_pNext =
1312                         _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext;
1313
1314                     if(pNextNode->_pNext != NULL)
1315                     {
1316                         pNextNode->_pNext->_pPrev = pNextNode;
1317                     }
1318
1319                     _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext =
1320                         pNextNode;
1321
1322                     pNextNode->_pPrev =
1323                         _vLevelEntries[uiStartLevel]->_vChildren[0].asT2();
1324                 }
1325             }
1326
1327             ++uiStartLevel;
1328
1329             uiCurrBits  = 0x0000;
1330
1331             pCurrNode   = pNextNode;
1332
1333             uiLevelSub += LevelBits;
1334             uiCurrIdx  -= LevelBits;
1335
1336             while(uiCurrIdx > LevelBits)
1337             {
1338                 if(pCurrNode->_vChildren[0].asT2() == NULL)
1339                 {
1340                     pNextNode = allocateNode();
1341
1342                     pCurrNode->_vChildren[0] = pNextNode;
1343
1344                     if(uiStartLevel == _vLevelEntries.size() - 1)
1345                     {
1346                         if(_vLevelEntries.back()->_vChildren[0].asT2() == NULL)
1347                         {
1348                             TreeNode *pTmpNode = allocateNode();
1349
1350                             _vLevelEntries.back()->_vChildren[0] = pTmpNode;
1351
1352                             _vLevelEntries.push_back(pTmpNode);
1353
1354                             pTmpNode->_pNext  = pNextNode;
1355                             pNextNode->_pPrev = pTmpNode;
1356                         }
1357                         else
1358                         {
1359                             _vLevelEntries.push_back(pNextNode);
1360                         }
1361                     }
1362                     else
1363                     {
1364                         pNextNode->_pNext =
1365                             _vLevelEntries[uiStartLevel]->
1366                                 _vChildren[0]->_pNext;
1367
1368                         if(pNextNode->_pNext != NULL)
1369                         {
1370                             pNextNode->_pNext->_pPrev = pNextNode;
1371                         }
1372
1373                         _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext=
1374                             pNextNode;
1375
1376                         pNextNode->_pPrev =
1377                             _vLevelEntries[uiStartLevel]->_vChildren[0].asT2();
1378                     }
1379                 }
1380
1381                 pCurrNode = pCurrNode->_vChildren[0].asT2();
1382
1383                 uiLevelSub += LevelBits;
1384                 uiCurrIdx  -= LevelBits;
1385                 ++uiStartLevel;
1386             }
1387
1388
1389
1390             uiCurrBits |= IdxToBits[uiCurrIdx];
1391        }
1392     }
1393
1394     if(pCurrNode != NULL)
1395     {
1396         TreeNode *pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
1397
1398         if(pNextNode != NULL)
1399         {
1400             if(pNextNode->_pObject == NULL)
1401             {
1402                 pNextNode->_pObject = pObject;
1403
1404                 returnValue = true;
1405             }
1406             else
1407             {
1408                 OSG_ASSERT(pNextNode->_pObject == pObject);
1409             }
1410         }
1411         else
1412         {
1413             pCurrNode->_vChildren[uiCurrBits] = pObject;
1414
1415             returnValue = true;
1416         }
1417     }
1418
1419     return returnValue;
1420 }
1421
1422 template<class ObjectT, UInt32 LevelBits> inline
1423 void ShaderCacheTreeV1<ObjectT, LevelBits>::sub(UInt32 uiIdx)
1424 {
1425     IdType uiStartLevel  = IdType((uiIdx - 1) * LevelFactor);
1426
1427     if(uiStartLevel >= _vLevelEntries.size())
1428     {
1429         return;
1430     }
1431
1432     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
1433     UInt32    uiCurrIdx  = uiIdx - uiLevelSub;
1434     UInt32    uiCurrBits = IdxToBits[uiCurrIdx];
1435
1436     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
1437
1438     for(; pCurrNode != NULL; pCurrNode = pCurrNode->_pNext)
1439     {
1440         for(UInt32 i = 0; i < LevelSize; ++i)
1441         {
1442             TreeNode *pChild = pCurrNode->_vChildren[i].asT2();
1443
1444             if(0x0000 != (i & uiCurrBits) && pChild != NULL)
1445             {
1446                 if(pChild->_pNext == NULL)
1447                 {
1448                     pChild->_pPrev->_pNext = NULL;
1449                 }
1450                 else
1451                 {
1452                     pChild->_pPrev->_pNext = pChild->_pNext;
1453                     pChild->_pNext->_pPrev = pChild->_pPrev;
1454                 }
1455
1456                 pChild->_pPrev = NULL;
1457                 pChild->_pNext = NULL;
1458
1459                 eraseNode(pCurrNode->_vChildren[i].asT2());
1460                 pCurrNode->_vChildren[i].setAsT2(NULL);
1461             }
1462             else if(pCurrNode->_vChildren[i].asT1() != NULL)
1463             {
1464                 pCurrNode->_vChildren[i].setAsT1(NULL);
1465             }
1466         }
1467     }
1468 }
1469
1470 template<class ObjectT, UInt32 LevelBits> inline
1471 void ShaderCacheTreeV1<ObjectT, LevelBits>::dumpDot(const Char8 *szFilename)
1472 {
1473     FILE *pOut = fopen(szFilename, "w");
1474
1475     if(pOut != NULL)
1476     {
1477         fprintf(pOut, "digraph structs\n");
1478         fprintf(pOut, "{\n");
1479         fprintf(pOut, "rankdir = LR;\n");
1480         fprintf(pOut, "splines=false\n");
1481
1482         fprintf(pOut, "node [shape=record];\n");
1483
1484         fprintf(pOut, "struct%d\n", 0);
1485         fprintf(pOut, "[\n");
1486         fprintf(pOut, "    label=\"");
1487
1488         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
1489         {
1490             if(_vLevelEntries[i] != NULL)
1491             {
1492                 fprintf(pOut, "<l%d> %d", i, i);
1493             }
1494             else
1495             {
1496                 fprintf(pOut, "<l%d> NIL", i);
1497             }
1498
1499             if(i == _vLevelEntries.size() - 1)
1500             {
1501                 fprintf(pOut, "\"\n");
1502             }
1503             else
1504             {
1505                 fprintf(pOut, "|");
1506             }
1507         }
1508
1509         fprintf(pOut, "]\n");
1510
1511         fprintf(pOut, "node [width = 1.5];\n");
1512
1513         std::vector<std::vector<TreeNode *> > vLevelStore;
1514
1515         dumpDotNode(_pRoot, pOut, vLevelStore, 0);
1516
1517 #ifdef OSG_DEBUG
1518         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
1519         {
1520             if(_vLevelEntries[i] != NULL)
1521             {
1522                 fprintf(pOut,
1523                         "struct%d:l%d -> struct%d:prev [color=\"green\"];\n",
1524                         0, i,
1525                         _vLevelEntries[i]->_uiNodeId);
1526             }
1527         }
1528 #if 0
1529         for(UInt32 i = 0; i < vLevelStore.size(); ++i)
1530         {
1531             fprintf(pOut, "{ rank=same;");
1532
1533             for(UInt32 j = 0; j < vLevelStore[i].size(); ++j)
1534             {
1535                 TreeNode *pChild = vLevelStore[i][j];
1536
1537                 if(pChild != NULL)
1538                 {
1539                     fprintf(pOut, "\"struct%d\";",
1540                             pChild->_uiNodeId);
1541                 }
1542             }
1543
1544             fprintf(pOut, "}\n");
1545         }
1546 #endif
1547 #endif
1548
1549         fprintf(pOut, "}\n");
1550         fclose(pOut);
1551     }
1552 }
1553
1554 template<class ObjectT, UInt32 LevelBits> inline
1555 void ShaderCacheTreeV1<ObjectT, LevelBits>::dumpDotNode(
1556     TreeNode                              *pNode,
1557     FILE                                  *pOut ,
1558     std::vector<std::vector<TreeNode *> > &vLevelStore,
1559     UInt32                                 uiLevel    )
1560 {
1561 #ifdef OSG_DEBUG
1562     if(pNode == NULL)
1563         return;
1564
1565     if(uiLevel == vLevelStore.size())
1566     {
1567         vLevelStore.push_back(std::vector<TreeNode *>());
1568     }
1569
1570     fprintf(pOut, "struct%d\n", pNode->_uiNodeId);
1571     fprintf(pOut, "[\n");
1572     fprintf(pOut, "    label=\"{");
1573
1574     if(pNode->_pPrev != NULL)
1575     {
1576         fprintf(pOut, "<prev> P|");
1577     }
1578     else
1579     {
1580         fprintf(pOut, "<prev> P:NIL|");
1581     }
1582
1583     for(UInt32 i = 0; i < LevelSize; ++i)
1584     {
1585         if(pNode->_vChildren[i].asT1() != NULL)
1586         {
1587             fprintf(pOut, "<l%d> O:%d|", i, i);
1588         }
1589         else if(pNode->_vChildren[i].asT2() != NULL)
1590         {
1591             fprintf(pOut, "<l%d> C:%d|", i, i);
1592         }
1593         else
1594         {
1595             fprintf(pOut, "<l%d> NIL|", i);
1596         }
1597     }
1598
1599     if(pNode->_pObject != NULL)
1600     {
1601         fprintf(pOut, "<val> VAL:Obj|");
1602     }
1603     else
1604     {
1605         fprintf(pOut, "<val> VAL:NIL|");
1606     }
1607
1608     if(pNode->_pNext != NULL)
1609     {
1610         fprintf(pOut, "<next> N}\"\n");
1611     }
1612     else
1613     {
1614         fprintf(pOut, "<next> N:NIL}\"\n");
1615     }
1616
1617     fprintf(pOut, "]\n");
1618
1619     for(UInt32 i = 0; i < LevelSize; ++i)
1620     {
1621         TreeNode *pChild = pNode->_vChildren[i].asT2();
1622
1623         if(pChild != NULL)
1624         {
1625             dumpDotNode(pChild, pOut, vLevelStore, uiLevel + 1);
1626
1627             fprintf(pOut,
1628                     "struct%d:l%d -> struct%d:l%d [constraint=\"false\"];\n",
1629                     pNode ->_uiNodeId, i,
1630                     pChild->_uiNodeId, i);
1631         }
1632     }
1633
1634     if(pNode->_pNext != NULL)
1635     {
1636         fprintf(pOut, "struct%d:next -> struct%d:prev;\n",
1637                 pNode ->_uiNodeId,
1638                 pNode->_pNext->_uiNodeId);
1639     }
1640     if(pNode->_pPrev != NULL)
1641     {
1642         fprintf(pOut, "struct%d:prev -> struct%d:next;\n",
1643                 pNode ->_uiNodeId,
1644                 pNode->_pPrev->_uiNodeId);
1645     }
1646
1647      vLevelStore[uiLevel].push_back(pNode);
1648 #endif
1649 }
1650
1651 template<class ObjectT, UInt32 LevelBits> inline
1652 ShaderCacheTreeV1<ObjectT, LevelBits>::ShaderCacheTreeV1(void) :
1653 #ifdef OSG_DEBUG
1654     _uiNodeCount  (0   ),
1655 #endif
1656     _pRoot        (NULL),
1657     _vLevelEntries(    ),
1658     _qFreeElements(    )
1659 {
1660     _pRoot = allocateNode();
1661
1662     _vLevelEntries.push_back(_pRoot);
1663 }
1664
1665 template<class ObjectT, UInt32 LevelBits> inline
1666 ShaderCacheTreeV1<ObjectT, LevelBits>::~ShaderCacheTreeV1(void)
1667 {
1668     typename std::deque <TreeNode *>::const_iterator qIt  =
1669         _qFreeElements.begin();
1670
1671     typename std::deque <TreeNode *>::const_iterator qEnd =
1672         _qFreeElements.end();
1673
1674     for(; qIt != qEnd; ++qIt)
1675     {
1676         delete (*qIt);
1677     }
1678 }
1679
1680 template<class ObjectT, UInt32 LevelBits> inline
1681 typename ShaderCacheTreeV1<ObjectT, LevelBits>::TreeNode *
1682     ShaderCacheTreeV1<ObjectT, LevelBits>::allocateNode(void)
1683 {
1684     TreeNode *returnValue = NULL;
1685
1686     if(_qFreeElements.empty() == false)
1687     {
1688         returnValue = _qFreeElements.back();
1689
1690         _qFreeElements.pop_back();
1691
1692         returnValue->clear();
1693     }
1694     else
1695     {
1696         returnValue = new TreeNode();
1697
1698 #ifdef OSG_DEBUG
1699         returnValue->_uiNodeId = ++_uiNodeCount;
1700 #endif
1701     }
1702
1703 #ifdef OSG_DEBUG
1704     UIntPointer rU = reinterpret_cast<UIntPointer>(returnValue);
1705
1706     OSG_ASSERT((rU & 0x0001) == 0x0000);
1707 #endif
1708
1709     return returnValue;
1710 }
1711
1712 template<class ObjectT, UInt32 LevelBits> inline
1713 void ShaderCacheTreeV1<ObjectT, LevelBits>::eraseNode(TreeNode *pNode)
1714 {
1715     for(UInt32 i = 0; i < LevelSize; ++i)
1716     {
1717         if(pNode->_vChildren[i].asT2() != NULL)
1718         {
1719             eraseNode(pNode->_vChildren[i].asT2());
1720         }
1721         else
1722         {
1723             pNode->_vChildren[i].setAsT1(NULL);
1724         }
1725     }
1726
1727     pNode->_pObject = NULL;
1728
1729     _qFreeElements.push_back(pNode);
1730 }
1731
1732 template<class ObjectT, UInt32 LevelBits>
1733 template <typename ElemDestFunc> inline
1734 void ShaderCacheTreeV1<ObjectT, LevelBits>::destroyNode(TreeNode     *pNode,
1735                                                         ElemDestFunc  destFunc)
1736 {
1737     if(pNode == NULL)
1738         return;
1739
1740     UInt32 uiChildStart = 0;
1741
1742     if(pNode->_pPrev == NULL)
1743         uiChildStart = 1;
1744
1745     for(UInt32 i = uiChildStart; i < LevelSize; ++i)
1746     {
1747         if(pNode->_vChildren[i].asT2() != NULL)
1748         {
1749             destroyNode(pNode->_vChildren[i].asT2(), destFunc);
1750         }
1751         else if(pNode->_vChildren[i].asT1() != NULL)
1752         {
1753 #ifndef OSG_SHC_REF_CLEANUP
1754             ObjectT *pObj = pNode->_vChildren[i].asT1();
1755             (destFunc)(pObj);
1756 #endif
1757             pNode->_vChildren[i].setAsT1(NULL);
1758         }
1759     }
1760
1761     if(pNode->_pObject != NULL)
1762     {
1763 #ifndef OSG_SHC_REF_CLEANUP
1764         (destFunc)(pNode->_pObject);
1765 #endif
1766         pNode->_pObject = NULL;
1767     }
1768
1769     delete pNode;
1770 }
1771
1772 template<class ObjectT, UInt32 LevelBits>
1773 template <typename ElemDestFunc> inline
1774 void ShaderCacheTreeV1<ObjectT, LevelBits>::destroy(ElemDestFunc destFunc)
1775 {
1776     destroyNode(_pRoot, destFunc);
1777
1778     _vLevelEntries[0] = NULL;
1779
1780     _pRoot = NULL;
1781 }
1782
1783
1784
1785
1786
1787
1788 /*---------------------------------------------------------------------------*/
1789 /*---------------------------------------------------------------------------*/
1790
1791 #if defined(WIN32) || defined(__APPLE__) || \
1792     defined(__GXX_EXPERIMENTAL_CXX0X__)
1793 template<class ObjectT, UInt32 LevelBits>
1794 const Real32 ShaderCacheTreeV2<ObjectT, LevelBits>::LevelFactor =
1795                                                             1.f / (LevelBits);
1796 #endif
1797
1798 template<class ObjectT, UInt32 LevelBits> inline
1799 ShaderCacheTreeV2<ObjectT, LevelBits>::TreeNode::TreeNode(void) :
1800 #ifdef OSG_DEBUG
1801     _uiNodeId(0   ),
1802 #endif
1803     _pObject (NULL),
1804     _pPrev   (NULL),
1805     _pNext   (NULL)
1806 {
1807     memset(&(_vJumps[0]), 0, LevelSize * sizeof(UInt16));
1808 }
1809
1810 template<class ObjectT, UInt32 LevelBits> inline
1811 ShaderCacheTreeV2<ObjectT, LevelBits>::TreeNode::~TreeNode(void)
1812 {
1813     _pObject = NULL;
1814     _pPrev   = NULL;
1815     _pNext   = NULL;
1816
1817     for(UInt32 i = 0; i < LevelSize; ++i)
1818     {
1819         _vChildren[i].setAsT1(NULL);
1820     }
1821 }
1822
1823 template<class ObjectT, UInt32 LevelBits> inline
1824 void ShaderCacheTreeV2<ObjectT, LevelBits>::TreeNode::clear(void)
1825 {
1826     _pObject = NULL;
1827     _pPrev   = NULL;
1828     _pNext   = NULL;
1829
1830     for(UInt32 i = 0; i < LevelSize; ++i)
1831     {
1832         _vChildren[i].setAsT1(NULL);
1833     }
1834
1835     memset(&(_vJumps[0]), 0, LevelSize * sizeof(UInt16));
1836 }
1837
1838
1839
1840 template<class ObjectT, UInt32 LevelBits> inline
1841 ObjectT *ShaderCacheTreeV2<ObjectT, LevelBits>::find(const IdStore &vIds)
1842 {
1843     if(vIds.size() < 1)
1844         return NULL;
1845
1846     ObjectT *returnValue = NULL;
1847
1848     IdType uiStartId     = vIds[0] - 1;
1849     IdType uiStartLevel  = IdType(uiStartId * LevelFactor);
1850
1851     UInt32 uiCurrId      = 0;
1852     UInt32 uiLastId      = vIds.size();
1853
1854
1855     if(uiStartLevel >= _vLevelEntries.size())
1856     {
1857         uiStartLevel = _vLevelEntries.size() - 1;
1858     }
1859
1860
1861     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
1862     UInt32    uiCurrBits = 0x0000;
1863     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
1864     TreeNode *pNextNode  = NULL;
1865
1866     if(pCurrNode == NULL)
1867         return NULL;
1868
1869     for(; uiCurrId < uiLastId; ++uiCurrId)
1870     {
1871         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
1872         UInt16 uiJumpDist = 1;
1873
1874         if(uiCurrIdx <= LevelBits)
1875         {
1876             uiCurrBits |= IdxToBits[uiCurrIdx];
1877
1878             continue;
1879         }
1880         else
1881         {
1882             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
1883
1884             if(pNextNode == NULL)
1885             {
1886                 pCurrNode = pNextNode;
1887                 break;
1888             }
1889
1890             uiJumpDist = UInt16((uiCurrIdx - 1) * LevelFactor);
1891             UInt32 uiTargetLevel = uiStartLevel + uiJumpDist;
1892
1893             if(uiJumpDist < pCurrNode->_vJumps[uiCurrBits])
1894             {
1895                 pCurrNode = NULL;
1896                 break;
1897             }
1898
1899             if(uiJumpDist > pCurrNode->_vJumps[uiCurrBits])
1900             {
1901                 uiLevelSub += LevelBits * pCurrNode->_vJumps[uiCurrBits];
1902                 uiCurrIdx  -= LevelBits * pCurrNode->_vJumps[uiCurrBits];
1903                 uiJumpDist -= pCurrNode->_vJumps[uiCurrBits];
1904
1905                 pCurrNode = pNextNode;
1906                 pNextNode = pCurrNode->_vChildren[0].asT2();
1907
1908                 uiCurrBits  = 0x0000;
1909
1910                 while(1)
1911                 {
1912                     if(uiCurrIdx <= LevelBits)
1913                     {
1914                         break;
1915                     }
1916
1917                     if(uiJumpDist == pCurrNode->_vJumps[0])
1918                     {
1919                         break;
1920                     }
1921
1922                     if(uiJumpDist < pCurrNode->_vJumps[0])
1923                     {
1924                         pNextNode = NULL;
1925                         break;
1926                     }
1927
1928                     if(pNextNode == NULL)
1929                     {
1930                         break;
1931                     }
1932
1933                     uiLevelSub +=
1934                         LevelBits * pCurrNode->_vJumps[0];
1935
1936                     uiCurrIdx  -=
1937                         LevelBits * pCurrNode->_vJumps[0];
1938
1939                     uiJumpDist -= pCurrNode->_vJumps[0];
1940
1941                     pCurrNode = pNextNode;
1942                     pNextNode = pCurrNode->_vChildren[0].asT2();
1943                 }
1944             }
1945
1946             pCurrNode = pNextNode;
1947
1948             if(pCurrNode == NULL)
1949             {
1950                 break;
1951             }
1952
1953             uiCurrBits  = 0x0000;
1954
1955             uiStartLevel = uiTargetLevel;
1956             uiLevelSub   = (uiStartLevel * LevelBits);
1957
1958             uiCurrIdx  -= uiJumpDist * LevelBits;
1959
1960
1961             uiCurrBits |= IdxToBits[uiCurrIdx];
1962         }
1963     }
1964
1965     if(pCurrNode != NULL)
1966     {
1967         TreeNode *pNext = pCurrNode->_vChildren[uiCurrBits].asT2();
1968
1969         if(pNext != NULL)
1970         {
1971             returnValue = pNext->_pObject;
1972         }
1973         else
1974         {
1975             returnValue = pCurrNode->_vChildren[uiCurrBits].asT1();
1976         }
1977     }
1978
1979     return returnValue;
1980 }
1981
1982
1983 template<class ObjectT, UInt32 LevelBits> inline
1984 bool ShaderCacheTreeV2<ObjectT, LevelBits>::add(const IdStore &vIds,
1985                                                       ObjectT *pObject)
1986 {
1987     bool returnValue = false;
1988
1989     if(vIds.size() < 1)
1990         return returnValue;
1991
1992     IdType uiStartId    = vIds[0] - 1;
1993
1994     IdType uiStartLevel = IdType(uiStartId * LevelFactor);
1995
1996     UInt32 uiCurrId     = 0;
1997     UInt32 uiLastId     = vIds.size();
1998
1999
2000     if(uiStartLevel >= _vLevelEntries.size())
2001     {
2002         uiStartLevel = _vLevelEntries.size() - 1;
2003     }
2004
2005
2006     TreeNode *pCurrNode = _vLevelEntries[uiStartLevel];
2007     TreeNode *pNextNode = NULL;
2008
2009     UInt32 uiCurrBits = 0x0000;
2010
2011     if(pCurrNode == NULL)
2012     {
2013         UInt32 uiLastValidLE = 0;
2014
2015         for(Int32 i = uiStartLevel; i >= 0; --i)
2016         {
2017             if(_vLevelEntries[i] != NULL)
2018             {
2019                 uiLastValidLE = i;
2020                 break;
2021             }
2022         }
2023
2024         uiStartLevel = uiLastValidLE;
2025         pCurrNode    = _vLevelEntries[uiStartLevel];
2026     }
2027
2028     UInt32 uiLevelSub   = (uiStartLevel * LevelBits);
2029
2030     for(; uiCurrId < uiLastId; ++uiCurrId)
2031     {
2032         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
2033         UInt16 uiJumpDist = 1;
2034
2035         if(uiCurrIdx <= LevelBits)
2036         {
2037             uiCurrBits |= IdxToBits[uiCurrIdx];
2038
2039             continue;
2040         }
2041         else
2042         {
2043             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
2044
2045             uiJumpDist           = UInt16((uiCurrIdx - 1) * LevelFactor);
2046             UInt32 uiTargetLevel = uiStartLevel + uiJumpDist;
2047
2048             if(pNextNode != NULL)
2049             {
2050                 if(uiJumpDist > pCurrNode->_vJumps[uiCurrBits])
2051                 {
2052                     uiLevelSub += LevelBits * pCurrNode->_vJumps[uiCurrBits];
2053                     uiCurrIdx  -= LevelBits * pCurrNode->_vJumps[uiCurrBits];
2054                     uiJumpDist -= pCurrNode->_vJumps[uiCurrBits];
2055
2056                     pCurrNode = pNextNode;
2057                     pNextNode = pCurrNode->_vChildren[0].asT2();
2058
2059                     uiCurrBits  = 0x0000;
2060
2061                     while(1)
2062                     {
2063                         if(uiCurrIdx <= LevelBits)
2064                         {
2065                             break;
2066                         }
2067
2068                         if(pNextNode == NULL)
2069                         {
2070                             break;
2071                         }
2072
2073                         if(uiJumpDist <= pCurrNode->_vJumps[0])
2074                         {
2075                             break;
2076                         }
2077
2078                         uiLevelSub +=
2079                             LevelBits * pCurrNode->_vJumps[0];
2080
2081                         uiCurrIdx  -=
2082                             LevelBits * pCurrNode->_vJumps[0];
2083
2084                         uiJumpDist -= pCurrNode->_vJumps[0];
2085
2086                         pCurrNode = pNextNode;
2087                         pNextNode = pCurrNode->_vChildren[0].asT2();
2088                     }
2089                 }
2090
2091                 if(uiJumpDist < pCurrNode->_vJumps[uiCurrBits])
2092                 {
2093                     pNextNode = allocateNode();
2094
2095                     pNextNode->_vJumps[0] =
2096                         pCurrNode->_vJumps   [uiCurrBits] - uiJumpDist;
2097
2098                     pNextNode->_vChildren[0] =
2099                         pCurrNode->_vChildren[uiCurrBits].asT2();
2100
2101                     pNextNode->_pObject =
2102                         pCurrNode->_vChildren[uiCurrBits].asT2()->_pObject;
2103
2104                     pCurrNode->_vChildren[uiCurrBits].asT2()->_pObject = NULL;
2105
2106                     pCurrNode->_vJumps   [uiCurrBits] = uiJumpDist;
2107                     pCurrNode->_vChildren[uiCurrBits] = pNextNode;
2108
2109                     if(_vLevelEntries[uiTargetLevel] == NULL)
2110                     {
2111                         UInt32 uiLastValidLE = 0;
2112
2113                         for(Int32 i = uiTargetLevel; i >= 0; --i)
2114                         {
2115                             if(_vLevelEntries[i] != NULL)
2116                             {
2117                                 uiLastValidLE = i;
2118                                 break;
2119                             }
2120                         }
2121
2122                         if(_vLevelEntries[uiLastValidLE] == pCurrNode &&
2123                             uiCurrBits                   == 0          )
2124                         {
2125                             _vLevelEntries[uiTargetLevel] = pNextNode;
2126                         }
2127                         else
2128                         {
2129                             TreeNode *pTmpNode = allocateNode();
2130
2131                             if(_vLevelEntries[
2132                                    uiLastValidLE]->_vChildren[0].asT2() != NULL)
2133                             {
2134                                 pTmpNode->_vChildren[0] =
2135                                     _vLevelEntries[
2136                                         uiLastValidLE]->_vChildren[0].asT2();
2137
2138                                 pTmpNode->_vJumps[0] =
2139                                     _vLevelEntries[
2140                                         uiLastValidLE]->_vJumps[0] -
2141                                     (uiTargetLevel - uiLastValidLE);
2142                             }
2143
2144                             _vLevelEntries[uiLastValidLE]->_vChildren[0] =
2145                                 pTmpNode;
2146                             _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
2147                                 uiTargetLevel - uiLastValidLE;
2148
2149                             _vLevelEntries[uiTargetLevel] = pTmpNode;
2150
2151                             pTmpNode ->_pNext = pNextNode;
2152                             pNextNode->_pPrev = pTmpNode;
2153                         }
2154                     }
2155                     else
2156                     {
2157                         pNextNode->_pNext =
2158                             _vLevelEntries[uiTargetLevel]->_pNext;
2159
2160                         if(pNextNode->_pNext != NULL)
2161                         {
2162                             pNextNode->_pNext->_pPrev = pNextNode;
2163                         }
2164
2165                         _vLevelEntries[uiTargetLevel]->_pNext = pNextNode;
2166
2167                         pNextNode->_pPrev = _vLevelEntries[uiTargetLevel];
2168                     }
2169                 }
2170             }
2171
2172             if(pNextNode == NULL)
2173             {
2174                 pNextNode = allocateNode();
2175
2176                 pCurrNode->_vJumps   [uiCurrBits] = uiJumpDist;
2177
2178                 if(pCurrNode->_vChildren[uiCurrBits].asT1() != NULL)
2179                 {
2180                     pNextNode->_pObject =
2181                         pCurrNode->_vChildren[uiCurrBits].asT1();
2182                 }
2183
2184                 pCurrNode->_vChildren[uiCurrBits] = pNextNode;
2185
2186                 if(uiTargetLevel >= _vLevelEntries.size())
2187                 {
2188                     _vLevelEntries.resize(uiTargetLevel + 1, NULL);
2189
2190                     UInt32 uiLastValidLE = 0;
2191
2192                     for(Int32 i = uiTargetLevel; i >= 0; --i)
2193                     {
2194                         if(_vLevelEntries[i] != NULL)
2195                         {
2196                             uiLastValidLE = i;
2197                             break;
2198                         }
2199                     }
2200
2201                     if(_vLevelEntries[uiLastValidLE] == pCurrNode &&
2202                         uiCurrBits                   == 0          )
2203                     {
2204                         _vLevelEntries[uiTargetLevel] = pNextNode;
2205                     }
2206                     else
2207                     {
2208                         TreeNode *pTmpNode = allocateNode();
2209
2210                         _vLevelEntries[uiLastValidLE]->_vChildren[0] = pTmpNode;
2211                         _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
2212                             uiTargetLevel - uiLastValidLE;
2213
2214                         _vLevelEntries[uiTargetLevel] = pTmpNode;
2215
2216                         pTmpNode ->_pNext = pNextNode;
2217                         pNextNode->_pPrev = pTmpNode;
2218                     }
2219                 }
2220                 else
2221                 {
2222                     if(_vLevelEntries[uiTargetLevel] == NULL)
2223                     {
2224                         UInt32 uiLastValidLE = 0;
2225
2226                         for(Int32 i = uiTargetLevel; i >= 0; --i)
2227                         {
2228                             if(_vLevelEntries[i] != NULL)
2229                             {
2230                                 uiLastValidLE = i;
2231                                 break;
2232                             }
2233                         }
2234
2235                         TreeNode *pTmpNode = allocateNode();
2236
2237                         if(_vLevelEntries[
2238                                uiLastValidLE]->_vChildren[0].asT2() != NULL)
2239                         {
2240                             pTmpNode->_vChildren[0] =
2241                                 _vLevelEntries[
2242                                     uiLastValidLE]->_vChildren[0].asT2();
2243
2244                             pTmpNode->_vJumps[0] =
2245                                 _vLevelEntries[uiLastValidLE]->_vJumps[0] -
2246                                 (uiTargetLevel - uiLastValidLE);
2247                         }
2248
2249                         _vLevelEntries[uiLastValidLE]->_vChildren[0] = pTmpNode;
2250                         _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
2251                             uiTargetLevel - uiLastValidLE;
2252
2253                         _vLevelEntries[uiTargetLevel] = pTmpNode;
2254
2255                         pTmpNode ->_pNext = pNextNode;
2256                         pNextNode->_pPrev = pTmpNode;
2257                     }
2258                     else
2259                     {
2260                         pNextNode->_pNext =
2261                             _vLevelEntries[uiTargetLevel]->_pNext;
2262
2263                         if(pNextNode->_pNext != NULL)
2264                         {
2265                             pNextNode->_pNext->_pPrev = pNextNode;
2266                         }
2267
2268                         _vLevelEntries[uiTargetLevel]->_pNext = pNextNode;
2269
2270                         pNextNode->_pPrev = _vLevelEntries[uiTargetLevel];
2271                     }
2272                 }
2273             }
2274
2275
2276             pCurrNode   = pNextNode;
2277
2278             uiCurrBits  = 0x0000;
2279
2280             uiStartLevel = uiTargetLevel;
2281             uiLevelSub   = (uiStartLevel * LevelBits);
2282
2283             uiCurrIdx  -= uiJumpDist * LevelBits;
2284
2285             uiCurrBits |= IdxToBits[uiCurrIdx];
2286         }
2287     }
2288
2289     if(pCurrNode != NULL)
2290     {
2291         TreeNode *pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
2292
2293         if(pNextNode != NULL)
2294         {
2295             if(pNextNode->_pObject == NULL)
2296             {
2297                 pNextNode->_pObject = pObject;
2298
2299                 returnValue = true;
2300             }
2301             else
2302             {
2303                 OSG_ASSERT(pNextNode->_pObject == pObject);
2304             }
2305         }
2306         else
2307         {
2308             pCurrNode->_vChildren[uiCurrBits] = pObject;
2309
2310             returnValue = true;
2311         }
2312     }
2313
2314     return returnValue;
2315 }
2316
2317 template<class ObjectT, UInt32 LevelBits> inline
2318 void ShaderCacheTreeV2<ObjectT, LevelBits>::sub(UInt32 uiIdx)
2319 {
2320     IdType uiStartLevel  = IdType((uiIdx - 1) * LevelFactor);
2321
2322     if(uiStartLevel >= _vLevelEntries.size())
2323     {
2324         return;
2325     }
2326
2327     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
2328     UInt32    uiCurrIdx  = uiIdx - uiLevelSub;
2329     UInt32    uiCurrBits = IdxToBits[uiCurrIdx];
2330
2331     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
2332
2333     for(; pCurrNode != NULL; pCurrNode = pCurrNode->_pNext)
2334     {
2335         for(UInt32 i = 0; i < LevelSize; ++i)
2336         {
2337             TreeNode *pChild = pCurrNode->_vChildren[i].asT2();
2338
2339             if(0x0000 != (i & uiCurrBits) && pChild != NULL)
2340             {
2341                 if(pChild->_pNext == NULL)
2342                 {
2343                     pChild->_pPrev->_pNext = NULL;
2344                 }
2345                 else
2346                 {
2347                     pChild->_pPrev->_pNext = pChild->_pNext;
2348                     pChild->_pNext->_pPrev = pChild->_pPrev;
2349                 }
2350
2351                 pChild->_pPrev = NULL;
2352                 pChild->_pNext = NULL;
2353
2354                 eraseNode(pCurrNode->_vChildren[i].asT2());
2355                 pCurrNode->_vJumps   [i] = 0;
2356                 pCurrNode->_vChildren[i].setAsT2(NULL);
2357             }
2358             else if(pCurrNode->_vChildren[i].asT1() != NULL)
2359             {
2360                 pCurrNode->_vChildren[i].setAsT1(NULL);
2361                 pCurrNode->_vJumps   [i] = 0;
2362             }
2363         }
2364     }
2365 }
2366
2367 #define OSG_DUMP_LEVELENTRIES
2368
2369 template<class ObjectT, UInt32 LevelBits> inline
2370 void ShaderCacheTreeV2<ObjectT, LevelBits>::dumpDot(const Char8 *szFilename)
2371 {
2372     FILE *pOut = fopen(szFilename, "w");
2373
2374     if(pOut != NULL)
2375     {
2376         fprintf(pOut, "digraph structs\n");
2377         fprintf(pOut, "{\n");
2378         fprintf(pOut, "rankdir = LR;\n");
2379         fprintf(pOut, "splines=false\n");
2380
2381         fprintf(pOut, "node [shape=record];\n");
2382
2383         fprintf(pOut, "struct%d\n", 0);
2384         fprintf(pOut, "[\n");
2385         fprintf(pOut, "    label=\"");
2386
2387         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
2388         {
2389             if(_vLevelEntries[i] != NULL)
2390             {
2391                 fprintf(pOut, "<l%d> %d", i, i);
2392             }
2393             else
2394             {
2395                 fprintf(pOut, "<l%d> NIL", i);
2396             }
2397
2398             if(i == _vLevelEntries.size() - 1)
2399             {
2400                 fprintf(pOut, "\"\n");
2401             }
2402             else
2403             {
2404                 fprintf(pOut, "|");
2405             }
2406         }
2407
2408         fprintf(pOut, "]\n");
2409
2410         fprintf(pOut, "node [width = 1.5];\n");
2411
2412         std::vector<std::vector<TreeNode *> > vLevelStore;
2413
2414         dumpDotNode(_pRoot, pOut, vLevelStore, 0);
2415
2416 #ifdef OSG_DEBUG
2417 #ifdef OSG_DUMP_LEVELENTRIES
2418         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
2419         {
2420             if(_vLevelEntries[i] != NULL)
2421             {
2422                 fprintf(pOut,
2423                         "struct%d:l%d -> struct%d:prev [color=\"green\"];\n",
2424                         0, i,
2425                         _vLevelEntries[i]->_uiNodeId);
2426             }
2427         }
2428 #endif
2429
2430 #if 0
2431         for(UInt32 i = 0; i < vLevelStore.size(); ++i)
2432         {
2433             fprintf(pOut, "{ rank=same;");
2434
2435             for(UInt32 j = 0; j < vLevelStore[i].size(); ++j)
2436             {
2437                 TreeNode *pChild = vLevelStore[i][j];
2438
2439                 if(pChild != NULL)
2440                 {
2441                     fprintf(pOut, "\"struct%d\";",
2442                             pChild->_uiNodeId);
2443                 }
2444             }
2445
2446             fprintf(pOut, "}\n");
2447         }
2448 #endif
2449 #endif
2450
2451         fprintf(pOut, "}\n");
2452         fclose(pOut);
2453     }
2454 }
2455
2456 template<class ObjectT, UInt32 LevelBits> inline
2457 void ShaderCacheTreeV2<ObjectT, LevelBits>::dumpDotNode(
2458     TreeNode                              *pNode,
2459     FILE                                  *pOut ,
2460     std::vector<std::vector<TreeNode *> > &vLevelStore,
2461     UInt32                                 uiLevel    )
2462 {
2463 #ifdef OSG_DEBUG
2464     if(pNode == NULL)
2465         return;
2466
2467     if(uiLevel == vLevelStore.size())
2468     {
2469         vLevelStore.push_back(std::vector<TreeNode *>());
2470     }
2471
2472     fprintf(pOut, "struct%d\n", pNode->_uiNodeId);
2473     fprintf(pOut, "[\n");
2474     fprintf(pOut, "    label=\"{");
2475
2476     if(pNode->_pPrev != NULL)
2477     {
2478         fprintf(pOut, "<prev> P|");
2479     }
2480     else
2481     {
2482         fprintf(pOut, "<prev> P:NIL|");
2483     }
2484
2485     for(UInt32 i = 0; i < LevelSize; ++i)
2486     {
2487         if(pNode->_vChildren[i].asT1() != NULL)
2488         {
2489             if(osgIsPower2(i) == true)
2490             {
2491                 fprintf(pOut, "<l%d> _O:%d|", i, i);
2492             }
2493             else
2494             {
2495                 fprintf(pOut, "<l%d> O:%d|", i, i);
2496             }
2497         }
2498         else if(pNode->_vChildren[i].asT2() != NULL)
2499         {
2500             if(osgIsPower2(i) == true)
2501             {
2502                 fprintf(pOut, "<l%d> _C:%d (%d)|", i, i, pNode->_vJumps[i]);
2503             }
2504             else
2505             {
2506                 fprintf(pOut, "<l%d> C:%d (%d)|", i, i, pNode->_vJumps[i]);
2507             }
2508         }
2509         else
2510         {
2511             if(osgIsPower2(i) == true)
2512             {
2513                 fprintf(pOut, "<l%d> _NIL|", i);
2514             }
2515             else
2516             {
2517                 fprintf(pOut, "<l%d> NIL|", i);
2518             }
2519         }
2520     }
2521
2522     if(pNode->_pObject != NULL)
2523     {
2524         fprintf(pOut, "<val> VAL:Obj|");
2525     }
2526     else
2527     {
2528         fprintf(pOut, "<val> VAL:NIL|");
2529     }
2530
2531     if(pNode->_pNext != NULL)
2532     {
2533         fprintf(pOut, "<next> N}\"\n");
2534     }
2535     else
2536     {
2537         fprintf(pOut, "<next> N:NIL}\"\n");
2538     }
2539
2540     fprintf(pOut, "]\n");
2541
2542     for(UInt32 i = 0; i < LevelSize; ++i)
2543     {
2544         TreeNode *pChild = pNode->_vChildren[i].asT2();
2545
2546         if(pChild != NULL)
2547         {
2548             dumpDotNode(pChild, pOut, vLevelStore, uiLevel + 1);
2549
2550             fprintf(pOut,
2551                     "struct%d:l%d -> struct%d:l%d [constraint=\"false\"];\n",
2552                     pNode ->_uiNodeId, i,
2553                     pChild->_uiNodeId, i);
2554         }
2555     }
2556
2557     if(pNode->_pNext != NULL)
2558     {
2559         fprintf(pOut, "struct%d:next -> struct%d:prev;\n",
2560                 pNode ->_uiNodeId,
2561                 pNode->_pNext->_uiNodeId);
2562     }
2563     if(pNode->_pPrev != NULL)
2564     {
2565         fprintf(pOut, "struct%d:prev -> struct%d:next;\n",
2566                 pNode ->_uiNodeId,
2567                 pNode->_pPrev->_uiNodeId);
2568     }
2569
2570      vLevelStore[uiLevel].push_back(pNode);
2571 #endif
2572 }
2573
2574 template<class ObjectT, UInt32 LevelBits> inline
2575 ShaderCacheTreeV2<ObjectT, LevelBits>::ShaderCacheTreeV2(void) :
2576 #ifdef OSG_DEBUG
2577     _uiNodeCount  (0   ),
2578 #endif
2579     _pRoot        (NULL),
2580     _vLevelEntries(    ),
2581     _qFreeElements(    )
2582 {
2583     _pRoot = allocateNode();
2584
2585     _vLevelEntries.push_back(_pRoot);
2586 }
2587
2588 template<class ObjectT, UInt32 LevelBits> inline
2589 ShaderCacheTreeV2<ObjectT, LevelBits>::~ShaderCacheTreeV2(void)
2590 {
2591     typename std::deque <TreeNode *>::iterator qIt  =
2592         _qFreeElements.begin();
2593
2594     typename std::deque <TreeNode *>::const_iterator qEnd =
2595         _qFreeElements.end();
2596
2597     for(; qIt != qEnd; ++qIt)
2598     {
2599         delete (*qIt);
2600
2601         *qIt = NULL;
2602     }
2603
2604     typename std::vector<TreeNode *>::iterator vIt  = _vLevelEntries.begin();
2605     typename std::vector<TreeNode *>::iterator vEnd = _vLevelEntries.end  ();
2606
2607     for(; vIt != vEnd; ++vIt)
2608     {
2609         delete (*vIt);
2610
2611         *vIt = NULL;
2612     }
2613 }
2614
2615 template<class ObjectT, UInt32 LevelBits> inline
2616 typename ShaderCacheTreeV2<ObjectT, LevelBits>::TreeNode *
2617     ShaderCacheTreeV2<ObjectT, LevelBits>::allocateNode(void)
2618 {
2619     TreeNode *returnValue = NULL;
2620
2621     if(_qFreeElements.empty() == false)
2622     {
2623         returnValue = _qFreeElements.back();
2624
2625         _qFreeElements.pop_back();
2626
2627         returnValue->clear();
2628     }
2629     else
2630     {
2631         returnValue = new TreeNode();
2632
2633 #ifdef OSG_DEBUG
2634         returnValue->_uiNodeId = ++_uiNodeCount;
2635 #endif
2636     }
2637
2638 #ifdef OSG_DEBUG
2639     UIntPointer rU = reinterpret_cast<UIntPointer>(returnValue);
2640
2641     OSG_ASSERT((rU & 0x0001) == 0x0000);
2642 #endif
2643
2644     return returnValue;
2645 }
2646
2647 template<class ObjectT, UInt32 LevelBits> inline
2648 void ShaderCacheTreeV2<ObjectT, LevelBits>::eraseNode(TreeNode *pNode)
2649 {
2650     for(UInt32 i = 0; i < LevelSize; ++i)
2651     {
2652         if(pNode->_vChildren[i].asT2() != NULL)
2653         {
2654             eraseNode(pNode->_vChildren[i].asT2());
2655
2656             pNode->_vChildren[i].setAsT2(NULL);
2657         }
2658         else
2659         {
2660             pNode->_vChildren[i].setAsT1(NULL);
2661         }
2662     }
2663
2664     pNode->_pObject = NULL;
2665
2666     _qFreeElements.push_back(pNode);
2667 }
2668
2669 template<class ObjectT, UInt32 LevelBits>
2670 template <typename ElemDestFunc> inline
2671 void ShaderCacheTreeV2<ObjectT, LevelBits>::destroyNode(TreeNode     *pNode,
2672                                                         ElemDestFunc  destFunc)
2673 {
2674     if(pNode == NULL)
2675         return;
2676
2677     for(UInt32 i = 0; i < LevelSize; ++i)
2678     {
2679         if(pNode->_vChildren[i].asT2() != NULL)
2680         {
2681             destroyNode(pNode->_vChildren[i].asT2(), destFunc);
2682         }
2683         else if(pNode->_vChildren[i].asT1() != NULL)
2684         {
2685 #ifndef OSG_SHC_REF_CLEANUP
2686             ObjectT *pObj = pNode->_vChildren[i].asT1();
2687             (destFunc)(pObj);
2688 #endif
2689             pNode->_vChildren[i].setAsT1(NULL);
2690         }
2691     }
2692
2693     if(pNode->_pObject != NULL)
2694     {
2695 #ifndef OSG_SHC_REF_CLEANUP
2696         (destFunc)(pNode->_pObject);
2697 #endif
2698         pNode->_pObject = NULL;
2699     }
2700
2701     delete pNode;
2702 }
2703
2704 template<class ObjectT, UInt32 LevelBits>
2705 template <typename ElemDestFunc> inline
2706 void ShaderCacheTreeV2<ObjectT, LevelBits>::destroy(ElemDestFunc destFunc)
2707 {
2708     destroyNode(_pRoot, destFunc);
2709
2710     _vLevelEntries[0] = NULL;
2711
2712     _pRoot = NULL;
2713 }
2714
2715
2716
2717
2718
2719
2720 /*---------------------------------------------------------------------------*/
2721 /*---------------------------------------------------------------------------*/
2722
2723 #if defined(WIN32) || defined(__APPLE__) || \
2724     defined(__GXX_EXPERIMENTAL_CXX0X__)
2725 template<class ObjectT, UInt32 LevelBits>
2726 const Real32 ShaderCacheTreeV3<ObjectT, LevelBits>::LevelFactor =
2727                                                             1.f / (LevelBits);
2728 #endif
2729
2730 template<class ObjectT, UInt32 LevelBits> inline
2731 ShaderCacheTreeV3<ObjectT, LevelBits>::TreeNode::TreeNode(void) :
2732 #ifdef OSG_DEBUG
2733     _uiNodeId(0   ),
2734 #endif
2735     _pObject (NULL),
2736     _pPrev   (NULL),
2737     _pNext   (NULL)
2738 {
2739     memset(&(_vJumps[0]), 0, LevelSize * sizeof(UInt16));
2740 }
2741
2742 template<class ObjectT, UInt32 LevelBits> inline
2743 ShaderCacheTreeV3<ObjectT, LevelBits>::TreeNode::~TreeNode(void)
2744 {
2745     _pObject = NULL;
2746     _pPrev   = NULL;
2747     _pNext   = NULL;
2748
2749     for(UInt32 i = 0; i < LevelSize; ++i)
2750     {
2751         _vChildren[i].setAsT1(NULL);
2752     }
2753 }
2754
2755 template<class ObjectT, UInt32 LevelBits> inline
2756 void ShaderCacheTreeV3<ObjectT, LevelBits>::TreeNode::clear(void)
2757 {
2758     _pObject = NULL;
2759     _pPrev   = NULL;
2760     _pNext   = NULL;
2761
2762     for(UInt32 i = 0; i < LevelSize; ++i)
2763     {
2764         _vChildren[i].setAsT1(NULL);
2765     }
2766
2767     memset(&(_vJumps[0]), 0, LevelSize * sizeof(UInt16));
2768 }
2769
2770
2771
2772 template<class ObjectT, UInt32 LevelBits> inline
2773 ObjectT *ShaderCacheTreeV3<ObjectT, LevelBits>::find(const IdStore &vIds)
2774 {
2775     if(vIds.size() < 1 || _pRoot == NULL)
2776         return NULL;
2777
2778     ObjectT *returnValue = NULL;
2779
2780     IdType uiStartId     = vIds[0] - 1;
2781     IdType uiStartLevel  = IdType(uiStartId * LevelFactor);
2782
2783     UInt32 uiCurrId      = 0;
2784     UInt32 uiLastId      = UInt32(vIds.size());
2785
2786
2787     if(uiStartLevel >= _vLevelEntries.size())
2788     {
2789         uiStartLevel = IdType(_vLevelEntries.size() - 1);
2790     }
2791
2792
2793     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
2794     UInt32    uiCurrBits = 0x0000;
2795     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
2796     TreeNode *pNextNode  = NULL;
2797
2798     if(pCurrNode == NULL)
2799         return NULL;
2800
2801     for(; uiCurrId < uiLastId; ++uiCurrId)
2802     {
2803         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
2804         UInt16 uiJumpDist = 1;
2805
2806         if(uiCurrIdx <= LevelBits)
2807         {
2808             uiCurrBits |= IdxToBits[uiCurrIdx];
2809
2810             continue;
2811         }
2812         else
2813         {
2814             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
2815
2816             if(pNextNode == NULL)
2817             {
2818                 pCurrNode = pNextNode;
2819                 break;
2820             }
2821
2822             uiJumpDist = UInt16((uiCurrIdx - 1) * LevelFactor);
2823             UInt32 uiTargetLevel = uiStartLevel + uiJumpDist;
2824
2825             if(uiJumpDist < pCurrNode->_vJumps[uiCurrBits])
2826             {
2827                 pCurrNode = NULL;
2828                 break;
2829             }
2830
2831             if(uiJumpDist > pCurrNode->_vJumps[uiCurrBits])
2832             {
2833                 uiLevelSub += LevelBits * pCurrNode->_vJumps[uiCurrBits];
2834                 uiCurrIdx  -= LevelBits * pCurrNode->_vJumps[uiCurrBits];
2835                 uiJumpDist -= pCurrNode->_vJumps[uiCurrBits];
2836
2837                 pCurrNode = pNextNode;
2838                 pNextNode = pCurrNode->_vChildren[0].asT2();
2839
2840                 uiCurrBits  = 0x0000;
2841
2842                 while(1)
2843                 {
2844                     if(uiCurrIdx <= LevelBits)
2845                     {
2846                         break;
2847                     }
2848
2849                     if(uiJumpDist == pCurrNode->_vJumps[0])
2850                     {
2851                         break;
2852                     }
2853
2854                     if(uiJumpDist < pCurrNode->_vJumps[0])
2855                     {
2856                         pNextNode = NULL;
2857                         break;
2858                     }
2859
2860                     if(pNextNode == NULL)
2861                     {
2862                         break;
2863                     }
2864
2865                     uiLevelSub +=
2866                         LevelBits * pCurrNode->_vJumps[0];
2867
2868                     uiCurrIdx  -=
2869                         LevelBits * pCurrNode->_vJumps[0];
2870
2871                     uiJumpDist -= pCurrNode->_vJumps[0];
2872
2873                     pCurrNode = pNextNode;
2874                     pNextNode = pCurrNode->_vChildren[0].asT2();
2875                 }
2876             }
2877
2878             pCurrNode = pNextNode;
2879
2880             if(pCurrNode == NULL)
2881             {
2882                 break;
2883             }
2884
2885             uiCurrBits  = 0x0000;
2886
2887             uiStartLevel = uiTargetLevel;
2888             uiLevelSub   = (uiStartLevel * LevelBits);
2889
2890             uiCurrIdx  -= uiJumpDist * LevelBits;
2891
2892
2893             uiCurrBits |= IdxToBits[uiCurrIdx];
2894         }
2895     }
2896
2897     if(pCurrNode != NULL)
2898     {
2899         TreeNode *pNext = pCurrNode->_vChildren[uiCurrBits].asT2();
2900
2901         if(pNext != NULL)
2902         {
2903             returnValue = pNext->_pObject;
2904         }
2905         else
2906         {
2907             returnValue = pCurrNode->_vChildren[uiCurrBits].asT1();
2908         }
2909     }
2910
2911     return returnValue;
2912 }
2913
2914
2915 template<class ObjectT, UInt32 LevelBits> inline
2916 bool ShaderCacheTreeV3<ObjectT, LevelBits>::add(const IdStore &vIds,
2917                                                       ObjectT *pObject)
2918 {
2919     bool returnValue = false;
2920
2921     if(vIds.size() < 1)
2922         return returnValue;
2923
2924     IdType uiStartId    = vIds[0] - 1;
2925
2926     IdType uiStartLevel = IdType(uiStartId * LevelFactor);
2927
2928     UInt32 uiCurrId     = 0;
2929     UInt32 uiLastId     = UInt32(vIds.size());
2930
2931 #ifdef OSG_DEBUG
2932     FDEBUG(("scv3::add : "));
2933     for(UInt32 i = 0; i < uiLastId; ++i)
2934     {
2935         FDEBUG(("%d ", vIds[i]));
2936     }
2937     FDEBUG(("\n"));
2938 #endif
2939
2940     if(_pRoot == NULL)
2941     {
2942         _pRoot = allocateNode();
2943
2944         OSG_ASSERT(_vLevelEntries.size() == 0);
2945
2946         _vLevelEntries.push_back(_pRoot);
2947     }
2948
2949     if(uiStartLevel >= _vLevelEntries.size())
2950     {
2951         uiStartLevel = IdType(_vLevelEntries.size() - 1);
2952     }
2953
2954
2955     TreeNode *pCurrNode = _vLevelEntries[uiStartLevel];
2956     TreeNode *pNextNode = NULL;
2957
2958     UInt32 uiCurrBits = 0x0000;
2959
2960     if(pCurrNode == NULL)
2961     {
2962         UInt32 uiLastValidLE = 0;
2963
2964         for(Int32 i = uiStartLevel; i >= 0; --i)
2965         {
2966             if(_vLevelEntries[i] != NULL)
2967             {
2968                 uiLastValidLE = i;
2969                 break;
2970             }
2971         }
2972
2973         uiStartLevel = uiLastValidLE;
2974         pCurrNode    = _vLevelEntries[uiStartLevel];
2975     }
2976
2977     UInt32 uiLevelSub   = (uiStartLevel * LevelBits);
2978
2979     for(; uiCurrId < uiLastId; ++uiCurrId)
2980     {
2981         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
2982         UInt16 uiJumpDist = 1;
2983
2984         if(uiCurrIdx <= LevelBits)
2985         {
2986             uiCurrBits |= IdxToBits[uiCurrIdx];
2987
2988             continue;
2989         }
2990         else
2991         {
2992             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
2993
2994             uiJumpDist           = UInt16((uiCurrIdx - 1) * LevelFactor);
2995             UInt32 uiTargetLevel = uiStartLevel + uiJumpDist;
2996
2997             if(pNextNode != NULL)
2998             {
2999                 if(uiJumpDist > pCurrNode->_vJumps[uiCurrBits])
3000                 {
3001                     uiLevelSub += LevelBits * pCurrNode->_vJumps[uiCurrBits];
3002                     uiCurrIdx  -= LevelBits * pCurrNode->_vJumps[uiCurrBits];
3003                     uiJumpDist -= pCurrNode->_vJumps[uiCurrBits];
3004
3005                     pCurrNode = pNextNode;
3006                     pNextNode = pCurrNode->_vChildren[0].asT2();
3007
3008                     uiCurrBits  = 0x0000;
3009
3010                     while(1)
3011                     {
3012                         if(uiCurrIdx <= LevelBits)
3013                         {
3014                             break;
3015                         }
3016
3017                         if(pNextNode == NULL)
3018                         {
3019                             break;
3020                         }
3021
3022                         if(uiJumpDist <= pCurrNode->_vJumps[0])
3023                         {
3024                             break;
3025                         }
3026
3027                         uiLevelSub +=
3028                             LevelBits * pCurrNode->_vJumps[0];
3029
3030                         uiCurrIdx  -=
3031                             LevelBits * pCurrNode->_vJumps[0];
3032
3033                         uiJumpDist -= pCurrNode->_vJumps[0];
3034
3035                         pCurrNode = pNextNode;
3036                         pNextNode = pCurrNode->_vChildren[0].asT2();
3037                     }
3038                 }
3039
3040                 if(uiJumpDist < pCurrNode->_vJumps[uiCurrBits])
3041                 {
3042                     pNextNode = allocateNode();
3043
3044                     pNextNode->_vJumps[0] =
3045                         pCurrNode->_vJumps   [uiCurrBits] - uiJumpDist;
3046
3047                     pNextNode->_vChildren[0] =
3048                         pCurrNode->_vChildren[uiCurrBits].asT2();
3049
3050                     pNextNode->_pObject =
3051                         pCurrNode->_vChildren[uiCurrBits].asT2()->_pObject;
3052
3053                     pCurrNode->_vChildren[uiCurrBits].asT2()->_pObject = NULL;
3054
3055                     pCurrNode->_vJumps   [uiCurrBits] = uiJumpDist;
3056                     pCurrNode->_vChildren[uiCurrBits] = pNextNode;
3057
3058                     if(_vLevelEntries[uiTargetLevel] == NULL)
3059                     {
3060                         UInt32 uiLastValidLE = 0;
3061
3062                         for(Int32 i = uiTargetLevel; i >= 0; --i)
3063                         {
3064                             if(_vLevelEntries[i] != NULL)
3065                             {
3066                                 uiLastValidLE = i;
3067                                 break;
3068                             }
3069                         }
3070
3071                         if(_vLevelEntries[uiLastValidLE] == pCurrNode &&
3072                             uiCurrBits                   == 0          )
3073                         {
3074                             _vLevelEntries[uiTargetLevel] = pNextNode;
3075                         }
3076                         else
3077                         {
3078                             TreeNode *pTmpNode = allocateNode();
3079
3080                             if(_vLevelEntries[
3081                                    uiLastValidLE]->_vChildren[0].asT2() != NULL)
3082                             {
3083                                 pTmpNode->_vChildren[0] =
3084                                     _vLevelEntries[
3085                                         uiLastValidLE]->_vChildren[0].asT2();
3086
3087                                 pTmpNode->_vJumps[0] =
3088                                     _vLevelEntries[
3089                                         uiLastValidLE]->_vJumps[0] -
3090                                     (uiTargetLevel - uiLastValidLE);
3091                             }
3092
3093                             _vLevelEntries[uiLastValidLE]->_vChildren[0] =
3094                                 pTmpNode;
3095                             _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
3096                                 uiTargetLevel - uiLastValidLE;
3097
3098                             _vLevelEntries[uiTargetLevel] = pTmpNode;
3099
3100                             pTmpNode ->_pNext = pNextNode;
3101                             pNextNode->_pPrev = pTmpNode;
3102                         }
3103                     }
3104                     else
3105                     {
3106                         pNextNode->_pNext =
3107                             _vLevelEntries[uiTargetLevel]->_pNext;
3108
3109                         if(pNextNode->_pNext != NULL)
3110                         {
3111                             pNextNode->_pNext->_pPrev = pNextNode;
3112                         }
3113
3114                         _vLevelEntries[uiTargetLevel]->_pNext = pNextNode;
3115
3116                         pNextNode->_pPrev = _vLevelEntries[uiTargetLevel];
3117                     }
3118                 }
3119             }
3120
3121             if(pNextNode == NULL)
3122             {
3123                 pNextNode = allocateNode();
3124
3125                 pCurrNode->_vJumps   [uiCurrBits] = uiJumpDist;
3126
3127                 if(pCurrNode->_vChildren[uiCurrBits].asT1() != NULL)
3128                 {
3129                     pNextNode->_pObject =
3130                         pCurrNode->_vChildren[uiCurrBits].asT1();
3131                 }
3132
3133                 pCurrNode->_vChildren[uiCurrBits] = pNextNode;
3134
3135                 if(uiTargetLevel >= _vLevelEntries.size())
3136                 {
3137                     _vLevelEntries.resize(uiTargetLevel + 1, NULL);
3138
3139                     UInt32 uiLastValidLE = 0;
3140
3141                     for(Int32 i = uiTargetLevel; i >= 0; --i)
3142                     {
3143                         if(_vLevelEntries[i] != NULL)
3144                         {
3145                             uiLastValidLE = i;
3146                             break;
3147                         }
3148                     }
3149
3150                     if(_vLevelEntries[uiLastValidLE] == pCurrNode &&
3151                         uiCurrBits                   == 0          )
3152                     {
3153                         _vLevelEntries[uiTargetLevel] = pNextNode;
3154                     }
3155                     else
3156                     {
3157                         TreeNode *pTmpNode = allocateNode();
3158
3159                         _vLevelEntries[uiLastValidLE]->_vChildren[0] = pTmpNode;
3160                         _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
3161                             uiTargetLevel - uiLastValidLE;
3162
3163                         _vLevelEntries[uiTargetLevel] = pTmpNode;
3164
3165                         pTmpNode ->_pNext = pNextNode;
3166                         pNextNode->_pPrev = pTmpNode;
3167                     }
3168                 }
3169                 else
3170                 {
3171                     if(_vLevelEntries[uiTargetLevel] == NULL)
3172                     {
3173                         UInt32 uiLastValidLE = 0;
3174
3175                         for(Int32 i = uiTargetLevel; i >= 0; --i)
3176                         {
3177                             if(_vLevelEntries[i] != NULL)
3178                             {
3179                                 uiLastValidLE = i;
3180                                 break;
3181                             }
3182                         }
3183
3184                         TreeNode *pTmpNode = allocateNode();
3185
3186                         if(_vLevelEntries[
3187                                uiLastValidLE]->_vChildren[0].asT2() != NULL)
3188                         {
3189                             pTmpNode->_vChildren[0] =
3190                                 _vLevelEntries[
3191                                     uiLastValidLE]->_vChildren[0].asT2();
3192
3193                             pTmpNode->_vJumps[0] =
3194                                 _vLevelEntries[uiLastValidLE]->_vJumps[0] -
3195                                 (uiTargetLevel - uiLastValidLE);
3196
3197                         }
3198
3199                         _vLevelEntries[uiLastValidLE]->_vChildren[0] = pTmpNode;
3200                         _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
3201                             uiTargetLevel - uiLastValidLE;
3202
3203                         _vLevelEntries[uiTargetLevel] = pTmpNode;
3204
3205                         pTmpNode ->_pNext = pNextNode;
3206                         pNextNode->_pPrev = pTmpNode;
3207                     }
3208                     else
3209                     {
3210                         pNextNode->_pNext =
3211                             _vLevelEntries[uiTargetLevel]->_pNext;
3212
3213                         if(pNextNode->_pNext != NULL)
3214                         {
3215                             pNextNode->_pNext->_pPrev = pNextNode;
3216                         }
3217
3218                         _vLevelEntries[uiTargetLevel]->_pNext = pNextNode;
3219
3220                         pNextNode->_pPrev = _vLevelEntries[uiTargetLevel];
3221                     }
3222                 }
3223             }
3224
3225
3226             pCurrNode   = pNextNode;
3227
3228             uiCurrBits  = 0x0000;
3229
3230             uiStartLevel = uiTargetLevel;
3231             uiLevelSub   = (uiStartLevel * LevelBits);
3232
3233             uiCurrIdx  -= uiJumpDist * LevelBits;
3234
3235             uiCurrBits |= IdxToBits[uiCurrIdx];
3236         }
3237     }
3238
3239     if(pCurrNode != NULL)
3240     {
3241         TreeNode *pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
3242
3243         if(pNextNode != NULL)
3244         {
3245             if(pNextNode->_pObject == NULL)
3246             {
3247                 pNextNode->_pObject = pObject;
3248
3249                 returnValue = true;
3250             }
3251             else
3252             {
3253                 OSG_ASSERT(pNextNode->_pObject == pObject);
3254             }
3255         }
3256         else
3257         {
3258             pCurrNode->_vChildren[uiCurrBits] = pObject;
3259
3260             returnValue = true;
3261         }
3262     }
3263
3264     return returnValue;
3265 }
3266
3267 template<class ObjectT, UInt32 LevelBits> inline
3268 void ShaderCacheTreeV3<ObjectT, LevelBits>::sub(UInt32 uiIdx)
3269 {
3270 #ifdef OSG_DEBUG
3271     FDEBUG(("scv3::sub : %d\n", uiIdx));
3272 #endif
3273
3274     IdType uiStartLevel  = IdType((uiIdx - 1) * LevelFactor);
3275
3276     if(uiStartLevel >= _vLevelEntries.size())
3277     {
3278         return;
3279     }
3280
3281     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
3282     UInt32    uiCurrIdx  = uiIdx - uiLevelSub;
3283     UInt32    uiCurrBits = IdxToBits[uiCurrIdx];
3284
3285     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
3286
3287     for(; pCurrNode != NULL; pCurrNode = pCurrNode->_pNext)
3288     {
3289         for(UInt32 i = 0; i < LevelSize; ++i)
3290         {
3291             TreeNode *pChild = pCurrNode->_vChildren[i].asT2();
3292
3293             if(0x0000 != (i & uiCurrBits) && pChild != NULL)
3294             {
3295                 if(pChild->_pNext == NULL)
3296                 {
3297                     pChild->_pPrev->_pNext = NULL;
3298                 }
3299                 else
3300                 {
3301                     pChild->_pPrev->_pNext = pChild->_pNext;
3302                     pChild->_pNext->_pPrev = pChild->_pPrev;
3303                 }
3304
3305                 pChild->_pPrev = NULL;
3306                 pChild->_pNext = NULL;
3307
3308                 eraseNode(pCurrNode->_vChildren[i].asT2());
3309                 pCurrNode->_vJumps   [i] = 0;
3310                 pCurrNode->_vChildren[i].setAsT2(NULL);
3311             }
3312             else if(pCurrNode->_vChildren[i].asT1() != NULL)
3313             {
3314                 pCurrNode->_vChildren[i].setAsT1(NULL);
3315                 pCurrNode->_vJumps   [i] = 0;
3316             }
3317         }
3318     }
3319 }
3320
3321 #define OSG_DUMP_LEVELENTRIES
3322
3323 template<class ObjectT, UInt32 LevelBits> inline
3324 void ShaderCacheTreeV3<ObjectT,
3325                        LevelBits>::dumpDot(const Char8 *szFilename,
3326                                                  bool   dumpEmptyLevelEntries)
3327 {
3328     FILE *pOut = fopen(szFilename, "w");
3329
3330     if(pOut != NULL)
3331     {
3332         fprintf(pOut, "digraph structs\n");
3333         fprintf(pOut, "{\n");
3334         fprintf(pOut, "rankdir = LR;\n");
3335         fprintf(pOut, "splines=false\n");
3336
3337         fprintf(pOut, "node [shape=record];\n");
3338
3339         fprintf(pOut, "struct%d\n", 0);
3340         fprintf(pOut, "[\n");
3341         fprintf(pOut, "    label=\"");
3342
3343         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
3344         {
3345             if(_vLevelEntries[i] != NULL)
3346             {
3347                 fprintf(pOut, "<l%d> %d", i, i);
3348             }
3349             else
3350             {
3351                 if(dumpEmptyLevelEntries == true)
3352                     fprintf(pOut, "<l%d> NIL", i);
3353             }
3354
3355             if(i == _vLevelEntries.size() - 1)
3356             {
3357                 fprintf(pOut, "\"\n");
3358             }
3359             else
3360             {
3361                 if(_vLevelEntries[i] != NULL || dumpEmptyLevelEntries == true)
3362                     fprintf(pOut, "|");
3363             }
3364         }
3365
3366         fprintf(pOut, "]\n");
3367
3368         fprintf(pOut, "node [width = 1.5];\n");
3369
3370         std::vector<std::vector<TreeNode *> > vLevelStore;
3371
3372         dumpDotNode(_pRoot, pOut, vLevelStore, 0);
3373
3374 #ifdef OSG_DEBUG
3375 #ifdef OSG_DUMP_LEVELENTRIES
3376         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
3377         {
3378             if(_vLevelEntries[i] != NULL)
3379             {
3380                 fprintf(pOut,
3381                         "struct%d:l%d -> struct%d:prev [color=\"green\"];\n",
3382                         0, i,
3383                         _vLevelEntries[i]->_uiNodeId);
3384             }
3385         }
3386 #endif
3387
3388 #if 0
3389         for(UInt32 i = 0; i < vLevelStore.size(); ++i)
3390         {
3391             fprintf(pOut, "{ rank=same;");
3392
3393             for(UInt32 j = 0; j < vLevelStore[i].size(); ++j)
3394             {
3395                 TreeNode *pChild = vLevelStore[i][j];
3396
3397                 if(pChild != NULL)
3398                 {
3399                     fprintf(pOut, "\"struct%d\";",
3400                             pChild->_uiNodeId);
3401                 }
3402             }
3403
3404             fprintf(pOut, "}\n");
3405         }
3406 #endif
3407 #endif
3408
3409         fprintf(pOut, "}\n");
3410         fclose(pOut);
3411     }
3412 }
3413
3414 template<class ObjectT, UInt32 LevelBits> inline
3415 void ShaderCacheTreeV3<ObjectT, LevelBits>::dumpDotNode(
3416     TreeNode                              *pNode,
3417     FILE                                  *pOut ,
3418     std::vector<std::vector<TreeNode *> > &vLevelStore,
3419     UInt32                                 uiLevel    )
3420 {
3421 #ifdef OSG_DEBUG
3422     if(pNode == NULL)
3423         return;
3424
3425     if(uiLevel == vLevelStore.size())
3426     {
3427         vLevelStore.push_back(std::vector<TreeNode *>());
3428     }
3429
3430     fprintf(pOut, "struct%d\n", pNode->_uiNodeId);
3431     fprintf(pOut, "[\n");
3432     fprintf(pOut, "    label=\"{");
3433
3434     if(pNode->_pPrev != NULL)
3435     {
3436         fprintf(pOut, "<prev> P|");
3437     }
3438     else
3439     {
3440         fprintf(pOut, "<prev> P:NIL|");
3441     }
3442
3443     for(UInt32 i = 0; i < LevelSize; ++i)
3444     {
3445         if(pNode->_vChildren[i].asT1() != NULL)
3446         {
3447             if(osgIsPower2(i) == true)
3448             {
3449                 fprintf(pOut, "<l%d> _O:%d|", i, i);
3450             }
3451             else
3452             {
3453                 fprintf(pOut, "<l%d> O:%d|", i, i);
3454             }
3455         }
3456         else if(pNode->_vChildren[i].asT2() != NULL)
3457         {
3458             if(osgIsPower2(i) == true)
3459             {
3460                 fprintf(pOut, "<l%d> _C:%d (%d)|", i, i, pNode->_vJumps[i]);
3461             }
3462             else
3463             {
3464                 fprintf(pOut, "<l%d> C:%d (%d)|", i, i, pNode->_vJumps[i]);
3465             }
3466         }
3467         else
3468         {
3469             if(osgIsPower2(i) == true)
3470             {
3471                 fprintf(pOut, "<l%d> _NIL|", i);
3472             }
3473             else
3474             {
3475                 fprintf(pOut, "<l%d> NIL|", i);
3476             }
3477         }
3478     }
3479
3480     if(pNode->_pObject != NULL)
3481     {
3482         fprintf(pOut, "<val> VAL:Obj|");
3483     }
3484     else
3485     {
3486         fprintf(pOut, "<val> VAL:NIL|");
3487     }
3488
3489     if(pNode->_pNext != NULL)
3490     {
3491         fprintf(pOut, "<next> N}\"\n");
3492     }
3493     else
3494     {
3495         fprintf(pOut, "<next> N:NIL}\"\n");
3496     }
3497
3498     fprintf(pOut, "]\n");
3499
3500     for(UInt32 i = 0; i < LevelSize; ++i)
3501     {
3502         TreeNode *pChild = pNode->_vChildren[i].asT2();
3503
3504         if(pChild != NULL)
3505         {
3506             dumpDotNode(pChild, pOut, vLevelStore, uiLevel + 1);
3507
3508             fprintf(pOut,
3509                     "struct%d:l%d -> struct%d:l%d [constraint=\"false\"];\n",
3510                     pNode ->_uiNodeId, i,
3511                     pChild->_uiNodeId, i);
3512         }
3513     }
3514
3515     if(pNode->_pNext != NULL)
3516     {
3517         fprintf(pOut, "struct%d:next -> struct%d:prev;\n",
3518                 pNode ->_uiNodeId,
3519                 pNode->_pNext->_uiNodeId);
3520     }
3521     if(pNode->_pPrev != NULL)
3522     {
3523         fprintf(pOut, "struct%d:prev -> struct%d:next;\n",
3524                 pNode ->_uiNodeId,
3525                 pNode->_pPrev->_uiNodeId);
3526     }
3527
3528      vLevelStore[uiLevel].push_back(pNode);
3529 #endif
3530 }
3531
3532 template<class ObjectT, UInt32 LevelBits> inline
3533 ShaderCacheTreeV3<ObjectT, LevelBits>::ShaderCacheTreeV3(void) :
3534 #ifdef OSG_DEBUG
3535     _uiNodeCount  (0   ),
3536 #endif
3537     _pRoot        (NULL),
3538     _vLevelEntries(    ),
3539     _qFreeElements(    )
3540 {
3541     _pRoot = allocateNode();
3542
3543     _vLevelEntries.push_back(_pRoot);
3544 }
3545
3546 template<class ObjectT, UInt32 LevelBits> inline
3547 ShaderCacheTreeV3<ObjectT, LevelBits>::~ShaderCacheTreeV3(void)
3548 {
3549     typename std::deque <TreeNode *>::iterator qIt  =
3550         _qFreeElements.begin();
3551
3552     typename std::deque <TreeNode *>::const_iterator qEnd =
3553         _qFreeElements.end();
3554
3555     for(; qIt != qEnd; ++qIt)
3556     {
3557         delete (*qIt);
3558
3559         *qIt = NULL;
3560     }
3561
3562     typename std::vector<TreeNode *>::iterator vIt  = _vLevelEntries.begin();
3563     typename std::vector<TreeNode *>::iterator vEnd = _vLevelEntries.end  ();
3564
3565     for(; vIt != vEnd; ++vIt)
3566     {
3567         delete (*vIt);
3568
3569         *vIt = NULL;
3570     }
3571 }
3572
3573 template<class ObjectT, UInt32 LevelBits> inline
3574 typename ShaderCacheTreeV3<ObjectT, LevelBits>::TreeNode *
3575     ShaderCacheTreeV3<ObjectT, LevelBits>::allocateNode(void)
3576 {
3577     TreeNode *returnValue = NULL;
3578
3579     if(_qFreeElements.empty() == false)
3580     {
3581         returnValue = _qFreeElements.back();
3582
3583         _qFreeElements.pop_back();
3584
3585         returnValue->clear();
3586     }
3587     else
3588     {
3589         returnValue = new TreeNode();
3590
3591 #ifdef OSG_DEBUG
3592         returnValue->_uiNodeId = ++_uiNodeCount;
3593 #endif
3594     }
3595
3596 #ifdef OSG_DEBUG
3597     UIntPointer rU = reinterpret_cast<UIntPointer>(returnValue);
3598
3599     OSG_ASSERT((rU & 0x0001) == 0x0000);
3600 #endif
3601
3602     return returnValue;
3603 }
3604
3605 template<class ObjectT, UInt32 LevelBits> inline
3606 void ShaderCacheTreeV3<ObjectT, LevelBits>::eraseNode(TreeNode *pNode)
3607 {
3608     for(UInt32 i = 0; i < LevelSize; ++i)
3609     {
3610         if(pNode->_vChildren[i].asT2() != NULL)
3611         {
3612             eraseNode(pNode->_vChildren[i].asT2());
3613
3614             pNode->_vChildren[i].setAsT2(NULL);
3615         }
3616         else
3617         {
3618             pNode->_vChildren[i].setAsT1(NULL);
3619         }
3620     }
3621
3622     pNode->_pObject = NULL;
3623
3624     _qFreeElements.push_back(pNode);
3625 }
3626
3627 template<class ObjectT, UInt32 LevelBits>
3628 template <typename ElemDestFunc> inline
3629 void ShaderCacheTreeV3<ObjectT, LevelBits>::destroyNode(TreeNode     *pNode,
3630                                                         ElemDestFunc  destFunc)
3631 {
3632     if(pNode == NULL)
3633         return;
3634
3635     UInt32 uiChildStart = 0;
3636
3637     for(UInt32 i = uiChildStart; i < LevelSize; ++i)
3638     {
3639         if(pNode->_vChildren[i].asT2() != NULL)
3640         {
3641             destroyNode(pNode->_vChildren[i].asT2(), destFunc);
3642         }
3643         else if(pNode->_vChildren[i].asT1() != NULL)
3644         {
3645 #ifndef OSG_SHC_REF_CLEANUP
3646             ObjectT *pObj = pNode->_vChildren[i].asT1();
3647             (destFunc)(pObj);
3648 #endif
3649             pNode->_vChildren[i].setAsT1(NULL);
3650         }
3651     }
3652
3653     if(pNode->_pObject != NULL)
3654     {
3655 #ifndef OSG_SHC_REF_CLEANUP
3656         (destFunc)(pNode->_pObject);
3657 #endif
3658         pNode->_pObject = NULL;
3659     }
3660
3661     delete pNode;
3662 }
3663
3664 template<class ObjectT, UInt32 LevelBits>
3665 template <typename ElemDestFunc> inline
3666 void ShaderCacheTreeV3<ObjectT, LevelBits>::destroy(ElemDestFunc destFunc)
3667 {
3668     destroyNode(_pRoot, destFunc);
3669
3670     TreeNodeVecIt      leIt  = _vLevelEntries.begin();
3671     TreeNodeVecConstIt leEnd = _vLevelEntries.end  ();
3672
3673     for(; leIt != leEnd; ++leIt)
3674     {
3675         *leIt = NULL;
3676     }
3677
3678     _vLevelEntries.clear();
3679
3680     _pRoot = NULL;
3681 }
3682
3683 OSG_END_NAMESPACE