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
13inline 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")*/
25template <class T>
26class LIST_EL
27{
28public:
29 T* m_Ptr;
30 LIST_EL <T> *m_Next;
31 LIST_EL(T *item) {m_Next = NULL; m_Ptr = item; };
32};
33
34template <class T>
35class LIFO
36{
37public:
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 };
57private:
58 LIST_EL <T> *m_pHead;
59 LIST_EL <T> *m_pTemp;
60};
61
62
63template <class T>
64class FIFO
65{
66public:
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; };
129private:
130 T** m_Arr;
131 ULONG m_ulCount;
132 ULONG m_ulOffset;
133 ULONG m_ulArrLen;
134};
135
136
137template <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//
201template <class T>
202class FIFO_INDEXED
203{
204public:
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())); };
280private:
281 T*** m_Arr;
282 ULONG m_ulCount;
283 ULONG m_ulOffset;
284 ULONG m_ulArrLen;
285 Indx256<T> m_Index;
286};
287
288template <class T>
289class SORTEDARRAY
290{
291public:
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 };
459private:
460 T** m_Arr;
461 ULONG m_ulCount;
462 ULONG m_ulOffset;
463 ULONG m_ulArrLen;
464};
465
466template <class T> struct RBNODE
467{
468private:
469 DWORD dwRed;
470public:
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
496template <class T> class RBNODEBUCKET
497{
498private:
499 RBNODEBUCKET<T>* pNext;
500 RBNODE<T> bucket[BUCKETCOUNT];
501 unsigned alloc_count;
502
503public:
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
549template <class T> class RBNODEPOOL
550{
551private:
552 RBNODEBUCKET<T> base;
553
554public:
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
591template <class T> class RBTREE
592{
593private:
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
684public:
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
797