Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Implementing an observer

Reply
Thread Tools

Implementing an observer

 
 
jacob navia
Guest
Posts: n/a
 
      11-18-2010
An observer is a "must have" for my container library.

For each container you should be able to add an "observer" to it, i.e.
adding a function that will be called when the container is modified.
The callback function should receive a lot of information about what is
being changed, but that is another problem.

As far as I see I have two choices.

(1) Add a slot to the header object. This is simple, but it would mean
that this already heavy objects are bigger by sizeof(void *), not
very exciting considering that in 99.99% of the case you are not
going to use it.

(2) Add some global list to the software that would maintain a list
(or hash table) of containers, each with a list of functions that
should be called when it changes. Then, the flags field that is now
mostly empty could be used to flag any container that posesses an
observer. If that flag is set, after any modification the software
would inspect the list of observers and see if this one is in
that list. Problems with this second solution is that it represents
a multi-threaded bottleneck, is much more expensive since the
global observer lists could be quite long.

Has anyone here any better solution?

By the way, does anyone know how is this implemented in the C++ STL (if
at all)?
 
Reply With Quote
 
 
 
 
Ian Collins
Guest
Posts: n/a
 
      11-19-2010
On 11/19/10 12:00 PM, jacob navia wrote:
> An observer is a "must have" for my container library.
>
> For each container you should be able to add an "observer" to it, i.e.
> adding a function that will be called when the container is modified.
> The callback function should receive a lot of information about what is
> being changed, but that is another problem.


I guess the obvious question is why is this a "must have"?

> As far as I see I have two choices.
>
> (1) Add a slot to the header object. This is simple, but it would mean
> that this already heavy objects are bigger by sizeof(void *), not
> very exciting considering that in 99.99% of the case you are not
> going to use it.
>
> (2) Add some global list to the software that would maintain a list
> (or hash table) of containers, each with a list of functions that
> should be called when it changes. Then, the flags field that is now
> mostly empty could be used to flag any container that posesses an
> observer. If that flag is set, after any modification the software
> would inspect the list of observers and see if this one is in
> that list. Problems with this second solution is that it represents
> a multi-threaded bottleneck, is much more expensive since the
> global observer lists could be quite long.
>
> Has anyone here any better solution?
>
> By the way, does anyone know how is this implemented in the C++ STL (if
> at all)?


It isn't. If you wanted to do this, you could derive privately from a
container and overload the methods that modify the it.

--
Ian Collins
 
Reply With Quote
 
 
 
 
Mark Wooding
Guest
Posts: n/a
 
      11-19-2010
jacob navia <(E-Mail Removed)> writes:

> (1) Add a slot to the header object.


This might not be too bad if there are other optional features which
require additional state and could share the same pointer. I can't
think of any obvious examples offhand, though.

> (2) Add some global list to the software that would maintain a list
> (or hash table) of containers,


Hashing pointers can't be done portably, but it would work much faster
than a (properly portable) list on the (common) platforms where it can
be done.

> Has anyone here any better solution?


Introduce subclasses supporting observation? Then you pay for it only
if you (expect to) use it.

A nonportable trick which might work: allocate container headers in
chunks with some known alignment, so that you can find the chunk base
easily given the header. Add a flag to each container header to say
whether it uses an extension record. Use a single word at the start of
the chunk to point to an extension record table for all the headers in
the chunk: the first time you need an extension record for one header,
allocate the extension record table for the chunk and an extension
record for the particular header. In the absence of contention, you
only pay one CAS for each chunk which needs an extension record. Memory
overheads are one word per chunk, plus one word per header if any
extension records are used, plus the needed extension records
themselves.

Example (completely untested!):

#define NCHUNK 16

struct ext {
/* ... */
};

struct hdr {
unsigned f;
#define F_EXT 1u
/* ... */
};

struct chunk {
struct ext **xv;
struct hdr hv[NCHUNK];
};

struct ext *ensure_ext(struct hdr *h)
{
struct chunk *c = CHUNK_BASE(h);
struct chunk **xv = c->xv;
int i = h - c->hv;

/* Quick check for extension record. */
if (!(h->f & F_EXT)) {

/* Ensure extension vector for the chunk exists: attention
* to concurrency required.
*/
if (!xv) {
if ((xv = malloc(NCHUNK * sizeof(*xv))) == 0)
return (0);
if (COMPARE_AND_SWAP(c->xv, xv, 0)) {
free(xv);
xv = c->xv;
}
}

/* Ensure extension record for the header. Assume single
* threaded access to the header. This can't be allocated yet.
*/
if ((xv[i] = malloc(sizeof(struct ext))) == 0)
return (0);
h->f |= F_EXT;
}

/* Done. */
return (xv[i]);
}

> By the way, does anyone know how is this implemented in the C++ STL (if at
> all)?


It isn't. You'd have to subclass manually.

-- [mdw]
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      11-19-2010
Le 19/11/10 01:48, Ian Collins a écrit :
> On 11/19/10 12:00 PM, jacob navia wrote:
>> An observer is a "must have" for my container library.
>>
>> For each container you should be able to add an "observer" to it, i.e.
>> adding a function that will be called when the container is modified.
>> The callback function should receive a lot of information about what is
>> being changed, but that is another problem.

>
> I guess the obvious question is why is this a "must have"?
>


Sorry, I forgot to mention the applications.

For instance, you have a list of files in a directory and you want to
be notified when some other process changes it.

You have pointers to some elements of a list and you want to keep them
current with the changes done to the list, avoiding pointers that point
to deleted objects, for instance.


You want to avoid a list getting too long, splitting it when it goes
beyond a threshold.

The applications are numerous. Actually this is a known pattern. See
"Design Patterns" by Gamma/Helm/Johnson/Vlissides, page 293.

>> As far as I see I have two choices.
>>
>> (1) Add a slot to the header object. This is simple, but it would mean
>> that this already heavy objects are bigger by sizeof(void *), not
>> very exciting considering that in 99.99% of the case you are not
>> going to use it.
>>
>> (2) Add some global list to the software that would maintain a list
>> (or hash table) of containers, each with a list of functions that
>> should be called when it changes. Then, the flags field that is now
>> mostly empty could be used to flag any container that posesses an
>> observer. If that flag is set, after any modification the software
>> would inspect the list of observers and see if this one is in
>> that list. Problems with this second solution is that it represents
>> a multi-threaded bottleneck, is much more expensive since the
>> global observer lists could be quite long.
>>
>> Has anyone here any better solution?
>>
>> By the way, does anyone know how is this implemented in the C++ STL (if
>> at all)?

>
> It isn't. If you wanted to do this, you could derive privately from a
> container and overload the methods that modify the it.
>


All of them?
Wow, kind of a tough job.

Thanks for your contribution.

 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      11-19-2010
Le 19/11/10 01:48, Mark Wooding a écrit :
> jacob navia<(E-Mail Removed)> writes:
>
>> (1) Add a slot to the header object.

>
> This might not be too bad if there are other optional features which
> require additional state and could share the same pointer. I can't
> think of any obvious examples offhand, though.
>


In most cases, you just use a list. In some rare cases, you want to have
a list that notifies you about changes. So, in most cases that slot
would be wasted...

>> (2) Add some global list to the software that would maintain a list
>> (or hash table) of containers,

>
> Hashing pointers can't be done portably, but it would work much faster
> than a (properly portable) list on the (common) platforms where it can
> be done.
>
>> Has anyone here any better solution?

>
> Introduce subclasses supporting observation? Then you pay for it only
> if you (expect to) use it.
>


That is complicated in C.


> A nonportable trick which might work: allocate container headers in
> chunks with some known alignment, so that you can find the chunk base
> easily given the header. Add a flag to each container header to say
> whether it uses an extension record. Use a single word at the start of
> the chunk to point to an extension record table for all the headers in
> the chunk: the first time you need an extension record for one header,
> allocate the extension record table for the chunk and an extension
> record for the particular header. In the absence of contention, you
> only pay one CAS for each chunk which needs an extension record. Memory
> overheads are one word per chunk, plus one word per header if any
> extension records are used, plus the needed extension records
> themselves.
>


Wow that is a clever schema. I think the essential point is to allocate
as needed, to avoid wasted storage. Thanks a lot for this idea.


> Example (completely untested!):
>
> #define NCHUNK 16
>
> struct ext {
> /* ... */
> };
>
> struct hdr {
> unsigned f;
> #define F_EXT 1u
> /* ... */
> };
>
> struct chunk {
> struct ext **xv;
> struct hdr hv[NCHUNK];
> };
>
> struct ext *ensure_ext(struct hdr *h)
> {
> struct chunk *c = CHUNK_BASE(h);
> struct chunk **xv = c->xv;
> int i = h - c->hv;
>
> /* Quick check for extension record. */
> if (!(h->f& F_EXT)) {
>
> /* Ensure extension vector for the chunk exists: attention
> * to concurrency required.
> */
> if (!xv) {
> if ((xv = malloc(NCHUNK * sizeof(*xv))) == 0)
> return (0);
> if (COMPARE_AND_SWAP(c->xv, xv, 0)) {
> free(xv);
> xv = c->xv;
> }
> }
>
> /* Ensure extension record for the header. Assume single
> * threaded access to the header. This can't be allocated yet.
> */
> if ((xv[i] = malloc(sizeof(struct ext))) == 0)
> return (0);
> h->f |= F_EXT;
> }
>
> /* Done. */
> return (xv[i]);
> }
>
>> By the way, does anyone know how is this implemented in the C++ STL (if at
>> all)?

