contrib/libstdc++/stl/stl_alloc.h

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