1 // This file is part of the ustl library, an STL implementation.
3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
4 // This file is free software, distributed under the MIT License.
8 /// \brief Utility templates.
10 /// Everything in here except min(), max(), distance(), and advance()
11 /// are uSTL extensions and are absent from other STL implementations.
14 #ifndef UUTILITY_H_6A58BD296269A82A4AAAA4FD19FDB3AC
15 #define UUTILITY_H_6A58BD296269A82A4AAAA4FD19FDB3AC
24 /// Returns the number of elements in a static vector
25 #define VectorSize(v) (sizeof(v) / sizeof(*v))
27 // Old compilers will not be able to evaluate *v on an empty vector.
28 // The tradeoff here is that VectorSize will not be able to measure arrays of local structs.
29 #define VectorSize(v) (sizeof(v) / ustl::size_of_elements(1, v))
32 /// Expands into a ptr,size expression for the given static vector; useful as link arguments.
33 #define VectorBlock(v) (v)+0, VectorSize(v) // +0 makes it work under gcc 2.95
34 /// Expands into a begin,end expression for the given static vector; useful for algorithm arguments.
35 #define VectorRange(v) VectorBlock(v)+(v)
37 /// Indexes into a static array with bounds limit
38 #define VectorElement(v,i) v[min(uoff_t(i),uoff_t(VectorSize(v)-1))]
40 /// Returns the number of bits in the given type
41 #define BitsInType(t) (sizeof(t) * CHAR_BIT)
43 /// Returns the mask of type \p t with the lowest \p n bits set.
44 #define BitMask(t,n) (t(~t(0)) >> ((sizeof(t) * CHAR_BIT) - (n)))
46 /// Argument that is used only in debug builds (as in an assert)
53 /// Shorthand for container iteration.
54 #define foreach(type,i,ctr) for (type i = (ctr).begin(); i != (ctr).end(); ++ i)
55 /// Shorthand for container reverse iteration.
56 #define eachfor(type,i,ctr) for (type i = (ctr).rbegin(); i != (ctr).rend(); ++ i)
58 #ifndef DOXYGEN_SHOULD_SKIP_THIS
59 // Macro for passing template types as macro arguments.
60 // These are deprecated. Use metamac macros instead. Will remove by next release.
61 #define TEMPLATE_FULL_DECL1(d1,t1) template <d1 t1>
62 #define TEMPLATE_FULL_DECL2(d1,t1,d2,t2) template <d1 t1, d2 t2>
63 #define TEMPLATE_FULL_DECL3(d1,t1,d2,t2,d3,t3) template <d1 t1, d2 t2, d3 t3>
64 #define TEMPLATE_DECL1(t1) TEMPLATE_FULL_DECL1(typename,t1)
65 #define TEMPLATE_DECL2(t1,t2) TEMPLATE_FULL_DECL2(typename,t1,typename,t2)
66 #define TEMPLATE_DECL3(t1,t2,t3) TEMPLATE_FULL_DECL3(typename,t1,typename,t2,typename,t3)
67 #define TEMPLATE_TYPE1(type,a1) type<a1>
68 #define TEMPLATE_TYPE2(type,a1,a2) type<a1,a2>
69 #define TEMPLATE_TYPE3(type,a1,a2,a3) type<a1,a2,a3>
72 /// Returns the minimum of \p a and \p b
73 template <typename T1
, typename T2
>
74 inline T1
min (const T1
& a
, const T2
& b
)
76 return (a
< b
? a
: b
);
79 /// Returns the maximum of \p a and \p b
80 template <typename T1
, typename T2
>
81 inline T1
max (const T1
& a
, const T2
& b
)
83 return (b
< a
? a
: b
);
86 /// \brief Divides \p n1 by \p n2 and rounds the result up.
87 /// This is in contrast to regular division, which rounds down.
88 /// Negative numbers are rounded down because they are an unusual case, supporting
89 /// which would require a branch. Since this is frequently used in graphics, the
90 /// speed is important.
92 template <typename T1
, typename T2
>
93 inline T1
DivRU (T1 n1
, T2 n2
)
95 return (n1
/ n2
+ (n1
% n2
> 0));
98 /// The alignment performed by default.
99 const size_t c_DefaultAlignment
= __alignof__(void*);
101 /// \brief Rounds \p n up to be divisible by \p grain
102 template <typename T
>
103 inline T
Align (T n
, size_t grain
= c_DefaultAlignment
)
106 T a
= n
+ (grain
- r
);
110 /// Returns a NULL pointer cast to T.
111 template <typename T
>
112 inline T
* NullPointer (void)
113 { return ((T
*) NULL
); }
115 /// \brief Returns a non-dereferentiable value reference.
116 /// This is useful for passing to alignof or the like which need a value but
117 /// don't need to actually use it.
118 template <typename T
>
119 inline T
& NullValue (void)
120 { return (*NullPointer
<T
>()); }
122 /// Offsets an iterator
123 template <typename T
>
124 inline T
advance (T i
, ssize_t offset
)
129 #ifndef DOXYGEN_SHOULD_SKIP_THIS
130 /// Offsets a void pointer
132 inline const void* advance (const void* p
, ssize_t offset
)
134 assert (p
|| !offset
);
135 return (reinterpret_cast<const uint8_t*>(p
) + offset
);
138 /// Offsets a void pointer
140 inline void* advance (void* p
, ssize_t offset
)
142 assert (p
|| !offset
);
143 return (reinterpret_cast<uint8_t*>(p
) + offset
);
147 /// Returns the difference \p p1 - \p p2
148 template <typename T1
, typename T2
>
149 inline ptrdiff_t distance (T1 i1
, T2 i2
)
154 #ifndef DOXYGEN_SHOULD_SKIP_THIS
155 #define UNVOID_DISTANCE(T1const,T2const) \
156 template <> inline ptrdiff_t distance (T1const void* p1, T2const void* p2) \
157 { return ((T2const uint8_t*)(p2) - (T1const uint8_t*)(p1)); }
159 UNVOID_DISTANCE(const,const)
160 UNVOID_DISTANCE(,const)
161 UNVOID_DISTANCE(const,)
162 #undef UNVOID_DISTANCE
165 /// \brief Returns the absolute value of \p v
166 /// Unlike the stdlib functions, this is inline and works with all types.
167 template <typename T
>
170 return (v
< 0 ? -v
: v
);
173 /// \brief Returns -1 for negative values, 1 for positive, and 0 for 0
174 template <typename T
>
177 return ((0 < v
) - (v
< 0));
180 /// Returns the absolute value of the distance i1 and i2
181 template <typename T1
, typename T2
>
182 inline size_t abs_distance (T1 i1
, T2 i2
)
184 return (absv (distance(i1
, i2
)));
187 /// Returns the size of \p n elements of size \p T
188 template <typename T
>
189 inline size_t size_of_elements (size_t n
, const T
*)
191 return (n
* sizeof(T
));
194 // Defined in byteswap.h, which is usually unusable.
199 #if CPU_HAS_CMPXCHG8 // If it has that, it has bswap.
200 inline uint16_t bswap_16 (uint16_t v
) { asm ("rorw $8, %w0" : "=r"(v
) : "0"(v
) : "cc"); return (v
); }
201 inline uint32_t bswap_32 (uint32_t v
) { asm ("bswap %0" : "=r"(v
) : "0"(v
)); return (v
); }
203 inline uint16_t bswap_16 (uint16_t v
) { return (v
<< 8 | v
>> 8); }
204 inline uint32_t bswap_32 (uint32_t v
) { return (v
<< 24 | (v
& 0xFF00) << 8 | (v
>> 8) & 0xFF00 | v
>> 24); }
207 inline uint64_t bswap_64 (uint64_t v
) { return ((uint64_t(bswap_32(v
)) << 32) | bswap_32(v
>> 32)); }
210 /// \brief Swaps the byteorder of \p v.
211 template <typename T
>
212 inline T
bswap (const T
& v
)
214 switch (BitsInType(T
)) {
216 case 16: return (T (bswap_16 (uint16_t (v
))));
217 case 32: return (T (bswap_32 (uint32_t (v
))));
219 case 64: return (T (bswap_64 (uint64_t (v
))));
224 #if BYTE_ORDER == BIG_ENDIAN
225 template <typename T
> inline T
le_to_native (const T
& v
) { return (bswap (v
)); }
226 template <typename T
> inline T
be_to_native (const T
& v
) { return (v
); }
227 template <typename T
> inline T
native_to_le (const T
& v
) { return (bswap (v
)); }
228 template <typename T
> inline T
native_to_be (const T
& v
) { return (v
); }
229 #elif BYTE_ORDER == LITTLE_ENDIAN
230 template <typename T
> inline T
le_to_native (const T
& v
) { return (v
); }
231 template <typename T
> inline T
be_to_native (const T
& v
) { return (bswap (v
)); }
232 template <typename T
> inline T
native_to_le (const T
& v
) { return (v
); }
233 template <typename T
> inline T
native_to_be (const T
& v
) { return (bswap (v
)); }
236 /// Deletes \p p and sets it to NULL
237 template <typename T
>
238 inline void Delete (T
*& p
)
244 /// Deletes \p p as an array and sets it to NULL
245 template <typename T
>
246 inline void DeleteVector (T
*& p
)
252 /// Template of making != from ! and ==
253 template <typename T
>
254 inline bool operator!= (const T
& x
, const T
& y
)
259 /// Template of making > from <
260 template <typename T
>
261 inline bool operator> (const T
& x
, const T
& y
)
266 /// Template of making <= from < and ==
267 template <typename T
>
268 inline bool operator<= (const T
& x
, const T
& y
)
273 /// Template of making >= from < and ==
274 template <typename T
>
275 inline bool operator>= (const T
& x
, const T
& y
)
280 /// Packs \p s multiple times into \p b. Useful for loop unrolling.
281 template <typename TSmall
, typename TBig
>
282 inline void pack_type (TSmall s
, TBig
& b
)
284 const size_t n
= sizeof(TBig
) / sizeof(TSmall
);
286 // Calls to min are here to avoid warnings for shifts bigger than the type. min will be gone when optimized.
288 b
= (b
<< min (BitsInType(TSmall
), BitsInType(TBig
))) | b
;
290 b
= (b
<< min (BitsInType(TSmall
) * 2, BitsInType(TBig
))) | b
;
292 b
= (b
<< min (BitsInType(TSmall
) * 4, BitsInType(TBig
))) | b
;
296 inline bool TestAndSet (int* pm
) __attribute__((always_inline
));
298 /// Sets the contents of \p pm to 1 and returns true if the previous value was 0.
299 inline bool TestAndSet (int* pm
)
304 asm volatile ( // cmpxchg compares to %eax and swaps if equal
305 "cmpxchgl %3, %1\n\t"
307 : "=a" (rv
), "=m" (*pm
), "=r" (oldVal
)
308 : "2" (oldVal
), "a" (0)
311 #elif __i386__ || __x86_64__
313 asm volatile ("xchgl %0, %1" : "=r"(oldVal
), "=m"(*pm
) : "0"(oldVal
), "m"(*pm
) : "memory");
315 #elif __sparc32__ // This has not been tested
317 asm volatile ("ldstub %1, %0" : "=r"(rv
), "=m"(*pm
) : "m"(pm
));
320 const int oldVal (*pm
);
326 /// \brief This template is to be used for dereferencing a type-punned pointer without a warning.
328 /// When casting a local variable to an unrelated type through a pointer (for
329 /// example, casting a float to a uint32_t without conversion), the resulting
330 /// memory location can be accessed through either pointer, which violates the
331 /// strict aliasing rule. While -fno-strict-aliasing option can be given to
332 /// the compiler, eliminating this warning, inefficient code may result in
333 /// some instances, because aliasing inhibits some optimizations. By using
334 /// this template, and by ensuring the memory is accessed in one way only,
335 /// efficient code can be produced without the warning. For gcc 4.1.0+.
337 template <typename DEST
, typename SRC
>
338 inline DEST
noalias (const DEST
&, SRC
* s
)
340 asm("":"+g"(s
)::"memory");
341 union UPun
{ SRC s
; DEST d
; };
342 return (((UPun
*)(s
))->d
);
345 template <typename DEST
, typename SRC
>
346 inline DEST
noalias_cast (SRC s
)
348 asm("":"+g"(s
)::"memory");
349 union { SRC s
; DEST d
; } u
= {s
};
354 /// Call after you are done using SIMD algorithms for 64 bit tuples.
356 inline void reset_mmx (void) __attribute__((always_inline
));
357 #define ALL_MMX_REGS_CHANGELIST "mm0","mm1","mm2","mm3","mm4","mm5","mm6","mm7","st","st(1)","st(2)","st(3)","st(4)","st(5)","st(6)","st(7)"
359 inline void reset_mmx (void) { asm ("femms":::ALL_MMX_REGS_CHANGELIST
); }
361 inline void reset_mmx (void) { asm ("emms":::ALL_MMX_REGS_CHANGELIST
); }
364 inline void reset_mmx (void) {}