00001 // This is core/vnl/vnl_alloc.h 00002 #ifndef vnl_alloc_h_ 00003 #define vnl_alloc_h_ 00004 #ifdef VCL_NEEDS_PRAGMA_INTERFACE 00005 #pragma interface 00006 #endif 00007 //: 00008 // \file 00009 // \author unknown 00010 // 00011 // \brief Default node allocator. 00012 // 00013 // With a reasonable compiler, this should be roughly as fast as the 00014 // original STL class-specific allocators, but with less fragmentation. 00015 // Default_alloc_template parameters are experimental and MAY 00016 // DISAPPEAR in the future. Clients should just use vcl_alloc for now. 00017 // 00018 // Important implementation properties: 00019 // - If the client request an object of size > __MAX_BYTES, the resulting 00020 // object will be obtained directly from malloc. 00021 // - In all other cases, we allocate an object of size exactly 00022 // ROUND_UP(requested_size). Thus the client has enough size 00023 // information that we can return the object to the proper free li*st 00024 // without permanently losing part of the object. 00025 // 00026 // The first template parameter specifies whether more than one thread 00027 // may use this allocator. It is safe to allocate an object from 00028 // one instance of a default_alloc and deallocate it with another 00029 // one. This effectively transfers its ownership to the second one. 00030 // This may have undesirable effects on reference locality. 00031 // The second parameter is unreferenced and serves only to allow the 00032 // creation of multiple default_alloc instances. 00033 // 00034 // Note that containers built on different allocator instances have 00035 // different types, limiting the utility of this approach. 00036 00037 #include <vcl_cstddef.h> // size_t lives here 00038 00039 const int VNL_ALLOC_ALIGN = 8; 00040 const vcl_size_t VNL_ALLOC_MAX_BYTES = 256; 00041 const vcl_size_t VNL_ALLOC_NFREELISTS = VNL_ALLOC_MAX_BYTES/VNL_ALLOC_ALIGN; 00042 00043 class vnl_alloc 00044 { 00045 static vcl_size_t ROUND_UP(vcl_size_t bytes) { 00046 return (bytes + VNL_ALLOC_ALIGN-1) & ~(VNL_ALLOC_ALIGN - 1); 00047 } 00048 union obj; 00049 friend union obj; 00050 union obj { 00051 union obj * free_list_link; 00052 char client_data[1]; /* The client sees this. */ 00053 }; 00054 # if defined ( __SUNPRO_CC ) || defined ( _AIX ) 00055 static obj * free_list[]; 00056 // Specifying a size results in duplicate def for 4.1 00057 # else 00058 static obj * free_list[VNL_ALLOC_NFREELISTS]; 00059 # endif 00060 static vcl_size_t FREELIST_INDEX(vcl_size_t bytes) { 00061 return (bytes + VNL_ALLOC_ALIGN-1)/VNL_ALLOC_ALIGN - 1; 00062 } 00063 00064 // Returns an object of size n, and optionally adds to size n free li*st. 00065 static void *refill(vcl_size_t n); 00066 // Allocates a chunk for nobjs of size size. nobjs may be reduced 00067 // if it is inconvenient to allocate the requested number. 00068 static char *chunk_alloc(vcl_size_t size, int &nobjs); 00069 00070 // Chunk allocation state. 00071 static char *start_free; 00072 static char *end_free; 00073 static vcl_size_t heap_size; 00074 00075 class lock 00076 { 00077 public: 00078 lock() {} 00079 ~lock() {} 00080 }; 00081 friend class lock; 00082 00083 public: 00084 // this one is needed for proper vcl_simple_alloc wrapping 00085 typedef char value_type; 00086 00087 /* n must be > 0 */ 00088 static void * allocate(vcl_size_t n) { 00089 obj * * my_free_list; 00090 obj * result; 00091 00092 if (n > VNL_ALLOC_MAX_BYTES) { 00093 return (void*)new char[n]; 00094 } 00095 my_free_list = free_list + FREELIST_INDEX(n); 00096 // Acquire the lock here with a constructor call. 00097 // This ensures that it is released in exit or during stack 00098 // unwinding. 00099 result = *my_free_list; 00100 if (result == 0) { 00101 void *r = refill(ROUND_UP(n)); 00102 return r; 00103 } 00104 *my_free_list = result -> free_list_link; 00105 return result; 00106 }; 00107 00108 /* p may not be 0 */ 00109 static void deallocate(void *p, vcl_size_t n) 00110 { 00111 obj *q = (obj *)p; 00112 obj * * my_free_list; 00113 00114 if (n > VNL_ALLOC_MAX_BYTES) { 00115 delete [] (char*)p; 00116 return; 00117 } 00118 my_free_list = free_list + FREELIST_INDEX(n); 00119 q -> free_list_link = *my_free_list; 00120 *my_free_list = q; 00121 } 00122 00123 static void * reallocate(void *p, vcl_size_t old_sz, vcl_size_t new_sz); 00124 }; 00125 00126 # endif // vnl_alloc_h_