aboutsummaryrefslogtreecommitdiff
path: root/libstdc++/stl/alloc.h
diff options
context:
space:
mode:
Diffstat (limited to 'libstdc++/stl/alloc.h')
-rw-r--r--libstdc++/stl/alloc.h674
1 files changed, 674 insertions, 0 deletions
diff --git a/libstdc++/stl/alloc.h b/libstdc++/stl/alloc.h
new file mode 100644
index 00000000000..917ce8fdb80
--- /dev/null
+++ b/libstdc++/stl/alloc.h
@@ -0,0 +1,674 @@
+/*
+ * Copyright (c) 1996-1997
+ * Silicon Graphics Computer Systems, Inc.
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Silicon Graphics makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ */
+
+#ifndef __ALLOC_H
+#define __ALLOC_H
+
+#include <stl_config.h>
+
+#ifdef __SUNPRO_CC
+# define __PRIVATE public
+ // Extra access restrictions prevent us from really making some things
+ // private.
+#else
+# define __PRIVATE private
+#endif
+
+#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
+# define __USE_MALLOC
+#endif
+
+
+// This implements some standard node allocators. These are
+// NOT the same as the allocators in the C++ draft standard or in
+// in the original STL. They do not encapsulate different pointer
+// types; indeed we assume that there is only one pointer type.
+// The allocation primitives are intended to allocate individual objects,
+// not larger arenas as with the original STL allocators.
+
+#if 0
+# include <new>
+# define __THROW_BAD_ALLOC throw bad_alloc
+#elif !defined(__THROW_BAD_ALLOC)
+# include <iostream.h>
+# define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
+#endif
+
+#ifndef __ALLOC
+# define __ALLOC alloc
+#endif
+#ifdef __STL_WIN32THREADS
+# include <windows.h>
+// This must precede stl_config.h
+#endif
+
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#ifndef __RESTRICT
+# define __RESTRICT
+#endif
+
+#if !defined(_PTHREADS) && !defined(_NOTHREADS) \
+ && !defined(__STL_SGI_THREADS) && !defined(__STL_WIN32THREADS)
+# define _NOTHREADS
+#endif
+
+# ifdef _PTHREADS
+ // POSIX Threads
+ // This is dubious, since this is likely to be a high contention
+ // lock. Performance may not be adequate.
+# include <pthread.h>
+# define __NODE_ALLOCATOR_LOCK \
+ if (threads) pthread_mutex_lock(&__node_allocator_lock)
+# define __NODE_ALLOCATOR_UNLOCK \
+ if (threads) pthread_mutex_unlock(&__node_allocator_lock)
+# define __NODE_ALLOCATOR_THREADS true
+# define __VOLATILE volatile // Needed at -O3 on SGI
+# endif
+# ifdef __STL_WIN32THREADS
+ // The lock needs to be initialized by constructing an allocator
+ // objects of the right type. We do that here explicitly for alloc.
+# define __NODE_ALLOCATOR_LOCK \
+ EnterCriticalSection(&__node_allocator_lock)
+# define __NODE_ALLOCATOR_UNLOCK \
+ LeaveCriticalSection(&__node_allocator_lock)
+# define __NODE_ALLOCATOR_THREADS true
+# define __VOLATILE volatile // may not be needed
+# endif /* WIN32THREADS */
+# ifdef __STL_SGI_THREADS
+ // This should work without threads, with sproc threads, or with
+ // pthreads. It is suboptimal in all cases.
+ // It is unlikely to even compile on nonSGI machines.
+# include <malloc.h>
+# define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \
+ { __lock(&__node_allocator_lock); }
+# define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \
+ { __unlock(&__node_allocator_lock); }
+# define __NODE_ALLOCATOR_THREADS true
+# define __VOLATILE volatile // Needed at -O3 on SGI
+# endif
+# ifdef _NOTHREADS
+// Thread-unsafe
+# define __NODE_ALLOCATOR_LOCK
+# define __NODE_ALLOCATOR_UNLOCK
+# define __NODE_ALLOCATOR_THREADS false
+# define __VOLATILE
+# endif
+
+#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
+#pragma set woff 1174
+#endif
+
+// Malloc-based allocator. Typically slower than default alloc below.
+// Typically thread-safe and more storage efficient.
+#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
+# ifdef __DECLARE_GLOBALS_HERE
+ void (* __malloc_alloc_oom_handler)() = 0;
+ // g++ 2.7.2 does not handle static template data members.
+# else
+ extern void (* __malloc_alloc_oom_handler)();
+# endif
+#endif
+
+template <int inst>
+class __malloc_alloc_template {
+
+private:
+
+static void *oom_malloc(size_t);
+
+static void *oom_realloc(void *, size_t);
+
+#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
+ static void (* __malloc_alloc_oom_handler)();
+#endif
+
+public:
+
+static void * allocate(size_t n)
+{
+ void *result = malloc(n);
+ if (0 == result) result = oom_malloc(n);
+ return result;
+}
+
+static void deallocate(void *p, size_t /* n */)
+{
+ free(p);
+}
+
+static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
+{
+ void * result = realloc(p, new_sz);
+ if (0 == result) result = oom_realloc(p, new_sz);
+ return result;
+}
+
+static void (* set_malloc_handler(void (*f)()))()
+{
+ void (* old)() = __malloc_alloc_oom_handler;
+ __malloc_alloc_oom_handler = f;
+ return(old);
+}
+
+};
+
+// malloc_alloc out-of-memory handling
+
+#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
+template <int inst>
+void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
+#endif
+
+template <int inst>
+void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
+{
+ void (* my_malloc_handler)();
+ void *result;
+
+ for (;;) {
+ my_malloc_handler = __malloc_alloc_oom_handler;
+ if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
+ (*my_malloc_handler)();
+ result = malloc(n);
+ if (result) return(result);
+ }
+}
+
+template <int inst>
+void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)
+{
+ void (* my_malloc_handler)();
+ void *result;
+
+ for (;;) {
+ my_malloc_handler = __malloc_alloc_oom_handler;
+ if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
+ (*my_malloc_handler)();
+ result = realloc(p, n);
+ if (result) return(result);
+ }
+}
+
+typedef __malloc_alloc_template<0> malloc_alloc;
+
+template<class T, class Alloc>
+class simple_alloc {
+
+public:
+ static T *allocate(size_t n)
+ { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
+ static T *allocate(void)
+ { return (T*) Alloc::allocate(sizeof (T)); }
+ static void deallocate(T *p, size_t n)
+ { if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
+ static void deallocate(T *p)
+ { Alloc::deallocate(p, sizeof (T)); }
+};
+
+// Allocator adaptor to check size arguments for debugging.
+// Reports errors using assert. Checking can be disabled with
+// NDEBUG, but it's far better to just use the underlying allocator
+// instead when no checking is desired.
+// There is some evidence that this can confuse Purify.
+template <class Alloc>
+class debug_alloc {
+
+private:
+
+enum {extra = 8}; // Size of space used to store size. Note
+ // that this must be large enough to preserve
+ // alignment.
+
+public:
+
+static void * allocate(size_t n)
+{
+ char *result = (char *)Alloc::allocate(n + extra);
+ *(size_t *)result = n;
+ return result + extra;
+}
+
+static void deallocate(void *p, size_t n)
+{
+ char * real_p = (char *)p - extra;
+ assert(*(size_t *)real_p == n);
+ Alloc::deallocate(real_p, n + extra);
+}
+
+static void * reallocate(void *p, size_t old_sz, size_t new_sz)
+{
+ char * real_p = (char *)p - extra;
+ assert(*(size_t *)real_p == old_sz);
+ char * result = (char *)
+ Alloc::reallocate(real_p, old_sz + extra, new_sz + extra);
+ *(size_t *)result = new_sz;
+ return result + extra;
+}
+
+
+};
+
+
+# ifdef __USE_MALLOC
+
+typedef malloc_alloc alloc;
+typedef malloc_alloc single_client_alloc;
+
+# else
+
+
+// Default node allocator.
+// With a reasonable compiler, this should be roughly as fast as the
+// original STL class-specific allocators, but with less fragmentation.
+// Default_alloc_template parameters are experimental and MAY
+// DISAPPEAR in the future. Clients should just use alloc for now.
+//
+// Important implementation properties:
+// 1. If the client request an object of size > __MAX_BYTES, the resulting
+// object will be obtained directly from malloc.
+// 2. In all other cases, we allocate an object of size exactly
+// ROUND_UP(requested_size). Thus the client has enough size
+// information that we can return the object to the proper free list
+// without permanently losing part of the object.
+//
+
+// The first template parameter specifies whether more than one thread
+// may use this allocator. It is safe to allocate an object from
+// one instance of a default_alloc and deallocate it with another
+// one. This effectively transfers its ownership to the second one.
+// This may have undesirable effects on reference locality.
+// The second parameter is unreferenced and serves only to allow the
+// creation of multiple default_alloc instances.
+// Node that containers built on different allocator instances have
+// different types, limiting the utility of this approach.
+#ifdef __SUNPRO_CC
+// breaks if we make these template class members:
+ enum {__ALIGN = 8};
+ enum {__MAX_BYTES = 128};
+ enum {__NFREELISTS = __MAX_BYTES/__ALIGN};
+#endif
+
+template <bool threads, int inst>
+class __default_alloc_template {
+
+private:
+ // Really we should use static const int x = N
+ // instead of enum { x = N }, but few compilers accept the former.
+# ifndef __SUNPRO_CC
+ enum {__ALIGN = 8};
+ enum {__MAX_BYTES = 128};
+ enum {__NFREELISTS = __MAX_BYTES/__ALIGN};
+# endif
+ static size_t ROUND_UP(size_t bytes) {
+ return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
+ }
+__PRIVATE:
+ union obj {
+ union obj * free_list_link;
+ char client_data[1]; /* The client sees this. */
+ };
+private:
+# ifdef __SUNPRO_CC
+ static obj * __VOLATILE free_list[];
+ // Specifying a size results in duplicate def for 4.1
+# else
+ static obj * __VOLATILE free_list[__NFREELISTS];
+# endif
+ static size_t FREELIST_INDEX(size_t bytes) {
+ return (((bytes) + __ALIGN-1)/__ALIGN - 1);
+ }
+
+ // Returns an object of size n, and optionally adds to size n free list.
+ static void *refill(size_t n);
+ // Allocates a chunk for nobjs of size size. nobjs may be reduced
+ // if it is inconvenient to allocate the requested number.
+ static char *chunk_alloc(size_t size, int &nobjs);
+
+ // Chunk allocation state.
+ static char *start_free;
+ static char *end_free;
+ static size_t heap_size;
+
+# ifdef __STL_SGI_THREADS
+ static volatile unsigned long __node_allocator_lock;
+ static void __lock(volatile unsigned long *);
+ static inline void __unlock(volatile unsigned long *);
+# endif
+
+# ifdef _PTHREADS
+ static pthread_mutex_t __node_allocator_lock;
+# endif
+
+# ifdef __STL_WIN32THREADS
+ static CRITICAL_SECTION __node_allocator_lock;
+ static bool __node_allocator_lock_initialized;
+
+ public:
+ __default_alloc_template() {
+ // This assumes the first constructor is called before threads
+ // are started.
+ if (!__node_allocator_lock_initialized) {
+ InitializeCriticalSection(&__node_allocator_lock);
+ __node_allocator_lock_initialized = true;
+ }
+ }
+ private:
+# endif
+
+ class lock {
+ public:
+ lock() { __NODE_ALLOCATOR_LOCK; }
+ ~lock() { __NODE_ALLOCATOR_UNLOCK; }
+ };
+ friend class lock;
+
+public:
+
+ /* n must be > 0 */
+ static void * allocate(size_t n)
+ {
+ obj * __VOLATILE * my_free_list;
+ obj * __RESTRICT result;
+
+ if (n > __MAX_BYTES) {
+ return(malloc_alloc::allocate(n));
+ }
+ my_free_list = free_list + FREELIST_INDEX(n);
+ // Acquire the lock here with a constructor call.
+ // This ensures that it is released in exit or during stack
+ // unwinding.
+ /*REFERENCED*/
+ lock lock_instance;
+ result = *my_free_list;
+ if (result == 0) {
+ void *r = refill(ROUND_UP(n));
+ return r;
+ }
+ *my_free_list = result -> free_list_link;
+ return (result);
+ };
+
+ /* p may not be 0 */
+ static void deallocate(void *p, size_t n)
+ {
+ obj *q = (obj *)p;
+ obj * __VOLATILE * my_free_list;
+
+ if (n > __MAX_BYTES) {
+ malloc_alloc::deallocate(p, n);
+ return;
+ }
+ my_free_list = free_list + FREELIST_INDEX(n);
+ // acquire lock
+ /*REFERENCED*/
+ lock lock_instance;
+ q -> free_list_link = *my_free_list;
+ *my_free_list = q;
+ // lock is released here
+ }
+
+ static void * reallocate(void *p, size_t old_sz, size_t new_sz);
+
+} ;
+
+typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
+typedef __default_alloc_template<false, 0> single_client_alloc;
+
+
+
+/* We allocate memory in large chunks in order to avoid fragmenting */
+/* the malloc heap too much. */
+/* We assume that size is properly aligned. */
+/* We hold the allocation lock. */
+template <bool threads, int inst>
+char*
+__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs)
+{
+ char * result;
+ size_t total_bytes = size * nobjs;
+ size_t bytes_left = end_free - start_free;
+
+ if (bytes_left >= total_bytes) {
+ result = start_free;
+ start_free += total_bytes;
+ return(result);
+ } else if (bytes_left >= size) {
+ nobjs = bytes_left/size;
+ total_bytes = size * nobjs;
+ result = start_free;
+ start_free += total_bytes;
+ return(result);
+ } else {
+ size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
+ // Try to make use of the left-over piece.
+ if (bytes_left > 0) {
+ obj * __VOLATILE * my_free_list =
+ free_list + FREELIST_INDEX(bytes_left);
+
+ ((obj *)start_free) -> free_list_link = *my_free_list;
+ *my_free_list = (obj *)start_free;
+ }
+ start_free = (char *)malloc(bytes_to_get);
+ if (0 == start_free) {
+ int i;
+ obj * __VOLATILE * my_free_list, *p;
+ // Try to make do with what we have. That can't
+ // hurt. We do not try smaller requests, since that tends
+ // to result in disaster on multi-process machines.
+ for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
+ my_free_list = free_list + FREELIST_INDEX(i);
+ p = *my_free_list;
+ if (0 != p) {
+ *my_free_list = p -> free_list_link;
+ start_free = (char *)p;
+ end_free = start_free + i;
+ return(chunk_alloc(size, nobjs));
+ // Any leftover piece will eventually make it to the
+ // right free list.
+ }
+ }
+ start_free = (char *)malloc_alloc::allocate(bytes_to_get);
+ // This should either throw an
+ // exception or remedy the situation. Thus we assume it
+ // succeeded.
+ }
+ heap_size += bytes_to_get;
+ end_free = start_free + bytes_to_get;
+ return(chunk_alloc(size, nobjs));
+ }
+}
+
+
+/* Returns an object of size n, and optionally adds to size n free list.*/
+/* We assume that n is properly aligned. */
+/* We hold the allocation lock. */
+template <bool threads, int inst>
+void* __default_alloc_template<threads, inst>::refill(size_t n)
+{
+ int nobjs = 20;
+ char * chunk = chunk_alloc(n, nobjs);
+ obj * __VOLATILE * my_free_list;
+ obj * result;
+ obj * current_obj, * next_obj;
+ int i;
+
+ if (1 == nobjs) return(chunk);
+ my_free_list = free_list + FREELIST_INDEX(n);
+
+ /* Build free list in chunk */
+ result = (obj *)chunk;
+ *my_free_list = next_obj = (obj *)(chunk + n);
+ for (i = 1; ; i++) {
+ current_obj = next_obj;
+ next_obj = (obj *)((char *)next_obj + n);
+ if (nobjs - 1 == i) {
+ current_obj -> free_list_link = 0;
+ break;
+ } else {
+ current_obj -> free_list_link = next_obj;
+ }
+ }
+ return(result);
+}
+
+template <bool threads, int inst>
+void*
+__default_alloc_template<threads, inst>::reallocate(void *p,
+ size_t old_sz,
+ size_t new_sz)
+{
+ void * result;
+ size_t copy_sz;
+
+ if (old_sz > __MAX_BYTES && new_sz > __MAX_BYTES) {
+ return(realloc(p, new_sz));
+ }
+ if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p);
+ result = allocate(new_sz);
+ copy_sz = new_sz > old_sz? old_sz : new_sz;
+ memcpy(result, p, copy_sz);
+ deallocate(p, old_sz);
+ return(result);
+}
+
+#ifdef _PTHREADS
+ template <bool threads, int inst>
+ pthread_mutex_t
+ __default_alloc_template<threads, inst>::__node_allocator_lock
+ = PTHREAD_MUTEX_INITIALIZER;
+#endif
+
+#ifdef __STL_WIN32THREADS
+ template <bool threads, int inst> CRITICAL_SECTION
+ __default_alloc_template<threads, inst>::__node_allocator_lock;
+
+ template <bool threads, int inst> bool
+ __default_alloc_template<threads, inst>::__node_allocator_lock_initialized
+ = false;
+#endif
+
+#ifdef __STL_SGI_THREADS
+#include <mutex.h>
+#include <time.h>
+// Somewhat generic lock implementations. We need only test-and-set
+// and some way to sleep. These should work with both SGI pthreads
+// and sproc threads. They may be useful on other systems.
+template <bool threads, int inst>
+volatile unsigned long
+__default_alloc_template<threads, inst>::__node_allocator_lock = 0;
+
+#if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64)) || defined(__GNUC__)
+# define __test_and_set(l,v) test_and_set(l,v)
+#endif
+
+template <bool threads, int inst>
+void
+__default_alloc_template<threads, inst>::__lock(volatile unsigned long *lock)
+{
+ const unsigned low_spin_max = 30; // spin cycles if we suspect uniprocessor
+ const unsigned high_spin_max = 1000; // spin cycles for multiprocessor
+ static unsigned spin_max = low_spin_max;
+ unsigned my_spin_max;
+ static unsigned last_spins = 0;
+ unsigned my_last_spins;
+ static struct timespec ts = {0, 1000};
+ unsigned junk;
+# define __ALLOC_PAUSE junk *= junk; junk *= junk; junk *= junk; junk *= junk
+ int i;
+
+ if (!__test_and_set((unsigned long *)lock, 1)) {
+ return;
+ }
+ my_spin_max = spin_max;
+ my_last_spins = last_spins;
+ for (i = 0; i < my_spin_max; i++) {
+ if (i < my_last_spins/2 || *lock) {
+ __ALLOC_PAUSE;
+ continue;
+ }
+ if (!__test_and_set((unsigned long *)lock, 1)) {
+ // got it!
+ // Spinning worked. Thus we're probably not being scheduled
+ // against the other process with which we were contending.
+ // Thus it makes sense to spin longer the next time.
+ last_spins = i;
+ spin_max = high_spin_max;
+ return;
+ }
+ }
+ // We are probably being scheduled against the other process. Sleep.
+ spin_max = low_spin_max;
+ for (;;) {
+ if (!__test_and_set((unsigned long *)lock, 1)) {
+ return;
+ }
+ nanosleep(&ts, 0);
+ }
+}
+
+template <bool threads, int inst>
+inline void
+__default_alloc_template<threads, inst>::__unlock(volatile unsigned long *lock)
+{
+# if defined(__GNUC__) && __mips >= 3
+ asm("sync");
+ *lock = 0;
+# elif __mips >= 3 && (defined (_ABIN32) || defined(_ABI64))
+ __lock_release(lock);
+# else
+ *lock = 0;
+ // This is not sufficient on many multiprocessors, since
+ // writes to protected variables and the lock may be reordered.
+# endif
+}
+#endif
+
+template <bool threads, int inst>
+char *__default_alloc_template<threads, inst>::start_free = 0;
+
+template <bool threads, int inst>
+char *__default_alloc_template<threads, inst>::end_free = 0;
+
+template <bool threads, int inst>
+size_t __default_alloc_template<threads, inst>::heap_size = 0;
+
+template <bool threads, int inst>
+__default_alloc_template<threads, inst>::obj * __VOLATILE
+__default_alloc_template<threads, inst> ::free_list[
+# ifdef __SUNPRO_CC
+ __NFREELISTS
+# else
+ __default_alloc_template<threads, inst>::__NFREELISTS
+# endif
+] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
+// The 16 zeros are necessary to make version 4.1 of the SunPro
+// compiler happy. Otherwise it appears to allocate too little
+// space for the array.
+
+# ifdef __STL_WIN32THREADS
+ // Create one to get critical section initialized.
+ // We do this onece per file, but only the first constructor
+ // does anything.
+ static alloc __node_allocator_dummy_instance;
+# endif
+
+#endif /* ! __USE_MALLOC */
+
+#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
+#pragma reset woff 1174
+#endif
+
+#endif /* __NODE_ALLOC_H */
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-18 15:54:54 +0000