Re: [boost] Boost: containers and allocators

From: Larry Evans (jcampbell3_at_[hidden])
Date: 2001-05-24 14:23:06

John Max Skaller wrote:

> 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

I think I'm understanding you better.  Thanks.
But let me paraphrase to see if I understand:

Felix will work if each dynamically allocated
piece of memory  to be garbage collected has an appropriate frame_t
tacked onto the front by the allocator.  Right?  Then for list<T*> to work,
there's got to be a frame_t for list<T*> which points to the head and
tail pointers of the doubly linked list (actually, one or the other would be
enough).  Also, the link nodes used must also be allocate with a frame_t for
them.  For example, if the link struct is:
  struct link{ link*pre,suc;void*data};
then the frame_t offsets for link would point to pre,suc,and data where pre is the
predecessor node, suc is the succesor node, and data actually points to a T.
Then the allocator would have to allocate these link nodes with such an offset.

For this to work WITHOUT refcount'ed smart pointers,  the list<T*>::pre and suc
would have to be designated as root pointers if a list<T*> were on the stack.
If refcount'ed smart pointers were used, then the push_proxies calls and for
loops in fakeDel, filterLive, and collectGarbage in the following subdirectory
in gc_sel_ssp.zip:
  lib/gc_sel_ssp/src/special/crc/collect_crc.cpp
could be replaced with something like the loop in flx_collector_t::scan_object.

Is that about right?