src/ilasm/asmtemplates.h

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 #ifndef ASMTEMPLATES_H
   6 #define ASMTEMPLATES_H
   7
   8 #ifdef _PREFAST_
   9 #pragma warning(push)
  10 #pragma warning(disable:22008) // "Suppress PREfast warnings about integer overflow"
  11 #endif
  12
  13 inline ULONG GrowBuffer(ULONG startingSize)
  14 {
  15     int toAdd = startingSize >> 1;
  16     if (toAdd < 8)
  17         toAdd = 8;
  18     if (toAdd > 2048)
  19         toAdd = 2048;
  20     return startingSize + toAdd;
  21 }
  22
  23 /*****************************************************************************/
  24 /* LIFO (stack) and FIFO (queue) templates (must precede #include "method.h")*/
  25 template <class T>
  26 class LIST_EL
  27 {
  28 public:
  29     T*  m_Ptr;
  30     LIST_EL <T> *m_Next;
  31     LIST_EL(T *item) {m_Next = NULL; m_Ptr = item; };
  32 };
  33
  34 template <class T>
  35 class LIFO
  36 {
  37 public:
  38     inline LIFO() { m_pHead = NULL; };
  39     inline ~LIFO() {T *val; while((val = POP()) != NULL) delete val; };
  40     void PUSH(T *item)
  41     {
  42         m_pTemp = new LIST_EL <T>(item);
  43         m_pTemp->m_Next = m_pHead;
  44         m_pHead = m_pTemp;
  45     };
  46     T* POP()
  47     {
  48         T* ret = NULL;
  49         if((m_pTemp = m_pHead) != NULL)
  50         {
  51             m_pHead = m_pHead->m_Next;
  52             ret = m_pTemp->m_Ptr;
  53             delete m_pTemp;
  54         }
  55         return ret;
  56     };
  57 private:
  58     LIST_EL <T> *m_pHead;
  59     LIST_EL <T> *m_pTemp;
  60 };
  61
  62
  63 template <class T>
  64 class FIFO
  65 {
  66 public:
  67     FIFO() { m_Arr = NULL; m_ulArrLen = 0; m_ulCount = 0; m_ulOffset = 0; };
  68     ~FIFO() {
  69         if(m_Arr) {
  70             for(ULONG i=0; i < m_ulCount; i++) {
  71                 if(m_Arr[i+m_ulOffset]) delete m_Arr[i+m_ulOffset];
  72             }
  73             delete [] m_Arr;
  74         }
  75     };
  76     void RESET(bool DeleteElements = true) {
  77         if(m_Arr) {
  78             for(ULONG i=0; i < m_ulCount; i++) {
  79                 if(DeleteElements) delete m_Arr[i+m_ulOffset];
  80                 m_Arr[i+m_ulOffset] = NULL;
  81             }
  82             m_ulCount = 0;
  83             m_ulOffset= 0;
  84         }
  85     };
  86     void PUSH(T *item)
  87     {
  88                 if(item)
  89                 {
  90                         if(m_ulCount+m_ulOffset >= m_ulArrLen)
  91                         {
  92                                 if(m_ulOffset)
  93                                 {
  94                                         memcpy(m_Arr,&m_Arr[m_ulOffset],m_ulCount*sizeof(T*));
  95                                         m_ulOffset = 0;
  96                                 }
  97                                 else
  98                                 {
  99                     m_ulArrLen = GrowBuffer(m_ulArrLen);
 100                                         T** tmp = new T*[m_ulArrLen];
 101                                         if(tmp)
 102                                         {
 103                                                 if(m_Arr)
 104                                                 {
 105                                                         memcpy(tmp,m_Arr,m_ulCount*sizeof(T*));
 106                                                         delete [] m_Arr;
 107                                                 }
 108                                                 m_Arr = tmp;
 109                                         }
 110                                         else fprintf(stderr,"\nOut of memory!\n");
 111                                 }
 112                         }
 113                         m_Arr[m_ulOffset+m_ulCount] = item;
 114                         m_ulCount++;
 115                 }
 116     };
 117     ULONG COUNT() { return m_ulCount; };
 118     T* POP()
 119     {
 120         T* ret = NULL;
 121         if(m_ulCount)
 122         {
 123             ret = m_Arr[m_ulOffset++];
 124             m_ulCount--;
 125         }
 126         return ret;
 127     };
 128     T* PEEK(ULONG idx) { return (idx < m_ulCount) ? m_Arr[m_ulOffset+idx] : NULL; };
 129 private:
 130     T** m_Arr;
 131     ULONG       m_ulCount;
 132     ULONG       m_ulOffset;
 133     ULONG       m_ulArrLen;
 134 };
 135
 136
 137 template <class T> struct Indx256
 138 {
 139     void* table[256];
 140     Indx256() { memset(table,0,sizeof(table)); };
 141     ~Indx256()
 142     {
 143         ClearAll(true);
 144         for(int i = 1; i < 256; i++) delete ((Indx256*)(table[i]));
 145     };
 146     T** IndexString(BYTE* psz, T* pObj)
 147     {
 148         if(*psz == 0)
 149         {
 150             table[0] = (void*)pObj;
 151             return (T**)table;
 152         }
 153         else
 154         {
 155             Indx256* pInd = (Indx256*)(table[*psz]);
 156             if(pInd == NULL)
 157             {
 158                 pInd = new Indx256;
 159                 if(pInd)
 160                     table[*psz] = pInd;
 161                 else
 162                 {
 163                     _ASSERTE(!"Out of memory in Indx256::IndexString!");
 164                     fprintf(stderr,"\nOut of memory in Indx256::IndexString!\n");
 165                     return NULL;
 166                 }
 167             }
 168             return pInd->IndexString(psz+1,pObj);
 169         }
 170     };
 171     T*  FindString(BYTE* psz)
 172     {
 173         if(*psz > 0)
 174         {
 175             Indx256* pInd = (Indx256*)(table[*psz]);
 176             return (pInd == NULL) ? NULL : pInd->FindString(psz+1);
 177         }
 178         return (T*)(table[0]); // if i==0
 179     };
 180
 181     void ClearAll(bool DeleteObj)
 182     {
 183         if(DeleteObj) delete (T*)(table[0]);
 184         table[0] = NULL;
 185         for(unsigned i = 1; i < 256; i++)
 186         {
 187             if(table[i])
 188             {
 189                 Indx256* pInd = (Indx256*)(table[i]);
 190                 pInd->ClearAll(DeleteObj);
 191                 //delete pInd;
 192                 //table[i] = NULL;
 193             }
 194         }
 195     };
 196 };
 197
 198 //
 199 // Template intended for named objects, that expose function char* NameOf()
 200 //
 201 template <class T>
 202 class FIFO_INDEXED
 203 {
 204 public:
 205     FIFO_INDEXED() { m_Arr = NULL; m_ulArrLen = 0; m_ulCount = 0; m_ulOffset = 0; };
 206     ~FIFO_INDEXED() {
 207         if(m_Arr)
 208         {
 209             RESET(true);
 210             delete [] m_Arr;
 211         }
 212     };
 213     void RESET(bool DeleteElements = true) {
 214         if(m_Arr) {
 215             unsigned i;
 216             if(DeleteElements)
 217             {
 218                 for(i=m_ulOffset; i < m_ulOffset+m_ulCount; i++)
 219                 {
 220                     T** ppT = m_Arr[i];
 221                     delete *ppT;
 222                 }
 223             }
 224             for(i=m_ulOffset; i < m_ulOffset+m_ulCount; i++)
 225             {
 226                 *m_Arr[i] = NULL;
 227             }
 228             memset(&m_Arr[m_ulOffset],0,m_ulCount*sizeof(void*));
 229             m_ulCount = 0;
 230             m_ulOffset= 0;
 231         }
 232     };
 233     void PUSH(T *item)
 234     {
 235                 if(item)
 236                 {
 237             T** itemaddr = m_Index.IndexString((BYTE*)(item->NameOf()),item);
 238             if(m_ulCount+m_ulOffset >= m_ulArrLen)
 239                         {
 240                                 if(m_ulOffset)
 241                                 {
 242                                         memcpy(m_Arr,&m_Arr[m_ulOffset],m_ulCount*sizeof(T*));
 243                                         m_ulOffset = 0;
 244                                 }
 245                                 else
 246                                 {
 247                                         m_ulArrLen = GrowBuffer(m_ulArrLen);
 248                                         T*** tmp = new T**[m_ulArrLen];
 249                                         if(tmp)
 250                                         {
 251                                                 if(m_Arr)
 252                                                 {
 253                                                         memcpy(tmp,m_Arr,m_ulCount*sizeof(T**));
 254                                                         delete [] m_Arr;
 255                                                 }
 256                                                 m_Arr = tmp;
 257                                         }
 258                                         else fprintf(stderr,"\nOut of memory!\n");
 259                                 }
 260                         }
 261                         m_Arr[m_ulOffset+m_ulCount] = itemaddr;
 262                         m_ulCount++;
 263                 }
 264     };
 265     ULONG COUNT() { return m_ulCount; };
 266     T* POP()
 267     {
 268         T* ret = NULL;
 269         if(m_ulCount)
 270         {
 271             ret = *(m_Arr[m_ulOffset]);
 272             *m_Arr[m_ulOffset] = NULL;
 273             m_ulOffset++;
 274             m_ulCount--;
 275         }
 276         return ret;
 277     };
 278     T* PEEK(ULONG idx) { return (idx < m_ulCount) ? *(m_Arr[m_ulOffset+idx]) : NULL; };
 279     T* FIND(T* item) { return m_Index.FindString((BYTE*)(item->NameOf())); };
 280 private:
 281     T*** m_Arr;
 282     ULONG       m_ulCount;
 283     ULONG       m_ulOffset;
 284     ULONG       m_ulArrLen;
 285     Indx256<T>  m_Index;
 286 };
 287
 288 template <class T>
 289 class SORTEDARRAY
 290 {
 291 public:
 292     SORTEDARRAY() { m_Arr = NULL; m_ulArrLen = 0; m_ulCount = 0; m_ulOffset = 0; };
 293     ~SORTEDARRAY() {
 294         if(m_Arr) {
 295             for(ULONG i=0; i < m_ulCount; i++) {
 296                 if(m_Arr[i+m_ulOffset]) delete m_Arr[i+m_ulOffset];
 297             }
 298             delete [] m_Arr;
 299         }
 300     };
 301     void RESET(bool DeleteElements = true) {
 302         if(m_Arr) {
 303             if(DeleteElements)
 304             {
 305                 for(ULONG i=0; i < m_ulCount; i++) {
 306                     delete m_Arr[i+m_ulOffset];
 307                 }
 308             }
 309             memset(m_Arr,0,m_ulArrLen*sizeof(T*));
 310             m_ulCount = 0;
 311             m_ulOffset= 0;
 312         }
 313     };
 314     void PUSH(T *item)
 315     {
 316                 if(item)
 317                 {
 318                         if(m_ulCount+m_ulOffset >= m_ulArrLen)
 319                         {
 320                                 if(m_ulOffset)
 321                                 {
 322                                         memcpy(m_Arr,&m_Arr[m_ulOffset],m_ulCount*sizeof(T*));
 323                                         m_ulOffset = 0;
 324                                 }
 325                                 else
 326                                 {
 327                                         m_ulArrLen = GrowBuffer(m_ulArrLen);
 328                                         T** tmp = new T*[m_ulArrLen];
 329                                         if(tmp)
 330                                         {
 331                                                 if(m_Arr)
 332                                                 {
 333                                                         memcpy(tmp,m_Arr,m_ulCount*sizeof(T*));
 334                                                         delete [] m_Arr;
 335                                                 }
 336                                                 m_Arr = tmp;
 337                                         }
 338                                         else fprintf(stderr,"\nOut of memory!\n");
 339                                 }
 340                         }
 341             if(m_ulCount)
 342             {
 343                 // find  1st arr.element > item
 344                 T** low = &m_Arr[m_ulOffset];
 345                 T** high = &m_Arr[m_ulOffset+m_ulCount-1];
 346                 T** mid;
 347
 348                 if(item->ComparedTo(*high) > 0) mid = high+1;
 349                 else if(item->ComparedTo(*low) < 0) mid = low;
 350                 else for(;;)
 351                 {
 352                     mid = &low[(high - low) >> 1];
 353
 354                     int cmp = item->ComparedTo(*mid);
 355
 356                     if (mid == low)
 357                     {
 358                         if(cmp > 0) mid++;
 359                         break;
 360                     }
 361
 362                     if (cmp > 0) low = mid;
 363                     else        high = mid;
 364                 }
 365
 366                 /////////////////////////////////////////////
 367                  memmove(mid+1,mid,(BYTE*)&m_Arr[m_ulOffset+m_ulCount]-(BYTE*)mid);
 368                 *mid = item;
 369             }
 370                         else m_Arr[m_ulOffset+m_ulCount] = item;
 371                         m_ulCount++;
 372                 }
 373     };
 374     ULONG COUNT() { return m_ulCount; };
 375     T* POP()
 376     {
 377         T* ret = NULL;
 378         if(m_ulCount)
 379         {
 380             ret = m_Arr[m_ulOffset++];
 381             m_ulCount--;
 382         }
 383         return ret;
 384     };
 385     T* PEEK(ULONG idx) { return (idx < m_ulCount) ? m_Arr[m_ulOffset+idx] : NULL; };
 386     T* FIND(T* item)
 387     {
 388         if(m_ulCount)
 389         {
 390             T** low = &m_Arr[m_ulOffset];
 391             T** high = &m_Arr[m_ulOffset+m_ulCount-1];
 392             T** mid;
 393             if(item->ComparedTo(*high) == 0) return(*high);
 394             for(;;)
 395             {
 396                 mid = &low[(high - low) >> 1];
 397                 int cmp = item->ComparedTo(*mid);
 398                 if (cmp == 0) return(*mid);
 399                 if (mid == low)  break;
 400                 if (cmp > 0) low = mid;
 401                 else        high = mid;
 402             }
 403         }
 404         return NULL;
 405     };
 406     /*
 407     T* FIND(U item)
 408     {
 409         if(m_ulCount)
 410         {
 411             T** low = &m_Arr[m_ulOffset];
 412             T** high = &m_Arr[m_ulOffset+m_ulCount-1];
 413             T** mid;
 414             if((*high)->Compare(item) == 0) return(*high);
 415             for(;;)
 416             {
 417                 mid = &low[(high - low) >> 1];
 418                 int cmp = (*mid)->Compare(item);
 419                 if (cmp == 0) return(*mid);
 420                 if (mid == low)  break;
 421                 if (cmp > 0) low = mid;
 422                 else        high = mid;
 423             }
 424         }
 425         return NULL;
 426     };
 427     */
 428     BOOL DEL(T* item)
 429     {
 430         if(m_ulCount)
 431         {
 432             T** low = &m_Arr[m_ulOffset];
 433             T** high = &m_Arr[m_ulOffset+m_ulCount-1];
 434             T** mid;
 435             if(item->ComparedTo(*high) == 0)
 436             {
 437                 delete (*high);
 438                 m_ulCount--;
 439                 return TRUE;
 440             }
 441             for(;;)
 442             {
 443                 mid = &low[(high - low) >> 1];
 444                 int cmp = item->ComparedTo(*mid);
 445                 if (cmp == 0)
 446                 {
 447                     delete (*mid);
 448                     memcpy(mid,mid+1,(BYTE*)&m_Arr[m_ulOffset+m_ulCount]-(BYTE*)mid-1);
 449                     m_ulCount--;
 450                     return TRUE;
 451                 }
 452                 if (mid == low)  break;
 453                 if (cmp > 0) low = mid;
 454                 else        high = mid;
 455             }
 456         }
 457         return FALSE;
 458     };
 459 private:
 460     T** m_Arr;
 461     ULONG       m_ulCount;
 462     ULONG       m_ulOffset;
 463     ULONG       m_ulArrLen;
 464 };
 465
 466 template <class T> struct RBNODE
 467 {
 468 private:
 469     DWORD       dwRed;
 470 public:
 471     DWORD       dwInUse;
 472     T*          tVal;
 473     RBNODE<T>*  pLeft;
 474     RBNODE<T>*  pRight;
 475     RBNODE<T>*  pParent;
 476     RBNODE()
 477     {
 478         pLeft = pRight = pParent = NULL;
 479         tVal = NULL;
 480         dwRed = dwInUse = 0;
 481     };
 482     RBNODE(T* pVal, DWORD dwColor)
 483     {
 484         pLeft = pRight = pParent = NULL;
 485         tVal = pVal;
 486         dwRed = dwColor;
 487         dwInUse = 0;
 488     };
 489     bool IsRed() { return (dwRed != 0); };
 490     void SetRed() { dwRed = 1; };
 491     void SetBlack() { dwRed = 0; };
 492 };
 493
 494 #define BUCKETCOUNT 512
 495
 496 template <class T> class RBNODEBUCKET
 497 {
 498 private:
 499     RBNODEBUCKET<T>* pNext;
 500     RBNODE<T> bucket[BUCKETCOUNT];
 501     unsigned  alloc_count;
 502
 503 public:
 504     RBNODEBUCKET()
 505     {
 506         alloc_count = 0;
 507         pNext = NULL;
 508     };
 509
 510     ~RBNODEBUCKET() { if(pNext) delete pNext; };
 511
 512     bool CanAlloc() { return (alloc_count < BUCKETCOUNT); };
 513
 514     RBNODE<T>* AllocNode()
 515     {
 516         RBNODE<T>* pRet;
 517         for(unsigned i = 0; i < BUCKETCOUNT; i++)
 518         {
 519             if(bucket[i].dwInUse == 0)
 520             {
 521                 alloc_count++;
 522                 pRet = &bucket[i];
 523                 memset(pRet, 0, sizeof(RBNODE<T>));
 524                 pRet->dwInUse = 1;
 525                 return pRet;
 526             }
 527         }
 528         _ASSERTE(!"AllocNode returns NULL");
 529         return NULL;
 530     };
 531
 532     bool FreeNode(RBNODE<T>* ptr)
 533     {
 534         size_t idx = ((size_t)ptr - (size_t)bucket)/sizeof(RBNODE<T>);
 535         if(idx < BUCKETCOUNT)
 536         {
 537             bucket[idx].dwInUse = 0;
 538             alloc_count--;
 539             return true;
 540         }
 541         return false;
 542     };
 543
 544     RBNODEBUCKET<T>* Next() { return pNext; };
 545
 546     void Append(RBNODEBUCKET<T>* ptr) { pNext = ptr; };
 547 };
 548
 549 template <class T> class RBNODEPOOL
 550 {
 551 private:
 552     RBNODEBUCKET<T> base;
 553
 554 public:
 555     RBNODEPOOL()
 556     {
 557         memset(&base,0,sizeof(RBNODEBUCKET<T>));
 558     };
 559
 560     RBNODE<T>* AllocNode()
 561     {
 562         RBNODEBUCKET<T>* pBucket = &base;
 563         RBNODEBUCKET<T>* pLastBucket = &base;
 564         do
 565         {
 566             if(pBucket->CanAlloc())
 567             {
 568                 return pBucket->AllocNode();
 569             }
 570             pLastBucket = pBucket;
 571             pBucket = pBucket->Next();
 572         }
 573         while (pBucket != NULL);
 574         pLastBucket->Append(new RBNODEBUCKET<T>);
 575         return pLastBucket->Next()->AllocNode();
 576     };
 577
 578     void FreeNode(RBNODE<T>* ptr)
 579     {
 580         RBNODEBUCKET<T>* pBucket = &base;
 581         do
 582         {
 583             if(pBucket->FreeNode(ptr))
 584                 break;
 585             pBucket = pBucket->Next();
 586         }
 587         while (pBucket != NULL);
 588     };
 589 };
 590
 591 template <class T> class RBTREE
 592 {
 593 private:
 594     RBNODE<T>* pRoot;
 595     RBNODE<T>* pNil;
 596     RBNODEPOOL<T> NodePool;
 597     void RotateLeft(RBNODE<T>* pX)
 598     {
 599         RBNODE<T>* pY;
 600
 601         pY = pX->pRight;
 602         pX->pRight = pY->pLeft;
 603
 604         if(pY->pLeft != pNil)
 605             pY->pLeft->pParent = pX;
 606
 607         pY->pParent = pX->pParent;
 608
 609         if(pX == pX->pParent->pLeft)
 610             pX->pParent->pLeft = pY;
 611         else
 612             pX->pParent->pRight = pY;
 613
 614         pY->pLeft = pX;
 615         pX->pParent = pY;
 616     };
 617
 618     void RotateRight(RBNODE<T>* pX)
 619     {
 620         RBNODE<T>* pY;
 621
 622         pY = pX->pLeft;
 623         pX->pLeft = pY->pRight;
 624
 625         if(pY->pRight != pNil)
 626             pY->pRight->pParent = pX;
 627
 628         pY->pParent = pX->pParent;
 629
 630         if(pX == pX->pParent->pLeft)
 631             pX->pParent->pLeft = pY;
 632         else
 633             pX->pParent->pRight = pY;
 634
 635         pY->pRight = pX;
 636         pX->pParent = pY;
 637
 638     };
 639
 640     void InsertNode(RBNODE<T>* pZ)
 641     {
 642         RBNODE<T>* pX;
 643         RBNODE<T>* pY;
 644
 645         pZ->pLeft = pZ->pRight = pNil;
 646         pY = pRoot;
 647         pX = pRoot->pLeft;
 648
 649         if(pX != pY)
 650         {
 651             while(pX != pNil)
 652             {
 653                 pY = pX;
 654                 if(pX->tVal->ComparedTo(pZ->tVal) > 0)
 655                     pX = pX->pLeft;
 656                 else
 657                     pX = pX->pRight;
 658             }
 659         }
 660         pZ->pParent = pY;
 661         if((pY == pRoot) || (pY->tVal->ComparedTo(pZ->tVal) > 0))
 662             pY->pLeft = pZ;
 663         else
 664             pY->pRight = pZ;
 665     };
 666
 667     void InitSpecNode(RBNODE<T>* pNode)
 668     {
 669         pNode->pLeft = pNode->pRight = pNode->pParent = pNode;
 670     };
 671
 672     void DeleteNode(RBNODE<T>* pNode, bool DeletePayload = true)
 673     {
 674         if((pNode != pNil)&&(pNode != pRoot))
 675         {
 676             DeleteNode(pNode->pLeft, DeletePayload);
 677             DeleteNode(pNode->pRight, DeletePayload);
 678             if(DeletePayload)
 679                 delete pNode->tVal;
 680             NodePool.FreeNode(pNode);
 681         }
 682     };
 683
 684 public:
 685     RBTREE()
 686     {
 687         pRoot = NodePool.AllocNode();
 688         InitSpecNode(pRoot);
 689
 690         pNil = NodePool.AllocNode();
 691         InitSpecNode(pNil);
 692     };
 693
 694     ~RBTREE()
 695     {
 696         //RESET(false);
 697         //NodePool.FreeNode(pRoot);
 698         //NodePool.FreeNode(pNil);
 699     };
 700
 701     void RESET(bool DeletePayload = true)
 702     {
 703         DeleteNode(pRoot->pLeft, DeletePayload);
 704         InitSpecNode(pRoot);
 705         InitSpecNode(pNil);
 706     };
 707
 708     void PUSH(T* pT)
 709     {
 710         RBNODE<T>* pX;
 711         RBNODE<T>* pY;
 712         RBNODE<T>* pNewNode = NodePool.AllocNode();
 713
 714         pNewNode->tVal = pT;
 715         pNewNode->SetRed();
 716
 717         InsertNode(pNewNode);
 718
 719         for(pX = pNewNode; pX->pParent->IsRed();)
 720         {
 721             if(pX->pParent == pX->pParent->pLeft)
 722             {
 723                 pY = pX->pParent->pRight;
 724                 if(pY->IsRed())
 725                 {
 726                     pX->pParent->SetBlack();
 727                     pY->SetBlack();
 728                     pX->pParent->pParent->SetRed();
 729                     pX = pX->pParent->pParent;
 730                 }
 731                 else
 732                 {
 733                     if(pX == pX->pParent->pRight)
 734                     {
 735                         pX = pX->pParent;
 736                         RotateLeft(pX);
 737                     }
 738                     pX->pParent->SetBlack();
 739                     pX->pParent->pParent->SetRed();
 740                     RotateRight(pX->pParent->pParent);
 741                 }
 742             }
 743             else // if(pX->pParent == pX->pParent->pRight)
 744             {
 745                 pY = pX->pParent->pParent->pLeft;
 746                 if(pY->IsRed())
 747                 {
 748                     pX->pParent->SetBlack();
 749                     pY->SetBlack();
 750                     pX->pParent->pParent->SetRed();
 751                     pX = pX->pParent->pParent;
 752                 }
 753                 else
 754                 {
 755                     if(pX == pX->pParent->pLeft)
 756                     {
 757                         pX = pX->pParent;
 758                         RotateRight(pX);
 759                     }
 760                     pX->pParent->SetBlack();
 761                     pX->pParent->pParent->SetRed();
 762                     RotateLeft(pX->pParent->pParent);
 763                 }
 764             }// end if(pX->pParent == pX->pParent->pLeft) -- else
 765         } // end for(pX = pNewNode; pX->pParent->IsRed();)
 766         pRoot->pLeft->SetBlack();
 767     };
 768
 769     T* FIND(T* pT)
 770     {
 771         RBNODE<T>* pX = pRoot->pLeft;
 772         if((pX != pNil) && (pX != pRoot))
 773         {
 774             int cmp = pX->tVal->ComparedTo(pT);
 775             while(cmp != 0)
 776             {
 777                 if(cmp > 0)
 778                     pX = pX->pLeft;
 779                 else
 780                     pX = pX->pRight;
 781                 if(pX == pNil)
 782                     return NULL;
 783                 cmp = pX->tVal->ComparedTo(pT);
 784             }
 785             return pX->tVal;
 786         }
 787         return NULL;
 788     };
 789 };
 790
 791 #ifdef _PREFAST_
 792 #pragma warning(pop)
 793 #endif
 794
 795 #endif //ASMTEMPLATES_H
 796