Implementing an observer

Discussion in 'C Programming' started by jacob navia, Nov 18, 2010.

  1. jacob navia

    jacob navia Guest

    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)?
     
    jacob navia, Nov 18, 2010
    #1
    1. Advertising

  2. jacob navia

    Ian Collins Guest

    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
     
    Ian Collins, Nov 19, 2010
    #2
    1. Advertising

  3. jacob navia

    Mark Wooding Guest

    jacob navia <> 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 = malloc(sizeof(struct ext))) == 0)
    return (0);
    h->f |= F_EXT;
    }

    /* Done. */
    return (xv);
    }

    > 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]
     
    Mark Wooding, Nov 19, 2010
    #3
  4. jacob navia

    jacob navia Guest

    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.
     
    jacob navia, Nov 19, 2010
    #4
  5. jacob navia

    jacob navia Guest

    Le 19/11/10 01:48, Mark Wooding a écrit :
    > jacob navia<> 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 = malloc(sizeof(struct ext))) == 0)
    > return (0);
    > h->f |= F_EXT;
    > }
    >
    > /* Done. */
    > return (xv);
    > }
    >
    >> 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
     
    jacob navia, Nov 19, 2010
    #5
  6. jacob navia

    Ian Collins Guest

    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
     
    Ian Collins, Nov 19, 2010
    #6
  7. jacob navia

    Ian Collins Guest

    On 11/19/10 10:14 PM, jacob navia wrote:
    > Le 19/11/10 01:48, Mark Wooding a écrit :
    >> jacob navia<> 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
     
    Ian Collins, Nov 19, 2010
    #7
  8. jacob navia

    jacob navia Guest

    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.
     
    jacob navia, Nov 19, 2010
    #8
  9. jacob navia

    ld Guest

    On Nov 19, 12:00 am, 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.
    >
    > 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.NotificationCenter.html

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

    for an Objective-C examples (Cocoa):
    http://developer.apple.com/library/...tifications/Articles/NotificationCenters.html

    for Java examples:
    http://download.oracle.com/javase/tutorial/uiswing/events/index.html

    regards,

    laurent
     
    ld, Nov 20, 2010
    #9
  10. jacob navia

    Tim Rentsch Guest

    jacob navia <> 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.
     
    Tim Rentsch, Nov 22, 2010
    #10
  11. jacob navia

    Gene Guest

    On Nov 19, 4:14 am, jacob navia <> wrote:
    > Le 19/11/10 01:48, Mark Wooding a écrit :
    >
    > > jacob navia<>  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 = malloc(sizeof(struct ext))) == 0)
    > >                return (0);
    > >              h->f |= F_EXT;
    > >            }

    >
    > >            /* Done. */
    > >            return (xv);
    > >          }

    >
    > >> 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.


    Another scheme that's totally portable and relatively clean, even in
    C89:

    typedef struct basic_container_s {
    unsigned flags;
    ... common fields of basic container functionality
    } BASIC_CONTAINER;

    typedef struct simple_container_s {
    BASIC_CONTAINER base[1];
    } SIMPLE_CONTAINER;

    typedef struct augmented_container_s {
    BASIC_CONTAINER base[1];
    OBSERVER observer[1];
    ... additional fields of a container with augmented functionality
    } AUGMENTED_CONTAINER;

    /* This may look wierd, but it leads to a correct result. */
    typedef BASIC_CONTAINER CONTAINER;

    CONTAINER *make_simple_container(void)
    {
    SIMPLE_CONTAINER *c = safe_malloc(sizeof *c);
    c->base->flags = 0;
    return c->base;
    }

    CONTAINER *make_augmented_container(void)
    {
    AUGMENTED_CONTAINER *c = safe_malloc(sizeof *c);
    c->base->flags = AUGMENTED;
    return c->base;
    }

    void set_observer(CONTAINER *c, OBSERVER *o)
    {
    die_unless(c->base->flags & AUGMENTED);
    *((AUGMENTED_CONTAINER)c)->observer = *o;
    }

    Now,

    CONTAINER c = make_simple_container();
    CONTAINER d = make_augmented_container();
    OBSERVER o[1] = {{ ... observer fields ... }};

    set_observer(d, o);
    set_observer(c, o); // !!! ERRROR !!!

    Essentially this gives you one nice level of subclassing. It doesn't
    continue gracefully to more than one level, however. If you need
    multiple kinds of augmentation, it may be best to augment with a
    single void pointer and hang different data on the pointer as needed.
    E.g. Lisp would use a property list.
     
    Gene, Nov 23, 2010
    #11
  12. "Mark Wooding" <> wrote in message
    news:...
    [...]

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


    I am wondering exactly how can you _assume_ single threaded access to
    `xv' here? If you could, then there should be no need for the CAS.
    AFAICT, in order for this to work, you would need to use something like:

    <quick pseudo-code>
    __________________________________________________________
    #define HEADERS_MAX 64U


    struct extension
    {
    // [...; list of observers; whatever...];
    };


    struct extension_header
    {
    struct extension* ext[HEADERS_MAX];
    };


    struct container_header
    {
    // [...];
    };


    struct container_mem_chunk
    {
    struct extension_header* xhdr; // = NULL
    struct container_header hdr[HEADERS_MAX];
    // [...];
    };


    struct extension*
    container_header_ensure_extension(
    struct container_header* const self
    ){
    struct container_mem_chunk* const chunk =
    CHUNK_FROM_HEADER(self);

    size_t hdr_idx = self - chunk->hdr;

    // conditionally create the extension_header `xhdr'
    struct extension_header* xhdr =
    ATOMIC_LOAD_CONSUME(&chunk->xhdr);

    if (! xhdr)
    {
    if (! (xhdr = malloc(sizeof(*xhdr)))) return NULL;

    struct extension_header* xhdr_cmp =
    ATOMIC_CAS_STRONG_ACQ_REL(&chunk->xhdr, NULL, xhdr);

    if (xhdr_cmp)
    {
    free(xhdr);
    xhdr = xhdr_cmp;
    }
    }


    // conditionally create the extension `x' specific to the header `self'
    struct extension* x =
    ATOMIC_LOAD_CONSUME(&xhdr->[hdr_idx]);

    if (! x)
    {
    if (! (x = malloc(sizeof(*x)))) return NULL;

    struct extension* x_cmp =
    ATOMIC_CAS_STRONG_ACQ_REL(&xhdr->ext[hdr_idx], NULL, x);

    if (x_cmp)
    {
    free(x);
    x = x_cmp;
    }
    }

    return x;
    }
    __________________________________________________________
     
    Chris M. Thomasson, Nov 23, 2010
    #12
  13. jacob navia

    jacob navia Guest

    Le 23/11/10 00:39, Tim Rentsch a écrit :

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


    What do you mean by that?

    Can you explain?

    Thanks
     
    jacob navia, Nov 23, 2010
    #13
  14. jacob navia

    Mark Wooding Guest

    "Chris M. Thomasson" <> writes:

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

    >
    > I am wondering exactly how can you _assume_ single threaded access to
    > `xv' here?


    Essentially, I'm imposing an obligation on the client to use each
    container object in a single threaded way. I inferred this obligation
    from Jacob's earlier posting: he complained that a hashtable-based
    implementation introduced a requirement for locking. Alternatively, the
    container implementation could arrange to lock the header before calling
    the function to ensure the extension record. Since `xv' is only
    accessed from the single thread working with the ith header in the
    chunk, this is sufficient.

    > If you could, then there should be no need for the CAS.


    I think the CAS is needed to synchronize between different threads using
    different headers in the same chunk concurrently, which is permitted.

    Does that seem reasonable?

    -- [mdw]
     
    Mark Wooding, Nov 23, 2010
    #14
  15. "Mark Wooding" <> wrote in message
    news:...
    > "Chris M. Thomasson" <> writes:
    >
    >> "Mark Wooding" <> wrote in message
    >> news:...


    [...]

    > Essentially, I'm imposing an obligation on the client to use each
    > container object in a single threaded way.


    Okay.

    [...]


    >> If you could, then there should be no need for the CAS.

    >
    > I think the CAS is needed to synchronize between different threads using
    > different headers in the same chunk concurrently, which is permitted.
    >
    > Does that seem reasonable?


    Yes.
     
    Chris M. Thomasson, Nov 23, 2010
    #15
  16. "Mark Wooding" <> wrote in message
    news:...
    > "Chris M. Thomasson" <> writes:
    >
    >> "Mark Wooding" <> wrote in message
    >> news:...


    [...]

    > Essentially, I'm imposing an obligation on the client to use each
    > container object in a single threaded way.


    Okay.

    [...]


    >> If you could, then there should be no need for the CAS.

    >
    > I think the CAS is needed to synchronize between different threads using
    > different headers in the same chunk concurrently, which is permitted.
    >
    > Does that seem reasonable?


    Yes.
     
    Chris M. Thomasson, Nov 23, 2010
    #16
  17. jacob navia

    ImpalerCore Guest

    On Nov 18, 6:00 pm, jacob navia <> wrote:
    > An observer is a "must have" for my container library.


    <snip>

    > not
    >      very exciting considering that in 99.99% of the case you are not
    >      going to use it.


    I have to admit I got a chuckle from your "must have" constraint for
    something you would use 0.01% of the time. There is a tradeoff
    between utility and complexity, and with those numbers I'd be pretty
    confident that this is not a good tradeoff.

    But if you want to pursue it for your own curiosity, go for it.

    Best regards,
    John D.
     
    ImpalerCore, Nov 23, 2010
    #17
  18. jacob navia

    jacob navia Guest

    Le 23/11/10 17:21, ImpalerCore a écrit :
    > On Nov 18, 6:00 pm, jacob navia<> wrote:
    >> An observer is a "must have" for my container library.

    >
    > <snip>
    >
    >> not
    >> very exciting considering that in 99.99% of the case you are not
    >> going to use it.

    >
    > I have to admit I got a chuckle from your "must have" constraint for
    > something you would use 0.01% of the time. There is a tradeoff
    > between utility and complexity, and with those numbers I'd be pretty
    > confident that this is not a good tradeoff.
    >
    > But if you want to pursue it for your own curiosity, go for it.
    >
    > Best regards,
    > John D.


    In most of the multi-threaded programs, 99.99% of the time there aren't
    any contention issues and you can spare yourself making a semaphore access.

    Problem is, in 0.01% of the cases there IS a contention and you need a
    semaphore. Even if you do not need it most of the time having a
    semaphore is absolutely essential...

    jacob
     
    jacob navia, Nov 23, 2010
    #18
  19. jacob navia

    Seebs Guest

    On 2010-11-23, jacob navia <> wrote:
    > Le 23/11/10 00:39, Tim Rentsch a ?crit :
    >> Are you going to offer any kind of statement of requirements?
    >> If not, I suggest the first order of business is to formulate
    >> one.


    > What do you mean by that?


    I'm not Tim, but it seemed to me that the first question is what
    the specification is. Implementing an observer is not useful unless
    users have a clear idea what the observer does. In particular, since
    you've proposed that other people might adopt the container library
    API, there should be a specification somewhere such that someone else
    could implement it, and a user of your library could switch to theirs
    (or vice versa) without any code breaking.

    -s
    --
    Copyright 2010, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
     
    Seebs, Nov 23, 2010
    #19
  20. jacob navia

    ImpalerCore Guest

    On Nov 23, 12:35 pm, jacob navia <> wrote:
    > Le 23/11/10 17:21, ImpalerCore a écrit :
    >
    >
    >
    > > On Nov 18, 6:00 pm, jacob navia<>  wrote:
    > >> An observer is a "must have" for my container library.

    >
    > > <snip>

    >
    > >>                                                                    not
    > >>       very exciting considering that in 99.99% of the case you are not
    > >>       going to use it.

    >
    > > I have to admit I got a chuckle from your "must have" constraint for
    > > something you would use 0.01% of the time.  There is a tradeoff
    > > between utility and complexity, and with those numbers I'd be pretty
    > > confident that this is not a good tradeoff.

    >
    > > But if you want to pursue it for your own curiosity, go for it.

    >
    > > Best regards,
    > > John D.

    >
    > In most of the multi-threaded programs, 99.99% of the time there aren't
    > any contention issues and you can spare yourself making a semaphore access.
    >
    > Problem is, in 0.01% of the cases there IS a contention and you need a
    > semaphore. Even if you do not need it most of the time having a
    > semaphore is absolutely essential...


    Ah, I didn't catch that you intended it for multi-threaded
    applications. I thought that you were referring to just needing an
    observer pattern out of any context.

    I don't have experience with multi-threaded containers, so I have no
    ideas to offer.
     
    ImpalerCore, Nov 23, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Timo Nentwig
    Replies:
    1
    Views:
    513
    xarax
    Oct 27, 2003
  2. Timo Nentwig
    Replies:
    1
    Views:
    1,256
    Thomas Fritsch
    Apr 16, 2004
  3. Rogan Dawes
    Replies:
    4
    Views:
    832
  4. jacob navia

    Implementing the observer pattern in C

    jacob navia, Mar 27, 2011, in forum: C Programming
    Replies:
    3
    Views:
    1,209
    jacob navia
    Mar 29, 2011
  5. Adam Akhtar
    Replies:
    8
    Views:
    226
    Adam Akhtar
    Nov 11, 2008
Loading...

Share This Page