>
> It isn't. You'd have to subclass manually.
>
> -- [mdw]


Well, in that case the C containers library will be better than the STL



Thanks for your very informative message.

jacob
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      11-19-2010
On 11/19/10 10:04 PM, jacob navia wrote:
> Le 19/11/10 01:48, Ian Collins a écrit :
>> On 11/19/10 12:00 PM, jacob navia wrote:
>>> An observer is a "must have" for my container library.
>>>
>>> For each container you should be able to add an "observer" to it, i.e.
>>> adding a function that will be called when the container is modified.
>>> The callback function should receive a lot of information about what is
>>> being changed, but that is another problem.

>>
>> I guess the obvious question is why is this a "must have"?
>>

>
> Sorry, I forgot to mention the applications.
>
> For instance, you have a list of files in a directory and you want to
> be notified when some other process changes it.


Then you definitely want to provide specialised mutators for the container.

> You have pointers to some elements of a list and you want to keep them
> current with the changes done to the list, avoiding pointers that point
> to deleted objects, for instance.


You can identify which containers invalidate pointers when they (the
containers) are modified. If you require the pointers to remain valid,
use a container that provide the appropriate guarantees.

I'm not sure what you mean by "avoiding pointers that point to deleted
objects".

> You want to avoid a list getting too long, splitting it when it goes
> beyond a threshold.


That shouldn't be the responsibility of the list, but of the process
that performs the insertion.

> The applications are numerous. Actually this is a known pattern. See
> "Design Patterns" by Gamma/Helm/Johnson/Vlissides, page 293.


They may appear numerous, but they are specialised. Probably too
specialised to encumber a generic container.

>>> By the way, does anyone know how is this implemented in the C++ STL (if
>>> at all)?

>>
>> It isn't. If you wanted to do this, you could derive privately from a
>> container and overload the methods that modify the it.

>
> All of them?
> Wow, kind of a tough job.


Not at all, there aren't that many (a mere handful) methods that mutate
a container.

If you are also considering mutation of objects within the container,
then you have a different set of problems.

--
Ian Collins
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      11-19-2010
On 11/19/10 10:14 PM, jacob navia wrote:
> Le 19/11/10 01:48, Mark Wooding a écrit :
>> jacob navia<(E-Mail Removed)> writes:
>>
>>> (1) Add a slot to the header object.

>>
>> This might not be too bad if there are other optional features which
>> require additional state and could share the same pointer. I can't
>> think of any obvious examples offhand, though.
>>

>
> In most cases, you just use a list. In some rare cases, you want to have
> a list that notifies you about changes. So, in most cases that slot
> would be wasted...
>
>>> (2) Add some global list to the software that would maintain a list
>>> (or hash table) of containers,

>>
>> Hashing pointers can't be done portably, but it would work much faster
>> than a (properly portable) list on the (common) platforms where it can
>> be done.
>>
>>> Has anyone here any better solution?

>>
>> Introduce subclasses supporting observation? Then you pay for it only
>> if you (expect to) use it.
>>

>
> That is complicated in C.
>
>
>> A nonportable trick which might work: allocate container headers in
>> chunks with some known alignment, so that you can find the chunk base
>> easily given the header. Add a flag to each container header to say
>> whether it uses an extension record. Use a single word at the start of
>> the chunk to point to an extension record table for all the headers in
>> the chunk: the first time you need an extension record for one header,
>> allocate the extension record table for the chunk and an extension
>> record for the particular header. In the absence of contention, you
>> only pay one CAS for each chunk which needs an extension record. Memory
>> overheads are one word per chunk, plus one word per header if any
>> extension records are used, plus the needed extension records
>> themselves.
>>

>
> Wow that is a clever schema. I think the essential point is to allocate
> as needed, to avoid wasted storage. Thanks a lot for this idea.


You could probably perform a similar trick with C++ containers by
including the callback mechanism in the allocator (all C++ container
have a allocator template parameter).

<snip>

> Well, in that case the C containers library will be better than the STL


For a subset of "better" and ignoring the "you don't pay for what you
don't use" rule!

