HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups 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 /// This routine describes how to change the size of an array.
30 /// It must increase the current_size by at least one!
31 ///
32 /// Current expected sequence of small sizes:
33 /// 4, 8, 16, 32, 48, 64, 80, 96, 112,
34 /// 128, 256, 384, 512, 640, 768, 896, 1024,
35 /// (increases by approx factor of 1.125 each time after this)
36 template <typename T>
37 static inline T
38 UTbumpAlloc(T current_size)
39 {
40  // For small values, we increment by fixed amounts. For
41  // large values, we increment by one eighth of the current size.
42  // This prevents n^2 behaviour with allocation one element at a time.
43  // A factor of 1/8 will waste 1/16 the memory on average, and will
44  // double the size of the array in approximately 6 reallocations.
45  if (current_size < T(8))
46  {
47  return (current_size < T(4)) ? T(4) : T(8);
48  }
49  if (current_size < T(BIG_ALLOC))
50  {
51  // Snap up to next multiple of SMALL_ALLOC (must be power of 2)
52  return (current_size + T(SMALL_ALLOC)) & ~T(SMALL_ALLOC-1);
53  }
54  if (current_size < T(BIG_ALLOC * 8))
55  {
56  // Snap up to next multiple of BIG_ALLOC (must be power of 2)
57  return (current_size + T(BIG_ALLOC)) & ~T(BIG_ALLOC-1);
58  }
59 
60  T bump = current_size >> 3; // Divided by 8.
61  current_size += bump;
62  return current_size;
63 }
64 
65 // This function is used by the symbol tables to bump to the next/previous
66 // prime size.
67 UT_API exint UTbumpAllocToPrime(exint current_size);
69 
70 #endif
71 
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)
int64 exint
Definition: SYS_Types.h:125
#define UT_API
Definition: UT_API.h:13
typedef int(WINAPI *PFNWGLRELEASEPBUFFERDCARBPROC)(HPBUFFERARB hPbuffer
#define SMALL_ALLOC
Definition: UT_ArrayHelp.h:26
#define BIG_ALLOC
Definition: UT_ArrayHelp.h:27