review of the "container library", part 1/?

Discussion in 'C Programming' started by Alan Curry, Mar 1, 2011.

  1. Alan Curry

    Alan Curry Guest

    To make up for posting in one of those threads of mass stupidity, here's
    something less off-topic.

    I downloaded the library from http://code.google.com/p/ccl/ and here's what
    I've noticed so far. This part is mostly about superficial packaging issues.
    The meaty stuff is harder to comment on since I'd have to read the
    documentation, and there's over 200 pages of that.

    unzipping splattered all over current directory. This makes a bad first
    impression. Can I apply tarball etiquette to zip files? Well, I just did.

    There was a mention of ccl.tex but I don't see it anywhere.

    The makefile actually worked, and is readable, instead of being a maze of
    $(shell stuff) and includes and other non-POSIX features. That's rare these
    days. However, when I tried it with a pmake (derived from NetBSD make) it
    failed. The reason: line-continuing backslashes are not immediately followed
    by newline. They have ^M's after them. "UNIX" makefile shouldn't have MS-DOS
    line endings.

    The ^M's in the C source files aren't fun to look at either.

    The build rule for dotest should use test.o, not test.c. The way you have it,
    test.c gets compiled with the implicit .c.o rule since test.o is one of OBJS,
    then test.o never gets used, because the link line of dotest compiles it
    again (without your CFLAGS!). Also, having test.o in OBJS means it's included
    in the .a which it probably shouldn't be. To fix all that, just remove test.o
    from OBJS and change the 2 instances of test.c in the dotest rule to test.o

    Header file dependencies are not expressed in the Makefile, so nothing gets
    rebuilt if a header file is modified. That's bad.

    A few warnings were issued with gcc 4.4.5 and the options in the Makefile.
    I'll go through them all:

    In test.c there are a couple of %lu printf's with size_t args - gcc warns
    about this as a potential mismatch. It should be %zu (clean, C99) or cast to
    unsigned long (icky, C89)

    The ULL suffixed integer constants in bitstrings.c give warnings because
    -pedantic without -std=c99 is asking for C89 pedanticness, which disallows
    long long.

    Dead code here: bitstrings.c:503: warning: 'AddRange' defined but not used

    More dead code here: searchtree.c:621: warning: 'hide' defined but not used

    And here's one that's a serious behavioral issue: searchtree.c in the
    definition of struct tagBinarySearchTreeNode has "char factor;" which is used
    to hold the values LEFT, BALANCED, and RIGHT defined as 1, 0, and -1. On my
    platform, char is unsigned so assigning -1 to a char makes it 255, and then
    comparing it to -1 is false. So all the ==RIGHT tests are useless. gcc didn't
    warn about those because you didn't include -W (-Wextra), but luckily it
    warned about the switch() statements with case RIGHT.

    Your test program segfaults because it gets severely confused by that
    searchtree factor bug. After changing "char factor;" to "signed char factor;"
    it didn't segfault. I can't interpret the test output so I won't say it
    definitely passed all the tests, but at least it returned a 0 exit code.

    One more formatting thing: it looks like you use tabstop=4. Lots of things
    look wrong with tabstop=8, the default in unix land. If you used tabs
    consistently this wouldn't be a problem but there are lots of places where a
    line indented with a tab is followed by a line indented with 4 spaces, so
    they don't line up for anyone who hasn't figured out that you wanted the
    files to be viewed with tabstop=4.

    Adding my own warning options, I get a lot more warnings. The most
    interesting ones led me to:

    casting away const in test.c:testDictionary on this line:
    pi = (int *)iDictionary.GetElement(d,(const unsigned char *)"Two");
    where GetElement returns const void *. This cast is not doing anything but
    throwing away the const. This is occasionally justifiable with complex
    interactions where the correct constness is situation-dependent, but this
    isn't one of those cases. Nothing attempts to modify *pi so there are no
    drawbacks to making pi a "const int *", and one big advantage: the cast can
    go away. There are lots of other bad casts losing const for no reason; this
    is just the one I picked as a representative of the group.

    A lot of casts seem to be present because there are strings being passed
    around as unsigned char * and then they get converted back to char * for use
    with strcmp and such. I'd try to get rid of the "unsigned" stuff except where
    it really matters. A function that wants to operate on a string of unsigned
    chars internally should still have its arguments declared as plain "char *"
    if that makes the caller's job easier.

    Then there's the general lack of const in the proper places. A function
    called Strcmp that wraps strcmp should really be able to take
    pointer-to-const parameters. Omitting the const is just screwing up the
    interface.

    In buffer.c:CBClear, gcc thinks the variable p "may be used uninitialized"
    and without studying too deeply, I can't disagree. It looks like the
    memset(p, ...) is reachable with p uninitialized in the case where
    cb->DestructorFn is false.

    The big picture: count me among those not convinced that "container" is a
    useful abstraction. Things indexed by integers and things indexed by strings
    don't have that much in common.

    part 2, later, if I have time to read the documentation.

    --
    Alan Curry
     
    Alan Curry, Mar 1, 2011
    #1
    1. Advertising

  2. Alan Curry

    jacob navia Guest

    Hi Alan.

    THANKS a LOT for your excellent review. I am at work now and can't
    answer all your points but I will come back to this this evening.

    jacob
     
    jacob navia, Mar 1, 2011
    #2
    1. Advertising

  3. Alan Curry

    Tom St Denis Guest

    On Feb 28, 8:42 pm, (Alan Curry) wrote:
    > To make up for posting in one of those threads of mass stupidity, here's
    > something less off-topic.
    >
    > I downloaded the library fromhttp://code.google.com/p/ccl/and here's what
    > I've noticed so far. This part is mostly about superficial packaging issues.
    > The meaty stuff is harder to comment on since I'd have to read the
    > documentation, and there's over 200 pages of that.
    >
    > unzipping splattered all over current directory. This makes a bad first
    > impression. Can I apply tarball etiquette to zip files? Well, I just did.
    >
    > There was a mention of ccl.tex but I don't see it anywhere.
    >
    > The makefile actually worked, and is readable, instead of being a maze of
    > $(shell stuff) and includes and other non-POSIX features. That's rare these
    > days. However, when I tried it with a pmake (derived from NetBSD make) it
    > failed. The reason: line-continuing backslashes are not immediately followed
    > by newline. They have ^M's after them. "UNIX" makefile shouldn't have MS-DOS
    > line endings.
    >
    > The ^M's in the C source files aren't fun to look at either.


    Unzip with -a.

    Tom
     
    Tom St Denis, Mar 1, 2011
    #3
  4. Alan Curry

    jacob navia Guest

    Le 01/03/11 02:42, Alan Curry a écrit :
    > To make up for posting in one of those threads of mass stupidity, here's
    > something less off-topic.
    >


    Thanks for this. Great help.

    > I downloaded the library from http://code.google.com/p/ccl/ and here's what
    > I've noticed so far. This part is mostly about superficial packaging issues.
    > The meaty stuff is harder to comment on since I'd have to read the
    > documentation, and there's over 200 pages of that.
    >
    > unzipping splattered all over current directory. This makes a bad first
    > impression. Can I apply tarball etiquette to zip files? Well, I just did.
    >


    Problem is that zip will include the .svn directory when using
    the recursive option. If I go to the upper directory and issue:
    zip -9 -r container-lib-src.zip ccl
    it will put all .svn stuff intoi the zip. And I did not find any way
    that works to exclude that (no --exclude "ccl/.svn" does NOT work
    for unknown reasons.

    > There was a mention of ccl.tex but I don't see it anywhere.
    >


    Yes, I have added images to the doc and alot of stuff so it would
    require tex and a lot of other non essential stuff, so I dropped tex
    doc sources and ship only pdfs

    > The makefile actually worked, and is readable, instead of being a maze of
    > $(shell stuff) and includes and other non-POSIX features. That's rare these
    > days. However, when I tried it with a pmake (derived from NetBSD make) it
    > failed. The reason: line-continuing backslashes are not immediately followed
    > by newline. They have ^M's after them. "UNIX" makefile shouldn't have MS-DOS
    > line endings.
    >


    OK. Eliminated that

    > The ^M's in the C source files aren't fun to look at either.
    >


    Please use the -a option when unzipping (unzip -a ...) This will
    eliminate the \r in Unix and ADD them under windows

    > The build rule for dotest should use test.o, not test.c. The way you have it,
    > test.c gets compiled with the implicit .c.o rule since test.o is one of OBJS,
    > then test.o never gets used, because the link line of dotest compiles it
    > again (without your CFLAGS!). Also, having test.o in OBJS means it's included
    > in the .a which it probably shouldn't be. To fix all that, just remove test.o
    > from OBJS and change the 2 instances of test.c in the dotest rule to test.o
    >


    Correct. Modified that.

    > Header file dependencies are not expressed in the Makefile, so nothing gets
    > rebuilt if a header file is modified. That's bad.
    >
    > A few warnings were issued with gcc 4.4.5 and the options in the Makefile.
    > I'll go through them all:
    >
    > In test.c there are a couple of %lu printf's with size_t args - gcc warns
    > about this as a potential mismatch. It should be %zu (clean, C99) or cast to
    > unsigned long (icky, C89)
    >
    > The ULL suffixed integer constants in bitstrings.c give warnings because
    > -pedantic without -std=c99 is asking for C89 pedanticness, which disallows
    > long long.
    >


    I did not find a way out. I wanted to avoid C99 but I think it will be
    necessary.

    > Dead code here: bitstrings.c:503: warning: 'AddRange' defined but not used
    >


    Yes, they are unfinished.

    > More dead code here: searchtree.c:621: warning: 'hide' defined but not used
    >

    Yes, this just sets a flag and marks the node as "hidden" instead of
    erasing it... I am not sure if this should be congtinued. I will ifdef
    it out

    > And here's one that's a serious behavioral issue: searchtree.c in the
    > definition of struct tagBinarySearchTreeNode has "char factor;" which is used
    > to hold the values LEFT, BALANCED, and RIGHT defined as 1, 0, and -1. On my
    > platform, char is unsigned so assigning -1 to a char makes it 255, and then
    > comparing it to -1 is false. So all the ==RIGHT tests are useless. gcc didn't
    > warn about those because you didn't include -W (-Wextra), but luckily it
    > warned about the switch() statements with case RIGHT.
    >


    Well, thanks a lot for finding this bug.I just didn't thought about
    having plain char as unsigned.


    > Your test program segfaults because it gets severely confused by that
    > searchtree factor bug. After changing "char factor;" to "signed char factor;"
    > it didn't segfault. I can't interpret the test output so I won't say it
    > definitely passed all the tests, but at least it returned a 0 exit code.
    >


    OK.

    > One more formatting thing: it looks like you use tabstop=4. Lots of things
    > look wrong with tabstop=8, the default in unix land. If you used tabs
    > consistently this wouldn't be a problem but there are lots of places where a
    > line indented with a tab is followed by a line indented with 4 spaces, so
    > they don't line up for anyone who hasn't figured out that you wanted the
    > files to be viewed with tabstop=4.
    >
    > Adding my own warning options, I get a lot more warnings. The most
    > interesting ones led me to:
    >
    > casting away const in test.c:testDictionary on this line:
    > pi = (int *)iDictionary.GetElement(d,(const unsigned char *)"Two");
    > where GetElement returns const void *. This cast is not doing anything but
    > throwing away the const. This is occasionally justifiable with complex
    > interactions where the correct constness is situation-dependent, but this
    > isn't one of those cases. Nothing attempts to modify *pi so there are no
    > drawbacks to making pi a "const int *", and one big advantage: the cast can
    > go away. There are lots of other bad casts losing const for no reason; this
    > is just the one I picked as a representative of the group.
    >


    Yes, you are right, "const correctness" is CONSTantly getting me mad...

    > A lot of casts seem to be present because there are strings being passed
    > around as unsigned char * and then they get converted back to char * for use
    > with strcmp and such. I'd try to get rid of the "unsigned" stuff except where
    > it really matters. A function that wants to operate on a string of unsigned
    > chars internally should still have its arguments declared as plain "char *"
    > if that makes the caller's job easier.
    >


    I started a discussion here some months ago about this problem.

    Apparently there is no solution. strcmp requires char * but I want to
    have unsigned chars in all CHARACTERS since I do NOT want any sign
    problems with them.


    > Then there's the general lack of const in the proper places. A function
    > called Strcmp that wraps strcmp should really be able to take
    > pointer-to-const parameters. Omitting the const is just screwing up the
    > interface.


    Yes, you are right.
    >
    > In buffer.c:CBClear, gcc thinks the variable p "may be used uninitialized"
    > and without studying too deeply, I can't disagree. It looks like the
    > memset(p, ...) is reachable with p uninitialized in the case where
    > cb->DestructorFn is false.
    >


    RIGHT!

    I added destructor support and included the initialization of p
    within the if () . That was a huge mistake. Thanks

    > The big picture: count me among those not convinced that "container" is a
    > useful abstraction. Things indexed by integers and things indexed by strings
    > don't have that much in common.
    >


    That is why there are two types of containers: sequantial and
    associative.

    What do they have in common?

    Size (# of elements they store)
    Flags (properties like read-,ly, etc)

    Methods like:

    contains (searches one element)
    clear (removes all element but not the container)
    erase (removes one element)
    Finalize (destroy)
    Sizeof (bytes used)

    > part 2, later, if I have time to read the documentation.
    >


    Again: Thanks for your interest.

    jacob
     
    jacob navia, Mar 1, 2011
    #4
  5. Alan Curry

    James Waldby Guest

    On Tue, 01 Mar 2011 20:51:37 +0100, jacob navia wrote:
    > Le 01/03/11 02:42, Alan Curry a écrit :

    ....
    >> I downloaded the library from http://code.google.com/p/ccl/ and here's
    >> what I've noticed so far. [...]
    >> unzipping splattered all over current directory. This makes a bad first
    >> impression. Can I apply tarball etiquette to zip files? [...]
    >>

    > Problem is that zip will include the .svn directory when using the
    > recursive option. If I go to the upper directory and issue:
    > zip -9 -r container-lib-src.zip ccl
    > it will put all .svn stuff into the zip. And I did not find any way
    > that works to exclude that (no --exclude "ccl/.svn" does NOT work for
    > unknown reasons.

    ....
    I don't know what the exclusion problem is, and imagine the lack of
    detail in your "does not work" sentence will keep others from knowing
    as well. However, you might try zip ... -x '.svn/\*'

    In any case, you can get whatever directory structure layout you
    want in a zip file by making a temporary clean copy of the structure
    and zipping that. You could write a shell script that creates the
    directory structure with no files, then in the structure adds links
    to desired files, then zips the structure, then deletes it. This
    would be on topic in comp.unix.shell newsgroup, rather than c.l.c.

    >> One more formatting thing: it looks like you use tabstop=4. Lots of
    >> things look wrong with tabstop=8, the default in unix land. If you used
    >> tabs consistently this wouldn't be a problem but there are lots of
    >> places where a line indented with a tab is followed by a line indented
    >> with 4 spaces, so they don't line up for anyone who hasn't figured out
    >> that you wanted the files to be viewed with tabstop=4.

    ....

    Consider running the code through indent -ut with other options
    set so that program layout doesn't change much except for conversion
    of some spaces to tabs.

    --
    jiw
     
    James Waldby, Mar 1, 2011
    #5
  6. Alan Curry

    Jorgen Grahn Guest

    On Tue, 2011-03-01, James Waldby wrote:
    > On Tue, 01 Mar 2011 20:51:37 +0100, jacob navia wrote:
    >> Le 01/03/11 02:42, Alan Curry a écrit :

    > ...
    >>> I downloaded the library from http://code.google.com/p/ccl/ and here's
    >>> what I've noticed so far. [...]
    >>> unzipping splattered all over current directory. This makes a bad first
    >>> impression. Can I apply tarball etiquette to zip files? [...]


    Yes, a /very/ bad impression.

    >> Problem is that zip will include the .svn directory when using the
    >> recursive option. If I go to the upper directory and issue:
    >> zip -9 -r container-lib-src.zip ccl
    >> it will put all .svn stuff into the zip. [...]

    ....
    > In any case, you can get whatever directory structure layout you
    > want in a zip file by making a temporary clean copy of the structure
    > and zipping that. You could write a shell script that creates the
    > directory structure with no files, then in the structure adds links
    > to desired files, then zips the structure, then deletes it. This
    > would be on topic in comp.unix.shell newsgroup, rather than c.l.c.


    It's offtopic, but I'll mention it anyway since it took me a few years
    to discover it myself: CVS has an 'export' command which is much like
    a checkout but creates a clean directory tree without the CVS/
    subdirectories and control files. I'm pretty sure SVN has an
    equivalent. That's what he should try first!

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Mar 1, 2011
    #6
  7. Alan Curry

    Ian Collins Guest

    On 03/ 2/11 08:51 AM, jacob navia wrote:
    > Le 01/03/11 02:42, Alan Curry a écrit :
    >> To make up for posting in one of those threads of mass stupidity, here's
    >> something less off-topic.
    >>

    >
    > Thanks for this. Great help.
    >
    >> I downloaded the library from http://code.google.com/p/ccl/ and here's
    >> what
    >> I've noticed so far. This part is mostly about superficial packaging
    >> issues.
    >> The meaty stuff is harder to comment on since I'd have to read the
    >> documentation, and there's over 200 pages of that.
    >>
    >> unzipping splattered all over current directory. This makes a bad first
    >> impression. Can I apply tarball etiquette to zip files? Well, I just did.
    >>

    >
    > Problem is that zip will include the .svn directory when using
    > the recursive option. If I go to the upper directory and issue:
    > zip -9 -r container-lib-src.zip ccl
    > it will put all .svn stuff intoi the zip. And I did not find any way
    > that works to exclude that (no --exclude "ccl/.svn" does NOT work
    > for unknown reasons.


    You could setup anonymous read access to your SVN repository, which is a
    better long term option.

    --
    Ian Collins
     
    Ian Collins, Mar 1, 2011
    #7
  8. Alan Curry

    Alan Curry Guest

    In article <ikjio6$b0l$>,
    jacob navia <> wrote:
    >Le 01/03/11 02:42, Alan Curry a écrit :
    >
    >> There was a mention of ccl.tex but I don't see it anywhere.
    >>

    >
    >Yes, I have added images to the doc and alot of stuff so it would
    >require tex and a lot of other non essential stuff, so I dropped tex
    >doc sources and ship only pdfs


    Since I didn't have an editable documentation format, I couldn't make changes
    as I found errors. So you won't be getting a diff, just a list of complaints.

    >
    >> The ^M's in the C source files aren't fun to look at either.
    >>

    >
    >Please use the -a option when unzipping (unzip -a ...) This will
    >eliminate the \r in Unix and ADD them under windows


    It's been so long since I saw a zip file (at least one with text files in
    it). I used to know about that option but forgot it.

    >
    >> And here's one that's a serious behavioral issue: searchtree.c in the
    >> definition of struct tagBinarySearchTreeNode has "char factor;" which is used
    >> to hold the values LEFT, BALANCED, and RIGHT defined as 1, 0, and -1. On my
    >> platform, char is unsigned so assigning -1 to a char makes it 255, and then
    >> comparing it to -1 is false. So all the ==RIGHT tests are useless. gcc didn't
    >> warn about those because you didn't include -W (-Wextra), but luckily it
    >> warned about the switch() statements with case RIGHT.
    >>

    >
    >Well, thanks a lot for finding this bug.I just didn't thought about
    >having plain char as unsigned.


    If you run your tests once with gcc -fsigned-char and once with
    gcc -funsigned-char, you will have both possibilities covered. The same
    segfault I saw will happen on any architecture with gcc -funsigned-char

    >
    >> A lot of casts seem to be present because there are strings being passed
    >> around as unsigned char * and then they get converted back to char * for use
    >> with strcmp and such. I'd try to get rid of the "unsigned" stuff except where
    >> it really matters. A function that wants to operate on a string of unsigned
    >> chars internally should still have its arguments declared as plain "char *"
    >> if that makes the caller's job easier.
    >>

    >
    >I started a discussion here some months ago about this problem.
    >
    >Apparently there is no solution. strcmp requires char * but I want to
    >have unsigned chars in all CHARACTERS since I do NOT want any sign
    >problems with them.


    Because of your unique idea that plain char is a "problem", your interfaces
    need a lot of tedious casts.

    --
    Alan Curry
     
    Alan Curry, Mar 2, 2011
    #8
  9. Alan Curry

    Alan Curry Guest

    review of the "container library", part 2/?

    For this post, I've not only built the library and run the test program, but
    also read the documentation! So mostly I'm reporting documentation bugs.

    In the example code for iVector.Erase, There's a "|n" typo, where "\n" should
    be.

    The iDictionary.Erase example code looks like an unmodified cut and paste of
    the iVector.Erase example.

    There are some odd features that I can only assume are the result of syntax
    errors in the source: The header for the iDlist.PushBack section is messed up,
    and iHashTable.Finalize looks similar. (Both have title in a small font
    preceded by "Synopsis" instead of a big font with a dividing line)

    Under "7.1.2 Lists", there's an "\item" in the middle of a struct definition.

    Somehow the charset has gone wrong, causing upside down question marks to
    appear in the iVector.GetRange and iHashTable.Add sections.

    Under iVector.AddRange, the prototype has "Add" instead of the correct name.
    iDeque.Front likewise has the wrong name (PeekFront) in the prototype.

    Now for a serious functional issue the came to mind while reading about
    iDictionary: the iterator functions (e.g. GetNext) don't give access to the
    key, just the value. That's a deficient interface compared to glib's hash
    tables for example.

    For part 3, I might even try to *use* the library...
    --
    Alan Curry
     
    Alan Curry, Mar 2, 2011
    #9
  10. In article <>,
    Jorgen Grahn <> wrote:
    >On Tue, 2011-03-01, James Waldby wrote:
    >> On Tue, 01 Mar 2011 20:51:37 +0100, jacob navia wrote:
    >>> Le 01/03/11 02:42, Alan Curry a écrit :

    >> ...
    >>>> I downloaded the library from http://code.google.com/p/ccl/ and here's
    >>>> what I've noticed so far. [...]
    >>>> unzipping splattered all over current directory. This makes a bad first
    >>>> impression. Can I apply tarball etiquette to zip files? [...]

    >
    >Yes, a /very/ bad impression.


    Yes, if you are 12 years old.

    Over the years, I've downloaded countless ZIPs, TARs, and g*d knows how
    many other archive format files. One thing I learned early is that
    sometimes there is a directory structure in the file, sometimes there
    isn't. Therefore, you should always look inside first before doing the
    "unzip" (or whatever). If you see inside the file that everything is at
    the top level, then you should of course, create an empty directory and
    do the unzipping there. Simple stuff, once you get used to it.

    To just blindly do the unzip without looking first is, to put it
    charitably, stupid. But it *is* typical CLC mindset at work...

    I believe the psychologists call this mindset "passive aggressive".

    --
    But the Bush apologists hope that you won't remember all that. And they
    also have a theory, which I've been hearing more and more - namely,
    that President Obama, though not yet in office or even elected, caused the
    2008 slump. You see, people were worried in advance about his future
    policies, and that's what caused the economy to tank. Seriously.

    (Paul Krugman - Addicted to Bush)
     
    Kenny McCormack, Mar 2, 2011
    #10
  11. Alan Curry

    Jorgen Grahn Guest

    On Wed, 2011-03-02, Kenny McCormack wrote:
    > In article <>,
    > Jorgen Grahn <> wrote:
    >>On Tue, 2011-03-01, James Waldby wrote:
    >>> On Tue, 01 Mar 2011 20:51:37 +0100, jacob navia wrote:
    >>>> Le 01/03/11 02:42, Alan Curry a écrit :
    >>> ...
    >>>>> I downloaded the library from http://code.google.com/p/ccl/ and here's
    >>>>> what I've noticed so far. [...]
    >>>>> unzipping splattered all over current directory. This makes a bad first
    >>>>> impression. Can I apply tarball etiquette to zip files? [...]

    >>
    >>Yes, a /very/ bad impression.

    >
    > Yes, if you are 12 years old.


    I don't see a reason for going ad hominem here. I snipped the further
    attacks below.

    > Over the years, I've downloaded countless ZIPs, TARs, and g*d knows how
    > many other archive format files. One thing I learned early is that
    > sometimes there is a directory structure in the file, sometimes there
    > isn't. Therefore, you should always look inside first before doing the
    > "unzip" (or whatever). If you see inside the file that everything is at
    > the top level, then you should of course, create an empty directory and
    > do the unzipping there. Simple stuff, once you get used to it.


    Perhaps customs are different on Windows, but with source tarballs on
    Unix no top-level directory is a sure sign that the author is a newbie
    and that other things are lacking as well.

    So of course I check before unpacking if I don't trust the source, but
    if I have to provide the directory myself ... that's not promising.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Mar 4, 2011
    #11
  12. Alan Curry

    Noob Guest

    Jorgen Grahn wrote:

    > It's off-topic, but I'll mention it anyway since it took me a few years
    > to discover it myself: CVS has an 'export' command which is much like
    > a checkout but creates a clean directory tree without the CVS/
    > sub-directories and control files. I'm pretty sure SVN has an
    > equivalent. That's what he should try first!


    http://svnbook.red-bean.com/en/1.5/svn.ref.svn.c.export.html
     
    Noob, Mar 9, 2011
    #12
  13. Alan Curry

    Noob Guest

    jacob navia wrote:

    > Problem is that zip will include the .svn directory when using
    > the recursive option. If I go to the upper directory and issue:
    > zip -9 -r container-lib-src.zip ccl
    > it will put all .svn stuff intoi the zip. And I did not find any way
    > that works to exclude that (no --exclude "ccl/.svn" does NOT work
    > for unknown reasons.


    svn export — Export a clean directory tree.
    http://svnbook.red-bean.com/en/1.5/svn.ref.svn.c.export.html

    Then compress the clean directory tree.
     
    Noob, Mar 9, 2011
    #13
  14. Alan Curry

    Alan Curry Guest

    review of the "container library", part 3/?

    I read through the test suite and it's obviously far from complete, but the
    parts that are there mostly behaved well. The exception is the bitstring
    implementation, which has lots of problems.

    TestBitstring fails the iBitString.Equal(b,c) test. It seems that nothing
    ever set c->count. iBitString.Copy should probably do that.

    iBitString.InsertAt loses a 1 bit because ShiftLeftByOne didn't do carry
    propagation correctly. Each byte gets its own high bit copied into its low
    bit.

    iBitString.GetRange is baffling. Did this test actually produce a reasonable
    result? The implementation looks wrong in several ways. In fact I think the
    BYTES_FROM_BITS macro and everything that depends on it is buggy. It seems to
    be trying to answer 2 different questions (how many bytes are needed to hold
    n bits, and what is the byte index of the byte containing the nth bit) and
    getting both of them wrong most of the time.

    Both of those questions are related to n/CHAR_BIT but the first needs to be
    rounded up, so it should be (n+(CHAR_BIT-1))/CHAR_BIT

    --
    Alan Curry
     
    Alan Curry, Mar 9, 2011
    #14
  15. Alan Curry

    jacob navia Guest

    Re: review of the "container library", part 3/?

    Le 09/03/11 23:05, Alan Curry a écrit :
    > I read through the test suite and it's obviously far from complete, but the
    > parts that are there mostly behaved well. The exception is the bitstring
    > implementation, which has lots of problems.
    >
    > TestBitstring fails the iBitString.Equal(b,c) test. It seems that nothing
    > ever set c->count. iBitString.Copy should probably do that.
    >
    > iBitString.InsertAt loses a 1 bit because ShiftLeftByOne didn't do carry
    > propagation correctly. Each byte gets its own high bit copied into its low
    > bit.
    >
    > iBitString.GetRange is baffling. Did this test actually produce a reasonable
    > result? The implementation looks wrong in several ways. In fact I think the
    > BYTES_FROM_BITS macro and everything that depends on it is buggy. It seems to
    > be trying to answer 2 different questions (how many bytes are needed to hold
    > n bits, and what is the byte index of the byte containing the nth bit) and
    > getting both of them wrong most of the time.
    >
    > Both of those questions are related to n/CHAR_BIT but the first needs to be
    > rounded up, so it should be (n+(CHAR_BIT-1))/CHAR_BIT
    >


    Thanks, I agree that GetRange was a mess. Here is a corrected version
    that I uploaded today.

    static BitString *GetRange(BitString *bs,size_t start,size_t end)
    {
    size_t t,len;
    BitString *result;
    size_t startbyte,endbyte,shiftamount,bytesToCopy,idx;

    if (bs == NULL) {
    NullPtrError("GetRange");
    return NULL;
    }
    if (start > end) {
    t = start;
    start = end;
    end = t;
    }
    if (end >= bs->count)
    end = bs->count;
    if (end != start)
    len = end-start;
    else len = 0;
    result = Create(len);
    if (len == 0)
    return result;
    startbyte = start/CHAR_BIT;
    endbyte = end/CHAR_BIT;
    shiftamount = start&(CHAR_BIT-1);
    /* Copy the first byte. Bring the first bit to be copied into
    the position zero by shifting right all bits smaller than
    the start index */
    result->contents[0] = (bs->contents[startbyte] >> shiftamount);
    bytesToCopy = 1+(endbyte-startbyte);
    idx = 1;
    while (bytesToCopy) {
    /* Perform 2 shifts to eliminate all lower order bits */
    unsigned b = (bs->contents[++startbyte] >>
    (CHAR_BIT-shiftamount));
    b = b << (CHAR_BIT-shiftamount);
    result->contents[idx-1] |= b;
    b = (bs->contents[startbyte] >> shiftamount);
    b = (bs->contents[startbyte] << shiftamount);
    result->contents[idx] |= b;
    bytesToCopy--;
    idx++;
    }
    /* Since we have modified directly the bits, set now the count to
    its correct value. */
    result->count = len;
    return result;
    }
     
    jacob navia, Mar 10, 2011
    #15
  16. Re: review of the "container library", part 3/?

    jacob navia <> writes:
    <snip>
    > Thanks, I agree that GetRange was a mess. Here is a corrected version
    > that I uploaded today.
    >
    > static BitString *GetRange(BitString *bs,size_t start,size_t end)
    > {
    > size_t t,len;
    > BitString *result;
    > size_t startbyte,endbyte,shiftamount,bytesToCopy,idx;
    >
    > if (bs == NULL) {
    > NullPtrError("GetRange");
    > return NULL;
    > }
    > if (start > end) {
    > t = start;
    > start = end;
    > end = t;
    > }
    > if (end >= bs->count)
    > end = bs->count;
    > if (end != start)
    > len = end-start;


    start can now be greater than end.

    > else len = 0;
    > result = Create(len);
    > if (len == 0)
    > return result;
    > startbyte = start/CHAR_BIT;
    > endbyte = end/CHAR_BIT;
    > shiftamount = start&(CHAR_BIT-1);
    > /* Copy the first byte. Bring the first bit to be copied into
    > the position zero by shifting right all bits smaller than
    > the start index */
    > result->contents[0] = (bs->contents[startbyte] >> shiftamount);
    > bytesToCopy = 1+(endbyte-startbyte);
    > idx = 1;
    > while (bytesToCopy) {
    > /* Perform 2 shifts to eliminate all lower order bits */
    > unsigned b = (bs->contents[++startbyte] >>
    > (CHAR_BIT-shiftamount));
    > b = b << (CHAR_BIT-shiftamount);
    > result->contents[idx-1] |= b;


    This looks wrong. Just looking at the first result byte, when
    shiftamount is 1, you'd need to add in the low-order bit from
    bs->contents[1] into the high-order position of result->contents[0].
    That's not what's happening.

    > b = (bs->contents[startbyte] >> shiftamount);
    > b = (bs->contents[startbyte] << shiftamount);
    > result->contents[idx] |= b;
    > bytesToCopy--;
    > idx++;
    > }
    > /* Since we have modified directly the bits, set now the count to
    > its correct value. */
    > result->count = len;
    > return result;
    > }


    --
    Ben.
     
    Ben Bacarisse, Mar 10, 2011
    #16
  17. Alan Curry

    Ike Naar Guest

    Re: review of the "container library", part 3/?

    On 2011-03-10, jacob navia <> wrote:
    > if (end != start)
    > len = end-start;
    > else len = 0;


    Why not simply

    len = end-start;

    ?
     
    Ike Naar, Mar 11, 2011
    #17
  18. Alan Curry

    jacob navia Guest

    Re: review of the "container library", part 3/?

    Le 11/03/11 01:07, Ike Naar a écrit :
    > On 2011-03-10, jacob navia<> wrote:
    >> if (end != start)
    >> len = end-start;
    >> else len = 0;

    >
    > Why not simply
    >
    > len = end-start;
    >
    > ?


    Becouuusseeee... er....mmmmmm... becausssse.....

    This dammed function is getting me absolutely MAD. Bit twiddling is not
    for me,but I got into this mess and now I have to get out of it in an
    honorablme fashion...


    :)
     
    jacob navia, Mar 11, 2011
    #18
  19. Alan Curry

    jacob navia Guest

    Re: review of the "container library", part 3/?

    Le 11/03/11 00:18, Ben Bacarisse a écrit :
    > jacob navia<> writes:
    > <snip>
    >> Thanks, I agree that GetRange was a mess. Here is a corrected version
    >> that I uploaded today.
    >>
    >> static BitString *GetRange(BitString *bs,size_t start,size_t end)
    >> {


    [snip]


    >> if (end>= bs->count)
    >> end = bs->count;
    >> if (end != start)
    >> len = end-start;

    >
    > start can now be greater than end.
    >


    Yes, I am missing the test for start > bs->count, in which case I should
    return NULL.


    [snip]
    >
    > This looks wrong. Just looking at the first result byte, when
    > shiftamount is 1, you'd need to add in the low-order bit from
    > bs->contents[1] into the high-order position of result->contents[0].
    > That's not what's happening.


    Yes, that wasn't happening at all. Now it is working but before I post
    a fixed version let me test a bit more...


    GOSH!

    Bit fiddling is quite a mess isn't it?

    Or maybe I am just sloppy.
     
    jacob navia, Mar 11, 2011
    #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. Pavol Droba
    Replies:
    0
    Views:
    325
    Pavol Droba
    Sep 27, 2004
  2. jacob navia

    A container library in C. Part 1: Header file

    jacob navia, Sep 28, 2009, in forum: C Programming
    Replies:
    14
    Views:
    677
    Tech07
    Oct 3, 2009
  3. jacob navia
    Replies:
    3
    Views:
    326
    jacob navia
    Sep 29, 2009
  4. jacob navia
    Replies:
    5
    Views:
    504
    jacob navia
    Sep 28, 2009
  5. jacob navia
    Replies:
    10
    Views:
    644
    jacob navia
    Oct 1, 2009
Loading...

Share This Page