Folks,

I'm trying to understand how I can leverage off STL to provide the
container and iterator behaviours I need. I'm still not seeing clearly
how to get what I want, and I was hoping some of you could help me out.

Let me be specific: I do a lot of work with multi-threading, and currently
I use a model that provides multi-threaded access to a container. The
scheme I am using now has these features:

- An entry in a container has a reference count. When positive, this
  count shows that the container still logically contains the item,
  and there are (count - 1) iterators looking at the item. When negative,
  the item has logically been removed from the container, and abs(count)
  is the number of iterators still looking at the item.
- The container itself has a mutex (or similar) to protect access to
  certain parts of the container's implementation (eg head and tail
  pointers in a list)
- When an item is removed from a container, it is logically removed
  if there are iterators looking at it, but only physically removed
  if no iterators are currently looking at it
- When an iterator moves off an item, if that item had been logically
  removed from the container, it is then physically removed
- An iterator++ operation must skip over logically deleted items when
  finding the next element in the container


Now, in my current implementations, I obviously need to add a reference
count field to my container entries, and a mutex or whatever to the
containers themselves, so something like:


template <class T>
class ListEntry
{
    ListEntry<T> *prev, *next;
    int refs;
    T item;
    // ...
};

template <class T>
class List
{
   // ...
   SomeMutex mutex;
};


To build on STL, I can easily derive a class from, say, list, to get
a list containing a mutex:

template <class T>
class mtlist: public list<T>
{
    // ...
  private:
    SomeMutex mutex;
};

What I can't see how to do is how to modify the internal aspects of the
list to:

- lock and unlock the mutex at the appropriate times
- take note of the reference counts in the list entries
- have iterators skip over logically removed entries

Can someone point the way?


Thanks

Ian
--
Consulting for Digital Equipment Corp  johnston@caiman.enet.dec.com
      (33) 92.95.51.74

In article <3mdias$juj@vbohub.vbo.dec.com>,
Ian Johnston <johnston@caiman.enet.dec.com> wrote:
>
>
>Folks,
>
>I'm trying to understand how I can leverage off STL to provide the
>container and iterator behaviours I need. I'm still not seeing clearly
>how to get what I want, and I was hoping some of you could help me out.

 [description elided]

 I think you have a design problem you have not yet seen --
so you haven't solved it.

 Lets start from scratch. Let C be some container of T.
Suppose C does not change. You can run iterators
up and down it. There is no problem, you can, if you want,
reference count the container itself so the container evaporates
when no iterators exist.

 Agree so far?

 Now suppose you permit _writing_ to elements of the container.
No insertions or deletions, just writing.

 Immediately, you have a major definitional problem.
Operations for which iteration is a simple and effective procedure
for computing functions defined on the whole container _at some
instant in time_ are no longer well defined unless the container
remains invariant during such iterative computations.

 For example: "What is the total amount of money owed
by this company?" Obviously, the very _question_ is meaningless
unless we add a qualification like "at this exact moment".

 So during such computations, the container needs to
be locked against modification. Even more fundamentally, one
should ask "Why an I trying to compute something which has no
meaning on a dynamically changing container?"

 If the answer is "We need a rough idea of how much
money the company owes" you may well NOT bother lock the container.
(You just tell the accountants exactly vaguely what "rough" means.
Let them do statistics to find out how accurate and useful
that particular "rough" is in practice :-)

 If the answer is "We need to verify our debits and
credits balance to zero" then you may need to lock
not only that container -- but several others too.

 So what you need to do is invent an OBJECT which represents
a "snapshot" (by locking the container). Using delegation, you
can then forward requests to construct iterators which require
invariant container contents in their lifetime.

 You can do this by providing you basic container
with functions such as

 begin_constant_view()

which return iterators which delegate through a single "constant view"
object so that the view is locked on the first request and unlocked
after all such iterators evaporate. You can also require user
explicitly construct the view and extract the begin() and end()
iterators from the view (I think thats what I'd do).

 The point of this is that there are many different _kinds_
of view that can be created. The idea that you can delete
a member of a conatiner to which another unrelated iterators
is refering is a clear indication of a design fault.
Merely reference counting prevents a machine crash, but it
doesn't solve the _real_ problem.

 The real problem  _has no universal solution_.
All you can do is build various specific solutions
(I mean "classes of solution") and invent more when ever the
ones you have prove inadequate (or are just too clumbsy).

 The notion of a view "encapsulates" the idea that several
iterators may be related. It doesn't solve the problem, but it
provides a technique for reducing its complexity.

 I hope this makes sense. For shared containers,
threading makes this kind of technique very programmable.
(Conversely, without threads, it is a nightmare ;-)


--
        JOHN (MAX) SKALLER,         INTERNET:maxtal@suphys.physics.su.oz.au
 Maxtal Pty Ltd,
        81A Glebe Point Rd, GLEBE   Mem: SA IT/9/22,SC22/WG21
        NSW 2037, AUSTRALIA     Phone: 61-2-566-2189

In article <3mdias$juj@vbohub.vbo.dec.com>,
Ian Johnston <johnston@caiman.enet.dec.com> wrote:
> I do a lot of work with multi-threading, and currently
>I use a model that provides multi-threaded access to a container. The
>scheme I am using now has these features:
>
>- An entry in a container has a reference count.
>- The container itself has a mutex
>- When an item is removed from a container, it is logically removed...
>- When an iterator moves off an item, if that item had been logically
>  removed from the container, it is then physically removed
>- An iterator++ operation must skip over logically deleted items when
>  finding the next element in the container
>
>To build on STL, I can easily derive a class from, say, list, to get
>a list containing a mutex:
>
>template <class T>
>class mtlist: public list<T> { ... }
>
>What I can't see how to do is how to modify the internal aspects of the
>list to:
>
>- lock and unlock the mutex at the appropriate times
>- take note of the reference counts in the list entries
>- have iterators skip over logically removed entries

This looks like a thorough design.  One thing, though... why
derive from list<T> ?  It looks as if you'll need to replace all
the member functions, and they're not virtual anyway.  Better to
make the standard list<T> a member, perhaps.  Then you have
control over all these issues.  (e.g. a logically-removed
entry gets moved to a different member list<>, where traversals
won't see it.)

Nathan Myers
myersn@roguewave.com