simple BST implementation

Discussion in 'C Programming' started by Mark, Oct 20, 2009.

  1. Mark

    Mark Guest

    Hello

    I've implemented a very simple and small binary-search tree library as a
    training exercise. I'm posting it here together with a testing program and
    expect to receive critics and useful recommendations :)

    It compiles fine with the following GCC options:

    -std=c99 -pedantic -W -Wall -Wcast-align -Wcast-qual -Wmissing-prototypes -Wshadow
    -Wnested-externs -Wstrict-prototypes -Waggregate-return -O0 -ggdb

    I put in various checkpoints tracing messages which help me to better
    understand BST and to debug, it can be disabled with -DWITH_TRACE compiler
    flag. I'm yet to decide where to carefully put 'asserts'.

    /* tree.h */
    #ifndef TREE_H
    #define TREE_H

    #include <stddef.h> /* for size_t */

    /* error codes */
    enum {
    T_ESUCCESS,
    T_EINVALID,
    T_EBADPTR,
    T_EDUP,
    T_ENOMEM,
    T_EMPTYTREE
    };

    struct tree_node {
    void *data;
    size_t size; /* for future to indicate the data size */
    struct tree_node *left;
    struct tree_node *right;
    };

    struct tree_node *tree_allocnode(void *data);

    int tree_addnode(struct tree_node **root, struct tree_node *node,
    int(*cmp_fn)(const void *d1, const void *d2));

    void tree_freenode(struct tree_node *node);

    struct tree_node *tree_lookup(struct tree_node *root, const void *data,
    int(*cmp_fn)(const void *d1, const void *d2));

    void tree_freetree(struct tree_node *node, void (*fn)(void *data));

    int tree_traverse(struct tree_node *root,
    int(*fn)(struct tree_node *node, void *arg), void *arg);

    #endif

    /* tree.c */
    #ifdef WITH_TRACE
    #include <stdarg.h>
    #endif
    #include <stdio.h>
    #include <stdlib.h>
    #include "tree.h"

    #ifdef WITH_TRACE
    #define TRACE(...) (printf("TRACE: "), printf(__VA_ARGS__), printf("\n"))
    #else
    #define TRACE(...)
    #endif

    struct tree_node *tree_allocnode(void *data)
    {
    struct tree_node *node = NULL;

    node = malloc(sizeof *node);
    if (node != NULL)
    {
    if (data != NULL)
    {
    node->data = data;
    node->left = node->right = NULL;
    TRACE("node @ %p, data=%s", (void *)node, (char *)data);
    }
    else
    {
    free(node);
    node = NULL;
    }
    }

    return node;
    }

    int tree_addnode(struct tree_node **root, struct tree_node *node,
    int(*cmp_fn)(const void *d1, const void *d2))
    {
    int res = T_ESUCCESS;
    int d;

    if (node != NULL)
    {
    /* empty tree case */
    if (NULL == *root)
    {
    *root = node;
    node->left = node->right = NULL;
    TRACE("root @ %p", (void *)*root);
    }
    else
    {
    d = cmp_fn(node->data, (*root)->data);
    if (d < 0)
    {
    tree_addnode(&(*root)->left, node, cmp_fn);
    TRACE("node(%p)->left=%p", (void *)(*root), (void
    *)(*root)->left);
    }
    else if (d > 0)
    {
    tree_addnode(&(*root)->right, node, cmp_fn);
    TRACE("node(%p)->right=%p", (void *)(*root), (void
    *)(*root)->right);
    }
    else /* d == 0, i.e. duplicate entry */
    {
    res = T_EDUP;
    }
    }
    }
    else
    {
    res = T_EBADPTR;
    }

    return res;
    }

    void tree_freenode(struct tree_node *node)
    {
    if (node != NULL)
    {
    if (node->data != NULL)
    {
    free(node->data);
    }
    free(node);
    }
    }

    struct tree_node *tree_lookup(struct tree_node *root, const void *data,
    int(*cmp_fn)(const void *d1, const void *d2))
    {
    struct tree_node *node = NULL;
    int d;

    if (root != NULL)
    {
    d = cmp_fn(data, root->data);
    if (d > 0)
    {
    return tree_lookup(root->right, data, cmp_fn);
    }
    else if (d < 0)
    {
    return tree_lookup(root->left, data, cmp_fn);
    }
    else
    {
    node = root;
    TRACE("node found %p", (void *)node);
    }
    }

    return node;
    }

    void tree_freetree(struct tree_node *node, void (*fn)(void *data))
    {
    if (node != NULL)
    {
    if (fn != NULL)
    {
    fn(node->data);
    }
    TRACE("deleting node(%p)->left=%p", (void *)node, (void
    *)node->left);
    tree_freetree(node->left, fn);
    TRACE("deleting node(%p)->right=%p", (void *)node, (void
    *)node->right);
    tree_freetree(node->right, fn);

    free(node);
    }
    }

    int tree_traverse(struct tree_node *root,
    int(*fn)(struct tree_node *root, void *arg), void *arg)
    {
    int res = T_ESUCCESS;

    if (root != NULL)
    {
    tree_traverse(root->left, fn, arg);
    fn(root, arg);
    tree_traverse(root->right, fn, arg);
    }
    else
    {
    res = T_EMPTYTREE;
    }

    return res;
    }

    /* tree-test.c */
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "tree.h"

    static int tdata1[] = { 10, 6, 900, 7, 1, 57, 928, 1, 987 };
    static char *tdata[] = { "yellow", "apple", "chess", "penguin", "car",
    "mixer", "Zoo", "loop", "zebra" };
    #define DNUM (sizeof(tdata) / sizeof(tdata[0]))

    static int comp(const void *d1, const void *d2)
    {
    int res;

    res = strcmp((const char *)d1, (const char *)d2);
    if (res > 0) {
    printf("%s > %s\n", (const char *)d1, (const char *)d2);
    return 1;
    } else if (res < 0) {
    printf("%s < %s\n", (const char *)d1, (const char *)d2);
    return -1;
    } else {
    printf("%s = %s\n", (const char *)d1, (const char *)d2);
    return 0;
    }
    }

    static int comp1(const void *d1, const void *d2)
    {
    if (*(const int *)d1 < *(const int *)d2) {
    printf("%d < %d\n", *(const int *)d1, *(const int *)d2);
    return -1;
    }
    else if (*(const int *)d1 > *(const int *)d2) {
    printf("%d > %d\n", *(const int *)d1, *(const int *)d2);
    return 1;
    }
    else { /* if (*(const int *)d1 == *(const int * )d2) */
    printf("%d = %d\n", *(const int *)d1, *(const int *)d2);
    return 0;
    }
    }

    static int walk(struct tree_node *node, void *arg)
    {
    printf(arg, (char *)node->data);
    return 0;
    }

    int main(void)
    {
    struct tree_node *tptr, *root = NULL;
    unsigned int i;

    puts("Populating the tree...\n");
    for (i = 0; i < DNUM; i++) {
    puts("-------------------------------------");
    tptr = tree_allocnode(tdata);
    if (NULL == tptr)
    {
    puts("Failed to allocate memory!");
    exit(EXIT_FAILURE);
    }
    tree_addnode(&root, tptr, comp);
    }

    puts("Traversing the tree...\n");
    tree_traverse(root, walk, "data=%s\n");
    printf("found node %p\n", (void *)tree_lookup(root, tdata[3], comp));
    puts("Destroying the tree...\n");
    tree_freetree(root, NULL);
    puts("Traversing the tree...\n");
    tree_traverse(root, walk, "data=%s\n");

    return 0;
    }

    --
    Mark
    Mark, Oct 20, 2009
    #1
    1. Advertising

  2. Mark

    Seebs Guest

    On 2009-10-20, Mark <> wrote:
    > /* error codes */
    > enum {
    > T_ESUCCESS,


    No.

    "EFOO" is widely recognized as indicating an *error*.

    Success is not an error, normally.

    > T_EINVALID,
    > T_EBADPTR,
    > T_EDUP,
    > T_ENOMEM,
    > T_EMPTYTREE


    It seems to me that you might see whether there's enough standard/common
    errno values defined that you could just use errno.

    > struct tree_node {
    > void *data;
    > size_t size; /* for future to indicate the data size */


    If you're not using it, don't put it here, IMHO.

    > struct tree_node *tree_allocnode(void *data);


    I'm not totally sold on this, although I'm not totally unsold on it
    either.

    > int tree_addnode(struct tree_node **root, struct tree_node *node,
    > int(*cmp_fn)(const void *d1, const void *d2));


    I'd probably do these two differently.

    tree_node *tree_addnode(struct tree_node *root, void *data, int (*cmp_fn))...

    But even this is error-prone. In this case, I think it makes more sense
    to distinguish betwen the tree and its nodes.

    So I recommend:

    struct tree {
    int (*cmp_fn)(const void *d1, const void *d2);
    struct tree_node *root;
    }

    Then:
    struct tree *tree_new(int (*cmp_fn)(const void *d1, const void *d2));

    .... and consider
    typedef int (*tree_cmp)(const void *d1, const_void *d2);

    Some people recommend omitting the parameter names in prototypes, although
    I'm currently leaning against it.

    So I guess:
    typedef int (*tree_cmp)(const void *d1, const_void *d2);
    struct tree {
    tree_cmp cmp;
    struct tree_node *root;
    }

    then:

    struct tree *tree_new(tree_cmp cmp);
    int tree_add(struct tree *t, void *data);
    struct tree_node *tree_root(struct tree *t);
    struct tree_node *tree_lookup(struct tree *t, const void *key);

    .... But you will, of course, note that this means you can't grab a subtree
    and do a lookup. But that can be addressed:

    struct tree_node *tree_node_lookup(struct tree_node *tn, const void *key);

    in which case:
    struct tree_node *tree_lookup(struct tree *t, const void *key) {
    if (!t || !t->root)
    return NULL;
    return tree_node_lookup(t->root, key);
    }

    The other corresponding change, then:

    int tree_add(struct tree *t, const void *data) {
    ... do the node allocation in here, don't make the user
    do it separately.
    }

    -s
    --
    Copyright 2009, 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!
    Seebs, Oct 20, 2009
    #2
    1. Advertising

  3. Mark

    Seebs Guest

    On 2009-10-20, Richard Heathfield <> wrote:
    > In <>, Seebs wrote:
    >
    >> On 2009-10-20, Mark <> wrote:
    >>> /* error codes */
    >>> enum {
    >>> T_ESUCCESS,

    >>
    >> No.
    >>
    >> "EFOO" is widely recognized as indicating an *error*.


    > No. EFOO is reserved for the implementation. Bad Seebs - no biscuit!


    Yeah, too terse, bad me. "T_E*" good, "ESUCCESS" bad, "T_ESUCCESS" still
    bad because people will see "T_E*" and assume it's an [E]rorr.

    >> It seems to me that you might see whether there's enough
    >> standard/common errno values defined that you could just use errno.


    > It is very unlikely that the standard ones will suffice. I could only
    > find three, EDOM, EILSEQ, and ERANGE. The moment you add "common"
    > ones, you make your program less portable.


    True.

    > He's probably going to be using it in the very next mod, so it's not
    > such a big deal. (Yes, okay, he could #if 0 it for now.)


    Agreed.

    > I would take a pointer to a tree structure (which manages the root and
    > any housekeeping information needed by the tree), the data, the size,
    > and an optional void * for side-channel information. (Consequently, I
    > would add an extra void * to the comparison function.)


    Good point about the side-channel. Hmm.

    Actually, that's an interesting question. Possibly the function should
    take:
    * item 1
    * item 2
    * tree
    * aux

    Because the tree might be relevant in some cases to the comparison function.
    (Not that I can think of them, but...)

    >> int tree_add(struct tree *t, const void *data) {
    >> ... do the node allocation in here, don't make the user
    >> do it separately.


    > Um, fair enough to factor it out, but tree_add should call
    > tree_allocate - one should not have to call it separately in advance.
    > Is that what you meant?


    Yes.

    At which point, I honestly don't think the user ever has a reason to
    call tree_allocate, because the only thing you can usefully do with that
    new node, normally, is add it to a tree.

    (Interesting question: Imagine a tree comparison function which, for any
    two items in a tree, tells you whether the first item comes before, or
    after, or is in the same place as the second function. Now reverse it and
    try to sort by it...)

    -s
    --
    Copyright 2009, 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!
    Seebs, Oct 20, 2009
    #3
  4. On 20 Oct, 06:16, Richard Heathfield <> wrote:
    > In <>, Seebs wrote:
    > > On 2009-10-20, Mark <> wrote:


    > >> /* error codes */
    > >> enum {
    > >>     T_ESUCCESS,

    >
    > > No.

    >
    > > "EFOO" is widely recognized as indicating an *error*.


    it's not uncommon (nor very wrong) to lump "success" in with the
    "error" codes.
    Though I must I admit I prefer to call them "return codes"

    <snip>

    > > Some people recommend omitting the parameter names in prototypes,
    > > although I'm currently leaning against it.

    >
    > Tough call, arguments on both sides, and I think the last time I
    > thought about this I was, like you, edging towards including names.


    I tend to omit the names unless putting them in adds useful
    information.
    I try to arrange it so the header file is as informative as possible.

    Retval transmitter_reset (Transmitter*);
    double sum (double[], size_t);
    void clear_element_in_instance_table (int element_id);

    though perhaps the last one is an argument for using a better type.

    <snip>
    Nick Keighley, Oct 20, 2009
    #4
  5. On 20 Oct, 06:08, Seebs <> wrote:
    > On 2009-10-20, Richard Heathfield <> wrote:
    > > In <>, Seebs wrote:


    > >> On 2009-10-20, Mark <> wrote:
    > >>> /* error codes */
    > >>> enum {
    > >>>     T_ESUCCESS,

    >
    > >> No.

    >
    > >> "EFOO" is widely recognized as indicating an *error*.

    >
    > > No. EFOO is reserved for the implementation. Bad Seebs - no biscuit!

    >
    > Yeah, too terse, bad me.  "T_E*" good, "ESUCCESS" bad, "T_ESUCCESS" still
    > bad because people will see "T_E*" and assume it's an [E]rorr.


    only if they were trying *really* hard not to understand

    "There are some ideas so wrong that only a very intelligent person
    could believe in them." -- George Orwell


    I was searching for a Dan Pop quote along these lines but I thought
    George would do in a pinch
    Nick Keighley, Oct 20, 2009
    #5
  6. "Mark" <> writes:

    > I've implemented a very simple and small binary-search tree library as
    > a training exercise. I'm posting it here together with a testing
    > program and expect to receive critics and useful recommendations :)


    Here are a few thoughts:

    I don't like interfaces where the library signals what the caller
    knows already. Your insert function returns T_EBADPTR if and only if
    node == NULL. The caller can test this as easily as the function can.
    In fact, the caller can probably test for it more simply than it can
    test for all the various return values.

    I'd write insert so that it adds data rather a node. I.e. it
    allocates the node when it will do the insert. In your design, the
    caller will probably have to allocate the node, try to insert it and
    then delete it if the insert did not happen.

    A more serious issue: don't delete what you don't allocate! Your
    freenode frees the data but it shouldn't. I may want to add pointers
    to non-'malloc'ed things. Moreover, when I free a node, I may want to
    keep the data.

    You could consider making the whole tree freeing function a call to a
    post-order walk function.

    <snip code>
    --
    Ben.
    Ben Bacarisse, Oct 20, 2009
    #6
  7. On Tue, 20 Oct 2009 08:02:15 +0000, Richard Heathfield wrote:

    > In <>,
    > Nick Keighley wrote:
    >
    >> I was searching for a Dan Pop quote along these lines but I thought
    >> George would do in a pinch

    >
    > You may have been thinking of this [from memory, so might be slightly
    > wrong]:
    >
    > "The expression isn't unclear /at all/, and only an expert could
    > possibly have any doubts about it."


    "The expression isn't unclear *at all* and only an expert could actually
    have doubts about it" - Dan Pop 2001-02-06


    /Nisse
    Nisse Engström, Oct 20, 2009
    #7
  8. "Ben Bacarisse" <> wrote in message
    news:...
    > "Mark" <> writes:
    >
    >> I've implemented a very simple and small binary-search tree library as
    >> a training exercise. I'm posting it here together with a testing
    >> program and expect to receive critics and useful recommendations :)

    >
    > Here are a few thoughts:
    >
    > I don't like interfaces where the library signals what the caller
    > knows already. Your insert function returns T_EBADPTR if and only if
    > node == NULL. The caller can test this as easily as the function can.
    > In fact, the caller can probably test for it more simply than it can
    > test for all the various return values.
    >
    > I'd write insert so that it adds data rather a node. I.e. it
    > allocates the node when it will do the insert. In your design, the
    > caller will probably have to allocate the node, try to insert it and
    > then delete it if the insert did not happen.


    [...]

    IMHO, intrusive data-structures can be more "efficient" than the more
    flexible container based allocation schemes. I basically agree with the
    first point you made. The caller can probably allocate the node more
    efficiently/simply than the end library function call can... Perhaps the
    end-user application has various objects that can be directly linked into a
    tree without the need of any auxiliary nodes:
    ___________________________________________________
    struct tree
    {
    struct tree* left;
    struct tree* right;
    struct tree** plink;
    };


    struct end_user_object
    {
    struct end_user_object* next;
    struct tree tree1;
    char x;
    struct tree tree2;
    double y;
    struct tree tree3;
    };


    struct end_user_object_region
    {
    struct end_user_object buffer[1024];
    struct end_user_object* flist;
    size_t bump;
    };


    static struct end_user_object_region g_region;

    static struct tree* g_trees[3];
    ___________________________________________________




    The application should be able to store an `end_user_object' on three
    separate trees at the same time without making a single function call to
    allocate any memory.




    IMVVHO, a generic container library should work on a free standing
    implementation that does not have access to `malloc' and friends...

    Intrusive data-structures to the rescue!!!

    :^o
    Chris M. Thomasson, Oct 21, 2009
    #8
  9. On 20 Oct, 23:35, Nisse Engström <>
    wrote:
    > On Tue, 20 Oct 2009 08:02:15 +0000, Richard Heathfield wrote:
    > > In <>,
    > > Nick Keighley wrote:


    > >> I was searching for a Dan Pop quote along these lines but I thought
    > >> George would do in a pinch

    >
    > > You may have been thinking of this [from memory, so might be slightly
    > > wrong]:

    >
    > > "The expression isn't unclear /at all/, and only an expert could
    > > possibly have any doubts about it."

    >
    > "The expression isn't unclear *at all* and only an expert could actually
    >  have doubts about it"  - Dan Pop 2001-02-06
    >
    > /Nisse


    excellent!
    Nick Keighley, Oct 21, 2009
    #9
  10. Mark

    Seebs Guest

    On 2009-10-20, Richard Heathfield <> wrote:
    > It should just take item 1, item 2, aux. (Good name, aux - I might
    > steal that!)


    It's hardly original to me, but I've been a big fan ever since I first
    saw it used, because it's as close as I've ever seen to self-documenting
    but still terse for sideband data.

    -s
    --
    Copyright 2009, 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!
    Seebs, Oct 22, 2009
    #10
  11. Mark

    Mark Guest

    Thank you for commentaries. Hope my late response will be noticed. I have a
    few more queries.

    Seebs wrote:
    [skip]
    > I'd probably do these two differently.
    >
    > tree_node *tree_addnode(struct tree_node *root, void *data, int
    > (*cmp_fn))...
    >
    > But even this is error-prone. In this case, I think it makes more
    > sense to distinguish betwen the tree and its nodes.
    >
    > So I recommend:
    >
    > struct tree {
    > int (*cmp_fn)(const void *d1, const void *d2);
    > struct tree_node *root;
    > }


    Richard Heathfield wrote:
    > I would take a pointer to a tree structure (which manages the root and
    > any housekeeping information needed by the tree), the data, the size,
    > and an optional void * for side-channel information. (Consequently, I
    > would add an extra void * to the comparison function.)


    So as I see it, both Seebs and Richard recommend to represent the
    abstraction of the BST in two structures - one for the tree's node and the
    other one is for the tree itself. What is the profit of doing this? When is
    it good to exploit such method and for what data structures?

    PS. Now I remember I have seen such technique somewhere in a circular list
    implementation.

    --
    Mark
    Mark, Oct 23, 2009
    #11
  12. Mark

    Seebs Guest

    On 2009-10-23, Mark <> wrote:
    > So as I see it, both Seebs and Richard recommend to represent the
    > abstraction of the BST in two structures - one for the tree's node and the
    > other one is for the tree itself. What is the profit of doing this? When is
    > it good to exploit such method and for what data structures?


    I usually do something like that when I feel that the container is somehow
    genuinely distinct from its "top" member. The tree seems to be the right
    place to, for instance, stash a comparator function -- since presumably you
    always want the same one for the tree (and some trees need a comparator to
    decide where a new item goes). It is not obvious to me that individual
    nodes are, in real use cases, likely to make sense to treat the same way
    you treat the tree as a whole.

    By contrast, I wouldn't usually do this for a singly-linked or doubly-linked
    list...

    > PS. Now I remember I have seen such technique somewhere in a circular list
    > implementation.


    That can make sense too.

    So why for a doubly-linked list, but not a circular list? Because for a
    doubly-linked list, you can always find the ends by iterating, but there
    isn't necessarily an end for a circular list.

    -s
    --
    Copyright 2009, 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!
    Seebs, Oct 23, 2009
    #12
  13. Mark

    user923005 Guest

    On Oct 22, 8:22 pm, Seebs <> wrote:
    > On 2009-10-23, Mark <> wrote:
    >
    > > So as I see it, both Seebs and Richard recommend to represent the
    > > abstraction of the BST in two structures - one for the tree's node and the
    > > other one is for the tree itself. What is the profit of doing this? When is
    > > it good to exploit such method and for what data structures?

    >
    > I usually do something like that when I feel that the container is somehow
    > genuinely distinct from its "top" member.  The tree seems to be the right
    > place to, for instance, stash a comparator function -- since presumably you
    > always want the same one for the tree (and some trees need a comparator to
    > decide where a new item goes).  It is not obvious to me that individual
    > nodes are, in real use cases, likely to make sense to treat the same way
    > you treat the tree as a whole.
    >
    > By contrast, I wouldn't usually do this for a singly-linked or doubly-linked
    > list...
    >
    > > PS. Now I remember I have seen such technique somewhere in a circular list
    > > implementation.

    >
    > That can make sense too.
    >
    > So why for a doubly-linked list, but not a circular list?  Because for a
    > doubly-linked list, you can always find the ends by iterating, but there
    > isn't necessarily an end for a circular list.


    Plus, the end of a ring buffer often rolls forward. So even after you
    found a start or an end, chances are it has moved shortly thereafter.
    Plus, ring buffers are either empty, partly full, or full. The
    elements of the ring buffer have no idea which state the ring buffer
    as a whole is in.
    A ring buffer needs a secondary observer thing that understands the
    ring state.
    user923005, Oct 23, 2009
    #13
  14. Mark

    user923005 Guest

    On Oct 23, 12:32 am, Richard Heathfield <> wrote:
    > In
    > <>,
    >
    > user923005 wrote:
    >
    > <snip>
    >
    > > Plus, ring buffers are either empty, partly full, or full.

    >
    > Not necessarily! :)  They can be dynamic, expanding as demand
    > requires. (Mine tend to do that.)
    >
    > <snip>


    Do you mean to tell me that your ring buffers are neither empty, full,
    nor partly full?

    Now that's an interesting data structure.
    user923005, Oct 23, 2009
    #14
  15. user923005 <> writes:
    > On Oct 23, 12:32 am, Richard Heathfield <> wrote:
    >> In
    >> <>,
    >>
    >> user923005 wrote:
    >>
    >> <snip>
    >>
    >> > Plus, ring buffers are either empty, partly full, or full.

    >>
    >> Not necessarily! :)  They can be dynamic, expanding as demand
    >> requires. (Mine tend to do that.)
    >>
    >> <snip>

    >
    > Do you mean to tell me that your ring buffers are neither empty, full,
    > nor partly full?
    >
    > Now that's an interesting data structure.


    If it can expand as demand requires, it needn't ever be full.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Oct 23, 2009
    #15
  16. Mark

    James Kuyper Guest

    Keith Thompson wrote:
    > user923005 <> writes:
    >> On Oct 23, 12:32 am, Richard Heathfield <> wrote:
    >>> In
    >>> <>,
    >>>
    >>> user923005 wrote:

    ....
    >>>> Plus, ring buffers are either empty, partly full, or full.
    >>> Not necessarily! :) They can be dynamic, expanding as demand
    >>> requires. (Mine tend to do that.)
    >>>
    >>> <snip>

    >> Do you mean to tell me that your ring buffers are neither empty, full,
    >> nor partly full?
    >>
    >> Now that's an interesting data structure.

    >
    > If it can expand as demand requires, it needn't ever be full.


    In that case, it should be either empty or partly full. To claim the
    existence of a situation where none of three options listed of
    user923005 apply you'll have to explain a lot more than just that.
    James Kuyper, Oct 23, 2009
    #16
  17. Mark

    user923005 Guest

    On Oct 23, 7:31 am, Keith Thompson <> wrote:
    > user923005 <> writes:
    > > On Oct 23, 12:32 am, Richard Heathfield <> wrote:
    > >> In
    > >> <>,

    >
    > >> user923005 wrote:

    >
    > >> <snip>

    >
    > >> > Plus, ring buffers are either empty, partly full, or full.

    >
    > >> Not necessarily! :)  They can be dynamic, expanding as demand
    > >> requires. (Mine tend to do that.)

    >
    > >> <snip>

    >
    > > Do you mean to tell me that your ring buffers are neither empty, full,
    > > nor partly full?

    >
    > > Now that's an interesting data structure.

    >
    > If it can expand as demand requires, it needn't ever be full.


    In that case, I want one. My data structures always fill up.

    I do think I will give expandable ring buffers a bit more thought.

    I have lots of ring buffers in my code base, but they tend to be fixed
    size (determined by some parameter).

    A little thought about ring buffers that size themselves might result
    in better code.
    user923005, Oct 23, 2009
    #17
  18. Mark

    user923005 Guest

    On Oct 23, 9:16 pm, Richard Heathfield <> wrote:
    > In <>,
    >
    > user923005 wrote:
    >
    > <snip>
    >
    > > A little thought about ring buffers that size themselves might
    > > result in better code.

    >
    > Don't you read the books you help write? :)


    It's not the reading part that stumbles me. It's the thinking.

    My data structures have to run by themselves in a darkened room, with
    evil men throwing their worst at them (I write database software). So
    I should expect the worst possible inputs to arrive billions at a
    time. What will my data structure do? I need to consider that the
    same evil perpetrators will be pounding the stuffings out of other
    data structures on 100 other threads and I am simply not allowed to
    run out of resources or fail to bring the calculation to completion in
    a timely manner.

    So (for me at least) these things are never as simple as they might
    seem on the surface.
    user923005, Oct 24, 2009
    #18
  19. On Tue, 20 Oct 2009 00:02:14 -0700 (PDT), Nick Keighley
    <> wrote:

    > On 20 Oct, 06:16, Richard Heathfield <> wrote:
    > > In <>, Seebs wrote:
    > > > On 2009-10-20, Mark <> wrote:

    >
    > > >> /* error codes */
    > > >> enum {
    > > >>     T_ESUCCESS,

    > >
    > > > No.

    > >
    > > > "EFOO" is widely recognized as indicating an *error*.

    >
    > it's not uncommon (nor very wrong) to lump "success" in with the
    > "error" codes.


    Especially with value 0, as here. Although I would write explicitly
    the formally-redundant = 0 .
    David Thompson, Nov 2, 2009
    #19
    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. Andrew Edwards

    BST & recursion

    Andrew Edwards, Jul 30, 2003, in forum: C++
    Replies:
    12
    Views:
    762
    Karl Heinz Buchegger
    Aug 4, 2003
  2. Rupert harrison

    BST

    Rupert harrison, Sep 15, 2003, in forum: C++
    Replies:
    2
    Views:
    546
    Karl Heinz Buchegger
    Sep 15, 2003
  3. Ridimz

    BST: remove less than

    Ridimz, Oct 4, 2003, in forum: C++
    Replies:
    8
    Views:
    523
    Josh Sebastian
    Oct 7, 2003
  4. Ice
    Replies:
    4
    Views:
    4,998
  5. puzzlecracker

    LL TO BST

    puzzlecracker, Jan 19, 2005, in forum: C++
    Replies:
    2
    Views:
    388
    Joseph Turian
    Jan 19, 2005
Loading...

Share This Page