HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_ArrayHelp.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_ArrayHelp.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  * Provides simple helper functions for the UT_*Array and UT_Symbol/
10  * HashTable classes.
11  *
12  * Should be private to the UT library, but needs to be exported
13  * so NT style template instantiation will work.
14  */
15 
16 #ifndef __UT_ArrayHelp__
17 #define __UT_ArrayHelp__
18 
19 #include "UT_API.h"
20 
21 #include <SYS/SYS_Types.h>
22 #include <SYS/SYS_BitUtil.h>
23 typedef int (*ut_ptr_compare_func_t)(const void *, const void *);
24 
25 // NOTE: These must be powers of two. See UTbumpAlloc below.
26 #define SMALL_ALLOC 16
27 #define BIG_ALLOC 128
28 
29 // Computes the size of a constant-sized array (e.g. int foo[10]).
30 // Only use when a constant expression is needed. Otherwise, use the templated
31 // version below for type safety.
32 #define UT_ARRAYSIZE(A) (sizeof(A)/sizeof(A[0]))
33 
34 // Better than the UT_ARRAYSIZE() macro, since it validates that
35 // the argument is actually an array (and so you can't pass a pointer).
36 // Can't be used as a constant expression in MSVC2008, however.
37 template<typename A, exint N>
38 exint UTarraySize(A(&)[N]) { return N; }
39 
40 
41 /// This routine describes how to change the size of an array.
42 /// It must increase the current_size by at least one!
43 ///
44 /// Current expected sequence of small sizes:
45 /// 4, 8, 16, 32, 48, 64, 80, 96, 112,
46 /// 128, 256, 384, 512, 640, 768, 896, 1024,
47 /// (increases by approx factor of 1.125 each time after this)
48 template <typename T>
49 static inline T
50 UTbumpAlloc(T current_size)
51 {
52  // For small values, we increment by fixed amounts. For
53  // large values, we increment by one eighth of the current size.
54  // This prevents n^2 behaviour with allocation one element at a time.
55  // A factor of 1/8 will waste 1/16 the memory on average, and will
56  // double the size of the array in approximately 6 reallocations.
57  if (current_size < T(8))
58  {
59  return (current_size < T(4)) ? T(4) : T(8);
60  }
61  if (current_size < T(BIG_ALLOC))
62  {
63  // Snap up to next multiple of SMALL_ALLOC (must be power of 2)
64  return (current_size + T(SMALL_ALLOC)) & ~T(SMALL_ALLOC-1);
65  }
66  if (current_size < T(BIG_ALLOC * 8))
67  {
68  // Snap up to next multiple of BIG_ALLOC (must be power of 2)
69  return (current_size + T(BIG_ALLOC)) & ~T(BIG_ALLOC-1);
70  }
71 
72  T bump = current_size >> 3; // Divided by 8.
73  current_size += bump;
74  return current_size;
75 }
76 
77 // This function is used by the symbol tables to bump to the next/previous
78 // prime size.
79 UT_API exint UTbumpAllocToPrime(exint current_size);
81 
82 #endif
83 
int(* ut_ptr_compare_func_t)(const void *, const void *)
Definition: UT_ArrayHelp.h:23
UT_API exint UTdecreaseAllocToPrime(exint current_size)
UT_API exint UTbumpAllocToPrime(exint current_size)
#define UT_API
Definition: UT_API.h:12
int64 exint
Definition: SYS_Types.h:115
exint UTarraySize(A(&)[N])
Definition: UT_ArrayHelp.h:38
typedef int
Definition: png.h:1175
#define SMALL_ALLOC
Definition: UT_ArrayHelp.h:26
#define BIG_ALLOC
Definition: UT_ArrayHelp.h:27
GA_API const UT_StringHolder N