1/* 2 * Copyright (c) 1996-1997 3 * Silicon Graphics Computer Systems, Inc. 4 * 5 * Permission to use, copy, modify, distribute and sell this software 6 * and its documentation for any purpose is hereby granted without fee, 7 * provided that the above copyright notice appear in all copies and 8 * that both that copyright notice and this permission notice appear 9 * in supporting documentation. Silicon Graphics makes no 10 * representations about the suitability of this software for any 11 * purpose. It is provided "as is" without express or implied warranty. 12 */ 13 14/* NOTE: This is an internal header file, included by other STL headers. 15 * You should not attempt to use it directly. 16 */ 17 18#ifndef __SGI_STL_INTERNAL_ALLOC_H 19#define __SGI_STL_INTERNAL_ALLOC_H 20 21#ifdef __SUNPRO_CC 22# define __PRIVATE public 23 // Extra access restrictions prevent us from really making some things 24 // private. 25#else 26# define __PRIVATE private 27#endif 28 29#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG 30# define __USE_MALLOC 31#endif 32 33// This implements some standard node allocators. These are 34// NOT the same as the allocators in the C++ draft standard or in 35// in the original STL. They do not encapsulate different pointer 36// types; indeed we assume that there is only one pointer type. 37// The allocation primitives are intended to allocate individual objects, 38// not larger arenas as with the original STL allocators. 39 40#if 0 41# include <new> 42# define __THROW_BAD_ALLOC throw bad_alloc() 43#elif !defined(__THROW_BAD_ALLOC) 44#if (defined(__BEOS__) || defined(__HAIKU__)) 45# include <stdio.h> 46# define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1) 47#else 48# include <iostream.h> 49# define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1) 50#endif 51#endif 52 53#ifdef __STL_WIN32THREADS 54# include <windows.h> 55#endif 56 57#include <stddef.h> 58#include <stdlib.h> 59#include <string.h> 60#include <assert.h> 61#ifndef __RESTRICT 62# define __RESTRICT 63#endif 64 65#if !defined(__STL_PTHREADS) && !defined(__STL_SOLTHREADS) \ 66 && !defined(_NOTHREADS) \ 67 && !defined(__STL_SGI_THREADS) && !defined(__STL_WIN32THREADS) 68# define _NOTHREADS 69#endif 70 71# ifdef __STL_PTHREADS 72 // POSIX Threads 73 // This is dubious, since this is likely to be a high contention 74 // lock. Performance may not be adequate. 75# include <pthread.h> 76# define __NODE_ALLOCATOR_LOCK \ 77 if (threads) pthread_mutex_lock(&_S_node_allocator_lock) 78# define __NODE_ALLOCATOR_UNLOCK \ 79 if (threads) pthread_mutex_unlock(&_S_node_allocator_lock) 80# define __NODE_ALLOCATOR_THREADS true 81# define __VOLATILE volatile // Needed at -O3 on SGI 82# endif 83# ifdef __STL_SOLTHREADS 84# include <thread.h> 85# define __NODE_ALLOCATOR_LOCK \ 86 if (threads) mutex_lock(&_S_node_allocator_lock) 87# define __NODE_ALLOCATOR_UNLOCK \ 88 if (threads) mutex_unlock(&_S_node_allocator_lock) 89# define __NODE_ALLOCATOR_THREADS true 90# define __VOLATILE 91# endif 92# ifdef __STL_WIN32THREADS 93 // The lock needs to be initialized by constructing an allocator 94 // objects of the right type. We do that here explicitly for alloc. 95# define __NODE_ALLOCATOR_LOCK \ 96 EnterCriticalSection(&_S_node_allocator_lock) 97# define __NODE_ALLOCATOR_UNLOCK \ 98 LeaveCriticalSection(&_S_node_allocator_lock) 99# define __NODE_ALLOCATOR_THREADS true 100# define __VOLATILE volatile // may not be needed 101# endif /* WIN32THREADS */ 102# ifdef __STL_SGI_THREADS 103 // This should work without threads, with sproc threads, or with 104 // pthreads. It is suboptimal in all cases. 105 // It is unlikely to even compile on nonSGI machines. 106 107 extern "C" { 108 extern int __us_rsthread_malloc; 109 } 110 // The above is copied from malloc.h. Including <malloc.h> 111 // would be cleaner but fails with certain levels of standard 112 // conformance. 113# define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \ 114 { _S_lock(&_S_node_allocator_lock); } 115# define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \ 116 { _S_unlock(&_S_node_allocator_lock); } 117# define __NODE_ALLOCATOR_THREADS true 118# define __VOLATILE volatile // Needed at -O3 on SGI 119# endif 120# ifdef _NOTHREADS 121// Thread-unsafe 122# define __NODE_ALLOCATOR_LOCK 123# define __NODE_ALLOCATOR_UNLOCK 124# define __NODE_ALLOCATOR_THREADS false 125# define __VOLATILE 126# endif 127 128__STL_BEGIN_NAMESPACE 129 130#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 131#pragma set woff 1174 132#endif 133 134// Malloc-based allocator. Typically slower than default alloc below. 135// Typically thread-safe and more storage efficient. 136#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG 137# ifdef __DECLARE_GLOBALS_HERE 138 void (* __malloc_alloc_oom_handler)() = 0; 139 // g++ 2.7.2 does not handle static template data members. 140# else 141 extern void (* __malloc_alloc_oom_handler)(); 142# endif 143#endif 144 145template <int __inst> 146class __malloc_alloc_template { 147 148private: 149 150 static void* _S_oom_malloc(size_t); 151 static void* _S_oom_realloc(void*, size_t); 152 153#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG 154 static void (* __malloc_alloc_oom_handler)(); 155#endif 156 157public: 158 159 static void* allocate(size_t __n) 160 { 161 void* __result = malloc(__n); 162 if (0 == __result) __result = _S_oom_malloc(__n); 163 return __result; 164 } 165 166 static void deallocate(void* __p, size_t /* __n */) 167 { 168 free(__p); 169 } 170 171 static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz) 172 { 173 void* __result = realloc(__p, __new_sz); 174 if (0 == __result) __result = _S_oom_realloc(__p, __new_sz); 175 return __result; 176 } 177 178 static void (* __set_malloc_handler(void (*__f)()))() 179 { 180 void (* __old)() = __malloc_alloc_oom_handler; 181 __malloc_alloc_oom_handler = __f; 182 return(__old); 183 } 184 185}; 186 187// malloc_alloc out-of-memory handling 188 189#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG 190template <int __inst> 191void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0; 192#endif 193 194template <int __inst> 195void* 196__malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n) 197{ 198 void (* __my_malloc_handler)(); 199 void* __result; 200 201 for (;;) { 202 __my_malloc_handler = __malloc_alloc_oom_handler; 203 if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; } 204 (*__my_malloc_handler)(); 205 __result = malloc(__n); 206 if (__result) return(__result); 207 } 208} 209 210template <int __inst> 211void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n) 212{ 213 void (* __my_malloc_handler)(); 214 void* __result; 215 216 for (;;) { 217 __my_malloc_handler = __malloc_alloc_oom_handler; 218 if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; } 219 (*__my_malloc_handler)(); 220 __result = realloc(__p, __n); 221 if (__result) return(__result); 222 } 223} 224 225typedef __malloc_alloc_template<0> malloc_alloc; 226 227template<class _Tp, class _Alloc> 228class simple_alloc { 229 230public: 231 static _Tp* allocate(size_t __n) 232 { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); } 233 static _Tp* allocate(void) 234 { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); } 235 static void deallocate(_Tp* __p, size_t __n) 236 { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); } 237 static void deallocate(_Tp* __p) 238 { _Alloc::deallocate(__p, sizeof (_Tp)); } 239}; 240 241// Allocator adaptor to check size arguments for debugging. 242// Reports errors using assert. Checking can be disabled with 243// NDEBUG, but it's far better to just use the underlying allocator 244// instead when no checking is desired. 245// There is some evidence that this can confuse Purify. 246template <class _Alloc> 247class debug_alloc { 248 249private: 250 251 enum {_S_extra = 8}; // Size of space used to store size. Note 252 // that this must be large enough to preserve 253 // alignment. 254 255public: 256 257 static void* allocate(size_t __n) 258 { 259 char* __result = (char*)_Alloc::allocate(__n + _S_extra); 260 *(size_t*)__result = __n; 261 return __result + _S_extra; 262 } 263 264 static void deallocate(void* __p, size_t __n) 265 { 266 char* __real_p = (char*)__p - _S_extra; 267 assert(*(size_t*)__real_p == __n); 268 _Alloc::deallocate(__real_p, __n + _S_extra); 269 } 270 271 static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz) 272 { 273 char* __real_p = (char*)__p - _S_extra; 274 assert(*(size_t*)__real_p == __old_sz); 275 char* __result = (char*) 276 _Alloc::reallocate(__real_p, __old_sz + _S_extra, __new_sz + _S_extra); 277 *(size_t*)__result = __new_sz; 278 return __result + _S_extra; 279 } 280 281}; 282 283 284# ifdef __USE_MALLOC 285 286typedef malloc_alloc alloc; 287typedef malloc_alloc single_client_alloc; 288 289# else 290 291 292// Default node allocator. 293// With a reasonable compiler, this should be roughly as fast as the 294// original STL class-specific allocators, but with less fragmentation. 295// Default_alloc_template parameters are experimental and MAY 296// DISAPPEAR in the future. Clients should just use alloc for now. 297// 298// Important implementation properties: 299// 1. If the client request an object of size > _MAX_BYTES, the resulting 300// object will be obtained directly from malloc. 301// 2. In all other cases, we allocate an object of size exactly 302// _S_round_up(requested_size). Thus the client has enough size 303// information that we can return the object to the proper free list 304// without permanently losing part of the object. 305// 306 307// The first template parameter specifies whether more than one thread 308// may use this allocator. It is safe to allocate an object from 309// one instance of a default_alloc and deallocate it with another 310// one. This effectively transfers its ownership to the second one. 311// This may have undesirable effects on reference locality. 312// The second parameter is unreferenced and serves only to allow the 313// creation of multiple default_alloc instances. 314// Node that containers built on different allocator instances have 315// different types, limiting the utility of this approach. 316#ifdef __SUNPRO_CC 317// breaks if we make these template class members: 318 enum {_ALIGN = 8}; 319 enum {_MAX_BYTES = 128}; 320 enum {_NFREELISTS = _MAX_BYTES/_ALIGN}; 321#endif 322 323template <bool threads, int inst> 324class __default_alloc_template { 325 326private: 327 // Really we should use static const int x = N 328 // instead of enum { x = N }, but few compilers accept the former. 329# ifndef __SUNPRO_CC 330 enum {_ALIGN = 8}; 331 enum {_MAX_BYTES = 128}; 332 enum {_NFREELISTS = _MAX_BYTES/_ALIGN}; 333# endif 334 static size_t 335 _S_round_up(size_t __bytes) 336 { return (((__bytes) + _ALIGN-1) & ~(_ALIGN - 1)); } 337 338__PRIVATE: 339 union _Obj { 340 union _Obj* _M_free_list_link; 341 char _M_client_data[1]; /* The client sees this. */ 342 }; 343private: 344# ifdef __SUNPRO_CC 345 static _Obj* __VOLATILE _S_free_list[]; 346 // Specifying a size results in duplicate def for 4.1 347# else 348 static _Obj* __VOLATILE _S_free_list[_NFREELISTS]; 349# endif 350 static size_t _S_freelist_index(size_t __bytes) { 351 return (((__bytes) + _ALIGN-1)/_ALIGN - 1); 352 } 353 354 // Returns an object of size __n, and optionally adds to size __n free list. 355 static void* _S_refill(size_t __n); 356 // Allocates a chunk for nobjs of size "size". nobjs may be reduced 357 // if it is inconvenient to allocate the requested number. 358 static char* _S_chunk_alloc(size_t __size, int& __nobjs); 359 360 // Chunk allocation state. 361 static char* _S_start_free; 362 static char* _S_end_free; 363 static size_t _S_heap_size; 364 365# ifdef __STL_SGI_THREADS 366 static volatile unsigned long _S_node_allocator_lock; 367 static void _S_lock(volatile unsigned long*); 368 static inline void _S_unlock(volatile unsigned long*); 369# endif 370 371# ifdef __STL_PTHREADS 372 static pthread_mutex_t _S_node_allocator_lock; 373# endif 374 375# ifdef __STL_SOLTHREADS 376 static mutex_t _S_node_allocator_lock; 377# endif 378 379# ifdef __STL_WIN32THREADS 380 static CRITICAL_SECTION _S_node_allocator_lock; 381 static bool _S_node_allocator_lock_initialized; 382 383 public: 384 __default_alloc_template() { 385 // This assumes the first constructor is called before threads 386 // are started. 387 if (!_S_node_allocator_lock_initialized) { 388 InitializeCriticalSection(&_S_node_allocator_lock); 389 _S_node_allocator_lock_initialized = true; 390 } 391 } 392 private: 393# endif 394 395 class _Lock { 396 public: 397 _Lock() { __NODE_ALLOCATOR_LOCK; } 398 ~_Lock() { __NODE_ALLOCATOR_UNLOCK; } 399 }; 400 friend class _Lock; 401 402public: 403 404 /* __n must be > 0 */ 405 static void* allocate(size_t __n) 406 { 407 _Obj* __VOLATILE* __my_free_list; 408 _Obj* __RESTRICT __result; 409 410 if (__n > (size_t) _MAX_BYTES) { 411 return(malloc_alloc::allocate(__n)); 412 } 413 __my_free_list = _S_free_list + _S_freelist_index(__n); 414 // Acquire the lock here with a constructor call. 415 // This ensures that it is released in exit or during stack 416 // unwinding. 417# ifndef _NOTHREADS 418 /*REFERENCED*/ 419 _Lock __lock_instance; 420# endif 421 __result = *__my_free_list; 422 if (__result == 0) { 423 void* __r = _S_refill(_S_round_up(__n)); 424 return __r; 425 } 426 *__my_free_list = __result -> _M_free_list_link; 427 return (__result); 428 }; 429 430 /* __p may not be 0 */ 431 static void deallocate(void* __p, size_t __n) 432 { 433 _Obj* __q = (_Obj*)__p; 434 _Obj* __VOLATILE* __my_free_list; 435 436 if (__n > (size_t) _MAX_BYTES) { 437 malloc_alloc::deallocate(__p, __n); 438 return; 439 } 440 __my_free_list = _S_free_list + _S_freelist_index(__n); 441 // acquire lock 442# ifndef _NOTHREADS 443 /*REFERENCED*/ 444 _Lock __lock_instance; 445# endif /* _NOTHREADS */ 446 __q -> _M_free_list_link = *__my_free_list; 447 *__my_free_list = __q; 448 // lock is released here 449 } 450 451 static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz); 452 453} ; 454 455typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc; 456typedef __default_alloc_template<false, 0> single_client_alloc; 457 458 459 460/* We allocate memory in large chunks in order to avoid fragmenting */ 461/* the malloc heap too much. */ 462/* We assume that size is properly aligned. */ 463/* We hold the allocation lock. */ 464template <bool __threads, int __inst> 465char* 466__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, 467 int& __nobjs) 468{ 469 char* __result; 470 size_t __total_bytes = __size * __nobjs; 471 size_t __bytes_left = _S_end_free - _S_start_free; 472 473 if (__bytes_left >= __total_bytes) { 474 __result = _S_start_free; 475 _S_start_free += __total_bytes; 476 return(__result); 477 } else if (__bytes_left >= __size) { 478 __nobjs = (int)(__bytes_left/__size); 479 __total_bytes = __size * __nobjs; 480 __result = _S_start_free; 481 _S_start_free += __total_bytes; 482 return(__result); 483 } else { 484 size_t __bytes_to_get = 485 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); 486 // Try to make use of the left-over piece. 487 if (__bytes_left > 0) { 488 _Obj* __VOLATILE* __my_free_list = 489 _S_free_list + _S_freelist_index(__bytes_left); 490 491 ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list; 492 *__my_free_list = (_Obj*)_S_start_free; 493 } 494 _S_start_free = (char*)malloc(__bytes_to_get); 495 if (0 == _S_start_free) { 496 size_t __i; 497 _Obj* __VOLATILE* __my_free_list; 498 _Obj* __p; 499 // Try to make do with what we have. That can't 500 // hurt. We do not try smaller requests, since that tends 501 // to result in disaster on multi-process machines. 502 for (__i = __size; __i <= _MAX_BYTES; __i += _ALIGN) { 503 __my_free_list = _S_free_list + _S_freelist_index(__i); 504 __p = *__my_free_list; 505 if (0 != __p) { 506 *__my_free_list = __p -> _M_free_list_link; 507 _S_start_free = (char*)__p; 508 _S_end_free = _S_start_free + __i; 509 return(_S_chunk_alloc(__size, __nobjs)); 510 // Any leftover piece will eventually make it to the 511 // right free list. 512 } 513 } 514 _S_end_free = 0; // In case of exception. 515 _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get); 516 // This should either throw an 517 // exception or remedy the situation. Thus we assume it 518 // succeeded. 519 } 520 _S_heap_size += __bytes_to_get; 521 _S_end_free = _S_start_free + __bytes_to_get; 522 return(_S_chunk_alloc(__size, __nobjs)); 523 } 524} 525 526 527/* Returns an object of size __n, and optionally adds to size __n free list.*/ 528/* We assume that __n is properly aligned. */ 529/* We hold the allocation lock. */ 530template <bool __threads, int __inst> 531void* 532__default_alloc_template<__threads, __inst>::_S_refill(size_t __n) 533{ 534 int __nobjs = 20; 535 char* __chunk = _S_chunk_alloc(__n, __nobjs); 536 _Obj* __VOLATILE* __my_free_list; 537 _Obj* __result; 538 _Obj* __current_obj; 539 _Obj* __next_obj; 540 int __i; 541 542 if (1 == __nobjs) return(__chunk); 543 __my_free_list = _S_free_list + _S_freelist_index(__n); 544 545 /* Build free list in chunk */ 546 __result = (_Obj*)__chunk; 547 *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); 548 for (__i = 1; ; __i++) { 549 __current_obj = __next_obj; 550 __next_obj = (_Obj*)((char*)__next_obj + __n); 551 if (__nobjs - 1 == __i) { 552 __current_obj -> _M_free_list_link = 0; 553 break; 554 } else { 555 __current_obj -> _M_free_list_link = __next_obj; 556 } 557 } 558 return(__result); 559} 560 561template <bool threads, int inst> 562void* 563__default_alloc_template<threads, inst>::reallocate(void* __p, 564 size_t __old_sz, 565 size_t __new_sz) 566{ 567 void* __result; 568 size_t __copy_sz; 569 570 if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) { 571 return(realloc(__p, __new_sz)); 572 } 573 if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p); 574 __result = allocate(__new_sz); 575 __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz; 576 memcpy(__result, __p, __copy_sz); 577 deallocate(__p, __old_sz); 578 return(__result); 579} 580 581#ifdef __STL_PTHREADS 582 template <bool __threads, int __inst> 583 pthread_mutex_t 584 __default_alloc_template<__threads, __inst>::_S_node_allocator_lock 585 = PTHREAD_MUTEX_INITIALIZER; 586#endif 587 588#ifdef __STL_SOLTHREADS 589 template <bool __threads, int __inst> 590 mutex_t 591 __default_alloc_template<__threads, __inst>::_S_node_allocator_lock 592 = DEFAULTMUTEX; 593#endif 594 595#ifdef __STL_WIN32THREADS 596 template <bool __threads, int __inst> 597 CRITICAL_SECTION 598 __default_alloc_template<__threads, __inst>:: 599 _S_node_allocator_lock; 600 601 template <bool __threads, int __inst> 602 bool 603 __default_alloc_template<__threads, __inst>:: 604 _S_node_allocator_lock_initialized 605 = false; 606#endif 607 608#ifdef __STL_SGI_THREADS 609__STL_END_NAMESPACE 610#include <mutex.h> 611#include <time.h> /* XXX should use <ctime> */ 612__STL_BEGIN_NAMESPACE 613// Somewhat generic lock implementations. We need only test-and-set 614// and some way to sleep. These should work with both SGI pthreads 615// and sproc threads. They may be useful on other systems. 616template <bool __threads, int __inst> 617volatile unsigned long 618__default_alloc_template<__threads, __inst>::_S_node_allocator_lock = 0; 619 620#if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64)) || defined(__GNUC__) 621# define __test_and_set(l,v) test_and_set(l,v) 622#endif 623 624template <bool __threads, int __inst> 625void 626__default_alloc_template<__threads, __inst>:: 627 _S_lock(volatile unsigned long* __lock) 628{ 629 const unsigned __low_spin_max = 30; // spins if we suspect uniprocessor 630 const unsigned __high_spin_max = 1000; // spins for multiprocessor 631 static unsigned __spin_max = __low_spin_max; 632 unsigned __my_spin_max; 633 static unsigned __last_spins = 0; 634 unsigned __my_last_spins; 635 unsigned __junk; 636# define __ALLOC_PAUSE \ 637 __junk *= __junk; __junk *= __junk; __junk *= __junk; __junk *= __junk 638 int __i; 639 640 if (!__test_and_set((unsigned long*)__lock, 1)) { 641 return; 642 } 643 __my_spin_max = __spin_max; 644 __my_last_spins = __last_spins; 645 for (__i = 0; __i < __my_spin_max; __i++) { 646 if (__i < __my_last_spins/2 || *__lock) { 647 __ALLOC_PAUSE; 648 continue; 649 } 650 if (!__test_and_set((unsigned long*)__lock, 1)) { 651 // got it! 652 // Spinning worked. Thus we're probably not being scheduled 653 // against the other process with which we were contending. 654 // Thus it makes sense to spin longer the next time. 655 __last_spins = __i; 656 __spin_max = __high_spin_max; 657 return; 658 } 659 } 660 // We are probably being scheduled against the other process. Sleep. 661 __spin_max = __low_spin_max; 662 for (__i = 0 ;; ++__i) { 663 struct timespec __ts; 664 int __log_nsec = __i + 6; 665 666 if (!__test_and_set((unsigned long *)__lock, 1)) { 667 return; 668 } 669 if (__log_nsec > 27) __log_nsec = 27; 670 /* Max sleep is 2**27nsec ~ 60msec */ 671 __ts.tv_sec = 0; 672 __ts.tv_nsec = 1 << __log_nsec; 673 nanosleep(&__ts, 0); 674 } 675} 676 677template <bool __threads, int __inst> 678inline void 679__default_alloc_template<__threads, __inst>::_S_unlock( 680 volatile unsigned long* __lock) 681{ 682# if defined(__GNUC__) && __mips >= 3 683 asm("sync"); 684 *__lock = 0; 685# elif __mips >= 3 && (defined (_ABIN32) || defined(_ABI64)) 686 __lock_release(__lock); 687# else 688 *__lock = 0; 689 // This is not sufficient on many multiprocessors, since 690 // writes to protected variables and the lock may be reordered. 691# endif 692} 693#endif 694 695template <bool __threads, int __inst> 696char* __default_alloc_template<__threads, __inst>::_S_start_free = 0; 697 698template <bool __threads, int __inst> 699char* __default_alloc_template<__threads, __inst>::_S_end_free = 0; 700 701template <bool __threads, int __inst> 702size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0; 703 704template <bool __threads, int __inst> 705__default_alloc_template<__threads, __inst>::_Obj* __VOLATILE 706__default_alloc_template<__threads, __inst> ::_S_free_list[ 707 _NFREELISTS 708] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }; 709// The 16 zeros are necessary to make version 4.1 of the SunPro 710// compiler happy. Otherwise it appears to allocate too little 711// space for the array. 712 713# ifdef __STL_WIN32THREADS 714 // Create one to get critical section initialized. 715 // We do this onece per file, but only the first constructor 716 // does anything. 717 static alloc __node_allocator_dummy_instance; 718# endif 719 720#endif /* ! __USE_MALLOC */ 721 722// This implements allocators as specified in the C++ standard. 723// 724// Note that standard-conforming allocators use many language features 725// that are not yet widely implemented. In particular, they rely on 726// member templates, partial specialization, partial ordering of function 727// templates, the typename keyword, and the use of the template keyword 728// to refer to a template member of a dependent type. 729 730#ifdef __STL_USE_STD_ALLOCATORS 731 732template <class _Tp> 733class allocator { 734 typedef alloc _Alloc; // The underlying allocator. 735public: 736 typedef size_t size_type; 737 typedef ptrdiff_t difference_type; 738 typedef _Tp* pointer; 739 typedef const _Tp* const_pointer; 740 typedef _Tp& reference; 741 typedef const _Tp& const_reference; 742 typedef _Tp value_type; 743 744 template <class _Tp1> struct rebind { 745 typedef allocator<_Tp1> other; 746 }; 747 748 allocator() __STL_NOTHROW {} 749 allocator(const allocator&) __STL_NOTHROW {} 750 template <class _Tp1> allocator(const allocator<_Tp1>&) __STL_NOTHROW {} 751 ~allocator() __STL_NOTHROW {} 752 753 pointer address(reference __x) const { return &__x; } 754 const_pointer address(const_reference __x) const { return &__x; } 755 756 // __n is permitted to be 0. The C++ standard says nothing about what 757 // the return value is when __n == 0. 758 _Tp* allocate(size_type __n, const void* = 0) { 759 return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) 760 : 0; 761 } 762 763 // __p is not permitted to be a null pointer. 764 void deallocate(pointer __p, size_type __n) 765 { _Alloc::deallocate(__p, __n * sizeof(_Tp)); } 766 767 size_type max_size() const __STL_NOTHROW 768 { return size_t(-1) / sizeof(_Tp); } 769 770 void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); } 771 void destroy(pointer __p) { __p->~_Tp(); } 772}; 773 774template<> 775class allocator<void> { 776 typedef size_t size_type; 777 typedef ptrdiff_t difference_type; 778 typedef void* pointer; 779 typedef const void* const_pointer; 780 typedef void value_type; 781 782 template <class _Tp1> struct rebind { 783 typedef allocator<_Tp1> other; 784 }; 785}; 786 787 788template <class _T1, class _T2> 789inline bool operator==(const allocator<_T1>&, const allocator<_T2>&) 790{ 791 return true; 792} 793 794template <class _T1, class _T2> 795inline bool operator!=(const allocator<_T1>&, const allocator<_T2>&) 796{ 797 return false; 798} 799 800// Allocator adaptor to turn an SGI-style allocator (e.g. alloc, malloc_alloc) 801// into a standard-conforming allocator. Note that this adaptor does 802// *not* assume that all objects of the underlying alloc class are 803// identical, nor does it assume that all of the underlying alloc's 804// member functions are static member functions. Note, also, that 805// __allocator<_Tp, alloc> is essentially the same thing as allocator<_Tp>. 806 807template <class _Tp, class _Alloc> 808struct __allocator { 809 _Alloc __underlying_alloc; 810 811 typedef size_t size_type; 812 typedef ptrdiff_t difference_type; 813 typedef _Tp* pointer; 814 typedef const _Tp* const_pointer; 815 typedef _Tp& reference; 816 typedef const _Tp& const_reference; 817 typedef _Tp value_type; 818 819 template <class _Tp1> struct rebind { 820 typedef __allocator<_Tp1, _Alloc> other; 821 }; 822 823 __allocator() __STL_NOTHROW {} 824 __allocator(const __allocator& __a) __STL_NOTHROW 825 : __underlying_alloc(__a.__underlying_alloc) {} 826 template <class _Tp1> 827 __allocator(const __allocator<_Tp1, _Alloc>& __a) __STL_NOTHROW 828 : __underlying_alloc(__a.__underlying_alloc) {} 829 ~__allocator() __STL_NOTHROW {} 830 831 pointer address(reference __x) const { return &__x; } 832 const_pointer address(const_reference __x) const { return &__x; } 833 834 // __n is permitted to be 0. 835 _Tp* allocate(size_type __n, const void* = 0) { 836 return __n != 0 837 ? static_cast<_Tp*>(__underlying_alloc.allocate(__n * sizeof(_Tp))) 838 : 0; 839 } 840 841 // __p is not permitted to be a null pointer. 842 void deallocate(pointer __p, size_type __n) 843 { __underlying_alloc.deallocate(__p, __n * sizeof(_Tp)); } 844 845 size_type max_size() const __STL_NOTHROW 846 { return size_t(-1) / sizeof(_Tp); } 847 848 void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); } 849 void destroy(pointer __p) { __p->~_Tp(); } 850}; 851 852template <class _Alloc> 853class __allocator<void, _Alloc> { 854 typedef size_t size_type; 855 typedef ptrdiff_t difference_type; 856 typedef void* pointer; 857 typedef const void* const_pointer; 858 typedef void value_type; 859 860 template <class _Tp1> struct rebind { 861 typedef __allocator<_Tp1, _Alloc> other; 862 }; 863}; 864 865template <class _Tp, class _Alloc> 866inline bool operator==(const __allocator<_Tp, _Alloc>& __a1, 867 const __allocator<_Tp, _Alloc>& __a2) 868{ 869 return __a1.__underlying_alloc == __a2.__underlying_alloc; 870} 871 872#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 873template <class _Tp, class _Alloc> 874inline bool operator!=(const __allocator<_Tp, _Alloc>& __a1, 875 const __allocator<_Tp, _Alloc>& __a2) 876{ 877 return __a1.__underlying_alloc != __a2.__underlying_alloc; 878} 879#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 880 881// Comparison operators for all of the predifined SGI-style allocators. 882// This ensures that __allocator<malloc_alloc> (for example) will 883// work correctly. 884 885template <int inst> 886inline bool operator==(const __malloc_alloc_template<inst>&, 887 const __malloc_alloc_template<inst>&) 888{ 889 return true; 890} 891 892#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 893template <int __inst> 894inline bool operator!=(const __malloc_alloc_template<__inst>&, 895 const __malloc_alloc_template<__inst>&) 896{ 897 return false; 898} 899#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 900 901#ifndef __USE_MALLOC 902template <bool __threads, int __inst> 903inline bool operator==(const __default_alloc_template<__threads, __inst>&, 904 const __default_alloc_template<__threads, __inst>&) 905{ 906 return true; 907} 908 909# ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 910template <bool __threads, int __inst> 911inline bool operator!=(const __default_alloc_template<__threads, __inst>&, 912 const __default_alloc_template<__threads, __inst>&) 913{ 914 return false; 915} 916# endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 917#endif 918 919template <class _Alloc> 920inline bool operator==(const debug_alloc<_Alloc>&, 921 const debug_alloc<_Alloc>&) { 922 return true; 923} 924 925#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 926template <class _Alloc> 927inline bool operator!=(const debug_alloc<_Alloc>&, 928 const debug_alloc<_Alloc>&) { 929 return false; 930} 931#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 932 933// Another allocator adaptor: _Alloc_traits. This serves two 934// purposes. First, make it possible to write containers that can use 935// either SGI-style allocators or standard-conforming allocator. 936// Second, provide a mechanism so that containers can query whether or 937// not the allocator has distinct instances. If not, the container 938// can avoid wasting a word of memory to store an empty object. 939 940// This adaptor uses partial specialization. The general case of 941// _Alloc_traits<_Tp, _Alloc> assumes that _Alloc is a 942// standard-conforming allocator, possibly with non-equal instances 943// and non-static members. (It still behaves correctly even if _Alloc 944// has static member and if all instances are equal. Refinements 945// affect performance, not correctness.) 946 947// There are always two members: allocator_type, which is a standard- 948// conforming allocator type for allocating objects of type _Tp, and 949// _S_instanceless, a static const member of type bool. If 950// _S_instanceless is true, this means that there is no difference 951// between any two instances of type allocator_type. Furthermore, if 952// _S_instanceless is true, then _Alloc_traits has one additional 953// member: _Alloc_type. This type encapsulates allocation and 954// deallocation of objects of type _Tp through a static interface; it 955// has two member functions, whose signatures are 956// static _Tp* allocate(size_t) 957// static void deallocate(_Tp*, size_t) 958 959// The fully general version. 960 961template <class _Tp, class _Allocator> 962struct _Alloc_traits 963{ 964 static const bool _S_instanceless = false; 965 typedef typename _Allocator::__STL_TEMPLATE rebind<_Tp>::other 966 allocator_type; 967}; 968 969template <class _Tp, class _Allocator> 970const bool _Alloc_traits<_Tp, _Allocator>::_S_instanceless; 971 972// The version for the default allocator. 973 974template <class _Tp, class _Tp1> 975struct _Alloc_traits<_Tp, allocator<_Tp1> > 976{ 977 static const bool _S_instanceless = true; 978 typedef simple_alloc<_Tp, alloc> _Alloc_type; 979 typedef allocator<_Tp> allocator_type; 980}; 981 982// Versions for the predefined SGI-style allocators. 983 984template <class _Tp, int __inst> 985struct _Alloc_traits<_Tp, __malloc_alloc_template<__inst> > 986{ 987 static const bool _S_instanceless = true; 988 typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type; 989 typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type; 990}; 991 992#ifndef __USE_MALLOC 993template <class _Tp, bool __threads, int __inst> 994struct _Alloc_traits<_Tp, __default_alloc_template<__threads, __inst> > 995{ 996 static const bool _S_instanceless = true; 997 typedef simple_alloc<_Tp, __default_alloc_template<__threads, __inst> > 998 _Alloc_type; 999 typedef __allocator<_Tp, __default_alloc_template<__threads, __inst> > 1000 allocator_type; 1001}; 1002#endif 1003 1004template <class _Tp, class _Alloc> 1005struct _Alloc_traits<_Tp, debug_alloc<_Alloc> > 1006{ 1007 static const bool _S_instanceless = true; 1008 typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type; 1009 typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type; 1010}; 1011 1012// Versions for the __allocator adaptor used with the predefined 1013// SGI-style allocators. 1014 1015template <class _Tp, class _Tp1, int __inst> 1016struct _Alloc_traits<_Tp, 1017 __allocator<_Tp1, __malloc_alloc_template<__inst> > > 1018{ 1019 static const bool _S_instanceless = true; 1020 typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type; 1021 typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type; 1022}; 1023 1024#ifndef __USE_MALLOC 1025template <class _Tp, class _Tp1, bool __thr, int __inst> 1026struct _Alloc_traits<_Tp, 1027 __allocator<_Tp1, 1028 __default_alloc_template<__thr, __inst> > > 1029{ 1030 static const bool _S_instanceless = true; 1031 typedef simple_alloc<_Tp, __default_alloc_template<__thr,__inst> > 1032 _Alloc_type; 1033 typedef __allocator<_Tp, __default_alloc_template<__thr,__inst> > 1034 allocator_type; 1035}; 1036#endif 1037 1038template <class _Tp, class _Tp1, class _Alloc> 1039struct _Alloc_traits<_Tp, __allocator<_Tp1, debug_alloc<_Alloc> > > 1040{ 1041 static const bool _S_instanceless = true; 1042 typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type; 1043 typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type; 1044}; 1045 1046 1047#endif /* __STL_USE_STD_ALLOCATORS */ 1048 1049#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 1050#pragma reset woff 1174 1051#endif 1052 1053__STL_END_NAMESPACE 1054 1055#undef __PRIVATE 1056 1057#endif /* __SGI_STL_INTERNAL_ALLOC_H */ 1058 1059// Local Variables: 1060// mode:C++ 1061// End: 1062