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