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