stl_alloc.h

Go to the documentation of this file.
00001 // Allocators -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * Copyright (c) 1996-1997 00032 * Silicon Graphics Computer Systems, Inc. 00033 * 00034 * Permission to use, copy, modify, distribute and sell this software 00035 * and its documentation for any purpose is hereby granted without fee, 00036 * provided that the above copyright notice appear in all copies and 00037 * that both that copyright notice and this permission notice appear 00038 * in supporting documentation. Silicon Graphics makes no 00039 * representations about the suitability of this software for any 00040 * purpose. It is provided "as is" without express or implied warranty. 00041 */ 00042 00043 /** @file stl_alloc.h 00044 * This is an internal header file, included by other library headers. 00045 * You should not attempt to use it directly. 00046 */ 00047 00048 #ifndef __GLIBCPP_INTERNAL_ALLOC_H 00049 #define __GLIBCPP_INTERNAL_ALLOC_H 00050 00051 /** 00052 * @defgroup Allocators Memory Allocators 00053 * @if maint 00054 * stl_alloc.h implements some node allocators. These are NOT the same as 00055 * allocators in the C++ standard, nor in the original H-P STL. They do not 00056 * encapsulate different pointer types; we assume that there is only one 00057 * pointer type. The C++ standard allocators are intended to allocate 00058 * individual objects, not pools or arenas. 00059 * 00060 * In this file allocators are of two different styles: "standard" and 00061 * "SGI" (quotes included). "Standard" allocators conform to 20.4. "SGI" 00062 * allocators differ in AT LEAST the following ways (add to this list as you 00063 * discover them): 00064 * 00065 * - "Standard" allocate() takes two parameters (n_count,hint=0) but "SGI" 00066 * allocate() takes one paramter (n_size). 00067 * - Likewise, "standard" deallocate()'s argument is a count, but in "SGI" 00068 * is a byte size. 00069 * - max_size(), construct(), and destroy() are missing in "SGI" allocators. 00070 * - reallocate(p,oldsz,newsz) is added in "SGI", and behaves as 00071 * if p=realloc(p,newsz). 00072 * 00073 * "SGI" allocators may be wrapped in __allocator to convert the interface 00074 * into a "standard" one. 00075 * @endif 00076 * 00077 * @note The @c reallocate member functions have been deprecated for 3.2 00078 * and will be removed in 3.4. You must define @c _GLIBCPP_DEPRECATED 00079 * to make this visible in 3.2; see c++config.h. 00080 * 00081 * The canonical description of these classes is in docs/html/ext/howto.html 00082 * or online at http://gcc.gnu.org/onlinedocs/libstdc++/ext/howto.html#3 00083 */ 00084 00085 #include <cstddef> 00086 #include <cstdlib> 00087 #include <cstring> 00088 #include <bits/functexcept.h> // For __throw_bad_alloc 00089 #include <bits/stl_threads.h> 00090 00091 #include <bits/atomicity.h> 00092 00093 namespace std 00094 { 00095 /** 00096 * @if maint 00097 * A new-based allocator, as required by the standard. Allocation and 00098 * deallocation forward to global new and delete. "SGI" style, minus 00099 * reallocate(). 00100 * @endif 00101 * (See @link Allocators allocators info @endlink for more.) 00102 */ 00103 class __new_alloc 00104 { 00105 public: 00106 static void* 00107 allocate(size_t __n) 00108 { return ::operator new(__n); } 00109 00110 static void 00111 deallocate(void* __p, size_t) 00112 { ::operator delete(__p); } 00113 }; 00114 00115 00116 /** 00117 * @if maint 00118 * A malloc-based allocator. Typically slower than the 00119 * __default_alloc_template (below). Typically thread-safe and more 00120 * storage efficient. The template argument is unused and is only present 00121 * to permit multiple instantiations (but see __default_alloc_template 00122 * for caveats). "SGI" style, plus __set_malloc_handler for OOM conditions. 00123 * @endif 00124 * (See @link Allocators allocators info @endlink for more.) 00125 */ 00126 template<int __inst> 00127 class __malloc_alloc_template 00128 { 00129 private: 00130 static void* _S_oom_malloc(size_t); 00131 static void* _S_oom_realloc(void*, size_t); 00132 static void (* __malloc_alloc_oom_handler)(); 00133 00134 public: 00135 static void* 00136 allocate(size_t __n) 00137 { 00138 void* __result = malloc(__n); 00139 if (__builtin_expect(__result == 0, 0)) 00140 __result = _S_oom_malloc(__n); 00141 return __result; 00142 } 00143 00144 static void 00145 deallocate(void* __p, size_t /* __n */) 00146 { free(__p); } 00147 00148 static void* 00149 reallocate(void* __p, size_t /* old_sz */, size_t __new_sz) 00150 { 00151 void* __result = realloc(__p, __new_sz); 00152 if (__builtin_expect(__result == 0, 0)) 00153 __result = _S_oom_realloc(__p, __new_sz); 00154 return __result; 00155 } 00156 00157 static void (* __set_malloc_handler(void (*__f)()))() 00158 { 00159 void (* __old)() = __malloc_alloc_oom_handler; 00160 __malloc_alloc_oom_handler = __f; 00161 return __old; 00162 } 00163 }; 00164 00165 // malloc_alloc out-of-memory handling 00166 template<int __inst> 00167 void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0; 00168 00169 template<int __inst> 00170 void* 00171 __malloc_alloc_template<__inst>:: 00172 _S_oom_malloc(size_t __n) 00173 { 00174 void (* __my_malloc_handler)(); 00175 void* __result; 00176 00177 for (;;) 00178 { 00179 __my_malloc_handler = __malloc_alloc_oom_handler; 00180 if (__builtin_expect(__my_malloc_handler == 0, 0)) 00181 __throw_bad_alloc(); 00182 (*__my_malloc_handler)(); 00183 __result = malloc(__n); 00184 if (__result) 00185 return __result; 00186 } 00187 } 00188 00189 template<int __inst> 00190 void* 00191 __malloc_alloc_template<__inst>:: 00192 _S_oom_realloc(void* __p, size_t __n) 00193 { 00194 void (* __my_malloc_handler)(); 00195 void* __result; 00196 00197 for (;;) 00198 { 00199 __my_malloc_handler = __malloc_alloc_oom_handler; 00200 if (__builtin_expect(__my_malloc_handler == 0, 0)) 00201 __throw_bad_alloc(); 00202 (*__my_malloc_handler)(); 00203 __result = realloc(__p, __n); 00204 if (__result) 00205 return __result; 00206 } 00207 } 00208 00209 // Should not be referenced within the library anymore. 00210 typedef __new_alloc __mem_interface; 00211 00212 /** 00213 * @if maint 00214 * This is used primarily (only?) in _Alloc_traits and other places to 00215 * help provide the _Alloc_type typedef. All it does is forward the 00216 * requests after some minimal checking. 00217 * 00218 * This is neither "standard"-conforming nor "SGI". The _Alloc parameter 00219 * must be "SGI" style. 00220 * @endif 00221 * (See @link Allocators allocators info @endlink for more.) 00222 */ 00223 template<typename _Tp, typename _Alloc> 00224 class __simple_alloc 00225 { 00226 public: 00227 static _Tp* 00228 allocate(size_t __n) 00229 { 00230 _Tp* __ret = 0; 00231 if (__n) 00232 __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))); 00233 return __ret; 00234 } 00235 00236 static _Tp* 00237 allocate() 00238 { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); } 00239 00240 static void 00241 deallocate(_Tp* __p, size_t __n) 00242 { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); } 00243 00244 static void 00245 deallocate(_Tp* __p) 00246 { _Alloc::deallocate(__p, sizeof (_Tp)); } 00247 }; 00248 00249 00250 /** 00251 * @if maint 00252 * An adaptor for an underlying allocator (_Alloc) to check the size 00253 * arguments for debugging. 00254 * 00255 * "There is some evidence that this can confuse Purify." - SGI comment 00256 * 00257 * This adaptor is "SGI" style. The _Alloc parameter must also be "SGI". 00258 * @endif 00259 * (See @link Allocators allocators info @endlink for more.) 00260 */ 00261 template<typename _Alloc> 00262 class __debug_alloc 00263 { 00264 private: 00265 // Size of space used to store size. Note that this must be 00266 // large enough to preserve alignment. 00267 enum {_S_extra = 8}; 00268 00269 public: 00270 static void* 00271 allocate(size_t __n) 00272 { 00273 char* __result = (char*)_Alloc::allocate(__n + (int) _S_extra); 00274 *(size_t*)__result = __n; 00275 return __result + (int) _S_extra; 00276 } 00277 00278 static void 00279 deallocate(void* __p, size_t __n) 00280 { 00281 char* __real_p = (char*)__p - (int) _S_extra; 00282 if (*(size_t*)__real_p != __n) 00283 abort(); 00284 _Alloc::deallocate(__real_p, __n + (int) _S_extra); 00285 } 00286 00287 static void* 00288 reallocate(void* __p, size_t __old_sz, size_t __new_sz) 00289 { 00290 char* __real_p = (char*)__p - (int) _S_extra; 00291 if (*(size_t*)__real_p != __old_sz) 00292 abort(); 00293 char* __result = (char*) _Alloc::reallocate(__real_p, 00294 __old_sz + (int) _S_extra, 00295 __new_sz + (int) _S_extra); 00296 *(size_t*)__result = __new_sz; 00297 return __result + (int) _S_extra; 00298 } 00299 }; 00300 00301 00302 /** 00303 * @if maint 00304 * Default node allocator. "SGI" style. Uses various allocators to 00305 * fulfill underlying requests (and makes as few requests as possible 00306 * when in default high-speed pool mode). 00307 * 00308 * Important implementation properties: 00309 * 0. If globally mandated, then allocate objects from __new_alloc 00310 * 1. If the clients request an object of size > _MAX_BYTES, the resulting 00311 * object will be obtained directly from __new_alloc 00312 * 2. In all other cases, we allocate an object of size exactly 00313 * _S_round_up(requested_size). Thus the client has enough size 00314 * information that we can return the object to the proper free list 00315 * without permanently losing part of the object. 00316 * 00317 * The first template parameter specifies whether more than one thread may 00318 * use this allocator. It is safe to allocate an object from one instance 00319 * of a default_alloc and deallocate it with another one. This effectively 00320 * transfers its ownership to the second one. This may have undesirable 00321 * effects on reference locality. 00322 * 00323 * The second parameter is unused and serves only to allow the creation of 00324 * multiple default_alloc instances. Note that containers built on different 00325 * allocator instances have different types, limiting the utility of this 00326 * approach. If you do not wish to share the free lists with the main 00327 * default_alloc instance, instantiate this with a non-zero __inst. 00328 * 00329 * @endif 00330 * (See @link Allocators allocators info @endlink for more.) 00331 */ 00332 template<bool __threads, int __inst> 00333 class __default_alloc_template 00334 { 00335 private: 00336 enum {_ALIGN = 8}; 00337 enum {_MAX_BYTES = 128}; 00338 enum {_NFREELISTS = _MAX_BYTES / _ALIGN}; 00339 00340 union _Obj 00341 { 00342 union _Obj* _M_free_list_link; 00343 char _M_client_data[1]; // The client sees this. 00344 }; 00345 00346 static _Obj* volatile _S_free_list[_NFREELISTS]; 00347 00348 // Chunk allocation state. 00349 static char* _S_start_free; 00350 static char* _S_end_free; 00351 static size_t _S_heap_size; 00352 00353 static _STL_mutex_lock _S_node_allocator_lock; 00354 00355 static size_t 00356 _S_round_up(size_t __bytes) 00357 { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); } 00358 00359 static size_t 00360 _S_freelist_index(size_t __bytes) 00361 { return (((__bytes) + (size_t)_ALIGN - 1)/(size_t)_ALIGN - 1); } 00362 00363 // Returns an object of size __n, and optionally adds to size __n 00364 // free list. 00365 static void* 00366 _S_refill(size_t __n); 00367 00368 // Allocates a chunk for nobjs of size size. nobjs may be reduced 00369 // if it is inconvenient to allocate the requested number. 00370 static char* 00371 _S_chunk_alloc(size_t __size, int& __nobjs); 00372 00373 // It would be nice to use _STL_auto_lock here. But we need a 00374 // test whether threads are in use. 00375 struct _Lock 00376 { 00377 _Lock() { if (__threads) _S_node_allocator_lock._M_acquire_lock(); } 00378 ~_Lock() { if (__threads) _S_node_allocator_lock._M_release_lock(); } 00379 } __attribute__ ((__unused__)); 00380 friend struct _Lock; 00381 00382 static _Atomic_word _S_force_new; 00383 00384 public: 00385 // __n must be > 0 00386 static void* 00387 allocate(size_t __n) 00388 { 00389 void* __ret = 0; 00390 00391 // If there is a race through here, assume answer from getenv 00392 // will resolve in same direction. Inspired by techniques 00393 // to efficiently support threading found in basic_string.h. 00394 if (_S_force_new == 0) 00395 { 00396 if (getenv("GLIBCPP_FORCE_NEW")) 00397 __atomic_add(&_S_force_new, 1); 00398 else 00399 __atomic_add(&_S_force_new, -1); 00400 } 00401 00402 if ((__n > (size_t) _MAX_BYTES) || (_S_force_new > 0)) 00403 __ret = __new_alloc::allocate(__n); 00404 else 00405 { 00406 _Obj* volatile* __my_free_list = _S_free_list 00407 + _S_freelist_index(__n); 00408 // Acquire the lock here with a constructor call. This 00409 // ensures that it is released in exit or during stack 00410 // unwinding. 00411 _Lock __lock_instance; 00412 _Obj* __restrict__ __result = *__my_free_list; 00413 if (__builtin_expect(__result == 0, 0)) 00414 __ret = _S_refill(_S_round_up(__n)); 00415 else 00416 { 00417 *__my_free_list = __result -> _M_free_list_link; 00418 __ret = __result; 00419 } 00420 if (__builtin_expect(__ret == 0, 0)) 00421 __throw_bad_alloc(); 00422 } 00423 return __ret; 00424 } 00425 00426 // __p may not be 0 00427 static void 00428 deallocate(void* __p, size_t __n) 00429 { 00430 if ((__n > (size_t) _MAX_BYTES) || (_S_force_new > 0)) 00431 __new_alloc::deallocate(__p, __n); 00432 else 00433 { 00434 _Obj* volatile* __my_free_list = _S_free_list 00435 + _S_freelist_index(__n); 00436 _Obj* __q = (_Obj*)__p; 00437 00438 // Acquire the lock here with a constructor call. This 00439 // ensures that it is released in exit or during stack 00440 // unwinding. 00441 _Lock __lock_instance; 00442 __q -> _M_free_list_link = *__my_free_list; 00443 *__my_free_list = __q; 00444 } 00445 } 00446 00447 static void* 00448 reallocate(void* __p, size_t __old_sz, size_t __new_sz); 00449 }; 00450 00451 template<bool __threads, int __inst> _Atomic_word 00452 __default_alloc_template<__threads, __inst>::_S_force_new = 0; 00453 00454 template<bool __threads, int __inst> 00455 inline bool 00456 operator==(const __default_alloc_template<__threads,__inst>&, 00457 const __default_alloc_template<__threads,__inst>&) 00458 { return true; } 00459 00460 template<bool __threads, int __inst> 00461 inline bool 00462 operator!=(const __default_alloc_template<__threads,__inst>&, 00463 const __default_alloc_template<__threads,__inst>&) 00464 { return false; } 00465 00466 00467 // We allocate memory in large chunks in order to avoid fragmenting the 00468 // heap too much. We assume that __size is properly aligned. We hold 00469 // the allocation lock. 00470 template<bool __threads, int __inst> 00471 char* 00472 __default_alloc_template<__threads, __inst>:: 00473 _S_chunk_alloc(size_t __size, int& __nobjs) 00474 { 00475 char* __result; 00476 size_t __total_bytes = __size * __nobjs; 00477 size_t __bytes_left = _S_end_free - _S_start_free; 00478 00479 if (__bytes_left >= __total_bytes) 00480 { 00481 __result = _S_start_free; 00482 _S_start_free += __total_bytes; 00483 return __result ; 00484 } 00485 else if (__bytes_left >= __size) 00486 { 00487 __nobjs = (int)(__bytes_left/__size); 00488 __total_bytes = __size * __nobjs; 00489 __result = _S_start_free; 00490 _S_start_free += __total_bytes; 00491 return __result; 00492 } 00493 else 00494 { 00495 size_t __bytes_to_get = 00496 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); 00497 // Try to make use of the left-over piece. 00498 if (__bytes_left > 0) 00499 { 00500 _Obj* volatile* __my_free_list = 00501 _S_free_list + _S_freelist_index(__bytes_left); 00502 00503 ((_Obj*)(void*)_S_start_free) -> _M_free_list_link = *__my_free_list; 00504 *__my_free_list = (_Obj*)(void*)_S_start_free; 00505 } 00506 _S_start_free = (char*) __new_alloc::allocate(__bytes_to_get); 00507 if (_S_start_free == 0) 00508 { 00509 size_t __i; 00510 _Obj* volatile* __my_free_list; 00511 _Obj* __p; 00512 // Try to make do with what we have. That can't hurt. We 00513 // do not try smaller requests, since that tends to result 00514 // in disaster on multi-process machines. 00515 __i = __size; 00516 for (; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN) 00517 { 00518 __my_free_list = _S_free_list + _S_freelist_index(__i); 00519 __p = *__my_free_list; 00520 if (__p != 0) 00521 { 00522 *__my_free_list = __p -> _M_free_list_link; 00523 _S_start_free = (char*)__p; 00524 _S_end_free = _S_start_free + __i; 00525 return _S_chunk_alloc(__size, __nobjs); 00526 // Any leftover piece will eventually make it to the 00527 // right free list. 00528 } 00529 } 00530 _S_end_free = 0; // In case of exception. 00531 _S_start_free = (char*)__new_alloc::allocate(__bytes_to_get); 00532 // This should either throw an exception or remedy the situation. 00533 // Thus we assume it succeeded. 00534 } 00535 _S_heap_size += __bytes_to_get; 00536 _S_end_free = _S_start_free + __bytes_to_get; 00537 return _S_chunk_alloc(__size, __nobjs); 00538 } 00539 } 00540 00541 00542 // Returns an object of size __n, and optionally adds to "size 00543 // __n"'s free list. We assume that __n is properly aligned. We 00544 // hold the allocation lock. 00545 template<bool __threads, int __inst> 00546 void* 00547 __default_alloc_template<__threads, __inst>::_S_refill(size_t __n) 00548 { 00549 int __nobjs = 20; 00550 char* __chunk = _S_chunk_alloc(__n, __nobjs); 00551 _Obj* volatile* __my_free_list; 00552 _Obj* __result; 00553 _Obj* __current_obj; 00554 _Obj* __next_obj; 00555 int __i; 00556 00557 if (1 == __nobjs) 00558 return __chunk; 00559 __my_free_list = _S_free_list + _S_freelist_index(__n); 00560 00561 // Build free list in chunk. 00562 __result = (_Obj*)(void*)__chunk; 00563 *__my_free_list = __next_obj = (_Obj*)(void*)(__chunk + __n); 00564 for (__i = 1; ; __i++) 00565 { 00566 __current_obj = __next_obj; 00567 __next_obj = (_Obj*)(void*)((char*)__next_obj + __n); 00568 if (__nobjs - 1 == __i) 00569 { 00570 __current_obj -> _M_free_list_link = 0; 00571 break; 00572 } 00573 else 00574 __current_obj -> _M_free_list_link = __next_obj; 00575 } 00576 return __result; 00577 } 00578 00579 00580 template<bool threads, int inst> 00581 void* 00582 __default_alloc_template<threads, inst>:: 00583 reallocate(void* __p, size_t __old_sz, size_t __new_sz) 00584 { 00585 void* __result; 00586 size_t __copy_sz; 00587 00588 if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) 00589 return(realloc(__p, __new_sz)); 00590 if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) 00591 return(__p); 00592 __result = allocate(__new_sz); 00593 __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz; 00594 memcpy(__result, __p, __copy_sz); 00595 deallocate(__p, __old_sz); 00596 return __result; 00597 } 00598 00599 template<bool __threads, int __inst> 00600 _STL_mutex_lock 00601 __default_alloc_template<__threads,__inst>::_S_node_allocator_lock 00602 __STL_MUTEX_INITIALIZER; 00603 00604 template<bool __threads, int __inst> 00605 char* __default_alloc_template<__threads,__inst>::_S_start_free = 0; 00606 00607 template<bool __threads, int __inst> 00608 char* __default_alloc_template<__threads,__inst>::_S_end_free = 0; 00609 00610 template<bool __threads, int __inst> 00611 size_t __default_alloc_template<__threads,__inst>::_S_heap_size = 0; 00612 00613 template<bool __threads, int __inst> 00614 typename __default_alloc_template<__threads,__inst>::_Obj* volatile 00615 __default_alloc_template<__threads,__inst>::_S_free_list[_NFREELISTS]; 00616 00617 typedef __default_alloc_template<true,0> __alloc; 00618 typedef __default_alloc_template<false,0> __single_client_alloc; 00619 00620 00621 /** 00622 * @brief The "standard" allocator, as per [20.4]. 00623 * 00624 * The private _Alloc is "SGI" style. (See comments at the top 00625 * of stl_alloc.h.) 00626 * 00627 * The underlying allocator behaves as follows. 00628 * - __default_alloc_template is used via two typedefs 00629 * - "__single_client_alloc" typedef does no locking for threads 00630 * - "__alloc" typedef is threadsafe via the locks 00631 * - __new_alloc is used for memory requests 00632 * 00633 * (See @link Allocators allocators info @endlink for more.) 00634 */ 00635 template<typename _Tp> 00636 class allocator 00637 { 00638 typedef __alloc _Alloc; // The underlying allocator. 00639 public: 00640 typedef size_t size_type; 00641 typedef ptrdiff_t difference_type; 00642 typedef _Tp* pointer; 00643 typedef const _Tp* const_pointer; 00644 typedef _Tp& reference; 00645 typedef const _Tp& const_reference; 00646 typedef _Tp value_type; 00647 00648 template<typename _Tp1> 00649 struct rebind 00650 { typedef allocator<_Tp1> other; }; 00651 00652 allocator() throw() {} 00653 allocator(const allocator&) throw() {} 00654 template<typename _Tp1> 00655 allocator(const allocator<_Tp1>&) throw() {} 00656 ~allocator() throw() {} 00657 00658 pointer 00659 address(reference __x) const { return &__x; } 00660 00661 const_pointer 00662 address(const_reference __x) const { return &__x; } 00663 00664 // NB: __n is permitted to be 0. The C++ standard says nothing 00665 // about what the return value is when __n == 0. 00666 _Tp* 00667 allocate(size_type __n, const void* = 0) 00668 { 00669 _Tp* __ret = 0; 00670 if (__n) 00671 { 00672 if (__n <= this->max_size()) 00673 __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))); 00674 else 00675 __throw_bad_alloc(); 00676 } 00677 return __ret; 00678 } 00679 00680 // __p is not permitted to be a null pointer. 00681 void 00682 deallocate(pointer __p, size_type __n) 00683 { _Alloc::deallocate(__p, __n * sizeof(_Tp)); } 00684 00685 size_type 00686 max_size() const throw() { return size_t(-1) / sizeof(_Tp); } 00687 00688 void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); } 00689 void destroy(pointer __p) { __p->~_Tp(); } 00690 }; 00691 00692 template<> 00693 class allocator<void> 00694 { 00695 public: 00696 typedef size_t size_type; 00697 typedef ptrdiff_t difference_type; 00698 typedef void* pointer; 00699 typedef const void* const_pointer; 00700 typedef void value_type; 00701 00702 template<typename _Tp1> 00703 struct rebind 00704 { typedef allocator<_Tp1> other; }; 00705 }; 00706 00707 00708 template<typename _T1, typename _T2> 00709 inline bool 00710 operator==(const allocator<_T1>&, const allocator<_T2>&) 00711 { return true; } 00712 00713 template<typename _T1, typename _T2> 00714 inline bool 00715 operator!=(const allocator<_T1>&, const allocator<_T2>&) 00716 { return false; } 00717 00718 00719 /** 00720 * @if maint 00721 * Allocator adaptor to turn an "SGI" style allocator (e.g., 00722 * __alloc, __malloc_alloc_template) into a "standard" conforming 00723 * allocator. Note that this adaptor does *not* assume that all 00724 * objects of the underlying alloc class are identical, nor does it 00725 * assume that all of the underlying alloc's member functions are 00726 * static member functions. Note, also, that __allocator<_Tp, 00727 * __alloc> is essentially the same thing as allocator<_Tp>. 00728 * @endif 00729 * (See @link Allocators allocators info @endlink for more.) 00730 */ 00731 template<typename _Tp, typename _Alloc> 00732 struct __allocator 00733 { 00734 _Alloc __underlying_alloc; 00735 00736 typedef size_t size_type; 00737 typedef ptrdiff_t difference_type; 00738 typedef _Tp* pointer; 00739 typedef const _Tp* const_pointer; 00740 typedef _Tp& reference; 00741 typedef const _Tp& const_reference; 00742 typedef _Tp value_type; 00743 00744 template<typename _Tp1> 00745 struct rebind 00746 { typedef __allocator<_Tp1, _Alloc> other; }; 00747 00748 __allocator() throw() {} 00749 __allocator(const __allocator& __a) throw() 00750 : __underlying_alloc(__a.__underlying_alloc) {} 00751 00752 template<typename _Tp1> 00753 __allocator(const __allocator<_Tp1, _Alloc>& __a) throw() 00754 : __underlying_alloc(__a.__underlying_alloc) {} 00755 00756 ~__allocator() throw() {} 00757 00758 pointer 00759 address(reference __x) const { return &__x; } 00760 00761 const_pointer 00762 address(const_reference __x) const { return &__x; } 00763 00764 // NB: __n is permitted to be 0. The C++ standard says nothing 00765 // about what the return value is when __n == 0. 00766 _Tp* 00767 allocate(size_type __n, const void* = 0) 00768 { 00769 _Tp* __ret = 0; 00770 if (__n) 00771 __ret = static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))); 00772 return __ret; 00773 } 00774 00775 // __p is not permitted to be a null pointer. 00776 void 00777 deallocate(pointer __p, size_type __n) 00778 { __underlying_alloc.deallocate(__p, __n * sizeof(_Tp)); } 00779 00780 size_type 00781 max_size() const throw() { return size_t(-1) / sizeof(_Tp); } 00782 00783 void 00784 construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); } 00785 00786 void 00787 destroy(pointer __p) { __p->~_Tp(); } 00788 }; 00789 00790 template<typename _Alloc> 00791 struct __allocator<void, _Alloc> 00792 { 00793 typedef size_t size_type; 00794 typedef ptrdiff_t difference_type; 00795 typedef void* pointer; 00796 typedef const void* const_pointer; 00797 typedef void value_type; 00798 00799 template<typename _Tp1> 00800 struct rebind 00801 { typedef __allocator<_Tp1, _Alloc> other; }; 00802 }; 00803 00804 template<typename _Tp, typename _Alloc> 00805 inline bool 00806 operator==(const __allocator<_Tp,_Alloc>& __a1, 00807 const __allocator<_Tp,_Alloc>& __a2) 00808 { return __a1.__underlying_alloc == __a2.__underlying_alloc; } 00809 00810 template<typename _Tp, typename _Alloc> 00811 inline bool 00812 operator!=(const __allocator<_Tp, _Alloc>& __a1, 00813 const __allocator<_Tp, _Alloc>& __a2) 00814 { return __a1.__underlying_alloc != __a2.__underlying_alloc; } 00815 00816 00817 //@{ 00818 /** Comparison operators for all of the predifined SGI-style allocators. 00819 * This ensures that __allocator<malloc_alloc> (for example) will work 00820 * correctly. As required, all allocators compare equal. 00821 */ 00822 template<int inst> 00823 inline bool 00824 operator==(const __malloc_alloc_template<inst>&, 00825 const __malloc_alloc_template<inst>&) 00826 { return true; } 00827 00828 template<int __inst> 00829 inline bool 00830 operator!=(const __malloc_alloc_template<__inst>&, 00831 const __malloc_alloc_template<__inst>&) 00832 { return false; } 00833 00834 template<typename _Alloc> 00835 inline bool 00836 operator==(const __debug_alloc<_Alloc>&, const __debug_alloc<_Alloc>&) 00837 { return true; } 00838 00839 template<typename _Alloc> 00840 inline bool 00841 operator!=(const __debug_alloc<_Alloc>&, const __debug_alloc<_Alloc>&) 00842 { return false; } 00843 //@} 00844 00845 00846 /** 00847 * @if maint 00848 * Another allocator adaptor: _Alloc_traits. This serves two purposes. 00849 * First, make it possible to write containers that can use either "SGI" 00850 * style allocators or "standard" allocators. Second, provide a mechanism 00851 * so that containers can query whether or not the allocator has distinct 00852 * instances. If not, the container can avoid wasting a word of memory to 00853 * store an empty object. For examples of use, see stl_vector.h, etc, or 00854 * any of the other classes derived from this one. 00855 * 00856 * This adaptor uses partial specialization. The general case of 00857 * _Alloc_traits<_Tp, _Alloc> assumes that _Alloc is a 00858 * standard-conforming allocator, possibly with non-equal instances and 00859 * non-static members. (It still behaves correctly even if _Alloc has 00860 * static member and if all instances are equal. Refinements affect 00861 * performance, not correctness.) 00862 * 00863 * There are always two members: allocator_type, which is a standard- 00864 * conforming allocator type for allocating objects of type _Tp, and 00865 * _S_instanceless, a static const member of type bool. If 00866 * _S_instanceless is true, this means that there is no difference 00867 * between any two instances of type allocator_type. Furthermore, if 00868 * _S_instanceless is true, then _Alloc_traits has one additional 00869 * member: _Alloc_type. This type encapsulates allocation and 00870 * deallocation of objects of type _Tp through a static interface; it 00871 * has two member functions, whose signatures are 00872 * 00873 * - static _Tp* allocate(size_t) 00874 * - static void deallocate(_Tp*, size_t) 00875 * 00876 * The size_t parameters are "standard" style (see top of stl_alloc.h) in 00877 * that they take counts, not sizes. 00878 * 00879 * @endif 00880 * (See @link Allocators allocators info @endlink for more.) 00881 */ 00882 //@{ 00883 // The fully general version. 00884 template<typename _Tp, typename _Allocator> 00885 struct _Alloc_traits 00886 { 00887 static const bool _S_instanceless = false; 00888 typedef typename _Allocator::template rebind<_Tp>::other allocator_type; 00889 }; 00890 00891 template<typename _Tp, typename _Allocator> 00892 const bool _Alloc_traits<_Tp, _Allocator>::_S_instanceless; 00893 00894 /// The version for the default allocator. 00895 template<typename _Tp, typename _Tp1> 00896 struct _Alloc_traits<_Tp, allocator<_Tp1> > 00897 { 00898 static const bool _S_instanceless = true; 00899 typedef __simple_alloc<_Tp, __alloc> _Alloc_type; 00900 typedef allocator<_Tp> allocator_type; 00901 }; 00902 //@} 00903 00904 //@{ 00905 /// Versions for the predefined "SGI" style allocators. 00906 template<typename _Tp, int __inst> 00907 struct _Alloc_traits<_Tp, __malloc_alloc_template<__inst> > 00908 { 00909 static const bool _S_instanceless = true; 00910 typedef __simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type; 00911 typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type; 00912 }; 00913 00914 template<typename _Tp, bool __threads, int __inst> 00915 struct _Alloc_traits<_Tp, __default_alloc_template<__threads, __inst> > 00916 { 00917 static const bool _S_instanceless = true; 00918 typedef __simple_alloc<_Tp, __default_alloc_template<__threads, __inst> > 00919 _Alloc_type; 00920 typedef __allocator<_Tp, __default_alloc_template<__threads, __inst> > 00921 allocator_type; 00922 }; 00923 00924 template<typename _Tp, typename _Alloc> 00925 struct _Alloc_traits<_Tp, __debug_alloc<_Alloc> > 00926 { 00927 static const bool _S_instanceless = true; 00928 typedef __simple_alloc<_Tp, __debug_alloc<_Alloc> > _Alloc_type; 00929 typedef __allocator<_Tp, __debug_alloc<_Alloc> > allocator_type; 00930 }; 00931 //@} 00932 00933 //@{ 00934 /// Versions for the __allocator adaptor used with the predefined 00935 /// "SGI" style allocators. 00936 template<typename _Tp, typename _Tp1, int __inst> 00937 struct _Alloc_traits<_Tp, 00938 __allocator<_Tp1, __malloc_alloc_template<__inst> > > 00939 { 00940 static const bool _S_instanceless = true; 00941 typedef __simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type; 00942 typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type; 00943 }; 00944 00945 template<typename _Tp, typename _Tp1, bool __thr, int __inst> 00946 struct _Alloc_traits<_Tp, __allocator<_Tp1, __default_alloc_template<__thr, __inst> > > 00947 { 00948 static const bool _S_instanceless = true; 00949 typedef __simple_alloc<_Tp, __default_alloc_template<__thr,__inst> > 00950 _Alloc_type; 00951 typedef __allocator<_Tp, __default_alloc_template<__thr,__inst> > 00952 allocator_type; 00953 }; 00954 00955 template<typename _Tp, typename _Tp1, typename _Alloc> 00956 struct _Alloc_traits<_Tp, __allocator<_Tp1, __debug_alloc<_Alloc> > > 00957 { 00958 static const bool _S_instanceless = true; 00959 typedef __simple_alloc<_Tp, __debug_alloc<_Alloc> > _Alloc_type; 00960 typedef __allocator<_Tp, __debug_alloc<_Alloc> > allocator_type; 00961 }; 00962 //@} 00963 00964 // Inhibit implicit instantiations for required instantiations, 00965 // which are defined via explicit instantiations elsewhere. 00966 // NB: This syntax is a GNU extension. 00967 #if _GLIBCPP_EXTERN_TEMPLATE 00968 extern template class allocator<char>; 00969 extern template class allocator<wchar_t>; 00970 extern template class __default_alloc_template<true,0>; 00971 #endif 00972 } // namespace std 00973 00974 #endif

Generated on Sun Sep 19 16:33:58 2004 for libstdc++-v3 Source by doxygen 1.3.8