Re: [boost] Boost: containers and allocators

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-05-24 04:55:05

Larry Evans wrote:

> >
> >         Finally: it is NOT obvious how to allocate
> > an array: we would need to allocate
> >
> >         struct raw_memory {
> >                 frame_t frame;
> >                 T data[n];
> >         };
> >
> > where 'n' is a VARIABLE. I know how big this is, but there
> > is no way to give the memory supplying allocator a
> > type to allocate for: we want n copies of T, and ONE frame.
> 
> I don't see how this can be generalized to any container with a dynamic number of
> pointers, e.g. list<T*> unless the frame_t is modified to contain a pointer to
> a class with a virtual function which  can enumerate the pointers because
> it knows its a list<T*> or whatever. 

        I'm not sure I understand. The struct above is what needs to
be allocated by the Felix GC when the client requests an array of
n T objects. At present, I could do this by creating an array
version of operator new, so I can know the size that needs to be 
allocated, add on 'sizeof(frame_t)'+padding, and allocate that:
I assume the resulting pointer to memory is aligned maximally.
But I don't call a _standard_ allocator. That is the problem here:
the only way to use a standard allocator to allocate storage is
to ask it for storage aligned for a T, and big enough for n of them.
There's no easy way to ask for 'sizeof(frame_t)+padding' extra bytes.

        There's no real problem with finding pointers: there
are only three cases:

        1) a struct
        2) a union
        3) an array of (1) or (2)

A list is made up of linked nodes, so there is no problem
of 'dynamic number of pointers'. The problem is that STL
uses an allocator to create and destroy the nodes,
so I have to model Felix GC as an allocator for it to
work with STL. Note that it will NOT work with
client code that uses 'plain new' and 'delete'
(unless these are replaced). In both cases, we have to 
use some kind of 'traits' information to find the
shape of a given type.

Vector is the only tricky case. It is easy enough to handle
arrays. The problem is to ensure

        a) all pointers in an array are initialised to NULL
        b) unused pointers are cleared to NULL

STL Vector doesn't ensure either of these. (a) can be forced
by Felix GC, at some cost. (b) cannot be enforced, so 
vector<T*> is likely to 'leak' (hold on to unreachable memory).
This can be fixed by the client using a wrapper (smart pointer).
For example:

        struct gc_ptr {
                T *data;
                gc_ptr() : data(0) {}
                ~gc_ptr() { data = 0; ]
                T * operator->() { return data; }
                ....
        };

For this reason, it isn't clear that zeroing pointers 
automatically is a good idea.

-- 
John (Max) Skaller, mailto:skaller_at_[hidden]
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net