gwnavruntime/kernel/HeapMH/HeapMH_FreeBin.h Source File

HeapMH_FreeBin.h
Go to the documentation of this file.
1 /*
2 * Copyright 2015 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 /**************************************************************************
8 
9 Filename : HeapMH_FreeBin.h
10 Content :
11 Created : 2010
12 Authors : Maxim Shemanarev
13 
14 Notes : Containers to store information about free memory areas
15 
16 **************************************************************************/
17 
18 #ifndef INC_KY_Kernel_HeapMH_FreeBin_H
19 #define INC_KY_Kernel_HeapMH_FreeBin_H
20 
22 
23 namespace Kaim { namespace HeapMH {
24 
25 //UInt32 Magic;
26 //UInt32 Index;
27 //UByte UseCount;
28 //SByte BitSet;
29 //UByte DataStart;
30 //UByte DataEnd;
31 
32 
33 struct BinNodeMH
34 {
35 #ifdef KY_64BIT_POINTERS
36  enum { MinBlocks = 2 };
37 #else
38  enum { MinBlocks = 1 };
39 #endif
40 
41  UPInt Prev;
42  UPInt Next;
43  PageMH* Page;
44 
45  UPInt GetBlocks() const
46  {
47  return (Prev & 0xF) | ((Next & 0xF) << 4);
48  }
49 
50  UPInt GetBytes() const
51  {
52  return GetBlocks() << PageMH::UnitShift;
53  }
54 
55  UPInt GetPrevBlocks() const
56  {
57  const UPInt* tail = ((const UPInt*)this) - 2;
58  return (tail[0] & 0xF) | ((tail[1] & 0xF) << 4);
59  }
60 
61  UPInt GetPrevBytes() const
62  {
63  return GetPrevBlocks() << PageMH::UnitShift;
64  }
65 
66  void SetBlocks(UPInt blocks)
67  {
68  UPInt bytes = blocks << PageMH::UnitShift;
69  UPInt* tail = ((UPInt*)this) + bytes / sizeof(UPInt) - 2;
70  tail[0] = Prev = (Prev & ~UPInt(0xF)) | (blocks & 0xF);
71  tail[1] = Next = (Next & ~UPInt(0xF)) | (blocks >> 4);
72  }
73 
74  void SetBytes(UPInt bytes)
75  {
76  UPInt blocks = bytes >> PageMH::UnitShift;
77  UPInt* tail = ((UPInt*)this) + bytes / sizeof(UPInt) - 2;
78  tail[0] = Prev = (Prev & ~UPInt(0xF)) | (blocks & 0xF);
79  tail[1] = Next = (Next & ~UPInt(0xF)) | (blocks >> 4);
80  }
81 
82  PageMH* GetPage()
83  {
84  return (GetBlocks() > MinBlocks) ? Page : 0;
85  }
86 
87  void SetPage(PageMH* page)
88  {
89  if (GetBlocks() > MinBlocks)
90  Page = page;
91  }
92 
93  BinNodeMH* GetPrev() const { return (BinNodeMH*)(Prev & ~UPInt(0xF)); }
94  BinNodeMH* GetNext() const { return (BinNodeMH*)(Next & ~UPInt(0xF)); }
95 
96  void SetPrev(BinNodeMH* prev) { Prev = UPInt(prev) | (Prev & 0xF); }
97  void SetNext(BinNodeMH* next) { Next = UPInt(next) | (Next & 0xF); }
98 
99  static BinNodeMH* MakeNode(UByte* start, UPInt bytes, PageMH* page)
100  {
101  BinNodeMH* node = (BinNodeMH*)start;
102  node->SetBytes(bytes);
103  node->SetPage(page);
104  return node;
105  }
106 };
107 
108 
109 //------------------------------------------------------------------------
110 struct ListBinMH
111 {
112  enum { BinSize = 8*sizeof(UPInt) }; // Assume Byte is 8 bits.
113 
114  ListBinMH();
115  void Reset();
116 
117  //--------------------------------------------------------------------
118  void Push(UByte* node);
119  void Pull(UByte* node);
120 
121  BinNodeMH* PullBest(UPInt blocks);
122  BinNodeMH* PullBest(UPInt blocks, UPInt alignMask);
123 
124  void Merge(UByte* node, UPInt bytes, bool left, bool right, PageMH* page);
125 
126  static UByte* GetAlignedPtr(UByte* start, UPInt alignMask);
127  static bool AlignmentIsOK(const BinNodeMH* node, UPInt blocks, UPInt alignMask);
128 
129 private:
130  void pushNode(UPInt idx, BinNodeMH* node);
131  void pullNode(UPInt idx, BinNodeMH* node);
132 
133  BinNodeMH* findAligned(BinNodeMH* root, UPInt blocks, UPInt alignMask);
134 
135 
136  BinNodeMH* getPrevAdjacent(UByte* node) const;
137  BinNodeMH* getNextAdjacent(UByte* node) const;
138 
139  //--------------------------------------------------------------------
140  UPInt Mask;
141  BinNodeMH* Roots[BinSize];
142 };
143 
144 
145 
146 }} // Kaim::HeapMH
147 
148 #endif
Definition: gamekitcrowddispersion.h:20