--
Ian Collins
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      11-19-2010
Le 19/11/10 11:24, Ian Collins a écrit :
>
> You could probably perform a similar trick with C++ containers by
> including the callback mechanism in the allocator (all C++ container
> have a allocator template parameter).
>


Probably, but it would be QUITE a development...

> <snip>
>
>> Well, in that case the C containers library will be better than the STL

>
> For a subset of "better" and ignoring the "you don't pay for what you
> don't use" rule!
>


The idea of Mark would allow to implement this rule. If we only build
things as they are required, we would avoid almost all overhead for
objects that do NOT use this facility.

 
Reply With Quote
 
ld
Guest
Posts: n/a
 
      11-20-2010
On Nov 19, 12:00*am, jacob navia <(E-Mail Removed)> wrote:
> An observer is a "must have" for my container library.
>
> For each container you should be able to add an "observer" to it, i.e.
> adding a function that will be called when the container is modified.
> The callback function should receive a lot of information about what is
> being changed, but that is another problem.
>
> As far as I see I have two choices.
>
> (1) Add a slot to the header object. This is simple, but it would mean
> * * *that this already heavy objects are bigger by sizeof(void *), not
> * * *very exciting considering that in 99.99% of the case you are not
> * * *going to use it.
>
> (2) Add some global list to the software that would maintain a list
> * * *(or hash table) of containers, each with a list of functions that
> * * * should be called when it changes. Then, the flags field that is now
> * * * mostly empty could be used to flag any container that posesses an
> * * * observer. If that flag is set, after any modification the software
> * * * would inspect the list of observers and see if this one is *in
> * * * that list. Problems with this second solution is that it represents
> * * * a multi-threaded bottleneck, is much more expensive since the
> * * * global observer lists could be quite long.
>
> Has anyone here any better solution?
>
> By the way, does anyone know how is this implemented in the C++ STL (if
> at all)?


There isn't an Observer Pattern in the STL and it doesn't fit well
with the STL itself which is more compile-time oriented (templates)
while Observers (C++ Signals or Java Listeners) are more runtime
oriented (messages).

It's usually much better and much simpler to use a notification
center. More flexible (before and after or key-based notification),
faster, less contention (cyclic reference), lazy creation and
notification (priority queue), etc... If you have a MOP (Meta Object
Protocol) and support messages and closures like in COS (or CLOS), the
thing become trivial. A spreadsheet is a typical example of a
notification center.

for C++ examples (Poco):
http://pocoproject.org/docs/Poco.Not...ionCenter.html

for C++ signals examples (Boost):
http://www.boost.org/doc/libs/1_45_0...l/signals.html
http://www.boost.org/doc/libs/1_45_0.../signals2.html (thread
safe)

for an Objective-C examples (Cocoa):
http://developer.apple.com/library/m...onCenters.html

for Java examples:
http://download.oracle.com/javase/tu...nts/index.html

regards,

laurent
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      11-22-2010
jacob navia <(E-Mail Removed)> writes:

> An observer is a "must have" for my container library.
>
> For each container you should be able to add an "observer" to it,
> i.e. adding a function that will be called when the container is
> modified.
> The callback function should receive a lot of information about what
> is being changed, but that is another problem.
>
> As far as I see I have two choices.
>
> (1) Add a slot to the header object. This is simple, but it would mean
> that this already heavy objects are bigger by sizeof(void *), not
> very exciting considering that in 99.99% of the case you are not
> going to use it.
>
> (2) Add some global list to the software that would maintain a list
> (or hash table) of containers, each with a list of functions that
> should be called when it changes. Then, the flags field that is now
> mostly empty could be used to flag any container that posesses an
> observer. If that flag is set, after any modification the software
> would inspect the list of observers and see if this one is in
> that list. Problems with this second solution is that it represents
> a multi-threaded bottleneck, is much more expensive since the
> global observer lists could be quite long.
>
> Has anyone here any better solution?


Are you going to offer any kind of statement of requirements?
If not, I suggest the first order of business is to formulate
one.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Implementing the observer pattern in C jacob navia C Programming 3 03-29-2011 06:48 AM
implementing mvc - using observer pattern - beginner to OOP Adam Akhtar Ruby 8 11-11-2008 01:31 PM
Observable, Observer and recursive update() problem Rogan Dawes Java 4 06-11-2004 02:34 PM
Observer/Observable: update not called Timo Nentwig Java 1 04-16-2004 04:21 PM
Why don't Listeners use Observer/Observable Timo Nentwig Java 1 10-27-2003 04:13 PM



Advertisments