OSDN Git Service

4279ba0321a8a19bcd87987db1fcac6c007ccfd2
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_alloc.h
1 // Allocators -*- C++ -*-
2
3 // Copyright (C) 2001 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING.  If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
19 // USA.
20
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction.  Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License.  This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
29
30 /*
31  * Copyright (c) 1996-1997
32  * Silicon Graphics Computer Systems, Inc.
33  *
34  * Permission to use, copy, modify, distribute and sell this software
35  * and its documentation for any purpose is hereby granted without fee,
36  * provided that the above copyright notice appear in all copies and
37  * that both that copyright notice and this permission notice appear
38  * in supporting documentation.  Silicon Graphics makes no
39  * representations about the suitability of this software for any
40  * purpose.  It is provided "as is" without express or implied warranty.
41  */
42
43 /** @file stl_alloc.h
44  *  This is an internal header file, included by other library headers.
45  *  You should not attempt to use it directly.
46  */
47
48 #ifndef __SGI_STL_INTERNAL_ALLOC_H
49 #define __SGI_STL_INTERNAL_ALLOC_H
50
51 // This implements some standard node allocators.  These are
52 // NOT the same as the allocators in the C++ draft standard or in
53 // in the original STL.  They do not encapsulate different pointer
54 // types; indeed we assume that there is only one pointer type.
55 // The allocation primitives are intended to allocate individual objects,
56 // not larger arenas as with the original STL allocators.
57
58 #include <bits/functexcept.h>   // for __throw_bad_alloc
59 #include <bits/std_cstddef.h>
60 #include <bits/std_cstdlib.h>
61 #include <bits/std_cstring.h>
62 #include <bits/std_cassert.h>
63 #ifndef __RESTRICT
64 #  define __RESTRICT
65 #endif
66
67 #ifdef __STL_THREADS
68 # include <bits/stl_threads.h>
69 # define __NODE_ALLOCATOR_THREADS true
70 # ifdef __STL_SGI_THREADS
71   // We test whether threads are in use before locking.
72   // Perhaps this should be moved into stl_threads.h, but that
73   // probably makes it harder to avoid the procedure call when
74   // it isn't needed.
75     extern "C" {
76       extern int __us_rsthread_malloc;
77     }
78         // The above is copied from malloc.h.  Including <malloc.h>
79         // would be cleaner but fails with certain levels of standard
80         // conformance.
81 #   define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \
82                 { _S_node_allocator_lock._M_acquire_lock(); }
83 #   define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \
84                 { _S_node_allocator_lock._M_release_lock(); }
85 # else /* !__STL_SGI_THREADS */
86 #   define __NODE_ALLOCATOR_LOCK \
87         { if (threads) _S_node_allocator_lock._M_acquire_lock(); }
88 #   define __NODE_ALLOCATOR_UNLOCK \
89         { if (threads) _S_node_allocator_lock._M_release_lock(); }
90 # endif
91 #else
92 //  Thread-unsafe
93 #   define __NODE_ALLOCATOR_LOCK
94 #   define __NODE_ALLOCATOR_UNLOCK
95 #   define __NODE_ALLOCATOR_THREADS false
96 #endif
97
98 namespace std
99 {
100   // A new-based allocator, as required by the standard.
101   class __new_alloc 
102   {
103   public:
104     static void* 
105     allocate(size_t __n)
106     { return ::operator new(__n); }
107     
108     static void 
109     deallocate(void* __p, size_t)
110     { ::operator delete(__p); }
111   };
112   
113   // Malloc-based allocator.  Typically slower than default alloc below.
114   // Typically thread-safe and more storage efficient.
115   template <int __inst>
116     class __malloc_alloc_template 
117     {
118     private:
119       static void* _S_oom_malloc(size_t);
120       static void* _S_oom_realloc(void*, size_t);
121       static void (* __malloc_alloc_oom_handler)();
122       
123     public:
124       static void* 
125       allocate(size_t __n)
126       {
127         void* __result = malloc(__n);
128         if (0 == __result) __result = _S_oom_malloc(__n);
129         return __result;
130       }
131
132       static void 
133       deallocate(void* __p, size_t /* __n */)
134       { free(__p); }
135
136       static void* 
137       reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
138       {
139         void* __result = realloc(__p, __new_sz);
140         if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
141         return __result;
142       }
143       
144       static void (* __set_malloc_handler(void (*__f)()))()
145       {
146         void (* __old)() = __malloc_alloc_oom_handler;
147         __malloc_alloc_oom_handler = __f;
148         return(__old);
149       }
150     };
151
152   // malloc_alloc out-of-memory handling
153   template <int __inst>
154     void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
155
156   template <int __inst>
157     void*
158     __malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
159     {
160       void (* __my_malloc_handler)();
161       void* __result;
162       
163       for (;;) 
164         {
165           __my_malloc_handler = __malloc_alloc_oom_handler;
166           if (0 == __my_malloc_handler) 
167             std::__throw_bad_alloc();
168           (*__my_malloc_handler)();
169           __result = malloc(__n);
170           if (__result) 
171             return(__result);
172         }
173     }
174   
175   template <int __inst>
176     void* 
177     __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
178     { 
179       void (* __my_malloc_handler)();
180       void* __result;
181       
182       for (;;) 
183         {
184           __my_malloc_handler = __malloc_alloc_oom_handler;
185           if (0 == __my_malloc_handler) 
186             std::__throw_bad_alloc();
187           (*__my_malloc_handler)();
188           __result = realloc(__p, __n);
189           if (__result) 
190             return(__result);
191         }
192     }
193
194   // Determines the underlying allocator choice.
195 # ifdef __USE_MALLOC
196   typedef __malloc_alloc_template<0> __mem_interface;
197 #else
198   typedef __new_alloc __mem_interface;
199 #endif
200
201 template<class _Tp, class _Alloc>
202 class simple_alloc {
203
204 public:
205     static _Tp* allocate(size_t __n)
206       { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
207     static _Tp* allocate(void)
208       { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
209     static void deallocate(_Tp* __p, size_t __n)
210       { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
211     static void deallocate(_Tp* __p)
212       { _Alloc::deallocate(__p, sizeof (_Tp)); }
213 };
214
215 // Allocator adaptor to check size arguments for debugging.
216 // Reports errors using assert.  Checking can be disabled with
217 // NDEBUG, but it's far better to just use the underlying allocator
218 // instead when no checking is desired.
219 // There is some evidence that this can confuse Purify.
220 template <class _Alloc>
221 class debug_alloc {
222
223 private:
224
225   enum {_S_extra = 8};  // Size of space used to store size.  Note
226                         // that this must be large enough to preserve
227                         // alignment.
228
229 public:
230
231   static void* allocate(size_t __n)
232   {
233     char* __result = (char*)_Alloc::allocate(__n + (int) _S_extra);
234     *(size_t*)__result = __n;
235     return __result + (int) _S_extra;
236   }
237
238   static void deallocate(void* __p, size_t __n)
239   {
240     char* __real_p = (char*)__p - (int) _S_extra;
241     assert(*(size_t*)__real_p == __n);
242     _Alloc::deallocate(__real_p, __n + (int) _S_extra);
243   }
244
245   static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz)
246   {
247     char* __real_p = (char*)__p - (int) _S_extra;
248     assert(*(size_t*)__real_p == __old_sz);
249     char* __result = (char*)
250       _Alloc::reallocate(__real_p, __old_sz + (int) _S_extra,
251                                    __new_sz + (int) _S_extra);
252     *(size_t*)__result = __new_sz;
253     return __result + (int) _S_extra;
254   }
255
256 };
257
258
259 # ifdef __USE_MALLOC
260
261 typedef malloc_alloc alloc;
262 typedef malloc_alloc single_client_alloc;
263
264 # else
265
266
267 // Default node allocator.
268 // With a reasonable compiler, this should be roughly as fast as the
269 // original STL class-specific allocators, but with less fragmentation.
270 // Default_alloc_template parameters are experimental and MAY
271 // DISAPPEAR in the future.  Clients should just use alloc for now.
272 //
273 // Important implementation properties:
274 // 1. If the client request an object of size > _MAX_BYTES, the resulting
275 //    object will be obtained directly from malloc.
276 // 2. In all other cases, we allocate an object of size exactly
277 //    _S_round_up(requested_size).  Thus the client has enough size
278 //    information that we can return the object to the proper free list
279 //    without permanently losing part of the object.
280 //
281
282 // The first template parameter specifies whether more than one thread
283 // may use this allocator.  It is safe to allocate an object from
284 // one instance of a default_alloc and deallocate it with another
285 // one.  This effectively transfers its ownership to the second one.
286 // This may have undesirable effects on reference locality.
287 // The second parameter is unreferenced and serves only to allow the
288 // creation of multiple default_alloc instances.
289 // Node that containers built on different allocator instances have
290 // different types, limiting the utility of this approach.
291
292 template <bool threads, int inst>
293 class __default_alloc_template {
294
295 private:
296   // Really we should use static const int x = N
297   // instead of enum { x = N }, but few compilers accept the former.
298   enum {_ALIGN = 8};
299   enum {_MAX_BYTES = 128};
300   enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN
301   static size_t
302   _S_round_up(size_t __bytes) 
303     { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
304
305   union _Obj {
306         union _Obj* _M_free_list_link;
307         char _M_client_data[1];    /* The client sees this.        */
308   };
309
310   static _Obj* volatile _S_free_list[]; 
311         // Specifying a size results in duplicate def for 4.1
312   static  size_t _S_freelist_index(size_t __bytes) {
313         return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
314   }
315
316   // Returns an object of size __n, and optionally adds to size __n free list.
317   static void* _S_refill(size_t __n);
318   // Allocates a chunk for nobjs of size size.  nobjs may be reduced
319   // if it is inconvenient to allocate the requested number.
320   static char* _S_chunk_alloc(size_t __size, int& __nobjs);
321
322   // Chunk allocation state.
323   static char* _S_start_free;
324   static char* _S_end_free;
325   static size_t _S_heap_size;
326
327 # ifdef __STL_THREADS
328     static _STL_mutex_lock _S_node_allocator_lock;
329 # endif
330
331     // It would be nice to use _STL_auto_lock here.  But we
332     // don't need the NULL check.  And we do need a test whether
333     // threads have actually been started.
334     class _Lock;
335     friend class _Lock;
336     class _Lock {
337         public:
338             _Lock() { __NODE_ALLOCATOR_LOCK; }
339             ~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
340     };
341
342 public:
343
344   /* __n must be > 0      */
345   static void* allocate(size_t __n)
346   {
347     void* __ret = 0;
348
349     if (__n > (size_t) _MAX_BYTES) 
350       __ret = __mem_interface::allocate(__n);
351     else 
352       {
353         _Obj* volatile* __my_free_list = _S_free_list + _S_freelist_index(__n);
354         // Acquire the lock here with a constructor call.
355         // This ensures that it is released in exit or during stack
356         // unwinding.
357 #     ifndef _NOTHREADS
358         /*REFERENCED*/
359         _Lock __lock_instance;
360 #     endif
361         _Obj* __RESTRICT __result = *__my_free_list;
362         if (__result == 0)
363           __ret = _S_refill(_S_round_up(__n));
364         else 
365           {
366             *__my_free_list = __result -> _M_free_list_link;
367             __ret = __result;
368           }
369       }
370     
371     return __ret;
372   };
373
374   /* __p may not be 0 */
375   static void deallocate(void* __p, size_t __n)
376   {
377     if (__n > (size_t) _MAX_BYTES)
378       __mem_interface::deallocate(__p, __n);
379     else 
380       {
381         _Obj* volatile*  __my_free_list
382           = _S_free_list + _S_freelist_index(__n);
383         _Obj* __q = (_Obj*)__p;
384         
385         // acquire lock
386 #       ifndef _NOTHREADS
387         /*REFERENCED*/
388         _Lock __lock_instance;
389 #       endif /* _NOTHREADS */
390         __q -> _M_free_list_link = *__my_free_list;
391         *__my_free_list = __q;
392         // lock is released here
393       }
394   }
395   
396   static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);
397 };
398
399 typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
400 typedef __default_alloc_template<false, 0> single_client_alloc;
401
402 template <bool __threads, int __inst>
403 inline bool operator==(const __default_alloc_template<__threads, __inst>&,
404                        const __default_alloc_template<__threads, __inst>&)
405 {
406   return true;
407 }
408
409 template <bool __threads, int __inst>
410 inline bool operator!=(const __default_alloc_template<__threads, __inst>&,
411                        const __default_alloc_template<__threads, __inst>&)
412 {
413   return false;
414 }
415
416
417
418 /* We allocate memory in large chunks in order to avoid fragmenting     */
419 /* the malloc heap too much.                                            */
420 /* We assume that size is properly aligned.                             */
421 /* We hold the allocation lock.                                         */
422 template <bool __threads, int __inst>
423 char*
424 __default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, 
425                                                             int& __nobjs)
426 {
427     char* __result;
428     size_t __total_bytes = __size * __nobjs;
429     size_t __bytes_left = _S_end_free - _S_start_free;
430
431     if (__bytes_left >= __total_bytes) 
432       {
433         __result = _S_start_free;
434         _S_start_free += __total_bytes;
435         return(__result);
436       } 
437     else if (__bytes_left >= __size) 
438       {
439         __nobjs = (int)(__bytes_left/__size);
440         __total_bytes = __size * __nobjs;
441         __result = _S_start_free;
442         _S_start_free += __total_bytes;
443         return(__result);
444     } 
445     else 
446       {
447         size_t __bytes_to_get = 
448           2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
449         // Try to make use of the left-over piece.
450         if (__bytes_left > 0) 
451           {
452             _Obj* volatile* __my_free_list =
453               _S_free_list + _S_freelist_index(__bytes_left);
454             
455             ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
456             *__my_free_list = (_Obj*)_S_start_free;
457           }
458         _S_start_free = (char*) __mem_interface::allocate(__bytes_to_get);
459         if (0 == _S_start_free) 
460           {
461             size_t __i;
462             _Obj* volatile* __my_free_list;
463             _Obj* __p;
464             // Try to make do with what we have.  That can't hurt.  We
465             // do not try smaller requests, since that tends to result
466             // in disaster on multi-process machines.
467             __i = __size;
468             for (; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN) 
469               {
470                 __my_free_list = _S_free_list + _S_freelist_index(__i);
471                 __p = *__my_free_list;
472                 if (0 != __p) 
473                   {
474                     *__my_free_list = __p -> _M_free_list_link;
475                     _S_start_free = (char*)__p;
476                     _S_end_free = _S_start_free + __i;
477                     return(_S_chunk_alloc(__size, __nobjs));
478                     // Any leftover piece will eventually make it to the
479                     // right free list.
480                   }
481               }
482             _S_end_free = 0;    // In case of exception.
483             _S_start_free = (char*)__mem_interface::allocate(__bytes_to_get);
484             // This should either throw an
485             // exception or remedy the situation.  Thus we assume it
486             // succeeded.
487           }
488         _S_heap_size += __bytes_to_get;
489         _S_end_free = _S_start_free + __bytes_to_get;
490         return(_S_chunk_alloc(__size, __nobjs));
491       }
492 }
493
494
495 /* Returns an object of size __n, and optionally adds to size __n free list.*/
496 /* We assume that __n is properly aligned.                                */
497 /* We hold the allocation lock.                                         */
498 template <bool __threads, int __inst>
499 void*
500 __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
501 {
502     int __nobjs = 20;
503     char* __chunk = _S_chunk_alloc(__n, __nobjs);
504     _Obj* volatile* __my_free_list;
505     _Obj* __result;
506     _Obj* __current_obj;
507     _Obj* __next_obj;
508     int __i;
509
510     if (1 == __nobjs) return(__chunk);
511     __my_free_list = _S_free_list + _S_freelist_index(__n);
512
513     /* Build free list in chunk */
514       __result = (_Obj*)__chunk;
515       *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
516       for (__i = 1; ; __i++) {
517         __current_obj = __next_obj;
518         __next_obj = (_Obj*)((char*)__next_obj + __n);
519         if (__nobjs - 1 == __i) {
520             __current_obj -> _M_free_list_link = 0;
521             break;
522         } else {
523             __current_obj -> _M_free_list_link = __next_obj;
524         }
525       }
526     return(__result);
527 }
528
529 template <bool threads, int inst>
530 void*
531 __default_alloc_template<threads, inst>::reallocate(void* __p,
532                                                     size_t __old_sz,
533                                                     size_t __new_sz)
534 {
535     void* __result;
536     size_t __copy_sz;
537
538     if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
539         return(realloc(__p, __new_sz));
540     }
541     if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
542     __result = allocate(__new_sz);
543     __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
544     memcpy(__result, __p, __copy_sz);
545     deallocate(__p, __old_sz);
546     return(__result);
547 }
548
549 #ifdef __STL_THREADS
550     template <bool __threads, int __inst>
551     _STL_mutex_lock
552     __default_alloc_template<__threads, __inst>::_S_node_allocator_lock
553         __STL_MUTEX_INITIALIZER;
554 #endif
555
556
557 template <bool __threads, int __inst>
558 char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;
559
560 template <bool __threads, int __inst>
561 char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;
562
563 template <bool __threads, int __inst>
564 size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;
565
566 template <bool __threads, int __inst>
567 typename __default_alloc_template<__threads, __inst>::_Obj* volatile
568 __default_alloc_template<__threads, __inst> ::_S_free_list[
569     __default_alloc_template<__threads, __inst>::_NFREELISTS
570 ] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
571 // The 16 zeros are necessary to make version 4.1 of the SunPro
572 // compiler happy.  Otherwise it appears to allocate too little
573 // space for the array.
574
575 #endif /* ! __USE_MALLOC */
576
577 // This implements allocators as specified in the C++ standard.  
578 //
579 // Note that standard-conforming allocators use many language features
580 // that are not yet widely implemented.  In particular, they rely on
581 // member templates, partial specialization, partial ordering of function
582 // templates, the typename keyword, and the use of the template keyword
583 // to refer to a template member of a dependent type.
584
585 template <class _Tp>
586 class allocator {
587   typedef alloc _Alloc;          // The underlying allocator.
588 public:
589   typedef size_t     size_type;
590   typedef ptrdiff_t  difference_type;
591   typedef _Tp*       pointer;
592   typedef const _Tp* const_pointer;
593   typedef _Tp&       reference;
594   typedef const _Tp& const_reference;
595   typedef _Tp        value_type;
596
597   template <class _Tp1> struct rebind {
598     typedef allocator<_Tp1> other;
599   };
600
601   allocator() throw() {}
602   allocator(const allocator&) throw() {}
603   template <class _Tp1> allocator(const allocator<_Tp1>&) throw() {}
604   ~allocator() throw() {}
605
606   pointer address(reference __x) const { return &__x; }
607   const_pointer address(const_reference __x) const { return &__x; }
608
609   // __n is permitted to be 0.  The C++ standard says nothing about what
610   // the return value is when __n == 0.
611   _Tp* allocate(size_type __n, const void* = 0) {
612     return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) 
613                     : 0;
614   }
615
616   // __p is not permitted to be a null pointer.
617   void deallocate(pointer __p, size_type __n)
618     { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }
619
620   size_type max_size() const throw() 
621     { return size_t(-1) / sizeof(_Tp); }
622
623   void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
624   void destroy(pointer __p) { __p->~_Tp(); }
625 };
626
627 template<>
628 class allocator<void> {
629 public:
630   typedef size_t      size_type;
631   typedef ptrdiff_t   difference_type;
632   typedef void*       pointer;
633   typedef const void* const_pointer;
634   typedef void        value_type;
635
636   template <class _Tp1> struct rebind {
637     typedef allocator<_Tp1> other;
638   };
639 };
640
641
642 template <class _T1, class _T2>
643 inline bool operator==(const allocator<_T1>&, const allocator<_T2>&) 
644 {
645   return true;
646 }
647
648 template <class _T1, class _T2>
649 inline bool operator!=(const allocator<_T1>&, const allocator<_T2>&)
650 {
651   return false;
652 }
653
654 // Allocator adaptor to turn an SGI-style allocator (e.g. alloc, malloc_alloc)
655 // into a standard-conforming allocator.   Note that this adaptor does
656 // *not* assume that all objects of the underlying alloc class are
657 // identical, nor does it assume that all of the underlying alloc's
658 // member functions are static member functions.  Note, also, that 
659 // __allocator<_Tp, alloc> is essentially the same thing as allocator<_Tp>.
660
661 template <class _Tp, class _Alloc>
662 struct __allocator {
663   _Alloc __underlying_alloc;
664
665   typedef size_t    size_type;
666   typedef ptrdiff_t difference_type;
667   typedef _Tp*       pointer;
668   typedef const _Tp* const_pointer;
669   typedef _Tp&       reference;
670   typedef const _Tp& const_reference;
671   typedef _Tp        value_type;
672
673   template <class _Tp1> struct rebind {
674     typedef __allocator<_Tp1, _Alloc> other;
675   };
676
677   __allocator() throw() {}
678   __allocator(const __allocator& __a) throw()
679     : __underlying_alloc(__a.__underlying_alloc) {}
680   template <class _Tp1> 
681   __allocator(const __allocator<_Tp1, _Alloc>& __a) throw()
682     : __underlying_alloc(__a.__underlying_alloc) {}
683   ~__allocator() throw() {}
684
685   pointer address(reference __x) const { return &__x; }
686   const_pointer address(const_reference __x) const { return &__x; }
687
688   // __n is permitted to be 0.
689   _Tp* allocate(size_type __n, const void* = 0) {
690     return __n != 0 
691         ? static_cast<_Tp*>(__underlying_alloc.allocate(__n * sizeof(_Tp))) 
692         : 0;
693   }
694
695   // __p is not permitted to be a null pointer.
696   void deallocate(pointer __p, size_type __n)
697     { __underlying_alloc.deallocate(__p, __n * sizeof(_Tp)); }
698
699   size_type max_size() const throw() 
700     { return size_t(-1) / sizeof(_Tp); }
701
702   void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
703   void destroy(pointer __p) { __p->~_Tp(); }
704 };
705
706 template <class _Alloc>
707 class __allocator<void, _Alloc> {
708   typedef size_t      size_type;
709   typedef ptrdiff_t   difference_type;
710   typedef void*       pointer;
711   typedef const void* const_pointer;
712   typedef void        value_type;
713
714   template <class _Tp1> struct rebind {
715     typedef __allocator<_Tp1, _Alloc> other;
716   };
717 };
718
719 template <class _Tp, class _Alloc>
720 inline bool operator==(const __allocator<_Tp, _Alloc>& __a1,
721                        const __allocator<_Tp, _Alloc>& __a2)
722 {
723   return __a1.__underlying_alloc == __a2.__underlying_alloc;
724 }
725
726 template <class _Tp, class _Alloc>
727 inline bool operator!=(const __allocator<_Tp, _Alloc>& __a1,
728                        const __allocator<_Tp, _Alloc>& __a2)
729 {
730   return __a1.__underlying_alloc != __a2.__underlying_alloc;
731 }
732
733 // Comparison operators for all of the predifined SGI-style allocators.
734 // This ensures that __allocator<malloc_alloc> (for example) will
735 // work correctly.
736
737 template <int inst>
738 inline bool operator==(const __malloc_alloc_template<inst>&,
739                        const __malloc_alloc_template<inst>&)
740 {
741   return true;
742 }
743
744 template <int __inst>
745 inline bool operator!=(const __malloc_alloc_template<__inst>&,
746                        const __malloc_alloc_template<__inst>&)
747 {
748   return false;
749 }
750
751 template <class _Alloc>
752 inline bool operator==(const debug_alloc<_Alloc>&,
753                        const debug_alloc<_Alloc>&) {
754   return true;
755 }
756
757 template <class _Alloc>
758 inline bool operator!=(const debug_alloc<_Alloc>&,
759                        const debug_alloc<_Alloc>&) {
760   return false;
761 }
762
763 // Another allocator adaptor: _Alloc_traits.  This serves two
764 // purposes.  First, make it possible to write containers that can use
765 // either SGI-style allocators or standard-conforming allocator.
766 // Second, provide a mechanism so that containers can query whether or
767 // not the allocator has distinct instances.  If not, the container
768 // can avoid wasting a word of memory to store an empty object.
769
770 // This adaptor uses partial specialization.  The general case of
771 // _Alloc_traits<_Tp, _Alloc> assumes that _Alloc is a
772 // standard-conforming allocator, possibly with non-equal instances
773 // and non-static members.  (It still behaves correctly even if _Alloc
774 // has static member and if all instances are equal.  Refinements
775 // affect performance, not correctness.)
776
777 // There are always two members: allocator_type, which is a standard-
778 // conforming allocator type for allocating objects of type _Tp, and
779 // _S_instanceless, a static const member of type bool.  If
780 // _S_instanceless is true, this means that there is no difference
781 // between any two instances of type allocator_type.  Furthermore, if
782 // _S_instanceless is true, then _Alloc_traits has one additional
783 // member: _Alloc_type.  This type encapsulates allocation and
784 // deallocation of objects of type _Tp through a static interface; it
785 // has two member functions, whose signatures are
786 //    static _Tp* allocate(size_t)
787 //    static void deallocate(_Tp*, size_t)
788
789 // The fully general version.
790
791 template <class _Tp, class _Allocator>
792 struct _Alloc_traits
793 {
794   static const bool _S_instanceless = false;
795   typedef typename _Allocator::template rebind<_Tp>::other allocator_type;
796 };
797
798 template <class _Tp, class _Allocator>
799 const bool _Alloc_traits<_Tp, _Allocator>::_S_instanceless;
800
801 // The version for the default allocator.
802
803 template <class _Tp, class _Tp1>
804 struct _Alloc_traits<_Tp, allocator<_Tp1> >
805 {
806   static const bool _S_instanceless = true;
807   typedef simple_alloc<_Tp, alloc> _Alloc_type;
808   typedef allocator<_Tp> allocator_type;
809 };
810
811 // Versions for the predefined SGI-style allocators.
812
813 template <class _Tp, int __inst>
814 struct _Alloc_traits<_Tp, __malloc_alloc_template<__inst> >
815 {
816   static const bool _S_instanceless = true;
817   typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
818   typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
819 };
820
821 #ifndef __USE_MALLOC
822 template <class _Tp, bool __threads, int __inst>
823 struct _Alloc_traits<_Tp, __default_alloc_template<__threads, __inst> >
824 {
825   static const bool _S_instanceless = true;
826   typedef simple_alloc<_Tp, __default_alloc_template<__threads, __inst> > 
827           _Alloc_type;
828   typedef __allocator<_Tp, __default_alloc_template<__threads, __inst> > 
829           allocator_type;
830 };
831 #endif
832
833 template <class _Tp, class _Alloc>
834 struct _Alloc_traits<_Tp, debug_alloc<_Alloc> >
835 {
836   static const bool _S_instanceless = true;
837   typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type;
838   typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type;
839 };
840
841 // Versions for the __allocator adaptor used with the predefined
842 // SGI-style allocators.
843
844 template <class _Tp, class _Tp1, int __inst>
845 struct _Alloc_traits<_Tp, 
846                      __allocator<_Tp1, __malloc_alloc_template<__inst> > >
847 {
848   static const bool _S_instanceless = true;
849   typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
850   typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
851 };
852
853 #ifndef __USE_MALLOC
854 template <class _Tp, class _Tp1, bool __thr, int __inst>
855 struct _Alloc_traits<_Tp, 
856                       __allocator<_Tp1, 
857                                   __default_alloc_template<__thr, __inst> > >
858 {
859   static const bool _S_instanceless = true;
860   typedef simple_alloc<_Tp, __default_alloc_template<__thr,__inst> > 
861           _Alloc_type;
862   typedef __allocator<_Tp, __default_alloc_template<__thr,__inst> > 
863           allocator_type;
864 };
865 #endif
866
867 template <class _Tp, class _Tp1, class _Alloc>
868 struct _Alloc_traits<_Tp, __allocator<_Tp1, debug_alloc<_Alloc> > >
869 {
870   static const bool _S_instanceless = true;
871   typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type;
872   typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type;
873 };
874
875 } // namespace std
876
877 #endif /* __SGI_STL_INTERNAL_ALLOC_H */
878
879 // Local Variables:
880 // mode:C++
881 // End: