gwnavruntime/kernel/SF_HeapBitSet2.h Source File

SF_HeapBitSet2.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 : KY_HeapBitSet2.h
10 Content :
11 Created : 2009
12 Authors : Maxim Shemanarev
13 
14 Notes : Allocator bit-set maintanance
15 
16 **************************************************************************/
17 
18 #ifndef INC_KY_Kernel_Heap_BitSet2_H
19 #define INC_KY_Kernel_Heap_BitSet2_H
20 
21 #include <string.h>
22 #include "gwnavruntime/kernel/SF_Types.h"
23 
24 namespace Kaim { namespace Heap {
25 
26 // ***** BitSet2
27 //
28 // This class represents a number of static functions for manipulating
29 // with allocation bit-sets. It uses two bits per block, that is, for the
30 // block size = 16 bytes, it will take 1K per every 64K of the payload.
31 // In average the bookkeeping information is less than the losses for minimal
32 // alignment itself. The idea is simple and straightforward. We have two
33 // bits per block that mean the following:
34 //
35 // Variant without alignment shift:
36 //------------------
37 // 00 - empty,
38 // 01 - 1 block
39 // 10 01 - 2 blocks
40 // 11 00 01 - 3 blocks
41 // 11 01 xx 01 - 4 blocks
42 // 11 10 xx xx 01 - 5 blocks
43 //
44 // 11 11 0n nn nn . . . 01 - 6 to 37 blocks. "n nn nn" - is a 5-bit number
45 // of blocks minus 6. 0 means 6 blocks.
46 //
47 // 11 11 11 . . . . . . 01 - 38 or more blocks. Since we have a at least
48 // 68 bits (2*38-6-2), it's guaranteed we can place
49 // a 32-bit number directly. And of course,
50 // it's aligned to 32-bit.
51 //
52 // Variant with alignment shift:
53 //------------------
54 // 00 - empty,
55 // 01 - 1 block
56 // 10 aa - 2 blocks, aa - alignment, 01 or 10
57 // 11 00 aa - 3 blocks, aa - alignment, 01 or 10
58 // 11 01 xx aa - 4 blocks, aa - alignment, 01, 10 or 11
59 // 11 10 xx xx aa - 5 blocks, aa - alignment, 01, 10 or 11
60 //
61 // 11 11 0n nn nn aa - 6 blocks. "n nn nn" - is a 5-bit number
62 // of blocks minus 6. "0 00 00" means 6 blocks.
63 // aa - alignment: 01, 10 or 11.
64 //
65 // 11 11 0n nn nn xx aa - 7 blocks. "n nn nn" equals "0 00 01" in this case.
66 // aa - alignment: 01, 10 or 11
67 //
68 // 11 11 0n nn nn aa aa a1 - 8 to 37 blocks. "aa aa a" - is a 5-bit alignment
69 // shift value, that is, 0:1, 1:2, 2:4, 3:8, etc.
70 //
71 // 11 11 11 . . . aa aa a1 - 38 or more blocks. Since we have a at least
72 // 64 bits (2*38-6-6), it's guaranteed we can place
73 // a 32-bit number directly. And of course,
74 // it's aligned to 32-bit.
75 //------------------------------------------------------------------------
76 class BitSet2
77 {
78 public:
79  // Calculate the number of 32-bit words needed for the
80  // bit-set with the particular data alignment. For example,
81  // 16-byte blocks must have alignmentShift=4.
82  //--------------------------------------------------------------------
83  static UPInt GetBitSetSize(UPInt dataSize, UPInt alignmentShift)
84  {
85  UPInt alignmentMask = (UPInt(1) << alignmentShift) - 1;
86  return (((dataSize + alignmentMask) >> alignmentShift) + 15) / 16;
87  }
88 
89  static void Clear(UInt32* buf, UPInt numWords)
90  {
91  memset(buf, 0, sizeof(UInt32) * numWords);
92  }
93 
94  // Get the two-bit value at the particular idx.
95  //--------------------------------------------------------------------
96  KY_INLINE static unsigned GetValue(const UInt32* buf, UPInt idx)
97  {
98  return (buf[idx >> 4] >> (2*idx & 30)) & 3;
99  }
100 
101  // Clear the two-bit value at the particular idx.
102  //--------------------------------------------------------------------
103  KY_INLINE static void ClearValue(UInt32* buf, UPInt idx)
104  {
105  buf[idx >> 4] &= ~(UInt32(3) << (2*idx & 30));
106  }
107 
108  // Set the two-bit value at the particular idx.
109  //--------------------------------------------------------------------
110  KY_INLINE static void SetValue(UInt32* buf, UPInt idx, unsigned val)
111  {
112  UPInt wrd = idx >> 4;
113  UPInt rem = 2*idx & 30;
114  buf[wrd] = (buf[wrd] & ~(UInt32(3) << rem)) | (UInt32(val) << rem);
115  }
116 
117  // Mark the array of blocks as empty. We need to mark the first
118  // and the last values as 00. It's necessary for proper merging.
119  //--------------------------------------------------------------------
120  KY_INLINE static void MarkFree(UInt32* buf, UPInt start, UPInt num)
121  {
122  ClearValue(buf, start);
123  ClearValue(buf, start+num-1);
124  }
125 
126  // Mark the array of blocks as busy without alignment info.
127  // The first and the last values must be non-zero for proper merging.
128  // The other bits are set according to the described above encoding method.
129  //--------------------------------------------------------------------
130  static void MarkBusy(UInt32* buf, UPInt start, UPInt num)
131  {
132  switch(num)
133  {
134  case 0:
135  case 1:
136  SetValue(buf, start, 1);
137  return;
138 
139  case 2:
140  SetValue(buf, start, 2);
141  break;
142 
143  case 3:
144  case 4:
145  case 5:
146  SetValue(buf, start, 3);
147  SetValue(buf, start+1, unsigned(num-3));
148  break;
149 
150  default:
151  if (num < 38)
152  {
153  unsigned n6 = unsigned(num-6);
154  SetValue(buf, start, 3);
155  SetValue(buf, start+1, 3);
156  SetValue(buf, start+2, n6 >> 4);
157  SetValue(buf, start+3, (n6 >> 2) & 3);
158  SetValue(buf, start+4, n6 & 3);
159  }
160  else
161  {
162  SetValue(buf, start, 3);
163  SetValue(buf, start+1, 3);
164  SetValue(buf, start+2, 3);
165  buf[(2*start + 6 + 31) >> 5] = UInt32(num);
166  }
167  break;
168  }
169  SetValue(buf, start+num-1, 1);
170  }
171 
172 
173  // Mark the array of blocks as busy with alignment info.
174  // The first and the last values must be non-zero for proper merging.
175  // The other bits are set according to the described above encoding method.
176  //--------------------------------------------------------------------
177  static void MarkBusy(UInt32* buf, UPInt start, UPInt num, UPInt alignShift)
178  {
179  switch(num)
180  {
181  case 0:
182  case 1:
183  SetValue(buf, start, 1);
184  return;
185 
186  case 2:
187  SetValue(buf, start, 2);
188  SetValue(buf, start+1, unsigned(alignShift+1));
189  return;
190 
191  case 3:
192  case 4:
193  case 5:
194  SetValue(buf, start, 3);
195  SetValue(buf, start+1, unsigned(num-3));
196  SetValue(buf, start+num-1, unsigned(alignShift+1));
197  return;
198 
199  case 6:
200  case 7:
201  SetValue(buf, start, 3);
202  SetValue(buf, start+1, 3);
203  SetValue(buf, start+2, 0);
204  SetValue(buf, start+3, 0);
205  SetValue(buf, start+4, unsigned(num-6));
206  SetValue(buf, start+num-1, unsigned(alignShift+1));
207  return;
208 
209  default:
210  {
211  if (num < 38)
212  {
213  unsigned n6 = unsigned(num-6);
214  SetValue(buf, start, 3);
215  SetValue(buf, start+1, 3);
216  SetValue(buf, start+2, n6 >> 4);
217  SetValue(buf, start+3, (n6 >> 2) & 3);
218  SetValue(buf, start+4, n6 & 3);
219  }
220  else
221  {
222  SetValue(buf, start, 3);
223  SetValue(buf, start+1, 3);
224  SetValue(buf, start+2, 3);
225  buf[(2*start + 6 + 31) >> 5] = UInt32(num);
226  }
227  unsigned a = unsigned(alignShift << 1) | 1;
228  SetValue(buf, start+num-3, a >> 4);
229  SetValue(buf, start+num-2, (a >> 2) & 3);
230  SetValue(buf, start+num-1, a & 3);
231  }
232  return;
233  }
234  }
235 
236  // Calculate the block size according to the described above
237  // encoding method.
238  //--------------------------------------------------------------------
239  static UPInt GetBlockSize(const UInt32* buf, UPInt start)
240  {
241  unsigned size;
242  size = GetValue(buf, start);
243  if (size < 3)
244  {
245  return size;
246  }
247  size = GetValue(buf, start+1);
248  if (size < 3)
249  {
250  return size+3;
251  }
252  size = GetValue(buf, start+2);
253  if (size < 3)
254  {
255  return 6 + ((size << 4) |
256  (GetValue(buf, start+3) << 2) |
257  GetValue(buf, start+4));
258  }
259  return buf[(2*start + 6 + 31) >> 5];
260  }
261 
262  //--------------------------------------------------------------------
263  static unsigned GetAlignShift(const UInt32* buf, UPInt start, UPInt num)
264  {
265  if (num < 8)
266  {
267  return GetValue(buf, start+num-1) - 1;
268  }
269  else
270  {
271  return (GetValue(buf, start+num-1) >> 1)|
272  (GetValue(buf, start+num-2) << 1)|
273  (GetValue(buf, start+num-3) << 3);
274  }
275 
276  }
277 };
278 
279 
280 }} // Kaim::Heap
281 
282 #endif
SF_Types.h
Kaim
Definition: gamekitcrowddispersion.h:20
Please send us your comment about this page