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         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     _val()
 985 {
 986     _val._pObj1 = NULL;
 987 }
 988
 989 template<typename Object1T, typename RefCountPol1,
 990          typename Object2T, typename RefCountPol2> inline
 991 VariantPtr<Object1T, RefCountPol1,
 992            Object2T, RefCountPol2>::~VariantPtr(void)
 993 {
 994     if(_val._uiIntVal & UIMaskChoice)  //isObj1
 995     {
 996         _val._uiIntVal &= UIMaskPtr;
 997
 998         RefCountPol1::subRef(_val._pObj1);
 999     }
1000 }
1001
1002 template<typename Object1T, typename RefCountPol1,
1003          typename Object2T, typename RefCountPol2> inline
1004 Object1T *VariantPtr<Object1T, RefCountPol1,
1005                      Object2T, RefCountPol2>::asT1(void) const
1006 {
1007
1008     if(_val._uiIntVal & UIMaskChoice) //isObj1
1009     {
1010         MemberU returnValue = { _val._uiIntVal & UIMaskPtr };
1011
1012         return returnValue._pObj1;
1013     }
1014
1015     return NULL;
1016 }
1017
1018 template<typename Object1T, typename RefCountPol1,
1019          typename Object2T, typename RefCountPol2> inline
1020 Object2T *VariantPtr<Object1T, RefCountPol1,
1021                      Object2T, RefCountPol2>::asT2(void) const
1022 {
1023
1024     if(!(_val._uiIntVal & UIMaskChoice)) //!isObj1
1025         return _val._pObj2;
1026
1027     return NULL;
1028 }
1029
1030 template<typename Object1T, typename RefCountPol1,
1031          typename Object2T, typename RefCountPol2> inline
1032 void VariantPtr<Object1T, RefCountPol1,
1033                 Object2T, RefCountPol2>::setAsT1(Object1T * const rhs)
1034 {
1035     if(_val._uiIntVal & UIMaskChoice) //isObj1
1036     {
1037         _val._uiIntVal &= UIMaskPtr;
1038
1039         RefCountPol1::setRefd(_val._pObj1, rhs);
1040     }
1041     else
1042     {
1043         RefCountPol1::addRef(rhs);
1044
1045         _val._pObj1 = rhs;
1046     }
1047
1048     //isObj1
1049     _val._uiIntVal |= UIMaskChoice;
1050
1051 }
1052
1053 template<typename Object1T, typename RefCountPol1,
1054          typename Object2T, typename RefCountPol2> inline
1055 void VariantPtr<Object1T, RefCountPol1,
1056                 Object2T, RefCountPol2>::setAsT2(Object2T * const rhs)
1057 {
1058     if(_val._uiIntVal & UIMaskChoice) //isObj1
1059     {
1060         _val._uiIntVal &= UIMaskPtr;
1061
1062         RefCountPol1::subRef(_val._pObj1);
1063     }
1064
1065     _val._pObj2 = rhs;
1066 }
1067
1068
1069 template<typename Object1T, typename RefCountPol1,
1070          typename Object2T, typename RefCountPol2> inline
1071 const VariantPtr<Object1T, RefCountPol1,
1072                  Object2T, RefCountPol2> &
1073     VariantPtr<Object1T, RefCountPol1,
1074                Object2T, RefCountPol2>::operator =(Object1T * const rhs)
1075 {
1076     setAsT1(rhs);
1077
1078     return *this;
1079 }
1080
1081 template<typename Object1T, typename RefCountPol1,
1082          typename Object2T, typename RefCountPol2> inline
1083 const VariantPtr<Object1T, RefCountPol1,
1084                  Object2T, RefCountPol2> &
1085     VariantPtr<Object1T, RefCountPol1,
1086                Object2T, RefCountPol2>::operator =(Object2T * const rhs)
1087 {
1088     setAsT2(rhs);
1089
1090     return *this;
1091 }
1092
1093
1094 template<typename Object1T, typename RefCountPol1,
1095          typename Object2T, typename RefCountPol2> inline
1096 Object2T *VariantPtr<Object1T, RefCountPol1,
1097                      Object2T, RefCountPol2>::operator ->(void) const
1098 {
1099     return this->asT2();
1100 }
1101
1102
1103
1104
1105 /*---------------------------------------------------------------------------*/
1106 /*---------------------------------------------------------------------------*/
1107
1108 #if defined(WIN32) || defined(__APPLE__) || \
1109     defined(__GXX_EXPERIMENTAL_CXX0X__)
1110 template<class ObjectT, UInt32 LevelBits>
1111 const Real32 ShaderCacheTreeV1<ObjectT, LevelBits>::LevelFactor =
1112                                                             1.f / (LevelBits);
1113 #endif
1114
1115 template<class ObjectT, UInt32 LevelBits> inline
1116 ShaderCacheTreeV1<ObjectT, LevelBits>::TreeNode::TreeNode(void) :
1117 #ifdef OSG_DEBUG
1118     _uiNodeId(0   ),
1119 #endif
1120     _pObject (NULL),
1121     _pPrev   (NULL),
1122     _pNext   (NULL)
1123 {
1124 }
1125
1126 template<class ObjectT, UInt32 LevelBits> inline
1127 ShaderCacheTreeV1<ObjectT, LevelBits>::TreeNode::~TreeNode(void)
1128 {
1129     _pObject = NULL;
1130     _pPrev   = NULL;
1131     _pNext   = NULL;
1132
1133     for(UInt32 i = 0; i < LevelSize; ++i)
1134     {
1135         _vChildren[i].setAsT1(NULL);
1136     }
1137 }
1138
1139 template<class ObjectT, UInt32 LevelBits> inline
1140 void ShaderCacheTreeV1<ObjectT, LevelBits>::TreeNode::clear(void)
1141 {
1142     _pObject = NULL;
1143     _pPrev   = NULL;
1144     _pNext   = NULL;
1145
1146     for(UInt32 i = 0; i < LevelSize; ++i)
1147     {
1148         _vChildren[i].setAsT1(NULL);
1149     }
1150 }
1151
1152
1153
1154 template<class ObjectT, UInt32 LevelBits> inline
1155 ObjectT *ShaderCacheTreeV1<ObjectT, LevelBits>::find(const IdStore &vIds)
1156 {
1157     if(vIds.size() < 1)
1158         return NULL;
1159
1160     ObjectT *returnValue = NULL;
1161
1162     IdType uiStartId     = vIds[0] - 1;
1163     IdType uiStartLevel  = IdType(uiStartId * LevelFactor);
1164
1165     UInt32 uiCurrId      = 0;
1166     UInt32 uiLastId      = vIds.size();
1167
1168
1169     if(uiStartLevel >= _vLevelEntries.size())
1170     {
1171         uiStartLevel = _vLevelEntries.size() - 1;
1172     }
1173
1174
1175     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
1176     UInt32    uiCurrBits = 0x0000;
1177     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
1178
1179     if(pCurrNode == NULL)
1180         return nullptr;
1181
1182     for(; uiCurrId < uiLastId; ++uiCurrId)
1183     {
1184         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
1185
1186         if(uiCurrIdx <= LevelBits)
1187         {
1188             uiCurrBits |= IdxToBits[uiCurrIdx];
1189
1190             continue;
1191         }
1192         else
1193         {
1194             pCurrNode = pCurrNode->_vChildren[uiCurrBits].asT2();
1195
1196             if(pCurrNode == NULL)
1197             {
1198                 break;
1199             }
1200
1201             uiCurrBits  = 0x0000;
1202
1203             uiLevelSub += LevelBits;
1204             uiCurrIdx  -= LevelBits;
1205
1206             while(uiCurrIdx > LevelBits)
1207             {
1208                 pCurrNode = pCurrNode->_vChildren[0].asT2();
1209
1210                 if(pCurrNode == NULL)
1211                 {
1212                     break;
1213                 }
1214                 uiLevelSub += LevelBits;
1215                 uiCurrIdx  -= LevelBits;
1216             }
1217
1218             if(pCurrNode == NULL)
1219             {
1220                 break;
1221             }
1222
1223             uiCurrBits |= IdxToBits[uiCurrIdx];
1224         }
1225     }
1226
1227     if(pCurrNode != NULL)
1228     {
1229         TreeNode *pNext = pCurrNode->_vChildren[uiCurrBits].asT2();
1230
1231         if(pNext != NULL)
1232         {
1233             returnValue = pNext->_pObject;
1234         }
1235         else
1236         {
1237             returnValue = pCurrNode->_vChildren[uiCurrBits].asT1();
1238         }
1239     }
1240
1241     return returnValue;
1242 }
1243
1244
1245 template<class ObjectT, UInt32 LevelBits> inline
1246 bool ShaderCacheTreeV1<ObjectT, LevelBits>::add(const IdStore &vIds,
1247                                                       ObjectT *pObject)
1248 {
1249     bool returnValue = false;
1250
1251     if(vIds.size() < 1)
1252         return returnValue;
1253
1254     IdType uiStartId    = vIds[0] - 1;
1255
1256     IdType uiStartLevel = IdType(uiStartId * LevelFactor);
1257
1258     UInt32 uiCurrId     = 0;
1259     UInt32 uiLastId     = vIds.size();
1260
1261
1262     if(uiStartLevel >= _vLevelEntries.size())
1263     {
1264         uiStartLevel = _vLevelEntries.size() - 1;
1265     }
1266
1267     UInt32 uiLevelSub   = (uiStartLevel * LevelBits);
1268
1269     TreeNode *pCurrNode = _vLevelEntries[uiStartLevel];
1270     TreeNode *pNextNode = NULL;
1271
1272     UInt32 uiCurrBits = 0x0000;
1273
1274     for(; uiCurrId < uiLastId; ++uiCurrId)
1275     {
1276         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
1277
1278         if(uiCurrIdx <= LevelBits)
1279         {
1280             uiCurrBits |= IdxToBits[uiCurrIdx];
1281
1282             continue;
1283         }
1284         else
1285         {
1286             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
1287
1288             if(pNextNode == NULL)
1289             {
1290                 pNextNode = allocateNode();
1291
1292                 if(pCurrNode->_vChildren[uiCurrBits].asT1() != NULL)
1293                 {
1294                     pNextNode->_pObject =
1295                         pCurrNode->_vChildren[uiCurrBits].asT1();
1296                 }
1297
1298                 pCurrNode->_vChildren[uiCurrBits] = pNextNode;
1299
1300                 if(uiStartLevel == _vLevelEntries.size() - 1)
1301                 {
1302                     if(_vLevelEntries.back()->_vChildren[0].asT2() == NULL)
1303                     {
1304                         TreeNode *pTmpNode = allocateNode();
1305
1306                         _vLevelEntries.back()->_vChildren[0] = pTmpNode;
1307
1308                         _vLevelEntries.push_back(pTmpNode);
1309
1310                         pTmpNode->_pNext  = pNextNode;
1311                         pNextNode->_pPrev = pTmpNode;
1312                     }
1313                     else
1314                     {
1315                         _vLevelEntries.push_back(pNextNode);
1316                     }
1317                 }
1318                 else
1319                 {
1320                     pNextNode->_pNext =
1321                         _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext;
1322
1323                     if(pNextNode->_pNext != NULL)
1324                     {
1325                         pNextNode->_pNext->_pPrev = pNextNode;
1326                     }
1327
1328                     _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext =
1329                         pNextNode;
1330
1331                     pNextNode->_pPrev =
1332                         _vLevelEntries[uiStartLevel]->_vChildren[0].asT2();
1333                 }
1334             }
1335
1336             ++uiStartLevel;
1337
1338             uiCurrBits  = 0x0000;
1339
1340             pCurrNode   = pNextNode;
1341
1342             uiLevelSub += LevelBits;
1343             uiCurrIdx  -= LevelBits;
1344
1345             while(uiCurrIdx > LevelBits)
1346             {
1347                 if(pCurrNode->_vChildren[0].asT2() == NULL)
1348                 {
1349                     pNextNode = allocateNode();
1350
1351                     pCurrNode->_vChildren[0] = pNextNode;
1352
1353                     if(uiStartLevel == _vLevelEntries.size() - 1)
1354                     {
1355                         if(_vLevelEntries.back()->_vChildren[0].asT2() == NULL)
1356                         {
1357                             TreeNode *pTmpNode = allocateNode();
1358
1359                             _vLevelEntries.back()->_vChildren[0] = pTmpNode;
1360
1361                             _vLevelEntries.push_back(pTmpNode);
1362
1363                             pTmpNode->_pNext  = pNextNode;
1364                             pNextNode->_pPrev = pTmpNode;
1365                         }
1366                         else
1367                         {
1368                             _vLevelEntries.push_back(pNextNode);
1369                         }
1370                     }
1371                     else
1372                     {
1373                         pNextNode->_pNext =
1374                             _vLevelEntries[uiStartLevel]->
1375                                 _vChildren[0]->_pNext;
1376
1377                         if(pNextNode->_pNext != NULL)
1378                         {
1379                             pNextNode->_pNext->_pPrev = pNextNode;
1380                         }
1381
1382                         _vLevelEntries[uiStartLevel]->_vChildren[0]->_pNext=
1383                             pNextNode;
1384
1385                         pNextNode->_pPrev =
1386                             _vLevelEntries[uiStartLevel]->_vChildren[0].asT2();
1387                     }
1388                 }
1389
1390                 pCurrNode = pCurrNode->_vChildren[0].asT2();
1391
1392                 uiLevelSub += LevelBits;
1393                 uiCurrIdx  -= LevelBits;
1394                 ++uiStartLevel;
1395             }
1396
1397
1398
1399             uiCurrBits |= IdxToBits[uiCurrIdx];
1400        }
1401     }
1402
1403     if(pCurrNode != NULL)
1404     {
1405         pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
1406
1407         if(pNextNode != NULL)
1408         {
1409             if(pNextNode->_pObject == NULL)
1410             {
1411                 pNextNode->_pObject = pObject;
1412
1413                 returnValue = true;
1414             }
1415             else
1416             {
1417                 OSG_ASSERT(pNextNode->_pObject == pObject);
1418             }
1419         }
1420         else
1421         {
1422             pCurrNode->_vChildren[uiCurrBits] = pObject;
1423
1424             returnValue = true;
1425         }
1426     }
1427
1428     return returnValue;
1429 }
1430
1431 template<class ObjectT, UInt32 LevelBits> inline
1432 void ShaderCacheTreeV1<ObjectT, LevelBits>::sub(UInt32 uiIdx)
1433 {
1434     IdType uiStartLevel  = IdType((uiIdx - 1) * LevelFactor);
1435
1436     if(uiStartLevel >= _vLevelEntries.size())
1437     {
1438         return;
1439     }
1440
1441     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
1442     UInt32    uiCurrIdx  = uiIdx - uiLevelSub;
1443     UInt32    uiCurrBits = IdxToBits[uiCurrIdx];
1444
1445     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
1446
1447     for(; pCurrNode != NULL; pCurrNode = pCurrNode->_pNext)
1448     {
1449         for(UInt32 i = 0; i < LevelSize; ++i)
1450         {
1451             TreeNode *pChild = pCurrNode->_vChildren[i].asT2();
1452
1453             if(0x0000 != (i & uiCurrBits) && pChild != NULL)
1454             {
1455                 if(pChild->_pNext == NULL)
1456                 {
1457                     pChild->_pPrev->_pNext = NULL;
1458                 }
1459                 else
1460                 {
1461                     pChild->_pPrev->_pNext = pChild->_pNext;
1462                     pChild->_pNext->_pPrev = pChild->_pPrev;
1463                 }
1464
1465                 pChild->_pPrev = NULL;
1466                 pChild->_pNext = NULL;
1467
1468                 eraseNode(pCurrNode->_vChildren[i].asT2());
1469                 pCurrNode->_vChildren[i].setAsT2(NULL);
1470             }
1471             else if(pCurrNode->_vChildren[i].asT1() != NULL)
1472             {
1473                 pCurrNode->_vChildren[i].setAsT1(NULL);
1474             }
1475         }
1476     }
1477 }
1478
1479 template<class ObjectT, UInt32 LevelBits> inline
1480 void ShaderCacheTreeV1<ObjectT, LevelBits>::dumpDot(const Char8 *szFilename)
1481 {
1482     FILE *pOut = fopen(szFilename, "w");
1483
1484     if(pOut != NULL)
1485     {
1486         fprintf(pOut, "digraph structs\n");
1487         fprintf(pOut, "{\n");
1488         fprintf(pOut, "rankdir = LR;\n");
1489         fprintf(pOut, "splines=false\n");
1490
1491         fprintf(pOut, "node [shape=record];\n");
1492
1493         fprintf(pOut, "struct%d\n", 0);
1494         fprintf(pOut, "[\n");
1495         fprintf(pOut, "    label=\"");
1496
1497         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
1498         {
1499             if(_vLevelEntries[i] != NULL)
1500             {
1501                 fprintf(pOut, "<l%d> %d", i, i);
1502             }
1503             else
1504             {
1505                 fprintf(pOut, "<l%d> NIL", i);
1506             }
1507
1508             if(i == _vLevelEntries.size() - 1)
1509             {
1510                 fprintf(pOut, "\"\n");
1511             }
1512             else
1513             {
1514                 fprintf(pOut, "|");
1515             }
1516         }
1517
1518         fprintf(pOut, "]\n");
1519
1520         fprintf(pOut, "node [width = 1.5];\n");
1521
1522         std::vector<std::vector<TreeNode *> > vLevelStore;
1523
1524         dumpDotNode(_pRoot, pOut, vLevelStore, 0);
1525
1526 #ifdef OSG_DEBUG
1527         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
1528         {
1529             if(_vLevelEntries[i] != NULL)
1530             {
1531                 fprintf(pOut,
1532                         "struct%d:l%d -> struct%d:prev [color=\"green\"];\n",
1533                         0, i,
1534                         _vLevelEntries[i]->_uiNodeId);
1535             }
1536         }
1537 #if 0
1538         for(UInt32 i = 0; i < vLevelStore.size(); ++i)
1539         {
1540             fprintf(pOut, "{ rank=same;");
1541
1542             for(UInt32 j = 0; j < vLevelStore[i].size(); ++j)
1543             {
1544                 TreeNode *pChild = vLevelStore[i][j];
1545
1546                 if(pChild != NULL)
1547                 {
1548                     fprintf(pOut, "\"struct%d\";",
1549                             pChild->_uiNodeId);
1550                 }
1551             }
1552
1553             fprintf(pOut, "}\n");
1554         }
1555 #endif
1556 #endif
1557
1558         fprintf(pOut, "}\n");
1559         fclose(pOut);
1560     }
1561 }
1562
1563 template<class ObjectT, UInt32 LevelBits> inline
1564 void ShaderCacheTreeV1<ObjectT, LevelBits>::dumpDotNode(
1565     TreeNode                              *pNode,
1566     FILE                                  *pOut ,
1567     std::vector<std::vector<TreeNode *> > &vLevelStore,
1568     UInt32                                 uiLevel    )
1569 {
1570 #ifdef OSG_DEBUG
1571     if(pNode == NULL)
1572         return;
1573
1574     if(uiLevel == vLevelStore.size())
1575     {
1576         vLevelStore.push_back(std::vector<TreeNode *>());
1577     }
1578
1579     fprintf(pOut, "struct%d\n", pNode->_uiNodeId);
1580     fprintf(pOut, "[\n");
1581     fprintf(pOut, "    label=\"{");
1582
1583     if(pNode->_pPrev != NULL)
1584     {
1585         fprintf(pOut, "<prev> P|");
1586     }
1587     else
1588     {
1589         fprintf(pOut, "<prev> P:NIL|");
1590     }
1591
1592     for(UInt32 i = 0; i < LevelSize; ++i)
1593     {
1594         if(pNode->_vChildren[i].asT1() != NULL)
1595         {
1596             fprintf(pOut, "<l%d> O:%d|", i, i);
1597         }
1598         else if(pNode->_vChildren[i].asT2() != NULL)
1599         {
1600             fprintf(pOut, "<l%d> C:%d|", i, i);
1601         }
1602         else
1603         {
1604             fprintf(pOut, "<l%d> NIL|", i);
1605         }
1606     }
1607
1608     if(pNode->_pObject != NULL)
1609     {
1610         fprintf(pOut, "<val> VAL:Obj|");
1611     }
1612     else
1613     {
1614         fprintf(pOut, "<val> VAL:NIL|");
1615     }
1616
1617     if(pNode->_pNext != NULL)
1618     {
1619         fprintf(pOut, "<next> N}\"\n");
1620     }
1621     else
1622     {
1623         fprintf(pOut, "<next> N:NIL}\"\n");
1624     }
1625
1626     fprintf(pOut, "]\n");
1627
1628     for(UInt32 i = 0; i < LevelSize; ++i)
1629     {
1630         TreeNode *pChild = pNode->_vChildren[i].asT2();
1631
1632         if(pChild != NULL)
1633         {
1634             dumpDotNode(pChild, pOut, vLevelStore, uiLevel + 1);
1635
1636             fprintf(pOut,
1637                     "struct%d:l%d -> struct%d:l%d [constraint=\"false\"];\n",
1638                     pNode ->_uiNodeId, i,
1639                     pChild->_uiNodeId, i);
1640         }
1641     }
1642
1643     if(pNode->_pNext != NULL)
1644     {
1645         fprintf(pOut, "struct%d:next -> struct%d:prev;\n",
1646                 pNode ->_uiNodeId,
1647                 pNode->_pNext->_uiNodeId);
1648     }
1649     if(pNode->_pPrev != NULL)
1650     {
1651         fprintf(pOut, "struct%d:prev -> struct%d:next;\n",
1652                 pNode ->_uiNodeId,
1653                 pNode->_pPrev->_uiNodeId);
1654     }
1655
1656      vLevelStore[uiLevel].push_back(pNode);
1657 #endif
1658 }
1659
1660 template<class ObjectT, UInt32 LevelBits> inline
1661 ShaderCacheTreeV1<ObjectT, LevelBits>::ShaderCacheTreeV1(void) :
1662 #ifdef OSG_DEBUG
1663     _uiNodeCount  (0   ),
1664 #endif
1665     _pRoot        (NULL),
1666     _vLevelEntries(    ),
1667     _qFreeElements(    )
1668 {
1669     _pRoot = allocateNode();
1670
1671     _vLevelEntries.push_back(_pRoot);
1672 }
1673
1674 template<class ObjectT, UInt32 LevelBits> inline
1675 ShaderCacheTreeV1<ObjectT, LevelBits>::~ShaderCacheTreeV1(void)
1676 {
1677     typename std::deque <TreeNode *>::const_iterator qIt  =
1678         _qFreeElements.begin();
1679
1680     typename std::deque <TreeNode *>::const_iterator qEnd =
1681         _qFreeElements.end();
1682
1683     for(; qIt != qEnd; ++qIt)
1684     {
1685         delete (*qIt);
1686     }
1687 }
1688
1689 template<class ObjectT, UInt32 LevelBits> inline
1690 typename ShaderCacheTreeV1<ObjectT, LevelBits>::TreeNode *
1691     ShaderCacheTreeV1<ObjectT, LevelBits>::allocateNode(void)
1692 {
1693     TreeNode *returnValue = NULL;
1694
1695     if(_qFreeElements.empty() == false)
1696     {
1697         returnValue = _qFreeElements.back();
1698
1699         _qFreeElements.pop_back();
1700
1701         returnValue->clear();
1702     }
1703     else
1704     {
1705         returnValue = new TreeNode();
1706
1707 #ifdef OSG_DEBUG
1708         returnValue->_uiNodeId = ++_uiNodeCount;
1709 #endif
1710     }
1711
1712 #ifdef OSG_DEBUG
1713     UIntPointer rU = reinterpret_cast<UIntPointer>(returnValue);
1714
1715     OSG_ASSERT((rU & 0x0001) == 0x0000);
1716 #endif
1717
1718     return returnValue;
1719 }
1720
1721 template<class ObjectT, UInt32 LevelBits> inline
1722 void ShaderCacheTreeV1<ObjectT, LevelBits>::eraseNode(TreeNode *pNode)
1723 {
1724     for(UInt32 i = 0; i < LevelSize; ++i)
1725     {
1726         if(pNode->_vChildren[i].asT2() != NULL)
1727         {
1728             eraseNode(pNode->_vChildren[i].asT2());
1729         }
1730         else
1731         {
1732             pNode->_vChildren[i].setAsT1(NULL);
1733         }
1734     }
1735
1736     pNode->_pObject = NULL;
1737
1738     _qFreeElements.push_back(pNode);
1739 }
1740
1741 template<class ObjectT, UInt32 LevelBits>
1742 template <typename ElemDestFunc> inline
1743 void ShaderCacheTreeV1<ObjectT, LevelBits>::destroyNode(TreeNode     *pNode,
1744                                                         ElemDestFunc  destFunc)
1745 {
1746     if(pNode == NULL)
1747         return;
1748
1749     UInt32 uiChildStart = 0;
1750
1751     if(pNode->_pPrev == NULL)
1752         uiChildStart = 1;
1753
1754     for(UInt32 i = uiChildStart; i < LevelSize; ++i)
1755     {
1756         if(pNode->_vChildren[i].asT2() != NULL)
1757         {
1758             destroyNode(pNode->_vChildren[i].asT2(), destFunc);
1759         }
1760         else if(pNode->_vChildren[i].asT1() != NULL)
1761         {
1762 #ifndef OSG_SHC_REF_CLEANUP
1763             ObjectT *pObj = pNode->_vChildren[i].asT1();
1764             (destFunc)(pObj);
1765 #endif
1766             pNode->_vChildren[i].setAsT1(NULL);
1767         }
1768     }
1769
1770     if(pNode->_pObject != NULL)
1771     {
1772 #ifndef OSG_SHC_REF_CLEANUP
1773         (destFunc)(pNode->_pObject);
1774 #endif
1775         pNode->_pObject = NULL;
1776     }
1777
1778     delete pNode;
1779 }
1780
1781 template<class ObjectT, UInt32 LevelBits>
1782 template <typename ElemDestFunc> inline
1783 void ShaderCacheTreeV1<ObjectT, LevelBits>::destroy(ElemDestFunc destFunc)
1784 {
1785     destroyNode(_pRoot, destFunc);
1786
1787     _vLevelEntries[0] = NULL;
1788
1789     _pRoot = NULL;
1790 }
1791
1792
1793
1794
1795
1796
1797 /*---------------------------------------------------------------------------*/
1798 /*---------------------------------------------------------------------------*/
1799
1800 #if defined(WIN32) || defined(__APPLE__) || \
1801     defined(__GXX_EXPERIMENTAL_CXX0X__)
1802 template<class ObjectT, UInt32 LevelBits>
1803 const Real32 ShaderCacheTreeV2<ObjectT, LevelBits>::LevelFactor =
1804                                                             1.f / (LevelBits);
1805 #endif
1806
1807 template<class ObjectT, UInt32 LevelBits> inline
1808 ShaderCacheTreeV2<ObjectT, LevelBits>::TreeNode::TreeNode(void) :
1809 #ifdef OSG_DEBUG
1810     _uiNodeId(0   ),
1811 #endif
1812     _pObject (NULL),
1813     _pPrev   (NULL),
1814     _pNext   (NULL)
1815 {
1816     memset(&(_vJumps[0]), 0, LevelSize * sizeof(UInt16));
1817 }
1818
1819 template<class ObjectT, UInt32 LevelBits> inline
1820 ShaderCacheTreeV2<ObjectT, LevelBits>::TreeNode::~TreeNode(void)
1821 {
1822     _pObject = NULL;
1823     _pPrev   = NULL;
1824     _pNext   = NULL;
1825
1826     for(UInt32 i = 0; i < LevelSize; ++i)
1827     {
1828         _vChildren[i].setAsT1(NULL);
1829     }
1830 }
1831
1832 template<class ObjectT, UInt32 LevelBits> inline
1833 void ShaderCacheTreeV2<ObjectT, LevelBits>::TreeNode::clear(void)
1834 {
1835     _pObject = NULL;
1836     _pPrev   = NULL;
1837     _pNext   = NULL;
1838
1839     for(UInt32 i = 0; i < LevelSize; ++i)
1840     {
1841         _vChildren[i].setAsT1(NULL);
1842     }
1843
1844     memset(&(_vJumps[0]), 0, LevelSize * sizeof(UInt16));
1845 }
1846
1847
1848
1849 template<class ObjectT, UInt32 LevelBits> inline
1850 ObjectT *ShaderCacheTreeV2<ObjectT, LevelBits>::find(const IdStore &vIds)
1851 {
1852     if(vIds.size() < 1)
1853         return NULL;
1854
1855     ObjectT *returnValue = NULL;
1856
1857     IdType uiStartId     = vIds[0] - 1;
1858     IdType uiStartLevel  = IdType(uiStartId * LevelFactor);
1859
1860     UInt32 uiCurrId      = 0;
1861     UInt32 uiLastId      = vIds.size();
1862
1863
1864     if(uiStartLevel >= _vLevelEntries.size())
1865     {
1866         uiStartLevel = _vLevelEntries.size() - 1;
1867     }
1868
1869
1870     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
1871     UInt32    uiCurrBits = 0x0000;
1872     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
1873     TreeNode *pNextNode  = NULL;
1874
1875     if(pCurrNode == NULL)
1876         return NULL;
1877
1878     for(; uiCurrId < uiLastId; ++uiCurrId)
1879     {
1880         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
1881         UInt16 uiJumpDist = 1;
1882
1883         if(uiCurrIdx <= LevelBits)
1884         {
1885             uiCurrBits |= IdxToBits[uiCurrIdx];
1886
1887             continue;
1888         }
1889         else
1890         {
1891             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
1892
1893             if(pNextNode == NULL)
1894             {
1895                 pCurrNode = pNextNode;
1896                 break;
1897             }
1898
1899             uiJumpDist = UInt16((uiCurrIdx - 1) * LevelFactor);
1900             UInt32 uiTargetLevel = uiStartLevel + uiJumpDist;
1901
1902             if(uiJumpDist < pCurrNode->_vJumps[uiCurrBits])
1903             {
1904                 pCurrNode = NULL;
1905                 break;
1906             }
1907
1908             if(uiJumpDist > pCurrNode->_vJumps[uiCurrBits])
1909             {
1910                 uiLevelSub += LevelBits * pCurrNode->_vJumps[uiCurrBits];
1911                 uiCurrIdx  -= LevelBits * pCurrNode->_vJumps[uiCurrBits];
1912                 uiJumpDist -= pCurrNode->_vJumps[uiCurrBits];
1913
1914                 pCurrNode = pNextNode;
1915                 pNextNode = pCurrNode->_vChildren[0].asT2();
1916
1917                 uiCurrBits  = 0x0000;
1918
1919                 while(1)
1920                 {
1921                     if(uiCurrIdx <= LevelBits)
1922                     {
1923                         break;
1924                     }
1925
1926                     if(uiJumpDist == pCurrNode->_vJumps[0])
1927                     {
1928                         break;
1929                     }
1930
1931                     if(uiJumpDist < pCurrNode->_vJumps[0])
1932                     {
1933                         pNextNode = NULL;
1934                         break;
1935                     }
1936
1937                     if(pNextNode == NULL)
1938                     {
1939                         break;
1940                     }
1941
1942                     uiLevelSub +=
1943                         LevelBits * pCurrNode->_vJumps[0];
1944
1945                     uiCurrIdx  -=
1946                         LevelBits * pCurrNode->_vJumps[0];
1947
1948                     uiJumpDist -= pCurrNode->_vJumps[0];
1949
1950                     pCurrNode = pNextNode;
1951                     pNextNode = pCurrNode->_vChildren[0].asT2();
1952                 }
1953             }
1954
1955             pCurrNode = pNextNode;
1956
1957             if(pCurrNode == NULL)
1958             {
1959                 break;
1960             }
1961
1962             uiCurrBits  = 0x0000;
1963
1964             uiStartLevel = uiTargetLevel;
1965             uiLevelSub   = (uiStartLevel * LevelBits);
1966
1967             uiCurrIdx  -= uiJumpDist * LevelBits;
1968
1969
1970             uiCurrBits |= IdxToBits[uiCurrIdx];
1971         }
1972     }
1973
1974     if(pCurrNode != NULL)
1975     {
1976         TreeNode *pNext = pCurrNode->_vChildren[uiCurrBits].asT2();
1977
1978         if(pNext != NULL)
1979         {
1980             returnValue = pNext->_pObject;
1981         }
1982         else
1983         {
1984             returnValue = pCurrNode->_vChildren[uiCurrBits].asT1();
1985         }
1986     }
1987
1988     return returnValue;
1989 }
1990
1991
1992 template<class ObjectT, UInt32 LevelBits> inline
1993 bool ShaderCacheTreeV2<ObjectT, LevelBits>::add(const IdStore &vIds,
1994                                                       ObjectT *pObject)
1995 {
1996     bool returnValue = false;
1997
1998     if(vIds.size() < 1)
1999         return returnValue;
2000
2001     IdType uiStartId    = vIds[0] - 1;
2002
2003     IdType uiStartLevel = IdType(uiStartId * LevelFactor);
2004
2005     UInt32 uiCurrId     = 0;
2006     UInt32 uiLastId     = vIds.size();
2007
2008
2009     if(uiStartLevel >= _vLevelEntries.size())
2010     {
2011         uiStartLevel = _vLevelEntries.size() - 1;
2012     }
2013
2014
2015     TreeNode *pCurrNode = _vLevelEntries[uiStartLevel];
2016     TreeNode *pNextNode = NULL;
2017
2018     UInt32 uiCurrBits = 0x0000;
2019
2020     if(pCurrNode == NULL)
2021     {
2022         UInt32 uiLastValidLE = 0;
2023
2024         for(Int32 i = uiStartLevel; i >= 0; --i)
2025         {
2026             if(_vLevelEntries[i] != NULL)
2027             {
2028                 uiLastValidLE = i;
2029                 break;
2030             }
2031         }
2032
2033         uiStartLevel = uiLastValidLE;
2034         pCurrNode    = _vLevelEntries[uiStartLevel];
2035     }
2036
2037     UInt32 uiLevelSub   = (uiStartLevel * LevelBits);
2038
2039     for(; uiCurrId < uiLastId; ++uiCurrId)
2040     {
2041         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
2042         UInt16 uiJumpDist = 1;
2043
2044         if(uiCurrIdx <= LevelBits)
2045         {
2046             uiCurrBits |= IdxToBits[uiCurrIdx];
2047
2048             continue;
2049         }
2050         else
2051         {
2052             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
2053
2054             uiJumpDist           = UInt16((uiCurrIdx - 1) * LevelFactor);
2055             UInt32 uiTargetLevel = uiStartLevel + uiJumpDist;
2056
2057             if(pNextNode != NULL)
2058             {
2059                 if(uiJumpDist > pCurrNode->_vJumps[uiCurrBits])
2060                 {
2061                     uiLevelSub += LevelBits * pCurrNode->_vJumps[uiCurrBits];
2062                     uiCurrIdx  -= LevelBits * pCurrNode->_vJumps[uiCurrBits];
2063                     uiJumpDist -= pCurrNode->_vJumps[uiCurrBits];
2064
2065                     pCurrNode = pNextNode;
2066                     pNextNode = pCurrNode->_vChildren[0].asT2();
2067
2068                     uiCurrBits  = 0x0000;
2069
2070                     while(1)
2071                     {
2072                         if(uiCurrIdx <= LevelBits)
2073                         {
2074                             break;
2075                         }
2076
2077                         if(pNextNode == NULL)
2078                         {
2079                             break;
2080                         }
2081
2082                         if(uiJumpDist <= pCurrNode->_vJumps[0])
2083                         {
2084                             break;
2085                         }
2086
2087                         uiLevelSub +=
2088                             LevelBits * pCurrNode->_vJumps[0];
2089
2090                         uiCurrIdx  -=
2091                             LevelBits * pCurrNode->_vJumps[0];
2092
2093                         uiJumpDist -= pCurrNode->_vJumps[0];
2094
2095                         pCurrNode = pNextNode;
2096                         pNextNode = pCurrNode->_vChildren[0].asT2();
2097                     }
2098                 }
2099
2100                 if(uiJumpDist < pCurrNode->_vJumps[uiCurrBits])
2101                 {
2102                     pNextNode = allocateNode();
2103
2104                     pNextNode->_vJumps[0] =
2105                         pCurrNode->_vJumps   [uiCurrBits] - uiJumpDist;
2106
2107                     pNextNode->_vChildren[0] =
2108                         pCurrNode->_vChildren[uiCurrBits].asT2();
2109
2110                     pNextNode->_pObject =
2111                         pCurrNode->_vChildren[uiCurrBits].asT2()->_pObject;
2112
2113                     pCurrNode->_vChildren[uiCurrBits].asT2()->_pObject = NULL;
2114
2115                     pCurrNode->_vJumps   [uiCurrBits] = uiJumpDist;
2116                     pCurrNode->_vChildren[uiCurrBits] = pNextNode;
2117
2118                     if(_vLevelEntries[uiTargetLevel] == NULL)
2119                     {
2120                         UInt32 uiLastValidLE = 0;
2121
2122                         for(Int32 i = uiTargetLevel; i >= 0; --i)
2123                         {
2124                             if(_vLevelEntries[i] != NULL)
2125                             {
2126                                 uiLastValidLE = i;
2127                                 break;
2128                             }
2129                         }
2130
2131                         if(_vLevelEntries[uiLastValidLE] == pCurrNode &&
2132                             uiCurrBits                   == 0          )
2133                         {
2134                             _vLevelEntries[uiTargetLevel] = pNextNode;
2135                         }
2136                         else
2137                         {
2138                             TreeNode *pTmpNode = allocateNode();
2139
2140                             if(_vLevelEntries[
2141                                    uiLastValidLE]->_vChildren[0].asT2() != NULL)
2142                             {
2143                                 pTmpNode->_vChildren[0] =
2144                                     _vLevelEntries[
2145                                         uiLastValidLE]->_vChildren[0].asT2();
2146
2147                                 pTmpNode->_vJumps[0] =
2148                                     _vLevelEntries[
2149                                         uiLastValidLE]->_vJumps[0] -
2150                                     (uiTargetLevel - uiLastValidLE);
2151                             }
2152
2153                             _vLevelEntries[uiLastValidLE]->_vChildren[0] =
2154                                 pTmpNode;
2155                             _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
2156                                 uiTargetLevel - uiLastValidLE;
2157
2158                             _vLevelEntries[uiTargetLevel] = pTmpNode;
2159
2160                             pTmpNode ->_pNext = pNextNode;
2161                             pNextNode->_pPrev = pTmpNode;
2162                         }
2163                     }
2164                     else
2165                     {
2166                         pNextNode->_pNext =
2167                             _vLevelEntries[uiTargetLevel]->_pNext;
2168
2169                         if(pNextNode->_pNext != NULL)
2170                         {
2171                             pNextNode->_pNext->_pPrev = pNextNode;
2172                         }
2173
2174                         _vLevelEntries[uiTargetLevel]->_pNext = pNextNode;
2175
2176                         pNextNode->_pPrev = _vLevelEntries[uiTargetLevel];
2177                     }
2178                 }
2179             }
2180
2181             if(pNextNode == NULL)
2182             {
2183                 pNextNode = allocateNode();
2184
2185                 pCurrNode->_vJumps   [uiCurrBits] = uiJumpDist;
2186
2187                 if(pCurrNode->_vChildren[uiCurrBits].asT1() != NULL)
2188                 {
2189                     pNextNode->_pObject =
2190                         pCurrNode->_vChildren[uiCurrBits].asT1();
2191                 }
2192
2193                 pCurrNode->_vChildren[uiCurrBits] = pNextNode;
2194
2195                 if(uiTargetLevel >= _vLevelEntries.size())
2196                 {
2197                     _vLevelEntries.resize(uiTargetLevel + 1, NULL);
2198
2199                     UInt32 uiLastValidLE = 0;
2200
2201                     for(Int32 i = uiTargetLevel; i >= 0; --i)
2202                     {
2203                         if(_vLevelEntries[i] != NULL)
2204                         {
2205                             uiLastValidLE = i;
2206                             break;
2207                         }
2208                     }
2209
2210                     if(_vLevelEntries[uiLastValidLE] == pCurrNode &&
2211                         uiCurrBits                   == 0          )
2212                     {
2213                         _vLevelEntries[uiTargetLevel] = pNextNode;
2214                     }
2215                     else
2216                     {
2217                         TreeNode *pTmpNode = allocateNode();
2218
2219                         _vLevelEntries[uiLastValidLE]->_vChildren[0] = pTmpNode;
2220                         _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
2221                             uiTargetLevel - uiLastValidLE;
2222
2223                         _vLevelEntries[uiTargetLevel] = pTmpNode;
2224
2225                         pTmpNode ->_pNext = pNextNode;
2226                         pNextNode->_pPrev = pTmpNode;
2227                     }
2228                 }
2229                 else
2230                 {
2231                     if(_vLevelEntries[uiTargetLevel] == NULL)
2232                     {
2233                         UInt32 uiLastValidLE = 0;
2234
2235                         for(Int32 i = uiTargetLevel; i >= 0; --i)
2236                         {
2237                             if(_vLevelEntries[i] != NULL)
2238                             {
2239                                 uiLastValidLE = i;
2240                                 break;
2241                             }
2242                         }
2243
2244                         TreeNode *pTmpNode = allocateNode();
2245
2246                         if(_vLevelEntries[
2247                                uiLastValidLE]->_vChildren[0].asT2() != NULL)
2248                         {
2249                             pTmpNode->_vChildren[0] =
2250                                 _vLevelEntries[
2251                                     uiLastValidLE]->_vChildren[0].asT2();
2252
2253                             pTmpNode->_vJumps[0] =
2254                                 _vLevelEntries[uiLastValidLE]->_vJumps[0] -
2255                                 (uiTargetLevel - uiLastValidLE);
2256                         }
2257
2258                         _vLevelEntries[uiLastValidLE]->_vChildren[0] = pTmpNode;
2259                         _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
2260                             uiTargetLevel - uiLastValidLE;
2261
2262                         _vLevelEntries[uiTargetLevel] = pTmpNode;
2263
2264                         pTmpNode ->_pNext = pNextNode;
2265                         pNextNode->_pPrev = pTmpNode;
2266                     }
2267                     else
2268                     {
2269                         pNextNode->_pNext =
2270                             _vLevelEntries[uiTargetLevel]->_pNext;
2271
2272                         if(pNextNode->_pNext != NULL)
2273                         {
2274                             pNextNode->_pNext->_pPrev = pNextNode;
2275                         }
2276
2277                         _vLevelEntries[uiTargetLevel]->_pNext = pNextNode;
2278
2279                         pNextNode->_pPrev = _vLevelEntries[uiTargetLevel];
2280                     }
2281                 }
2282             }
2283
2284
2285             pCurrNode   = pNextNode;
2286
2287             uiCurrBits  = 0x0000;
2288
2289             uiStartLevel = uiTargetLevel;
2290             uiLevelSub   = (uiStartLevel * LevelBits);
2291
2292             uiCurrIdx  -= uiJumpDist * LevelBits;
2293
2294             uiCurrBits |= IdxToBits[uiCurrIdx];
2295         }
2296     }
2297
2298     if(pCurrNode != NULL)
2299     {
2300         pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
2301
2302         if(pNextNode != NULL)
2303         {
2304             if(pNextNode->_pObject == NULL)
2305             {
2306                 pNextNode->_pObject = pObject;
2307
2308                 returnValue = true;
2309             }
2310             else
2311             {
2312                 OSG_ASSERT(pNextNode->_pObject == pObject);
2313             }
2314         }
2315         else
2316         {
2317             pCurrNode->_vChildren[uiCurrBits] = pObject;
2318
2319             returnValue = true;
2320         }
2321     }
2322
2323     return returnValue;
2324 }
2325
2326 template<class ObjectT, UInt32 LevelBits> inline
2327 void ShaderCacheTreeV2<ObjectT, LevelBits>::sub(UInt32 uiIdx)
2328 {
2329     IdType uiStartLevel  = IdType((uiIdx - 1) * LevelFactor);
2330
2331     if(uiStartLevel >= _vLevelEntries.size())
2332     {
2333         return;
2334     }
2335
2336     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
2337     UInt32    uiCurrIdx  = uiIdx - uiLevelSub;
2338     UInt32    uiCurrBits = IdxToBits[uiCurrIdx];
2339
2340     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
2341
2342     for(; pCurrNode != NULL; pCurrNode = pCurrNode->_pNext)
2343     {
2344         for(UInt32 i = 0; i < LevelSize; ++i)
2345         {
2346             TreeNode *pChild = pCurrNode->_vChildren[i].asT2();
2347
2348             if(0x0000 != (i & uiCurrBits) && pChild != NULL)
2349             {
2350                 if(pChild->_pNext == NULL)
2351                 {
2352                     pChild->_pPrev->_pNext = NULL;
2353                 }
2354                 else
2355                 {
2356                     pChild->_pPrev->_pNext = pChild->_pNext;
2357                     pChild->_pNext->_pPrev = pChild->_pPrev;
2358                 }
2359
2360                 pChild->_pPrev = NULL;
2361                 pChild->_pNext = NULL;
2362
2363                 eraseNode(pCurrNode->_vChildren[i].asT2());
2364                 pCurrNode->_vJumps   [i] = 0;
2365                 pCurrNode->_vChildren[i].setAsT2(NULL);
2366             }
2367             else if(pCurrNode->_vChildren[i].asT1() != NULL)
2368             {
2369                 pCurrNode->_vChildren[i].setAsT1(NULL);
2370                 pCurrNode->_vJumps   [i] = 0;
2371             }
2372         }
2373     }
2374 }
2375
2376 #define OSG_DUMP_LEVELENTRIES
2377
2378 template<class ObjectT, UInt32 LevelBits> inline
2379 void ShaderCacheTreeV2<ObjectT, LevelBits>::dumpDot(const Char8 *szFilename)
2380 {
2381     FILE *pOut = fopen(szFilename, "w");
2382
2383     if(pOut != NULL)
2384     {
2385         fprintf(pOut, "digraph structs\n");
2386         fprintf(pOut, "{\n");
2387         fprintf(pOut, "rankdir = LR;\n");
2388         fprintf(pOut, "splines=false\n");
2389
2390         fprintf(pOut, "node [shape=record];\n");
2391
2392         fprintf(pOut, "struct%d\n", 0);
2393         fprintf(pOut, "[\n");
2394         fprintf(pOut, "    label=\"");
2395
2396         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
2397         {
2398             if(_vLevelEntries[i] != NULL)
2399             {
2400                 fprintf(pOut, "<l%d> %d", i, i);
2401             }
2402             else
2403             {
2404                 fprintf(pOut, "<l%d> NIL", i);
2405             }
2406
2407             if(i == _vLevelEntries.size() - 1)
2408             {
2409                 fprintf(pOut, "\"\n");
2410             }
2411             else
2412             {
2413                 fprintf(pOut, "|");
2414             }
2415         }
2416
2417         fprintf(pOut, "]\n");
2418
2419         fprintf(pOut, "node [width = 1.5];\n");
2420
2421         std::vector<std::vector<TreeNode *> > vLevelStore;
2422
2423         dumpDotNode(_pRoot, pOut, vLevelStore, 0);
2424
2425 #ifdef OSG_DEBUG
2426 #ifdef OSG_DUMP_LEVELENTRIES
2427         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
2428         {
2429             if(_vLevelEntries[i] != NULL)
2430             {
2431                 fprintf(pOut,
2432                         "struct%d:l%d -> struct%d:prev [color=\"green\"];\n",
2433                         0, i,
2434                         _vLevelEntries[i]->_uiNodeId);
2435             }
2436         }
2437 #endif
2438
2439 #if 0
2440         for(UInt32 i = 0; i < vLevelStore.size(); ++i)
2441         {
2442             fprintf(pOut, "{ rank=same;");
2443
2444             for(UInt32 j = 0; j < vLevelStore[i].size(); ++j)
2445             {
2446                 TreeNode *pChild = vLevelStore[i][j];
2447
2448                 if(pChild != NULL)
2449                 {
2450                     fprintf(pOut, "\"struct%d\";",
2451                             pChild->_uiNodeId);
2452                 }
2453             }
2454
2455             fprintf(pOut, "}\n");
2456         }
2457 #endif
2458 #endif
2459
2460         fprintf(pOut, "}\n");
2461         fclose(pOut);
2462     }
2463 }
2464
2465 template<class ObjectT, UInt32 LevelBits> inline
2466 void ShaderCacheTreeV2<ObjectT, LevelBits>::dumpDotNode(
2467     TreeNode                              *pNode,
2468     FILE                                  *pOut ,
2469     std::vector<std::vector<TreeNode *> > &vLevelStore,
2470     UInt32                                 uiLevel    )
2471 {
2472 #ifdef OSG_DEBUG
2473     if(pNode == NULL)
2474         return;
2475
2476     if(uiLevel == vLevelStore.size())
2477     {
2478         vLevelStore.push_back(std::vector<TreeNode *>());
2479     }
2480
2481     fprintf(pOut, "struct%d\n", pNode->_uiNodeId);
2482     fprintf(pOut, "[\n");
2483     fprintf(pOut, "    label=\"{");
2484
2485     if(pNode->_pPrev != NULL)
2486     {
2487         fprintf(pOut, "<prev> P|");
2488     }
2489     else
2490     {
2491         fprintf(pOut, "<prev> P:NIL|");
2492     }
2493
2494     for(UInt32 i = 0; i < LevelSize; ++i)
2495     {
2496         if(pNode->_vChildren[i].asT1() != NULL)
2497         {
2498             if(osgIsPower2(i) == true)
2499             {
2500                 fprintf(pOut, "<l%d> _O:%d|", i, i);
2501             }
2502             else
2503             {
2504                 fprintf(pOut, "<l%d> O:%d|", i, i);
2505             }
2506         }
2507         else if(pNode->_vChildren[i].asT2() != NULL)
2508         {
2509             if(osgIsPower2(i) == true)
2510             {
2511                 fprintf(pOut, "<l%d> _C:%d (%d)|", i, i, pNode->_vJumps[i]);
2512             }
2513             else
2514             {
2515                 fprintf(pOut, "<l%d> C:%d (%d)|", i, i, pNode->_vJumps[i]);
2516             }
2517         }
2518         else
2519         {
2520             if(osgIsPower2(i) == true)
2521             {
2522                 fprintf(pOut, "<l%d> _NIL|", i);
2523             }
2524             else
2525             {
2526                 fprintf(pOut, "<l%d> NIL|", i);
2527             }
2528         }
2529     }
2530
2531     if(pNode->_pObject != NULL)
2532     {
2533         fprintf(pOut, "<val> VAL:Obj|");
2534     }
2535     else
2536     {
2537         fprintf(pOut, "<val> VAL:NIL|");
2538     }
2539
2540     if(pNode->_pNext != NULL)
2541     {
2542         fprintf(pOut, "<next> N}\"\n");
2543     }
2544     else
2545     {
2546         fprintf(pOut, "<next> N:NIL}\"\n");
2547     }
2548
2549     fprintf(pOut, "]\n");
2550
2551     for(UInt32 i = 0; i < LevelSize; ++i)
2552     {
2553         TreeNode *pChild = pNode->_vChildren[i].asT2();
2554
2555         if(pChild != NULL)
2556         {
2557             dumpDotNode(pChild, pOut, vLevelStore, uiLevel + 1);
2558
2559             fprintf(pOut,
2560                     "struct%d:l%d -> struct%d:l%d [constraint=\"false\"];\n",
2561                     pNode ->_uiNodeId, i,
2562                     pChild->_uiNodeId, i);
2563         }
2564     }
2565
2566     if(pNode->_pNext != NULL)
2567     {
2568         fprintf(pOut, "struct%d:next -> struct%d:prev;\n",
2569                 pNode ->_uiNodeId,
2570                 pNode->_pNext->_uiNodeId);
2571     }
2572     if(pNode->_pPrev != NULL)
2573     {
2574         fprintf(pOut, "struct%d:prev -> struct%d:next;\n",
2575                 pNode ->_uiNodeId,
2576                 pNode->_pPrev->_uiNodeId);
2577     }
2578
2579      vLevelStore[uiLevel].push_back(pNode);
2580 #endif
2581 }
2582
2583 template<class ObjectT, UInt32 LevelBits> inline
2584 ShaderCacheTreeV2<ObjectT, LevelBits>::ShaderCacheTreeV2(void) :
2585 #ifdef OSG_DEBUG
2586     _uiNodeCount  (0   ),
2587 #endif
2588     _pRoot        (NULL),
2589     _vLevelEntries(    ),
2590     _qFreeElements(    )
2591 {
2592     _pRoot = allocateNode();
2593
2594     _vLevelEntries.push_back(_pRoot);
2595 }
2596
2597 template<class ObjectT, UInt32 LevelBits> inline
2598 ShaderCacheTreeV2<ObjectT, LevelBits>::~ShaderCacheTreeV2(void)
2599 {
2600     typename std::deque <TreeNode *>::iterator qIt  =
2601         _qFreeElements.begin();
2602
2603     typename std::deque <TreeNode *>::const_iterator qEnd =
2604         _qFreeElements.end();
2605
2606     for(; qIt != qEnd; ++qIt)
2607     {
2608         delete (*qIt);
2609
2610         *qIt = NULL;
2611     }
2612
2613     typename std::vector<TreeNode *>::iterator vIt  = _vLevelEntries.begin();
2614     typename std::vector<TreeNode *>::iterator vEnd = _vLevelEntries.end  ();
2615
2616     for(; vIt != vEnd; ++vIt)
2617     {
2618         delete (*vIt);
2619
2620         *vIt = NULL;
2621     }
2622 }
2623
2624 template<class ObjectT, UInt32 LevelBits> inline
2625 typename ShaderCacheTreeV2<ObjectT, LevelBits>::TreeNode *
2626     ShaderCacheTreeV2<ObjectT, LevelBits>::allocateNode(void)
2627 {
2628     TreeNode *returnValue = NULL;
2629
2630     if(_qFreeElements.empty() == false)
2631     {
2632         returnValue = _qFreeElements.back();
2633
2634         _qFreeElements.pop_back();
2635
2636         returnValue->clear();
2637     }
2638     else
2639     {
2640         returnValue = new TreeNode();
2641
2642 #ifdef OSG_DEBUG
2643         returnValue->_uiNodeId = ++_uiNodeCount;
2644 #endif
2645     }
2646
2647 #ifdef OSG_DEBUG
2648     UIntPointer rU = reinterpret_cast<UIntPointer>(returnValue);
2649
2650     OSG_ASSERT((rU & 0x0001) == 0x0000);
2651 #endif
2652
2653     return returnValue;
2654 }
2655
2656 template<class ObjectT, UInt32 LevelBits> inline
2657 void ShaderCacheTreeV2<ObjectT, LevelBits>::eraseNode(TreeNode *pNode)
2658 {
2659     for(UInt32 i = 0; i < LevelSize; ++i)
2660     {
2661         if(pNode->_vChildren[i].asT2() != NULL)
2662         {
2663             eraseNode(pNode->_vChildren[i].asT2());
2664
2665             pNode->_vChildren[i].setAsT2(NULL);
2666         }
2667         else
2668         {
2669             pNode->_vChildren[i].setAsT1(NULL);
2670         }
2671     }
2672
2673     pNode->_pObject = NULL;
2674
2675     _qFreeElements.push_back(pNode);
2676 }
2677
2678 template<class ObjectT, UInt32 LevelBits>
2679 template <typename ElemDestFunc> inline
2680 void ShaderCacheTreeV2<ObjectT, LevelBits>::destroyNode(TreeNode     *pNode,
2681                                                         ElemDestFunc  destFunc)
2682 {
2683     if(pNode == NULL)
2684         return;
2685
2686     for(UInt32 i = 0; i < LevelSize; ++i)
2687     {
2688         if(pNode->_vChildren[i].asT2() != NULL)
2689         {
2690             destroyNode(pNode->_vChildren[i].asT2(), destFunc);
2691         }
2692         else if(pNode->_vChildren[i].asT1() != NULL)
2693         {
2694 #ifndef OSG_SHC_REF_CLEANUP
2695             ObjectT *pObj = pNode->_vChildren[i].asT1();
2696             (destFunc)(pObj);
2697 #endif
2698             pNode->_vChildren[i].setAsT1(NULL);
2699         }
2700     }
2701
2702     if(pNode->_pObject != NULL)
2703     {
2704 #ifndef OSG_SHC_REF_CLEANUP
2705         (destFunc)(pNode->_pObject);
2706 #endif
2707         pNode->_pObject = NULL;
2708     }
2709
2710     delete pNode;
2711 }
2712
2713 template<class ObjectT, UInt32 LevelBits>
2714 template <typename ElemDestFunc> inline
2715 void ShaderCacheTreeV2<ObjectT, LevelBits>::destroy(ElemDestFunc destFunc)
2716 {
2717     destroyNode(_pRoot, destFunc);
2718
2719     _vLevelEntries[0] = NULL;
2720
2721     _pRoot = NULL;
2722 }
2723
2724
2725
2726
2727
2728
2729 /*---------------------------------------------------------------------------*/
2730 /*---------------------------------------------------------------------------*/
2731
2732 #if defined(WIN32) || defined(__APPLE__) || \
2733     defined(__GXX_EXPERIMENTAL_CXX0X__)
2734 template<class ObjectT, UInt32 LevelBits>
2735 const Real32 ShaderCacheTreeV3<ObjectT, LevelBits>::LevelFactor =
2736                                                             1.f / (LevelBits);
2737 #endif
2738
2739 template<class ObjectT, UInt32 LevelBits> inline
2740 ShaderCacheTreeV3<ObjectT, LevelBits>::TreeNode::TreeNode(void) :
2741 #ifdef OSG_DEBUG
2742     _uiNodeId(0   ),
2743 #endif
2744     _pObject (NULL),
2745     _pPrev   (NULL),
2746     _pNext   (NULL)
2747 {
2748     memset(&(_vJumps[0]), 0, LevelSize * sizeof(UInt16));
2749 }
2750
2751 template<class ObjectT, UInt32 LevelBits> inline
2752 ShaderCacheTreeV3<ObjectT, LevelBits>::TreeNode::~TreeNode(void)
2753 {
2754     _pObject = NULL;
2755     _pPrev   = NULL;
2756     _pNext   = NULL;
2757
2758     for(UInt32 i = 0; i < LevelSize; ++i)
2759     {
2760         _vChildren[i].setAsT1(NULL);
2761     }
2762 }
2763
2764 template<class ObjectT, UInt32 LevelBits> inline
2765 void ShaderCacheTreeV3<ObjectT, LevelBits>::TreeNode::clear(void)
2766 {
2767     _pObject = NULL;
2768     _pPrev   = NULL;
2769     _pNext   = NULL;
2770
2771     for(UInt32 i = 0; i < LevelSize; ++i)
2772     {
2773         _vChildren[i].setAsT1(NULL);
2774     }
2775
2776     memset(&(_vJumps[0]), 0, LevelSize * sizeof(UInt16));
2777 }
2778
2779
2780
2781 template<class ObjectT, UInt32 LevelBits> inline
2782 ObjectT *ShaderCacheTreeV3<ObjectT, LevelBits>::find(const IdStore &vIds)
2783 {
2784     if(vIds.size() < 1 || _pRoot == NULL)
2785         return NULL;
2786
2787     ObjectT *returnValue = NULL;
2788
2789     IdType uiStartId     = vIds[0] - 1;
2790     IdType uiStartLevel  = IdType(uiStartId * LevelFactor);
2791
2792     UInt32 uiCurrId      = 0;
2793     UInt32 uiLastId      = UInt32(vIds.size());
2794
2795
2796     if(uiStartLevel >= _vLevelEntries.size())
2797     {
2798         uiStartLevel = IdType(_vLevelEntries.size() - 1);
2799     }
2800
2801
2802     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
2803     UInt32    uiCurrBits = 0x0000;
2804     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
2805     TreeNode *pNextNode  = NULL;
2806
2807     if(pCurrNode == NULL)
2808         return NULL;
2809
2810     for(; uiCurrId < uiLastId; ++uiCurrId)
2811     {
2812         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
2813         UInt16 uiJumpDist = 1;
2814
2815         if(uiCurrIdx <= LevelBits)
2816         {
2817             uiCurrBits |= IdxToBits[uiCurrIdx];
2818
2819             continue;
2820         }
2821         else
2822         {
2823             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
2824
2825             if(pNextNode == NULL)
2826             {
2827                 pCurrNode = pNextNode;
2828                 break;
2829             }
2830
2831             uiJumpDist = UInt16((uiCurrIdx - 1) * LevelFactor);
2832             UInt32 uiTargetLevel = uiStartLevel + uiJumpDist;
2833
2834             if(uiJumpDist < pCurrNode->_vJumps[uiCurrBits])
2835             {
2836                 pCurrNode = NULL;
2837                 break;
2838             }
2839
2840             if(uiJumpDist > pCurrNode->_vJumps[uiCurrBits])
2841             {
2842                 uiLevelSub += LevelBits * pCurrNode->_vJumps[uiCurrBits];
2843                 uiCurrIdx  -= LevelBits * pCurrNode->_vJumps[uiCurrBits];
2844                 uiJumpDist -= pCurrNode->_vJumps[uiCurrBits];
2845
2846                 pCurrNode = pNextNode;
2847                 pNextNode = pCurrNode->_vChildren[0].asT2();
2848
2849                 uiCurrBits  = 0x0000;
2850
2851                 while(1)
2852                 {
2853                     if(uiCurrIdx <= LevelBits)
2854                     {
2855                         break;
2856                     }
2857
2858                     if(uiJumpDist == pCurrNode->_vJumps[0])
2859                     {
2860                         break;
2861                     }
2862
2863                     if(uiJumpDist < pCurrNode->_vJumps[0])
2864                     {
2865                         pNextNode = NULL;
2866                         break;
2867                     }
2868
2869                     if(pNextNode == NULL)
2870                     {
2871                         break;
2872                     }
2873
2874                     uiLevelSub +=
2875                         LevelBits * pCurrNode->_vJumps[0];
2876
2877                     uiCurrIdx  -=
2878                         LevelBits * pCurrNode->_vJumps[0];
2879
2880                     uiJumpDist -= pCurrNode->_vJumps[0];
2881
2882                     pCurrNode = pNextNode;
2883                     pNextNode = pCurrNode->_vChildren[0].asT2();
2884                 }
2885             }
2886
2887             pCurrNode = pNextNode;
2888
2889             if(pCurrNode == NULL)
2890             {
2891                 break;
2892             }
2893
2894             uiCurrBits  = 0x0000;
2895
2896             uiStartLevel = uiTargetLevel;
2897             uiLevelSub   = (uiStartLevel * LevelBits);
2898
2899             uiCurrIdx  -= uiJumpDist * LevelBits;
2900
2901
2902             uiCurrBits |= IdxToBits[uiCurrIdx];
2903         }
2904     }
2905
2906     if(pCurrNode != NULL)
2907     {
2908         TreeNode *pNext = pCurrNode->_vChildren[uiCurrBits].asT2();
2909
2910         if(pNext != NULL)
2911         {
2912             returnValue = pNext->_pObject;
2913         }
2914         else
2915         {
2916             returnValue = pCurrNode->_vChildren[uiCurrBits].asT1();
2917         }
2918     }
2919
2920     return returnValue;
2921 }
2922
2923
2924 template<class ObjectT, UInt32 LevelBits> inline
2925 bool ShaderCacheTreeV3<ObjectT, LevelBits>::add(const IdStore &vIds,
2926                                                       ObjectT *pObject)
2927 {
2928     bool returnValue = false;
2929
2930     if(vIds.size() < 1)
2931         return returnValue;
2932
2933     IdType uiStartId    = vIds[0] - 1;
2934
2935     IdType uiStartLevel = IdType(uiStartId * LevelFactor);
2936
2937     UInt32 uiCurrId     = 0;
2938     UInt32 uiLastId     = UInt32(vIds.size());
2939
2940 #ifdef OSG_DEBUG
2941     FDEBUG(("scv3::add : "));
2942     for(UInt32 i = 0; i < uiLastId; ++i)
2943     {
2944         FDEBUG(("%d ", vIds[i]));
2945     }
2946     FDEBUG(("\n"));
2947 #endif
2948
2949     if(_pRoot == NULL)
2950     {
2951         _pRoot = allocateNode();
2952
2953         OSG_ASSERT(_vLevelEntries.size() == 0);
2954
2955         _vLevelEntries.push_back(_pRoot);
2956     }
2957
2958     if(uiStartLevel >= _vLevelEntries.size())
2959     {
2960         uiStartLevel = IdType(_vLevelEntries.size() - 1);
2961     }
2962
2963
2964     TreeNode *pCurrNode = _vLevelEntries[uiStartLevel];
2965     TreeNode *pNextNode = NULL;
2966
2967     UInt32 uiCurrBits = 0x0000;
2968
2969     if(pCurrNode == NULL)
2970     {
2971         UInt32 uiLastValidLE = 0;
2972
2973         for(Int32 i = uiStartLevel; i >= 0; --i)
2974         {
2975             if(_vLevelEntries[i] != NULL)
2976             {
2977                 uiLastValidLE = i;
2978                 break;
2979             }
2980         }
2981
2982         uiStartLevel = uiLastValidLE;
2983         pCurrNode    = _vLevelEntries[uiStartLevel];
2984     }
2985
2986     UInt32 uiLevelSub   = (uiStartLevel * LevelBits);
2987
2988     for(; uiCurrId < uiLastId; ++uiCurrId)
2989     {
2990         UInt32 uiCurrIdx  = vIds[uiCurrId] - uiLevelSub;
2991         UInt16 uiJumpDist = 1;
2992
2993         if(uiCurrIdx <= LevelBits)
2994         {
2995             uiCurrBits |= IdxToBits[uiCurrIdx];
2996
2997             continue;
2998         }
2999         else
3000         {
3001             pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
3002
3003             uiJumpDist           = UInt16((uiCurrIdx - 1) * LevelFactor);
3004             UInt32 uiTargetLevel = uiStartLevel + uiJumpDist;
3005
3006             if(pNextNode != NULL)
3007             {
3008                 if(uiJumpDist > pCurrNode->_vJumps[uiCurrBits])
3009                 {
3010                     uiLevelSub += LevelBits * pCurrNode->_vJumps[uiCurrBits];
3011                     uiCurrIdx  -= LevelBits * pCurrNode->_vJumps[uiCurrBits];
3012                     uiJumpDist -= pCurrNode->_vJumps[uiCurrBits];
3013
3014                     pCurrNode = pNextNode;
3015                     pNextNode = pCurrNode->_vChildren[0].asT2();
3016
3017                     uiCurrBits  = 0x0000;
3018
3019                     while(1)
3020                     {
3021                         if(uiCurrIdx <= LevelBits)
3022                         {
3023                             break;
3024                         }
3025
3026                         if(pNextNode == NULL)
3027                         {
3028                             break;
3029                         }
3030
3031                         if(uiJumpDist <= pCurrNode->_vJumps[0])
3032                         {
3033                             break;
3034                         }
3035
3036                         uiLevelSub +=
3037                             LevelBits * pCurrNode->_vJumps[0];
3038
3039                         uiCurrIdx  -=
3040                             LevelBits * pCurrNode->_vJumps[0];
3041
3042                         uiJumpDist -= pCurrNode->_vJumps[0];
3043
3044                         pCurrNode = pNextNode;
3045                         pNextNode = pCurrNode->_vChildren[0].asT2();
3046                     }
3047                 }
3048
3049                 if(uiJumpDist < pCurrNode->_vJumps[uiCurrBits])
3050                 {
3051                     pNextNode = allocateNode();
3052
3053                     pNextNode->_vJumps[0] =
3054                         pCurrNode->_vJumps   [uiCurrBits] - uiJumpDist;
3055
3056                     pNextNode->_vChildren[0] =
3057                         pCurrNode->_vChildren[uiCurrBits].asT2();
3058
3059                     pNextNode->_pObject =
3060                         pCurrNode->_vChildren[uiCurrBits].asT2()->_pObject;
3061
3062                     pCurrNode->_vChildren[uiCurrBits].asT2()->_pObject = NULL;
3063
3064                     pCurrNode->_vJumps   [uiCurrBits] = uiJumpDist;
3065                     pCurrNode->_vChildren[uiCurrBits] = pNextNode;
3066
3067                     if(_vLevelEntries[uiTargetLevel] == NULL)
3068                     {
3069                         UInt32 uiLastValidLE = 0;
3070
3071                         for(Int32 i = uiTargetLevel; i >= 0; --i)
3072                         {
3073                             if(_vLevelEntries[i] != NULL)
3074                             {
3075                                 uiLastValidLE = i;
3076                                 break;
3077                             }
3078                         }
3079
3080                         if(_vLevelEntries[uiLastValidLE] == pCurrNode &&
3081                             uiCurrBits                   == 0          )
3082                         {
3083                             _vLevelEntries[uiTargetLevel] = pNextNode;
3084                         }
3085                         else
3086                         {
3087                             TreeNode *pTmpNode = allocateNode();
3088
3089                             if(_vLevelEntries[
3090                                    uiLastValidLE]->_vChildren[0].asT2() != NULL)
3091                             {
3092                                 pTmpNode->_vChildren[0] =
3093                                     _vLevelEntries[
3094                                         uiLastValidLE]->_vChildren[0].asT2();
3095
3096                                 pTmpNode->_vJumps[0] =
3097                                     _vLevelEntries[
3098                                         uiLastValidLE]->_vJumps[0] -
3099                                     (uiTargetLevel - uiLastValidLE);
3100                             }
3101
3102                             _vLevelEntries[uiLastValidLE]->_vChildren[0] =
3103                                 pTmpNode;
3104                             _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
3105                                 uiTargetLevel - uiLastValidLE;
3106
3107                             _vLevelEntries[uiTargetLevel] = pTmpNode;
3108
3109                             pTmpNode ->_pNext = pNextNode;
3110                             pNextNode->_pPrev = pTmpNode;
3111                         }
3112                     }
3113                     else
3114                     {
3115                         pNextNode->_pNext =
3116                             _vLevelEntries[uiTargetLevel]->_pNext;
3117
3118                         if(pNextNode->_pNext != NULL)
3119                         {
3120                             pNextNode->_pNext->_pPrev = pNextNode;
3121                         }
3122
3123                         _vLevelEntries[uiTargetLevel]->_pNext = pNextNode;
3124
3125                         pNextNode->_pPrev = _vLevelEntries[uiTargetLevel];
3126                     }
3127                 }
3128             }
3129
3130             if(pNextNode == NULL)
3131             {
3132                 pNextNode = allocateNode();
3133
3134                 pCurrNode->_vJumps   [uiCurrBits] = uiJumpDist;
3135
3136                 if(pCurrNode->_vChildren[uiCurrBits].asT1() != NULL)
3137                 {
3138                     pNextNode->_pObject =
3139                         pCurrNode->_vChildren[uiCurrBits].asT1();
3140                 }
3141
3142                 pCurrNode->_vChildren[uiCurrBits] = pNextNode;
3143
3144                 if(uiTargetLevel >= _vLevelEntries.size())
3145                 {
3146                     _vLevelEntries.resize(uiTargetLevel + 1, NULL);
3147
3148                     UInt32 uiLastValidLE = 0;
3149
3150                     for(Int32 i = uiTargetLevel; i >= 0; --i)
3151                     {
3152                         if(_vLevelEntries[i] != NULL)
3153                         {
3154                             uiLastValidLE = i;
3155                             break;
3156                         }
3157                     }
3158
3159                     if(_vLevelEntries[uiLastValidLE] == pCurrNode &&
3160                         uiCurrBits                   == 0          )
3161                     {
3162                         _vLevelEntries[uiTargetLevel] = pNextNode;
3163                     }
3164                     else
3165                     {
3166                         TreeNode *pTmpNode = allocateNode();
3167
3168                         _vLevelEntries[uiLastValidLE]->_vChildren[0] = pTmpNode;
3169                         _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
3170                             uiTargetLevel - uiLastValidLE;
3171
3172                         _vLevelEntries[uiTargetLevel] = pTmpNode;
3173
3174                         pTmpNode ->_pNext = pNextNode;
3175                         pNextNode->_pPrev = pTmpNode;
3176                     }
3177                 }
3178                 else
3179                 {
3180                     if(_vLevelEntries[uiTargetLevel] == NULL)
3181                     {
3182                         UInt32 uiLastValidLE = 0;
3183
3184                         for(Int32 i = uiTargetLevel; i >= 0; --i)
3185                         {
3186                             if(_vLevelEntries[i] != NULL)
3187                             {
3188                                 uiLastValidLE = i;
3189                                 break;
3190                             }
3191                         }
3192
3193                         TreeNode *pTmpNode = allocateNode();
3194
3195                         if(_vLevelEntries[
3196                                uiLastValidLE]->_vChildren[0].asT2() != NULL)
3197                         {
3198                             pTmpNode->_vChildren[0] =
3199                                 _vLevelEntries[
3200                                     uiLastValidLE]->_vChildren[0].asT2();
3201
3202                             pTmpNode->_vJumps[0] =
3203                                 _vLevelEntries[uiLastValidLE]->_vJumps[0] -
3204                                 (uiTargetLevel - uiLastValidLE);
3205
3206                         }
3207
3208                         _vLevelEntries[uiLastValidLE]->_vChildren[0] = pTmpNode;
3209                         _vLevelEntries[uiLastValidLE]->_vJumps   [0] =
3210                             uiTargetLevel - uiLastValidLE;
3211
3212                         _vLevelEntries[uiTargetLevel] = pTmpNode;
3213
3214                         pTmpNode ->_pNext = pNextNode;
3215                         pNextNode->_pPrev = pTmpNode;
3216                     }
3217                     else
3218                     {
3219                         pNextNode->_pNext =
3220                             _vLevelEntries[uiTargetLevel]->_pNext;
3221
3222                         if(pNextNode->_pNext != NULL)
3223                         {
3224                             pNextNode->_pNext->_pPrev = pNextNode;
3225                         }
3226
3227                         _vLevelEntries[uiTargetLevel]->_pNext = pNextNode;
3228
3229                         pNextNode->_pPrev = _vLevelEntries[uiTargetLevel];
3230                     }
3231                 }
3232             }
3233
3234
3235             pCurrNode   = pNextNode;
3236
3237             uiCurrBits  = 0x0000;
3238
3239             uiStartLevel = uiTargetLevel;
3240             uiLevelSub   = (uiStartLevel * LevelBits);
3241
3242             uiCurrIdx  -= uiJumpDist * LevelBits;
3243
3244             uiCurrBits |= IdxToBits[uiCurrIdx];
3245         }
3246     }
3247
3248     if(pCurrNode != NULL)
3249     {
3250         pNextNode = pCurrNode->_vChildren[uiCurrBits].asT2();
3251
3252         if(pNextNode != NULL)
3253         {
3254             if(pNextNode->_pObject == NULL)
3255             {
3256                 pNextNode->_pObject = pObject;
3257
3258                 returnValue = true;
3259             }
3260             else
3261             {
3262                 OSG_ASSERT(pNextNode->_pObject == pObject);
3263             }
3264         }
3265         else
3266         {
3267             pCurrNode->_vChildren[uiCurrBits] = pObject;
3268
3269             returnValue = true;
3270         }
3271     }
3272
3273     return returnValue;
3274 }
3275
3276 template<class ObjectT, UInt32 LevelBits> inline
3277 void ShaderCacheTreeV3<ObjectT, LevelBits>::sub(UInt32 uiIdx)
3278 {
3279 #ifdef OSG_DEBUG
3280     FDEBUG(("scv3::sub : %d\n", uiIdx));
3281 #endif
3282
3283     IdType uiStartLevel  = IdType((uiIdx - 1) * LevelFactor);
3284
3285     if(uiStartLevel >= _vLevelEntries.size())
3286     {
3287         return;
3288     }
3289
3290     UInt32    uiLevelSub = (uiStartLevel * LevelBits);
3291     UInt32    uiCurrIdx  = uiIdx - uiLevelSub;
3292     UInt32    uiCurrBits = IdxToBits[uiCurrIdx];
3293
3294     TreeNode *pCurrNode  = _vLevelEntries[uiStartLevel];
3295
3296     for(; pCurrNode != NULL; pCurrNode = pCurrNode->_pNext)
3297     {
3298         for(UInt32 i = 0; i < LevelSize; ++i)
3299         {
3300             if(0x0000 != (i & uiCurrBits))
3301             {
3302                 TreeNode *pChild = pCurrNode->_vChildren[i].asT2();
3303
3304                 if(pChild != NULL)
3305                 {
3306                     if(pChild->_pNext == NULL)
3307                     {
3308                         pChild->_pPrev->_pNext = NULL;
3309                     }
3310                     else
3311                     {
3312                         pChild->_pPrev->_pNext = pChild->_pNext;
3313                         pChild->_pNext->_pPrev = pChild->_pPrev;
3314                     }
3315
3316                     pChild->_pPrev = NULL;
3317                     pChild->_pNext = NULL;
3318
3319                     eraseNode(pCurrNode->_vChildren[i].asT2());
3320                     pCurrNode->_vJumps   [i] = 0;
3321                     pCurrNode->_vChildren[i].setAsT2(NULL);
3322                 }
3323                 else if(pCurrNode->_vChildren[i].asT1() != NULL)
3324                 {
3325                     pCurrNode->_vChildren[i].setAsT1(NULL);
3326                     pCurrNode->_vJumps   [i] = 0;
3327                 }
3328             }
3329         }
3330     }
3331 }
3332
3333 #define OSG_DUMP_LEVELENTRIES
3334
3335 template<class ObjectT, UInt32 LevelBits> inline
3336 void ShaderCacheTreeV3<ObjectT,
3337                        LevelBits>::dumpDot(const Char8 *szFilename,
3338                                                  bool   dumpEmptyLevelEntries)
3339 {
3340     FILE *pOut = fopen(szFilename, "w");
3341
3342     if(pOut != NULL)
3343     {
3344         fprintf(pOut, "digraph structs\n");
3345         fprintf(pOut, "{\n");
3346         fprintf(pOut, "rankdir = LR;\n");
3347         fprintf(pOut, "splines=false\n");
3348
3349         fprintf(pOut, "node [shape=record];\n");
3350
3351         fprintf(pOut, "struct%d\n", 0);
3352         fprintf(pOut, "[\n");
3353         fprintf(pOut, "    label=\"");
3354
3355         if(_vLevelEntries.empty())
3356             fprintf(pOut, "\"\n");
3357
3358         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
3359         {
3360             if(_vLevelEntries[i] != NULL)
3361             {
3362                 fprintf(pOut, "<l%d> %d", i, i);
3363             }
3364             else
3365             {
3366                 if(dumpEmptyLevelEntries == true)
3367                     fprintf(pOut, "<l%d> NIL", i);
3368             }
3369
3370             if(i == _vLevelEntries.size() - 1)
3371             {
3372                 fprintf(pOut, "\"\n");
3373             }
3374             else
3375             {
3376                 if(_vLevelEntries[i] != NULL || dumpEmptyLevelEntries == true)
3377                     fprintf(pOut, "|");
3378             }
3379         }
3380
3381         fprintf(pOut, "]\n");
3382
3383         fprintf(pOut, "node [width = 1.5];\n");
3384
3385         std::vector<std::vector<TreeNode *> > vLevelStore;
3386
3387         dumpDotNode(_pRoot, pOut, vLevelStore, 0);
3388
3389 #ifdef OSG_DEBUG
3390 #ifdef OSG_DUMP_LEVELENTRIES
3391         for(UInt32 i = 0; i < _vLevelEntries.size(); ++i)
3392         {
3393             if(_vLevelEntries[i] != NULL)
3394             {
3395                 fprintf(pOut,
3396                         "struct%d:l%d -> struct%d:prev [color=\"green\"];\n",
3397                         0, i,
3398                         _vLevelEntries[i]->_uiNodeId);
3399             }
3400         }
3401 #endif
3402
3403 #if 0
3404         for(UInt32 i = 0; i < vLevelStore.size(); ++i)
3405         {
3406             fprintf(pOut, "{ rank=same;");
3407
3408             for(UInt32 j = 0; j < vLevelStore[i].size(); ++j)
3409             {
3410                 TreeNode *pChild = vLevelStore[i][j];
3411
3412                 if(pChild != NULL)
3413                 {
3414                     fprintf(pOut, "\"struct%d\";",
3415                             pChild->_uiNodeId);
3416                 }
3417             }
3418
3419             fprintf(pOut, "}\n");
3420         }
3421 #endif
3422 #endif
3423
3424         fprintf(pOut, "}\n");
3425         fclose(pOut);
3426     }
3427 }
3428
3429 template<class ObjectT, UInt32 LevelBits> inline
3430 void ShaderCacheTreeV3<ObjectT, LevelBits>::dumpDotNode(
3431     TreeNode                              *pNode,
3432     FILE                                  *pOut ,
3433     std::vector<std::vector<TreeNode *> > &vLevelStore,
3434     UInt32                                 uiLevel    )
3435 {
3436 #ifdef OSG_DEBUG
3437     if(pNode == NULL)
3438         return;
3439
3440     if(uiLevel == vLevelStore.size())
3441     {
3442         vLevelStore.push_back(std::vector<TreeNode *>());
3443     }
3444
3445     fprintf(pOut, "struct%d\n", pNode->_uiNodeId);
3446     fprintf(pOut, "[\n");
3447     fprintf(pOut, "    label=\"{");
3448
3449     if(pNode->_pPrev != NULL)
3450     {
3451         fprintf(pOut, "<prev> P|");
3452     }
3453     else
3454     {
3455         fprintf(pOut, "<prev> P:NIL|");
3456     }
3457
3458     for(UInt32 i = 0; i < LevelSize; ++i)
3459     {
3460         if(pNode->_vChildren[i].asT1() != NULL)
3461         {
3462             if(osgIsPower2(i) == true)
3463             {
3464                 fprintf(pOut, "<l%d> _O:%d|", i, i);
3465             }
3466             else
3467             {
3468                 fprintf(pOut, "<l%d> O:%d|", i, i);
3469             }
3470         }
3471         else if(pNode->_vChildren[i].asT2() != NULL)
3472         {
3473             if(osgIsPower2(i) == true)
3474             {
3475                 fprintf(pOut, "<l%d> _C:%d (%d)|", i, i, pNode->_vJumps[i]);
3476             }
3477             else
3478             {
3479                 fprintf(pOut, "<l%d> C:%d (%d)|", i, i, pNode->_vJumps[i]);
3480             }
3481         }
3482         else
3483         {
3484             if(osgIsPower2(i) == true)
3485             {
3486                 fprintf(pOut, "<l%d> _NIL|", i);
3487             }
3488             else
3489             {
3490                 fprintf(pOut, "<l%d> NIL|", i);
3491             }
3492         }
3493     }
3494
3495     if(pNode->_pObject != NULL)
3496     {
3497         fprintf(pOut, "<val> VAL:Obj|");
3498     }
3499     else
3500     {
3501         fprintf(pOut, "<val> VAL:NIL|");
3502     }
3503
3504     if(pNode->_pNext != NULL)
3505     {
3506         fprintf(pOut, "<next> N}\"\n");
3507     }
3508     else
3509     {
3510         fprintf(pOut, "<next> N:NIL}\"\n");
3511     }
3512
3513     fprintf(pOut, "]\n");
3514
3515     for(UInt32 i = 0; i < LevelSize; ++i)
3516     {
3517         TreeNode *pChild = pNode->_vChildren[i].asT2();
3518
3519         if(pChild != NULL)
3520         {
3521             dumpDotNode(pChild, pOut, vLevelStore, uiLevel + 1);
3522
3523             fprintf(pOut,
3524                     "struct%d:l%d -> struct%d:l%d [constraint=\"false\"];\n",
3525                     pNode ->_uiNodeId, i,
3526                     pChild->_uiNodeId, i);
3527         }
3528     }
3529
3530     if(pNode->_pNext != NULL)
3531     {
3532         fprintf(pOut, "struct%d:next -> struct%d:prev;\n",
3533                 pNode ->_uiNodeId,
3534                 pNode->_pNext->_uiNodeId);
3535     }
3536     if(pNode->_pPrev != NULL)
3537     {
3538         fprintf(pOut, "struct%d:prev -> struct%d:next;\n",
3539                 pNode ->_uiNodeId,
3540                 pNode->_pPrev->_uiNodeId);
3541     }
3542
3543      vLevelStore[uiLevel].push_back(pNode);
3544 #endif
3545 }
3546
3547 template<class ObjectT, UInt32 LevelBits> inline
3548 ShaderCacheTreeV3<ObjectT, LevelBits>::ShaderCacheTreeV3(void) :
3549 #ifdef OSG_DEBUG
3550     _uiNodeCount  (0   ),
3551 #endif
3552     _pRoot        (NULL),
3553     _vLevelEntries(    ),
3554     _qFreeElements(    )
3555 {
3556     _pRoot = allocateNode();
3557
3558     _vLevelEntries.push_back(_pRoot);
3559 }
3560
3561 template<class ObjectT, UInt32 LevelBits> inline
3562 ShaderCacheTreeV3<ObjectT, LevelBits>::~ShaderCacheTreeV3(void)
3563 {
3564     typename std::deque <TreeNode *>::iterator qIt  =
3565         _qFreeElements.begin();
3566
3567     typename std::deque <TreeNode *>::const_iterator qEnd =
3568         _qFreeElements.end();
3569
3570     for(; qIt != qEnd; ++qIt)
3571     {
3572         delete (*qIt);
3573
3574         *qIt = NULL;
3575     }
3576
3577     typename std::vector<TreeNode *>::iterator vIt  = _vLevelEntries.begin();
3578     typename std::vector<TreeNode *>::iterator vEnd = _vLevelEntries.end  ();
3579
3580     for(; vIt != vEnd; ++vIt)
3581     {
3582         delete (*vIt);
3583
3584         *vIt = NULL;
3585     }
3586 }
3587
3588 template<class ObjectT, UInt32 LevelBits> inline
3589 typename ShaderCacheTreeV3<ObjectT, LevelBits>::TreeNode *
3590     ShaderCacheTreeV3<ObjectT, LevelBits>::allocateNode(void)
3591 {
3592     TreeNode *returnValue = NULL;
3593
3594     if(_qFreeElements.empty() == false)
3595     {
3596         returnValue = _qFreeElements.back();
3597
3598         _qFreeElements.pop_back();
3599
3600         returnValue->clear();
3601     }
3602     else
3603     {
3604         returnValue = new TreeNode();
3605
3606 #ifdef OSG_DEBUG
3607         returnValue->_uiNodeId = ++_uiNodeCount;
3608 #endif
3609     }
3610
3611 #ifdef OSG_DEBUG
3612     UIntPointer rU = reinterpret_cast<UIntPointer>(returnValue);
3613
3614     OSG_ASSERT((rU & 0x0001) == 0x0000);
3615 #endif
3616
3617     return returnValue;
3618 }
3619
3620 template<class ObjectT, UInt32 LevelBits> inline
3621 void ShaderCacheTreeV3<ObjectT, LevelBits>::eraseNode(TreeNode *pNode)
3622 {
3623     for(UInt32 i = 0; i < LevelSize; ++i)
3624     {
3625         if(pNode->_vChildren[i].asT2() != NULL)
3626         {
3627             eraseNode(pNode->_vChildren[i].asT2());
3628
3629             pNode->_vChildren[i].setAsT2(NULL);
3630         }
3631         else
3632         {
3633             pNode->_vChildren[i].setAsT1(NULL);
3634         }
3635     }
3636
3637     pNode->_pObject = NULL;
3638
3639     _qFreeElements.push_back(pNode);
3640 }
3641
3642 template<class ObjectT, UInt32 LevelBits>
3643 template <typename ElemDestFunc> inline
3644 void ShaderCacheTreeV3<ObjectT, LevelBits>::destroyNode(TreeNode     *pNode,
3645                                                         ElemDestFunc  destFunc)
3646 {
3647     if(pNode == NULL)
3648         return;
3649
3650     UInt32 uiChildStart = 0;
3651
3652     for(UInt32 i = uiChildStart; i < LevelSize; ++i)
3653     {
3654         if(pNode->_vChildren[i].asT2() != NULL)
3655         {
3656             destroyNode(pNode->_vChildren[i].asT2(), destFunc);
3657         }
3658         else if(pNode->_vChildren[i].asT1() != NULL)
3659         {
3660 #ifndef OSG_SHC_REF_CLEANUP
3661             ObjectT *pObj = pNode->_vChildren[i].asT1();
3662             (destFunc)(pObj);
3663 #endif
3664             pNode->_vChildren[i].setAsT1(NULL);
3665         }
3666     }
3667
3668     if(pNode->_pObject != NULL)
3669     {
3670 #ifndef OSG_SHC_REF_CLEANUP
3671         (destFunc)(pNode->_pObject);
3672 #endif
3673         pNode->_pObject = NULL;
3674     }
3675
3676     delete pNode;
3677 }
3678
3679 template<class ObjectT, UInt32 LevelBits>
3680 template <typename ElemDestFunc> inline
3681 void ShaderCacheTreeV3<ObjectT, LevelBits>::destroy(ElemDestFunc destFunc)
3682 {
3683     destroyNode(_pRoot, destFunc);
3684
3685     TreeNodeVecIt      leIt  = _vLevelEntries.begin();
3686     TreeNodeVecConstIt leEnd = _vLevelEntries.end  ();
3687
3688     for(; leIt != leEnd; ++leIt)
3689     {
3690         *leIt = NULL;
3691     }
3692
3693     _vLevelEntries.clear();
3694
3695     _pRoot = NULL;
3696 }
3697
3698 OSG_END_NAMESPACE