gwnavruntime/kernel/HeapPT/HeapPT_AllocLite.h Source File

HeapPT_AllocLite.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 : HeapPT_AllocLite.h
10 Content : Allocator based on binary search trees
11 Created : 2009
12 Authors : Maxim Shemanarev
13 
14 Notes : The granulator requests the system allocator for
15  large memory blocks and granulates them as necessary,
16  providing smaller granularity to the consumer.
17 
18 **************************************************************************/
19 
20 #ifndef INC_KY_Kernel_HeapPT_AllocLite_H
21 #define INC_KY_Kernel_HeapPT_AllocLite_H
22 
23 #include "gwnavruntime/kernel/SF_List.h"
24 #include "gwnavruntime/kernel/SF_RadixTree.h"
25 #include "gwnavruntime/kernel/SF_HeapTypes.h"
26 
27 namespace Kaim {
28 
29 namespace Heap { class SegVisitor; }
30 
31 namespace HeapPT {
32 
33 using namespace Heap;
34 
35 //------------------------------------------------------------------------
36 struct HdrPage;
37 struct TreeSeg
38 {
39  TreeSeg* AddrParent;
40  TreeSeg* AddrChild[2];
41  HdrPage* Headers;
42  UByte* Buffer;
43  UPInt Size;
44  UPInt UseCount;
45  UPIntHalf AlignShift;
46  UPIntHalf HeadBytes;
47 };
48 
49 
50 //------------------------------------------------------------------------
51 struct DualTNode : ListNode<DualTNode>
52 {
53  DualTNode* Parent;
54  DualTNode* Child[2];
55  DualTNode* AddrParent;
56  DualTNode* AddrChild[2];
57  TreeSeg* ParentSeg;
58  UPInt Size;
59 
60  //--------------------------------------------------------------------
61  static KY_INLINE UByte* GetAlignedPtr(UByte* start, UPInt alignMask)
62  {
63  UPInt aligned = (UPInt(start) + alignMask) & ~alignMask;
64  UPInt head = aligned - UPInt(start);
65  while (head && head < 16*sizeof(void*))
66  {
67  aligned += alignMask+1;
68  head += alignMask+1;
69  }
70  return (UByte*)aligned;
71  }
72 
73  KY_INLINE bool AlignmentIsOK(UPInt blocks, UPInt shift, UPInt alignMask) const
74  {
75  UPInt bytes = blocks << shift;
76  UPInt aligned = UPInt(GetAlignedPtr((UByte*)this, alignMask));
77  return aligned + bytes <= UPInt(this) + (Size << shift);
78  }
79 };
80 
81 //------------------------------------------------------------------------
82 class AllocLite
83 {
84  typedef DualTNode FreeNode;
85 
86 public:
87  //--------------------------------------------------------------------
88  struct SizeAccessor
89  {
90  static UPInt GetKey (const FreeNode* n) { return n->Size; }
91  static FreeNode* GetChild ( FreeNode* n, UPInt i) { return n->Child[i]; }
92  static const FreeNode* GetChild (const FreeNode* n, UPInt i) { return n->Child[i]; }
93  static FreeNode** GetChildPtr( FreeNode* n, UPInt i) { return &n->Child[i]; }
94 
95  static FreeNode* GetParent ( FreeNode* n) { return n->Parent; }
96  static const FreeNode* GetParent (const FreeNode* n) { return n->Parent; }
97 
98  static void SetParent (FreeNode* n, FreeNode* p) { n->Parent = p; }
99  static void SetChild (FreeNode* n, UPInt i, FreeNode* c) { n->Child[i] = c; }
100  static void ClearLinks(FreeNode* n) { n->Parent = n->Child[0] = n->Child[1] = 0; }
101  };
102 
103  //--------------------------------------------------------------------
104  struct AddrAccessor
105  {
106  static UPInt GetKey (const FreeNode* n) { return UPInt(n); }
107  static FreeNode* GetChild ( FreeNode* n, UPInt i) { return n->AddrChild[i]; }
108  static const FreeNode* GetChild (const FreeNode* n, UPInt i) { return n->AddrChild[i]; }
109  static FreeNode** GetChildPtr( FreeNode* n, UPInt i) { return &n->AddrChild[i]; }
110 
111  static FreeNode* GetParent ( FreeNode* n) { return n->AddrParent; }
112  static const FreeNode* GetParent (const FreeNode* n) { return n->AddrParent; }
113 
114  static void SetParent (FreeNode* n, FreeNode* p) { n->AddrParent = p; }
115  static void SetChild (FreeNode* n, UPInt i, FreeNode* c) { n->AddrChild[i] = c; }
116  static void ClearLinks(FreeNode* n) { n->AddrParent = n->AddrChild[0] = n->AddrChild[1] = 0; }
117  };
118 
119 public:
120  //--------------------------------------------------------------------
121  enum ReallocResult
122  {
123  // Don't change these values because the check for successful
124  // operation looks like (res < ReallocFailed).
125  ReallocSucceeded = 0,
126  ReallocShrinkedAtTail = 1,
127  ReallocFailed = 2,
128  ReallocFailedAtTail = 3
129  };
130 
131  AllocLite(UPInt minSize);
132 
133  void InitSegment(TreeSeg* seg);
134  void ReleaseSegment(TreeSeg* seg);
135 
136  void* Alloc(UPInt size, UPInt alignSize, TreeSeg** allocSeg);
137  void Free(TreeSeg* seg, void* ptr, UPInt size, UPInt alignSize);
138 
139  ReallocResult ReallocInPlace(TreeSeg* seg, void* ptr, UPInt oldSize,
140  UPInt newSize, UPInt alignSize);
141 
142  void Extend(TreeSeg* seg, UPInt incSize);
143  bool TrimAt(TreeSeg* seg, UByte* ptrAt);
144 
145  UPInt GetMinSize() const { return MinSize; }
146  UPInt GetFreeBytes() const { return FreeBlocks << MinShift; }
147  void VisitMem(MemVisitor* visitor, MemVisitor::Category cat) const;
148  void VisitUnused(SegVisitor* visitor, unsigned cat) const;
149 
150 private:
151  //--------------------------------------------------------------------
152  typedef RadixTreeMulti<FreeNode, SizeAccessor> SizeTreeType;
153  typedef RadixTree <FreeNode, AddrAccessor> AddrTreeType;
154 
155  //--------------------------------------------------------------------
156  void pushNode(FreeNode* node, TreeSeg* seg, UPInt blocks);
157  void pullNode(FreeNode* node);
158  FreeNode* pullBest(UPInt blocks);
159  FreeNode* pullBest(UPInt blocks, UPInt alignMask);
160  void splitNode(FreeNode* node, UByte* start, UPInt size);
161 
162  void visitTree(const FreeNode* root,
163  HeapSegment* seg,
164  MemVisitor* visitor,
165  MemVisitor::Category cat) const;
166 
167  void visitUnusedNode(const FreeNode* node,
168  SegVisitor* visitor,
169  unsigned cat) const;
170 
171  void visitUnusedInTree(const FreeNode* root,
172  SegVisitor* visitor,
173  unsigned cat) const;
174 
175  //--------------------------------------------------------------------
176  UPInt MinShift;
177  UPInt MinSize;
178  UPInt MinMask;
179  SizeTreeType SizeTree;
180  AddrTreeType AddrTree;
181  UPInt FreeBlocks;
182 };
183 
184 }} // Kaim::Heap
185 
186 #endif
SF_RadixTree.h
SF_HeapTypes.h
Kaim
Definition: gamekitcrowddispersion.h:20
SF_List.h
Please send us your comment about this page