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