1 /*---------------------------------------------------------------------------*
2   Project:  Horizon
3   File:     util_Bits.h
4 
5   Copyright (C)2009-2012 Nintendo Co., Ltd.  All rights reserved.
6 
7   These coded instructions, statements, and computer programs contain
8   proprietary information of Nintendo of America Inc. and/or Nintendo
9   Company Ltd., and are protected by Federal copyright law.  They may
10   not be disclosed to third parties or copied or duplicated in any form,
11   in whole or in part, without the prior written consent of Nintendo.
12 
13   $Rev:$
14  *---------------------------------------------------------------------------*/
15 
16 #ifdef __cplusplus
17 
18 #ifndef NN_UTIL_UTIL_BITS_H_
19 #define NN_UTIL_UTIL_BITS_H_
20 
21 namespace nn { namespace util {
22 
23 struct Bit32Set
24 {
25     bit32 n;
GetBit32Set26     bool Get(int i) const { return n & (1 << i); }
Set0Bit32Set27     void Set0(int i) { n &= ~(1 << i); }
Set1Bit32Set28     void Set1(int i) { n |= (1 << i); }
29 };
30 
31 class Bit32Allocator
32 {
33 private:
34 
35     Bit32Set m_N;
36 
37 public:
38 
Bit32Allocator()39     Bit32Allocator() {}
40 
Bit32Allocator(int size)41     Bit32Allocator(int size)
42     {
43         this->Initialize(size);
44     }
45 
Initialize(int size)46     void Initialize(int size)
47     {
48         this->m_N.n = ~(~0 << size);
49     }
50 
Allocate()51     int Allocate()
52     {
53         int clz = __clz(m_N.n);
54         if (clz < 32)
55         {
56             int i = 31 - clz;
57             m_N.Set0(i);
58             return i;
59         }
60         return -1;
61     }
62 
Deallocate(int i)63     void Deallocate(int i)
64     {
65         if (m_N.Get(i))
66         {
67             NN_TPANIC_("");
68         }
69         m_N.Set1(i);
70     }
71 
72 };
73 
74 namespace detail {
75 
76     class BitsAllocatorBase
77     {
78     protected:
79 
BitsAllocatorBase(Bit32Allocator * bits,int size,int n)80         BitsAllocatorBase(Bit32Allocator* bits, int size, int n)
81         {
82             for (int i = 0; i < n; ++i)
83             {
84                 if (size <= 32)
85                 {
86                     bits[i].Initialize(size);
87                     return;
88                 }
89                 else
90                 {
91                     bits[i].Initialize(32);
92                     size -= 32;
93                 }
94             }
95             NN_TPANIC_("");
96         }
97 
AllocateImpl(Bit32Allocator * bits,int n)98         int AllocateImpl(Bit32Allocator* bits, int n)
99         {
100             for (int i = 0; i < n; ++i)
101             {
102                 int j = bits[i].Allocate();
103                 if (j >= 0)
104                 {
105                     return i * 32 + j;
106                 }
107             }
108             return -1;
109         }
110 
DeallocateImpl(Bit32Allocator * bits,int i)111         void DeallocateImpl(Bit32Allocator* bits, int i)
112         {
113             bits[i / 32].Deallocate(i % 32);
114         }
115 
116     };
117 
118     template <int N>
119     class BitsAllocatorTemplate : private BitsAllocatorBase
120     {
121     private:
122         Bit32Allocator m_Bits[N];
123     public:
BitsAllocatorTemplate(int size)124         BitsAllocatorTemplate(int size) : BitsAllocatorBase(m_Bits, size, N) {}
Allocate()125         int Allocate() { return BitsAllocatorBase::AllocateImpl(m_Bits, N); }
Deallocate(int i)126         void Deallocate(int i) { BitsAllocatorBase::DeallocateImpl(m_Bits, i); }
127     };
128 
129 }
130 
131 template <int N>
132 class BitsAllocator : public detail::BitsAllocatorTemplate<(N - 1) / 32 + 1>
133 {
134 public:
BitsAllocator()135     BitsAllocator() : detail::BitsAllocatorTemplate<(N - 1) / 32 + 1>(N) {}
136 };
137 
138 }}
139 
140 
141 #endif
142 
143 #endif
144