1 #ifndef __TEMPLATES_H__
2 #define __TEMPLATES_H__
3
4 #include "utypes.h"
5 #include <assert.h>
6
7 #if defined(POSIX)
8 /* Allow over-writing FORCEINLINE from makefile because gcc 3.4.4 for buffalo
9 doesn't seem to support __attribute__((always_inline)) in -O0 build
10 (strangely, it works in -Os build) */
11 #ifndef FORCEINLINE
12 // The always_inline attribute asks gcc to inline the function even if no optimization is being requested.
13 // This macro should be used exclusive-or with the inline directive (use one or the other but not both)
14 // since Microsoft uses __forceinline to also mean inline,
15 // and this code is following a Microsoft compatibility model.
16 // Just setting the attribute without also specifying the inline directive apparently won't inline the function,
17 // as evidenced by multiply-defined symbols found at link time.
18 #define FORCEINLINE inline __attribute__((always_inline))
19 #endif
20 #endif
21
22 #ifdef __GNUC__
23 // Used for gcc tool chains accepting but not supporting pragma pack
24 // See http://gcc.gnu.org/onlinedocs/gcc/Type-Attributes.html
25 #define PACKED_ATTRIBUTE __attribute__((__packed__))
26 #else
27 #define PACKED_ATTRIBUTE
28 #endif
29
30 #ifdef __GNUC__
31 #define ALIGNED_ATTRIBUTE(x) __attribute__((aligned (x)))
32 #else
33 #define ALIGNED_ATTRIBUTE(x)
34 #endif
35
36 // Utility templates
37 #undef min
38 #undef max
39
min(T a,T b)40 template <typename T> static inline T min(T a, T b) { if (a < b) return a; return b; }
max(T a,T b)41 template <typename T> static inline T max(T a, T b) { if (a > b) return a; return b; }
42
min(T a,T b,T c)43 template <typename T> static inline T min(T a, T b, T c) { return min(min(a,b),c); }
max(T a,T b,T c)44 template <typename T> static inline T max(T a, T b, T c) { return max(max(a,b),c); }
clamp(T v,T mi,T ma)45 template <typename T> static inline T clamp(T v, T mi, T ma)
46 {
47 if (v > ma) v = ma;
48 if (v < mi) v = mi;
49 return v;
50 }
51
52 #if (defined(__SVR4) && defined(__sun))
53 #pragma pack(1)
54 #else
55 #pragma pack(push,1)
56 #endif
57
58 namespace aux
59 {
host_to_network(uint16 i)60 FORCEINLINE uint16 host_to_network(uint16 i) { return htons(i); }
host_to_network(uint32 i)61 FORCEINLINE uint32 host_to_network(uint32 i) { return htonl(i); }
host_to_network(int32 i)62 FORCEINLINE int32 host_to_network(int32 i) { return htonl(i); }
network_to_host(uint16 i)63 FORCEINLINE uint16 network_to_host(uint16 i) { return ntohs(i); }
network_to_host(uint32 i)64 FORCEINLINE uint32 network_to_host(uint32 i) { return ntohl(i); }
network_to_host(int32 i)65 FORCEINLINE int32 network_to_host(int32 i) { return ntohl(i); }
66 }
67
68 template <class T>
69 struct PACKED_ATTRIBUTE big_endian
70 {
71 T operator=(T i) { m_integer = aux::host_to_network(i); return i; }
Tbig_endian72 operator T() const { return aux::network_to_host(m_integer); }
73 private:
74 T m_integer;
75 };
76
77 typedef big_endian<int32> int32_big;
78 typedef big_endian<uint32> uint32_big;
79 typedef big_endian<uint16> uint16_big;
80
81 #if (defined(__SVR4) && defined(__sun))
82 #pragma pack(0)
83 #else
84 #pragma pack(pop)
85 #endif
86
87 template<typename T> static inline void zeromem(T *a, size_t count = 1) { memset(a, 0, count * sizeof(T)); }
88
89 typedef int SortCompareProc(const void *, const void *);
90
QuickSortT(T * base,size_t num,int (* comp)(const T *,const T *))91 template<typename T> static FORCEINLINE void QuickSortT(T *base, size_t num, int (*comp)(const T *, const T *)) { qsort(base, num, sizeof(T), (SortCompareProc*)comp); }
92
93
94 // WARNING: The template parameter MUST be a POD type!
95 template <typename T, size_t minsize = 16> class Array {
96 protected:
97 T *mem;
98 size_t alloc,count;
99
100 public:
Array(size_t init)101 Array(size_t init) { Init(init); }
Array()102 Array() { Init(); }
~Array()103 ~Array() { Free(); }
104
Init()105 void inline Init() { mem = NULL; alloc = count = 0; }
Init(size_t init)106 void inline Init(size_t init) { Init(); if (init) Resize(init); }
GetCount()107 size_t inline GetCount() const { return count; }
GetAlloc()108 size_t inline GetAlloc() const { return alloc; }
SetCount(size_t c)109 void inline SetCount(size_t c) { count = c; }
110
111 inline T& operator[](size_t offset) { assert(offset ==0 || offset<alloc); return mem[offset]; }
112 inline const T& operator[](size_t offset) const { assert(offset ==0 || offset<alloc); return mem[offset]; }
113
Resize(size_t a)114 void inline Resize(size_t a) {
115 if (a == 0) { free(mem); Init(); }
116 else { mem = (T*)realloc(mem, (alloc=a) * sizeof(T)); }
117 }
118
Grow()119 void Grow() { Resize(::max<size_t>(minsize, alloc * 2)); }
120
Append(const T & t)121 inline size_t Append(const T &t) {
122 if (count >= alloc) Grow();
123 size_t r=count++;
124 mem[r] = t;
125 return r;
126 }
127
Append()128 T inline &Append() {
129 if (count >= alloc) Grow();
130 return mem[count++];
131 }
132
Compact()133 void inline Compact() {
134 Resize(count);
135 }
136
Free()137 void inline Free() {
138 free(mem);
139 Init();
140 }
141
Clear()142 void inline Clear() {
143 count = 0;
144 }
145
MoveUpLast(size_t index)146 bool inline MoveUpLast(size_t index) {
147 assert(index < count);
148 size_t c = --count;
149 if (index != c) {
150 mem[index] = mem[c];
151 return true;
152 }
153 return false;
154 }
155
MoveUpLastExist(const T & v)156 bool inline MoveUpLastExist(const T &v) {
157 return MoveUpLast(LookupElementExist(v));
158 }
159
LookupElement(const T & v)160 size_t inline LookupElement(const T &v) const {
161 for(size_t i = 0; i != count; i++)
162 if (mem[i] == v)
163 return i;
164 return (size_t) -1;
165 }
166
HasElement(const T & v)167 bool inline HasElement(const T &v) const {
168 return LookupElement(v) != -1;
169 }
170
171 typedef int SortCompareProc(const T *a, const T *b);
172
Sort(SortCompareProc * proc,size_t start,size_t end)173 void Sort(SortCompareProc* proc, size_t start, size_t end) {
174 QuickSortT(&mem[start], end - start, proc);
175 }
176
Sort(SortCompareProc * proc,size_t start)177 void Sort(SortCompareProc* proc, size_t start) {
178 Sort(proc, start, count);
179 }
180
Sort(SortCompareProc * proc)181 void Sort(SortCompareProc* proc) {
182 Sort(proc, 0, count);
183 }
184 };
185
186 #endif //__TEMPLATES_H__
187