- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_alloc.h

    00001 /*
    00002  * Copyright (c) 1996-1997
    00003  * Silicon Graphics Computer Systems, Inc.
    00004  *
    00005  * Permission to use, copy, modify, distribute and sell this software
    00006  * and its documentation for any purpose is hereby granted without fee,
    00007  * provided that the above copyright notice appear in all copies and
    00008  * that both that copyright notice and this permission notice appear
    00009  * in supporting documentation.  Silicon Graphics makes no
    00010  * representations about the suitability of this software for any
    00011  * purpose.  It is provided "as is" without express or implied warranty.
    00012  */
    00013
    00014 /* NOTE: This is an internal header file, included by other STL headers.
    00015  *   You should not attempt to use it directly.
    00016  */
    00017
    00018 #ifndef __SGI_STL_INTERNAL_ALLOC_H
    00019 #define __SGI_STL_INTERNAL_ALLOC_H
    00020
    00021 #ifdef __SUNPRO_CC
    00022 #  define __PRIVATE public
    00023    // Extra access restrictions prevent us from really making some things
    00024    // private.
    00025 #else
    00026 #  define __PRIVATE private
    00027 #endif
    00028
    00029 #ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
    00030 #  define __USE_MALLOC
    00031 #endif
    00032
    00033
    00034 // This implements some standard node allocators.  These are
    00035 // NOT the same as the allocators in the C++ draft standard or in
    00036 // in the original STL.  They do not encapsulate different pointer
    00037 // types; indeed we assume that there is only one pointer type.
    00038 // The allocation primitives are intended to allocate individual objects,
    00039 // not larger arenas as with the original STL allocators.
    00040
    00041 #if 0
    00042 #   include <new>
    00043 #   define __THROW_BAD_ALLOC throw bad_alloc()
    00044 #elif !defined(__THROW_BAD_ALLOC)
    00045 #   include <iostream>
    00046 #   define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
    00047 #endif
    00048
    00049 #ifdef __STL_WIN32THREADS
    00050 #   include <windows.h>
    00051 #endif
    00052
    00053 #include <stddef.h>
    00054 #include <stdlib.h>
    00055 #include <string.h>
    00056 #include <assert.h>
    00057 #ifndef __RESTRICT
    00058 #  define __RESTRICT
    00059 #endif
    00060
    00061 #if !defined(__STL_PTHREADS) && !defined(__STL_SOLTHREADS) \
    00062  && !defined(_NOTHREADS) \
    00063  && !defined(__STL_SGI_THREADS) && !defined(__STL_WIN32THREADS)
    00064 #   define _NOTHREADS
    00065 #endif
    00066
    00067 # ifdef __STL_PTHREADS
    00068     // POSIX Threads
    00069     // This is dubious, since this is likely to be a high contention
    00070     // lock.   Performance may not be adequate.
    00071 #   include <pthread.h>
    00072 #   define __NODE_ALLOCATOR_LOCK \
    00073         if (threads) pthread_mutex_lock(&_S_node_allocator_lock)
    00074 #   define __NODE_ALLOCATOR_UNLOCK \
    00075         if (threads) pthread_mutex_unlock(&_S_node_allocator_lock)
    00076 #   define __NODE_ALLOCATOR_THREADS true
    00077 #   define __VOLATILE volatile  // Needed at -O3 on SGI
    00078 # endif
    00079 # ifdef __STL_SOLTHREADS
    00080 #   include <thread.h>
    00081 #   define __NODE_ALLOCATOR_LOCK \
    00082         if (threads) mutex_lock(&_S_node_allocator_lock)
    00083 #   define __NODE_ALLOCATOR_UNLOCK \
    00084         if (threads) mutex_unlock(&_S_node_allocator_lock)
    00085 #   define __NODE_ALLOCATOR_THREADS true
    00086 #   define __VOLATILE
    00087 # endif
    00088 # ifdef __STL_WIN32THREADS
    00089     // The lock needs to be initialized by constructing an allocator
    00090     // objects of the right type.  We do that here explicitly for alloc.
    00091 #   define __NODE_ALLOCATOR_LOCK \
    00092         EnterCriticalSection(&_S_node_allocator_lock)
    00093 #   define __NODE_ALLOCATOR_UNLOCK \
    00094         LeaveCriticalSection(&_S_node_allocator_lock)
    00095 #   define __NODE_ALLOCATOR_THREADS true
    00096 #   define __VOLATILE volatile  // may not be needed
    00097 # endif /* WIN32THREADS */
    00098 # ifdef __STL_SGI_THREADS
    00099     // This should work without threads, with sproc threads, or with
    00100     // pthreads.  It is suboptimal in all cases.
    00101     // It is unlikely to even compile on nonSGI machines.
    00102
    00103     extern "C" {
    00104       extern int __us_rsthread_malloc;
    00105     }
    00106         // The above is copied from malloc.h.  Including <malloc.h>
    00107         // would be cleaner but fails with certain levels of standard
    00108         // conformance.
    00109 #   define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \
    00110                 { _S_lock(&_S_node_allocator_lock); }
    00111 #   define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \
    00112                 { _S_unlock(&_S_node_allocator_lock); }
    00113 #   define __NODE_ALLOCATOR_THREADS true
    00114 #   define __VOLATILE volatile  // Needed at -O3 on SGI
    00115 # endif
    00116 # ifdef _NOTHREADS
    00117 //  Thread-unsafe
    00118 #   define __NODE_ALLOCATOR_LOCK
    00119 #   define __NODE_ALLOCATOR_UNLOCK
    00120 #   define __NODE_ALLOCATOR_THREADS false
    00121 #   define __VOLATILE
    00122 # endif
    00123
    00124 __STL_BEGIN_NAMESPACE
    00125
    00126 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00127 #pragma set woff 1174
    00128 #endif
    00129
    00130 // Malloc-based allocator.  Typically slower than default alloc below.
    00131 // Typically thread-safe and more storage efficient.
    00132 #ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
    00133 # ifdef __DECLARE_GLOBALS_HERE
    00134     void (* __malloc_alloc_oom_handler)() = 0;
    00135     // g++ 2.7.2 does not handle static template data members.
    00136 # else
    00137     extern void (* __malloc_alloc_oom_handler)();
    00138 # endif
    00139 #endif
    00140
    00141 template <int __inst>
    00142 class __malloc_alloc_template {
    00143
    00144 private:
    00145
    00146   static void* _S_oom_malloc(size_t);
    00147   static void* _S_oom_realloc(void*, size_t);
    00148
    00149 #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    00150   static void (* __malloc_alloc_oom_handler)();
    00151 #endif
    00152
    00153 public:
    00154
    00155   static void* allocate(size_t __n)
    00156   {
    00157     void* __result = malloc(__n);
    00158     if (0 == __result) __result = _S_oom_malloc(__n);
    00159     return __result;
    00160   }
    00161
    00162   static void deallocate(void* __p, size_t /* __n */)
    00163   {
    00164     free(__p);
    00165   }
    00166
    00167   static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
    00168   {
    00169     void* __result = realloc(__p, __new_sz);
    00170     if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
    00171     return __result;
    00172   }
    00173
    00174   static void (* __set_malloc_handler(void (*__f)()))()
    00175   {
    00176     void (* __old)() = __malloc_alloc_oom_handler;
    00177     __malloc_alloc_oom_handler = __f;
    00178     return(__old);
    00179   }
    00180
    00181 };
    00182
    00183 // malloc_alloc out-of-memory handling
    00184
    00185 #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    00186 template <int __inst>
    00187 void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
    00188 #endif
    00189
    00190 template <int __inst>
    00191 void*
    00192 __malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
    00193 {
    00194     void (* __my_malloc_handler)();
    00195     void* __result;
    00196
    00197     for (;;) {
    00198         __my_malloc_handler = __malloc_alloc_oom_handler;
    00199         if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
    00200         (*__my_malloc_handler)();
    00201         __result = malloc(__n);
    00202         if (__result) return(__result);
    00203     }
    00204 }
    00205
    00206 template <int __inst>
    00207 void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
    00208 {
    00209     void (* __my_malloc_handler)();
    00210     void* __result;
    00211
    00212     for (;;) {
    00213         __my_malloc_handler = __malloc_alloc_oom_handler;
    00214         if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
    00215         (*__my_malloc_handler)();
    00216         __result = realloc(__p, __n);
    00217         if (__result) return(__result);
    00218     }
    00219 }
    00220
    00221 typedef __malloc_alloc_template<0> malloc_alloc;
    00222
    00223 template<class _Tp, class _Alloc>
    00224 class simple_alloc {
    00225
    00226 public:
    00227     static _Tp* allocate(size_t __n)
    00228       { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
    00229     static _Tp* allocate(void)
    00230       { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
    00231     static void deallocate(_Tp* __p, size_t __n)
    00232       { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
    00233     static void deallocate(_Tp* __p)
    00234       { _Alloc::deallocate(__p, sizeof (_Tp)); }
    00235 };
    00236
    00237 // Allocator adaptor to check size arguments for debugging.
    00238 // Reports errors using assert.  Checking can be disabled with
    00239 // NDEBUG, but it's far better to just use the underlying allocator
    00240 // instead when no checking is desired.
    00241 // There is some evidence that this can confuse Purify.
    00242 template <class _Alloc>
    00243 class debug_alloc {
    00244
    00245 private:
    00246
    00247   enum {_S_extra = 8};  // Size of space used to store size.  Note
    00248                         // that this must be large enough to preserve
    00249                         // alignment.
    00250
    00251 public:
    00252
    00253   static void* allocate(size_t __n)
    00254   {
    00255     char* __result = (char*)_Alloc::allocate(__n + _S_extra);
    00256     *(size_t*)__result = __n;
    00257     return __result + _S_extra;
    00258   }
    00259
    00260   static void deallocate(void* __p, size_t __n)
    00261   {
    00262     char* __real_p = (char*)__p - _S_extra;
    00263     assert(*(size_t*)__real_p == __n);
    00264     _Alloc::deallocate(__real_p, __n + _S_extra);
    00265   }
    00266
    00267   static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz)
    00268   {
    00269     char* __real_p = (char*)__p - _S_extra;
    00270     assert(*(size_t*)__real_p == __old_sz);
    00271     char* __result = (char*)
    00272       _Alloc::reallocate(__real_p, __old_sz + _S_extra, __new_sz + _S_extra);
    00273     *(size_t*)__result = __new_sz;
    00274     return __result + _S_extra;
    00275   }
    00276
    00277 };
    00278
    00279
    00280 # ifdef __USE_MALLOC
    00281
    00282 typedef malloc_alloc alloc;
    00283 typedef malloc_alloc single_client_alloc;
    00284
    00285 # else
    00286
    00287
    00288 // Default node allocator.
    00289 // With a reasonable compiler, this should be roughly as fast as the
    00290 // original STL class-specific allocators, but with less fragmentation.
    00291 // Default_alloc_template parameters are experimental and MAY
    00292 // DISAPPEAR in the future.  Clients should just use alloc for now.
    00293 //
    00294 // Important implementation properties:
    00295 // 1. If the client request an object of size > _MAX_BYTES, the resulting
    00296 //    object will be obtained directly from malloc.
    00297 // 2. In all other cases, we allocate an object of size exactly
    00298 //    _S_round_up(requested_size).  Thus the client has enough size
    00299 //    information that we can return the object to the proper free list
    00300 //    without permanently losing part of the object.
    00301 //
    00302
    00303 // The first template parameter specifies whether more than one thread
    00304 // may use this allocator.  It is safe to allocate an object from
    00305 // one instance of a default_alloc and deallocate it with another
    00306 // one.  This effectively transfers its ownership to the second one.
    00307 // This may have undesirable effects on reference locality.
    00308 // The second parameter is unreferenced and serves only to allow the
    00309 // creation of multiple default_alloc instances.
    00310 // Node that containers built on different allocator instances have
    00311 // different types, limiting the utility of this approach.
    00312 #ifdef __SUNPRO_CC
    00313 // breaks if we make these template class members:
    00314   enum {_ALIGN = 8};
    00315   enum {_MAX_BYTES = 128};
    00316   enum {_NFREELISTS = _MAX_BYTES/_ALIGN};
    00317 #endif
    00318
    00319 template <bool threads, int inst>
    00320 class __default_alloc_template {
    00321
    00322 private:
    00323   // Really we should use static const int x = N
    00324   // instead of enum { x = N }, but few compilers accept the former.
    00325 # ifndef __SUNPRO_CC
    00326     enum {_ALIGN = 8};
    00327     enum {_MAX_BYTES = 128};
    00328     enum {_NFREELISTS = _MAX_BYTES/_ALIGN};
    00329 # endif
    00330   static size_t
    00331   _S_round_up(size_t __bytes)
    00332     { return (((__bytes) + _ALIGN-1) & ~(_ALIGN - 1)); }
    00333
    00334 __PRIVATE:
    00335   union _Obj {
    00336         union _Obj* _M_free_list_link;
    00337         char _M_client_data[1];    /* The client sees this.        */
    00338   };
    00339 private:
    00340 # ifdef __SUNPRO_CC
    00341     static _Obj* __VOLATILE _S_free_list[];
    00342         // Specifying a size results in duplicate def for 4.1
    00343 # else
    00344     static _Obj* __VOLATILE _S_free_list[_NFREELISTS];
    00345 # endif
    00346   static  size_t _S_freelist_index(size_t __bytes) {
    00347         return (((__bytes) + _ALIGN-1)/_ALIGN - 1);
    00348   }
    00349
    00350   // Returns an object of size __n, and optionally adds to size __n free list.
    00351   static void* _S_refill(size_t __n);
    00352   // Allocates a chunk for nobjs of size "size".  nobjs may be reduced
    00353   // if it is inconvenient to allocate the requested number.
    00354   static char* _S_chunk_alloc(size_t __size, int& __nobjs);
    00355
    00356   // Chunk allocation state.
    00357   static char* _S_start_free;
    00358   static char* _S_end_free;
    00359   static size_t _S_heap_size;
    00360
    00361 # ifdef __STL_SGI_THREADS
    00362     static volatile unsigned long _S_node_allocator_lock;
    00363     static void _S_lock(volatile unsigned long*);
    00364     static inline void _S_unlock(volatile unsigned long*);
    00365 # endif
    00366
    00367 # ifdef __STL_PTHREADS
    00368     static pthread_mutex_t _S_node_allocator_lock;
    00369 # endif
    00370
    00371 # ifdef __STL_SOLTHREADS
    00372     static mutex_t _S_node_allocator_lock;
    00373 # endif
    00374
    00375 # ifdef __STL_WIN32THREADS
    00376     static CRITICAL_SECTION _S_node_allocator_lock;
    00377     static bool _S_node_allocator_lock_initialized;
    00378
    00379   public:
    00380     __default_alloc_template() {
    00381         // This assumes the first constructor is called before threads
    00382         // are started.
    00383         if (!_S_node_allocator_lock_initialized) {
    00384             InitializeCriticalSection(&_S_node_allocator_lock);
    00385             _S_node_allocator_lock_initialized = true;
    00386         }
    00387     }
    00388   private:
    00389 # endif
    00390
    00391     class _Lock {
    00392         public:
    00393             _Lock() { __NODE_ALLOCATOR_LOCK; }
    00394             ~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
    00395     };
    00396     friend class _Lock;
    00397
    00398 public:
    00399
    00400   /* __n must be > 0      */
    00401   static void* allocate(size_t __n)
    00402   {
    00403     _Obj* __VOLATILE* __my_free_list;
    00404     _Obj* __RESTRICT __result;
    00405
    00406     if (__n > (size_t) _MAX_BYTES) {
    00407         return(malloc_alloc::allocate(__n));
    00408     }
    00409     __my_free_list = _S_free_list + _S_freelist_index(__n);
    00410     // Acquire the lock here with a constructor call.
    00411     // This ensures that it is released in exit or during stack
    00412     // unwinding.
    00413 #       ifndef _NOTHREADS
    00414         /*REFERENCED*/
    00415         _Lock __lock_instance;
    00416 #       endif
    00417     __result = *__my_free_list;
    00418     if (__result == 0) {
    00419         void* __r = _S_refill(_S_round_up(__n));
    00420         return __r;
    00421     }
    00422     *__my_free_list = __result -> _M_free_list_link;
    00423     return (__result);
    00424   };
    00425
    00426   /* __p may not be 0 */
    00427   static void deallocate(void* __p, size_t __n)
    00428   {
    00429     _Obj* __q = (_Obj*)__p;
    00430     _Obj* __VOLATILE* __my_free_list;
    00431
    00432     if (__n > (size_t) _MAX_BYTES) {
    00433         malloc_alloc::deallocate(__p, __n);
    00434         return;
    00435     }
    00436     __my_free_list = _S_free_list + _S_freelist_index(__n);
    00437     // acquire lock
    00438 #       ifndef _NOTHREADS
    00439         /*REFERENCED*/
    00440         _Lock __lock_instance;
    00441 #       endif /* _NOTHREADS */
    00442     __q -> _M_free_list_link = *__my_free_list;
    00443     *__my_free_list = __q;
    00444     // lock is released here
    00445   }
    00446
    00447   static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);
    00448
    00449 } ;
    00450
    00451 typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
    00452 typedef __default_alloc_template<false, 0> single_client_alloc;
    00453
    00454
    00455
    00456 /* We allocate memory in large chunks in order to avoid fragmenting     */
    00457 /* the malloc heap too much.                                            */
    00458 /* We assume that size is properly aligned.                             */
    00459 /* We hold the allocation lock.                                         */
    00460 template <bool __threads, int __inst>
    00461 char*
    00462 __default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
    00463                                                             int& __nobjs)
    00464 {
    00465     char* __result;
    00466     size_t __total_bytes = __size * __nobjs;
    00467     size_t __bytes_left = _S_end_free - _S_start_free;
    00468
    00469     if (__bytes_left >= __total_bytes) {
    00470         __result = _S_start_free;
    00471         _S_start_free += __total_bytes;
    00472         return(__result);
    00473     } else if (__bytes_left >= __size) {
    00474         __nobjs = (int)(__bytes_left/__size);
    00475         __total_bytes = __size * __nobjs;
    00476         __result = _S_start_free;
    00477         _S_start_free += __total_bytes;
    00478         return(__result);
    00479     } else {
    00480         size_t __bytes_to_get =
    00481           2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
    00482         // Try to make use of the left-over piece.
    00483         if (__bytes_left > 0) {
    00484             _Obj* __VOLATILE* __my_free_list =
    00485                         _S_free_list + _S_freelist_index(__bytes_left);
    00486
    00487             ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
    00488             *__my_free_list = (_Obj*)_S_start_free;
    00489         }
    00490         _S_start_free = (char*)malloc(__bytes_to_get);
    00491         if (0 == _S_start_free) {
    00492             size_t __i;
    00493             _Obj* __VOLATILE* __my_free_list;
    00494             _Obj* __p;
    00495             // Try to make do with what we have.  That can't
    00496             // hurt.  We do not try smaller requests, since that tends
    00497             // to result in disaster on multi-process machines.
    00498             for (__i = __size; __i <= _MAX_BYTES; __i += _ALIGN) {
    00499                 __my_free_list = _S_free_list + _S_freelist_index(__i);
    00500                 __p = *__my_free_list;
    00501                 if (0 != __p) {
    00502                     *__my_free_list = __p -> _M_free_list_link;
    00503                     _S_start_free = (char*)__p;
    00504                     _S_end_free = _S_start_free + __i;
    00505                     return(_S_chunk_alloc(__size, __nobjs));
    00506                     // Any leftover piece will eventually make it to the
    00507                     // right free list.
    00508                 }
    00509             }
    00510             _S_end_free = 0;    // In case of exception.
    00511             _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
    00512             // This should either throw an
    00513             // exception or remedy the situation.  Thus we assume it
    00514             // succeeded.
    00515         }
    00516         _S_heap_size += __bytes_to_get;
    00517         _S_end_free = _S_start_free + __bytes_to_get;
    00518         return(_S_chunk_alloc(__size, __nobjs));
    00519     }
    00520 }
    00521
    00522
    00523 /* Returns an object of size __n, and optionally adds to size __n free list.*/
    00524 /* We assume that __n is properly aligned.                                */
    00525 /* We hold the allocation lock.                                         */
    00526 template <bool __threads, int __inst>
    00527 void*
    00528 __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
    00529 {
    00530     int __nobjs = 20;
    00531     char* __chunk = _S_chunk_alloc(__n, __nobjs);
    00532     _Obj* __VOLATILE* __my_free_list;
    00533     _Obj* __result;
    00534     _Obj* __current_obj;
    00535     _Obj* __next_obj;
    00536     int __i;
    00537
    00538     if (1 == __nobjs) return(__chunk);
    00539     __my_free_list = _S_free_list + _S_freelist_index(__n);
    00540
    00541     /* Build free list in chunk */
    00542       __result = (_Obj*)__chunk;
    00543       *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
    00544       for (__i = 1; ; __i++) {
    00545         __current_obj = __next_obj;
    00546         __next_obj = (_Obj*)((char*)__next_obj + __n);
    00547         if (__nobjs - 1 == __i) {
    00548             __current_obj -> _M_free_list_link = 0;
    00549             break;
    00550         } else {
    00551             __current_obj -> _M_free_list_link = __next_obj;
    00552         }
    00553       }
    00554     return(__result);
    00555 }
    00556
    00557 template <bool threads, int inst>
    00558 void*
    00559 __default_alloc_template<threads, inst>::reallocate(void* __p,
    00560                                                     size_t __old_sz,
    00561                                                     size_t __new_sz)
    00562 {
    00563     void* __result;
    00564     size_t __copy_sz;
    00565
    00566     if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
    00567         return(realloc(__p, __new_sz));
    00568     }
    00569     if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
    00570     __result = allocate(__new_sz);
    00571     __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
    00572     memcpy(__result, __p, __copy_sz);
    00573     deallocate(__p, __old_sz);
    00574     return(__result);
    00575 }
    00576
    00577 #ifdef __STL_PTHREADS
    00578     template <bool __threads, int __inst>
    00579     pthread_mutex_t
    00580     __default_alloc_template<__threads, __inst>::_S_node_allocator_lock
    00581         = PTHREAD_MUTEX_INITIALIZER;
    00582 #endif
    00583
    00584 #ifdef __STL_SOLTHREADS
    00585     template <bool __threads, int __inst>
    00586     mutex_t
    00587     __default_alloc_template<__threads, __inst>::_S_node_allocator_lock
    00588         = DEFAULTMUTEX;
    00589 #endif
    00590
    00591 #ifdef __STL_WIN32THREADS
    00592     template <bool __threads, int __inst>
    00593     CRITICAL_SECTION
    00594     __default_alloc_template<__threads, __inst>::
    00595       _S_node_allocator_lock;
    00596
    00597     template <bool __threads, int __inst>
    00598     bool
    00599     __default_alloc_template<__threads, __inst>::
    00600       _S_node_allocator_lock_initialized
    00601         = false;
    00602 #endif
    00603
    00604 #ifdef __STL_SGI_THREADS
    00605 __STL_END_NAMESPACE
    00606 #include <mutex.h>
    00607 #include <time.h>  /* XXX should use <ctime> */
    00608 __STL_BEGIN_NAMESPACE
    00609 // Somewhat generic lock implementations.  We need only test-and-set
    00610 // and some way to sleep.  These should work with both SGI pthreads
    00611 // and sproc threads.  They may be useful on other systems.
    00612 template <bool __threads, int __inst>
    00613 volatile unsigned long
    00614 __default_alloc_template<__threads, __inst>::_S_node_allocator_lock = 0;
    00615
    00616 #if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64)) || defined(__GNUC__)
    00617 #   define __test_and_set(l,v) test_and_set(l,v)
    00618 #endif
    00619
    00620 template <bool __threads, int __inst>
    00621 void
    00622 __default_alloc_template<__threads, __inst>::
    00623   _S_lock(volatile unsigned long* __lock)
    00624 {
    00625     const unsigned __low_spin_max = 30;  // spins if we suspect uniprocessor
    00626     const unsigned __high_spin_max = 1000; // spins for multiprocessor
    00627     static unsigned __spin_max = __low_spin_max;
    00628     unsigned __my_spin_max;
    00629     static unsigned __last_spins = 0;
    00630     unsigned __my_last_spins;
    00631     unsigned __junk;
    00632 #   define __ALLOC_PAUSE \
    00633       __junk *= __junk; __junk *= __junk; __junk *= __junk; __junk *= __junk
    00634     int __i;
    00635
    00636     if (!__test_and_set((unsigned long*)__lock, 1)) {
    00637         return;
    00638     }
    00639     __my_spin_max = __spin_max;
    00640     __my_last_spins = __last_spins;
    00641     for (__i = 0; __i < __my_spin_max; __i++) {
    00642         if (__i < __my_last_spins/2 || *__lock) {
    00643             __ALLOC_PAUSE;
    00644             continue;
    00645         }
    00646         if (!__test_and_set((unsigned long*)__lock, 1)) {
    00647             // got it!
    00648             // Spinning worked.  Thus we're probably not being scheduled
    00649             // against the other process with which we were contending.
    00650             // Thus it makes sense to spin longer the next time.
    00651             __last_spins = __i;
    00652             __spin_max = __high_spin_max;
    00653             return;
    00654         }
    00655     }
    00656     // We are probably being scheduled against the other process.  Sleep.
    00657     __spin_max = __low_spin_max;
    00658     for (__i = 0 ;; ++__i) {
    00659         struct timespec __ts;
    00660         int __log_nsec = __i + 6;
    00661
    00662         if (!__test_and_set((unsigned long *)__lock, 1)) {
    00663             return;
    00664         }
    00665         if (__log_nsec > 27) __log_nsec = 27;
    00666                 /* Max sleep is 2**27nsec ~ 60msec      */
    00667         __ts.tv_sec = 0;
    00668         __ts.tv_nsec = 1 << __log_nsec;
    00669         nanosleep(&__ts, 0);
    00670     }
    00671 }
    00672
    00673 template <bool __threads, int __inst>
    00674 inline void
    00675 __default_alloc_template<__threads, __inst>::_S_unlock(
    00676   volatile unsigned long* __lock)
    00677 {
    00678 #   if defined(__GNUC__) && __mips >= 3
    00679         asm("sync");
    00680         *__lock = 0;
    00681 #   elif __mips >= 3 && (defined (_ABIN32) || defined(_ABI64))
    00682         __lock_release(__lock);
    00683 #   else
    00684         *__lock = 0;
    00685         // This is not sufficient on many multiprocessors, since
    00686         // writes to protected variables and the lock may be reordered.
    00687 #   endif
    00688 }
    00689 #endif
    00690
    00691 template <bool __threads, int __inst>
    00692 char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;
    00693
    00694 template <bool __threads, int __inst>
    00695 char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;
    00696
    00697 template <bool __threads, int __inst>
    00698 size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;
    00699
    00700 template <bool __threads, int __inst>
    00701 __default_alloc_template<__threads, __inst>::_Obj* __VOLATILE
    00702 __default_alloc_template<__threads, __inst> ::_S_free_list[
    00703     _NFREELISTS
    00704 ] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
    00705 // The 16 zeros are necessary to make version 4.1 of the SunPro
    00706 // compiler happy.  Otherwise it appears to allocate too little
    00707 // space for the array.
    00708
    00709 # ifdef __STL_WIN32THREADS
    00710   // Create one to get critical section initialized.
    00711   // We do this onece per file, but only the first constructor
    00712   // does anything.
    00713   static alloc __node_allocator_dummy_instance;
    00714 # endif
    00715
    00716 #endif /* ! __USE_MALLOC */
    00717
    00718 // This implements allocators as specified in the C++ standard.
    00719 //
    00720 // Note that standard-conforming allocators use many language features
    00721 // that are not yet widely implemented.  In particular, they rely on
    00722 // member templates, partial specialization, partial ordering of function
    00723 // templates, the typename keyword, and the use of the template keyword
    00724 // to refer to a template member of a dependent type.
    00725
    00726 #ifdef __STL_USE_STD_ALLOCATORS
    00727
    00728 template <class _Tp>
    00729 class allocator {
    00730   typedef alloc _Alloc;          // The underlying allocator.
    00731 public:
    00732   typedef size_t     size_type;
    00733   typedef ptrdiff_t  difference_type;
    00734   typedef _Tp*       pointer;
    00735   typedef const _Tp* const_pointer;
    00736   typedef _Tp&       reference;
    00737   typedef const _Tp& const_reference;
    00738   typedef _Tp        value_type;
    00739
    00740   template <class _Tp1> struct rebind {
    00741     typedef allocator<_Tp1> other;
    00742   };
    00743
    00744   allocator() __STL_NOTHROW {}
    00745   allocator(const allocator&) __STL_NOTHROW {}
    00746   template <class _Tp1> allocator(const allocator<_Tp1>&) __STL_NOTHROW {}
    00747   ~allocator() __STL_NOTHROW {}
    00748
    00749   pointer address(reference __x) const { return &__x; }
    00750   const_pointer address(const_reference __x) const { return &__x; }
    00751
    00752   // __n is permitted to be 0.  The C++ standard says nothing about what
    00753   // the return value is when __n == 0.
    00754   _Tp* allocate(size_type __n, const void* = 0) {
    00755     return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)))
    00756                     : 0;
    00757   }
    00758
    00759   // __p is not permitted to be a null pointer.
    00760   void deallocate(pointer __p, size_type __n)
    00761     { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }
    00762
    00763   size_type max_size() const __STL_NOTHROW
    00764     { return size_t(-1) / sizeof(_Tp); }
    00765
    00766   void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
    00767   void destroy(pointer __p) { __p->~_Tp(); }
    00768 };
    00769
    00770 template<>
    00771 class allocator<void> {
    00772   typedef size_t      size_type;
    00773   typedef ptrdiff_t   difference_type;
    00774   typedef void*       pointer;
    00775   typedef const void* const_pointer;
    00776   typedef void        value_type;
    00777
    00778   template <class _Tp1> struct rebind {
    00779     typedef allocator<_Tp1> other;
    00780   };
    00781 };
    00782
    00783
    00784 template <class _T1, class _T2>
    00785 inline bool operator==(const allocator<_T1>&, const allocator<_T2>&)
    00786 {
    00787   return true;
    00788 }
    00789
    00790 template <class _T1, class _T2>
    00791 inline bool operator!=(const allocator<_T1>&, const allocator<_T2>&)
    00792 {
    00793   return false;
    00794 }
    00795
    00796 // Allocator adaptor to turn an SGI-style allocator (e.g. alloc, malloc_alloc)
    00797 // into a standard-conforming allocator.   Note that this adaptor does
    00798 // *not* assume that all objects of the underlying alloc class are
    00799 // identical, nor does it assume that all of the underlying alloc's
    00800 // member functions are static member functions.  Note, also, that
    00801 // __allocator<_Tp, alloc> is essentially the same thing as allocator<_Tp>.
    00802
    00803 template <class _Tp, class _Alloc>
    00804 struct __allocator {
    00805   _Alloc __underlying_alloc;
    00806
    00807   typedef size_t    size_type;
    00808   typedef ptrdiff_t difference_type;
    00809   typedef _Tp*       pointer;
    00810   typedef const _Tp* const_pointer;
    00811   typedef _Tp&       reference;
    00812   typedef const _Tp& const_reference;
    00813   typedef _Tp        value_type;
    00814
    00815   template <class _Tp1> struct rebind {
    00816     typedef __allocator<_Tp1, _Alloc> other;
    00817   };
    00818
    00819   __allocator() __STL_NOTHROW {}
    00820   __allocator(const __allocator& __a) __STL_NOTHROW
    00821     : __underlying_alloc(__a.__underlying_alloc) {}
    00822   template <class _Tp1>
    00823   __allocator(const __allocator<_Tp1, _Alloc>& __a) __STL_NOTHROW
    00824     : __underlying_alloc(__a.__underlying_alloc) {}
    00825   ~__allocator() __STL_NOTHROW {}
    00826
    00827   pointer address(reference __x) const { return &__x; }
    00828   const_pointer address(const_reference __x) const { return &__x; }
    00829
    00830   // __n is permitted to be 0.
    00831   _Tp* allocate(size_type __n, const void* = 0) {
    00832     return __n != 0
    00833         ? static_cast<_Tp*>(__underlying_alloc.allocate(__n * sizeof(_Tp)))
    00834         : 0;
    00835   }
    00836
    00837   // __p is not permitted to be a null pointer.
    00838   void deallocate(pointer __p, size_type __n)
    00839     { __underlying_alloc.deallocate(__p, __n * sizeof(_Tp)); }
    00840
    00841   size_type max_size() const __STL_NOTHROW
    00842     { return size_t(-1) / sizeof(_Tp); }
    00843
    00844   void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
    00845   void destroy(pointer __p) { __p->~_Tp(); }
    00846 };
    00847
    00848 template <class _Alloc>
    00849 class __allocator<void, _Alloc> {
    00850   typedef size_t      size_type;
    00851   typedef ptrdiff_t   difference_type;
    00852   typedef void*       pointer;
    00853   typedef const void* const_pointer;
    00854   typedef void        value_type;
    00855
    00856   template <class _Tp1> struct rebind {
    00857     typedef __allocator<_Tp1, _Alloc> other;
    00858   };
    00859 };
    00860
    00861 template <class _Tp, class _Alloc>
    00862 inline bool operator==(const __allocator<_Tp, _Alloc>& __a1,
    00863                        const __allocator<_Tp, _Alloc>& __a2)
    00864 {
    00865   return __a1.__underlying_alloc == __a2.__underlying_alloc;
    00866 }
    00867
    00868 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
    00869 template <class _Tp, class _Alloc>
    00870 inline bool operator!=(const __allocator<_Tp, _Alloc>& __a1,
    00871                        const __allocator<_Tp, _Alloc>& __a2)
    00872 {
    00873   return __a1.__underlying_alloc != __a2.__underlying_alloc;
    00874 }
    00875 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
    00876
    00877 // Comparison operators for all of the predifined SGI-style allocators.
    00878 // This ensures that __allocator<malloc_alloc> (for example) will
    00879 // work correctly.
    00880
    00881 template <int inst>
    00882 inline bool operator==(const __malloc_alloc_template<inst>&,
    00883                        const __malloc_alloc_template<inst>&)
    00884 {
    00885   return true;
    00886 }
    00887
    00888 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
    00889 template <int __inst>
    00890 inline bool operator!=(const __malloc_alloc_template<__inst>&,
    00891                        const __malloc_alloc_template<__inst>&)
    00892 {
    00893   return false;
    00894 }
    00895 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
    00896
    00897 #ifndef __USE_MALLOC
    00898 template <bool __threads, int __inst>
    00899 inline bool operator==(const __default_alloc_template<__threads, __inst>&,
    00900                        const __default_alloc_template<__threads, __inst>&)
    00901 {
    00902   return true;
    00903 }
    00904
    00905 # ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
    00906 template <bool __threads, int __inst>
    00907 inline bool operator!=(const __default_alloc_template<__threads, __inst>&,
    00908                        const __default_alloc_template<__threads, __inst>&)
    00909 {
    00910   return false;
    00911 }
    00912 # endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
    00913 #endif
    00914
    00915 template <class _Alloc>
    00916 inline bool operator==(const debug_alloc<_Alloc>&,
    00917                        const debug_alloc<_Alloc>&) {
    00918   return true;
    00919 }
    00920
    00921 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
    00922 template <class _Alloc>
    00923 inline bool operator!=(const debug_alloc<_Alloc>&,
    00924                        const debug_alloc<_Alloc>&) {
    00925   return false;
    00926 }
    00927 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
    00928
    00929 // Another allocator adaptor: _Alloc_traits.  This serves two
    00930 // purposes.  First, make it possible to write containers that can use
    00931 // either SGI-style allocators or standard-conforming allocator.
    00932 // Second, provide a mechanism so that containers can query whether or
    00933 // not the allocator has distinct instances.  If not, the container
    00934 // can avoid wasting a word of memory to store an empty object.
    00935
    00936 // This adaptor uses partial specialization.  The general case of
    00937 // _Alloc_traits<_Tp, _Alloc> assumes that _Alloc is a
    00938 // standard-conforming allocator, possibly with non-equal instances
    00939 // and non-static members.  (It still behaves correctly even if _Alloc
    00940 // has static member and if all instances are equal.  Refinements
    00941 // affect performance, not correctness.)
    00942
    00943 // There are always two members: allocator_type, which is a standard-
    00944 // conforming allocator type for allocating objects of type _Tp, and
    00945 // _S_instanceless, a static const member of type bool.  If
    00946 // _S_instanceless is true, this means that there is no difference
    00947 // between any two instances of type allocator_type.  Furthermore, if
    00948 // _S_instanceless is true, then _Alloc_traits has one additional
    00949 // member: _Alloc_type.  This type encapsulates allocation and
    00950 // deallocation of objects of type _Tp through a static interface; it
    00951 // has two member functions, whose signatures are
    00952 //    static _Tp* allocate(size_t)
    00953 //    static void deallocate(_Tp*, size_t)
    00954
    00955 // The fully general version.
    00956
    00957 template <class _Tp, class _Allocator>
    00958 struct _Alloc_traits
    00959 {
    00960   static const bool _S_instanceless = false;
    00961   typedef typename _Allocator::__STL_TEMPLATE rebind<_Tp>::other
    00962           allocator_type;
    00963 };
    00964
    00965 template <class _Tp, class _Allocator>
    00966 const bool _Alloc_traits<_Tp, _Allocator>::_S_instanceless;
    00967
    00968 // The version for the default allocator.
    00969
    00970 template <class _Tp, class _Tp1>
    00971 struct _Alloc_traits<_Tp, allocator<_Tp1> >
    00972 {
    00973   static const bool _S_instanceless = true;
    00974   typedef simple_alloc<_Tp, alloc> _Alloc_type;
    00975   typedef allocator<_Tp> allocator_type;
    00976 };
    00977
    00978 // Versions for the predefined SGI-style allocators.
    00979
    00980 template <class _Tp, int __inst>
    00981 struct _Alloc_traits<_Tp, __malloc_alloc_template<__inst> >
    00982 {
    00983   static const bool _S_instanceless = true;
    00984   typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
    00985   typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
    00986 };
    00987
    00988 #ifndef __USE_MALLOC
    00989 template <class _Tp, bool __threads, int __inst>
    00990 struct _Alloc_traits<_Tp, __default_alloc_template<__threads, __inst> >
    00991 {
    00992   static const bool _S_instanceless = true;
    00993   typedef simple_alloc<_Tp, __default_alloc_template<__threads, __inst> >
    00994           _Alloc_type;
    00995   typedef __allocator<_Tp, __default_alloc_template<__threads, __inst> >
    00996           allocator_type;
    00997 };
    00998 #endif
    00999
    01000 template <class _Tp, class _Alloc>
    01001 struct _Alloc_traits<_Tp, debug_alloc<_Alloc> >
    01002 {
    01003   static const bool _S_instanceless = true;
    01004   typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type;
    01005   typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type;
    01006 };
    01007
    01008 // Versions for the __allocator adaptor used with the predefined
    01009 // SGI-style allocators.
    01010
    01011 template <class _Tp, class _Tp1, int __inst>
    01012 struct _Alloc_traits<_Tp,
    01013                      __allocator<_Tp1, __malloc_alloc_template<__inst> > >
    01014 {
    01015   static const bool _S_instanceless = true;
    01016   typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
    01017   typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
    01018 };
    01019
    01020 #ifndef __USE_MALLOC
    01021 template <class _Tp, class _Tp1, bool __thr, int __inst>
    01022 struct _Alloc_traits<_Tp,
    01023                       __allocator<_Tp1,
    01024                                   __default_alloc_template<__thr, __inst> > >
    01025 {
    01026   static const bool _S_instanceless = true;
    01027   typedef simple_alloc<_Tp, __default_alloc_template<__thr,__inst> >
    01028           _Alloc_type;
    01029   typedef __allocator<_Tp, __default_alloc_template<__thr,__inst> >
    01030           allocator_type;
    01031 };
    01032 #endif
    01033
    01034 template <class _Tp, class _Tp1, class _Alloc>
    01035 struct _Alloc_traits<_Tp, __allocator<_Tp1, debug_alloc<_Alloc> > >
    01036 {
    01037   static const bool _S_instanceless = true;
    01038   typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type;
    01039   typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type;
    01040 };
    01041
    01042
    01043 #endif /* __STL_USE_STD_ALLOCATORS */
    01044
    01045 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    01046 #pragma reset woff 1174
    01047 #endif
    01048
    01049 __STL_END_NAMESPACE
    01050
    01051 #undef __PRIVATE
    01052
    01053 #endif /* __SGI_STL_INTERNAL_ALLOC_H */
    01054
    01055 // Local Variables:
    01056 // mode:C++
    01057 // End: