OSDev.org

Posted: **Tue May 13, 2008 4:49 pm**

Heya folks,

Ive just finished writing another nifty ADT, called the Radix Tree.
Its useful for very high speed string searching.

It is written in a way so that it should be easy to port to anyones Kernel, should they wish to use it.

Allocation/Deallocation wrappers are there; Its all fully commented.

Anywho, What id like feedback with is :

- Current coding style.
- The commenting.

Id appreciate any input,
Thanks!

~Z / elderK

Posted: **Wed May 14, 2008 12:29 am**

I saw a goto statement and suddenly felt a urge to stop reviewing..

Posted: **Wed May 14, 2008 1:30 am**

It looks very good, nicely commented etc. With the exception of place_node of course - I advise rewriting that to remove the gotos. They're not needed - the same control flow can be created without them.

Cheers,

James

Posted: **Wed May 14, 2008 5:15 am**

I saw several occurences of // comments within /* */ comments, which struck me as odd.

Compiles without warnings, even with -Wall -Wextra -pedantic -std=c99... I am impressed!

The gotos are revolting, of course.

Unions and void pointers aren't a beauty, either, but without doing an in-depth review I'll assume they are necessary given the problem domain.

Which brings me to the lack of a README.txt explaining in layman terms what it is, and how it is used, including an example.

Otherwise, I have seen lots worse, and few better. Congrats!

Posted: **Wed May 14, 2008 7:08 am**

Thanks for the feedback!
I will post a revision soon - addressing the Gotos

Restructure something like ...

WITH GOTO

Code: Select all


    /*
        compare the two identifiers; compare only up to the smallest
        strings length. Break to NO_MATCH when a difference is detected.
        If no difference is detected, fall through.
    */
    for(diff_pos = 0; diff_pos < *compare_len; diff_pos++)
        if(exstr[diff_pos] ^ itstr[diff_pos])
            goto no_match;

    /* match: */
        /*
            it has been decided that one of the strings, is a prefix.
            thats all well and jolly, but we need to know WHICH is the
            prefix. Iterator or External?
        */
        diff_cache = (compare_len == &extern(external).ne_identifier_len);

        /* mark the internal node, signalling that it details a prefix/es */
        internal->n_flag = NT_INTERN_MARKED;

    place:
        /*
            setup the internal nodes references...

            diff_cache stores the "direction" of the external node.
            Left = 0, Right = 1.

            As mentioned in the radix.h header, ni_diff_pos's interpretation
            differs depending on whether the internal node is marked or not.
            *compare_len points to the prefix length (if prefix case) and the
            bit index of difference (if not prefix).
        */
        intern(internal).ni_diff_pos = *compare_len;
        intern(internal).ni_link[diff_cache] = external;
        intern(internal).ni_link[!diff_cache] = iterator;

        return internal;

    no_match:
        /* cache the differing byte */
        diff_cache = (uint8_t)(exstr[diff_pos] ^ itstr[diff_pos]);
        
        /* isolate the bit position of the difference */
        for(diff_pos <<= 3; !(diff_cache & 1); diff_cache >>= 1, diff_pos++);

        /* determine which side of the internal node external will be placed */
        diff_cache = (exstr[diff_pos >> 0x3] & (1 << (diff_pos & 0x7))) > 0;

        /*
            ensure the internal node is UNMARKED and that compare_len points
            to the correct data; in this case, the bit index of the difference.
        */
        internal->n_flag = NT_INTERN_UNMARKED;
        compare_len = &diff_pos;
        goto place;

to something more like this?

WITHOUT GOTO

Code: Select all


    /*
        Assume that two strings will be identical - a prefix case.
        diff_cache determines which (external or iterator) is the
        prefix.

        Assuming a prefix here, allows us to skip an IF later!
    */
    diff_cache = (compare_len == &extern(external).ne_identifier_len);

    /*
        compare the two identifiers; compare only up to the smallest
        strings length.
    */
    for(diff_pos = 0; diff_pos < *compare_len; diff_pos++)
    {
        /* Do the bytes match? */
        if(exstr[diff_pos] ^ itstr[diff_pos])
        {
            /* cache the differing byte */
            diff_cache = (uint8_t)(exstr[diff_pos] ^ itstr[diff_pos]);
            
            /* isolate the bit position of the difference */
            for(diff_pos <<= 3; !(diff_cache & 1); diff_cache >>= 1, diff_pos++);
    
            /* determine which side of the internal node external will be placed */
            diff_cache = (exstr[diff_pos >> 0x3] & (1 << (diff_pos & 0x7))) > 0;
    
            /*
                ensure the internal node is UNMARKED and that compare_len points
                to the correct data; in this case, the bit index of the difference.
            */
            internal->n_flag = NT_INTERN_UNMARKED;
            compare_len = &diff_pos;

            /* Short circuit the loop */
            break;
        }
    }

    place:
    /*
        setup the internal nodes references...

        diff_cache stores the "direction" of the external node.
        Left = 0, Right = 1.

        As mentioned in the radix.h header, ni_diff_pos's interpretation
        differs depending on whether the internal node is marked or not.
        *compare_len points to the prefix length (if prefix case) and the
        bit index of difference (if not prefix).
    */
    intern(internal).ni_diff_pos = *compare_len;
    intern(internal).ni_link[diff_cache] = external;
    intern(internal).ni_link[!diff_cache] = iterator;

    return internal;

In the ungotoified code, the labels remain for now, just to show how I have restructured it.

Any less creepy?

~K

OSDev.org

Feedback, please!

Feedback, please!