Detection of a loop in a linked tree (or linked list)

Discussion in 'C Programming' started by mac, May 27, 2008.

  1. mac

    mac Guest

    I found that with memory allocating techniques used nowadays
    (addresses alignment, eg. on 32bit machines) one can detect loops in a
    tree structure very fast, without using extra memory. This is due to a
    possibility of storing extra information in unused bits of the tree
    pointers (it works for linked lists too). One can say it is dangerous
    or obvious, but I haven't seen it anywhere, and maybe it will be
    useful for someone.

    The procedure of loops detection has two steps:
    1. Going through the tree with marking visited nodes (in pointers to
    them) and checking if every node was visited only once (visiting node
    twice means a loop)
    2. Going through the tree once again and fixing tree pointers values,
    to get the original tree structure
    Below is an example code in C - you need only to add tree creation
    function you like.

    /*
    * BEGINNING OF THE FILE
    */

    #include "stdio.h"
    #include "ctype.h"
    #include "malloc.h"


    #define LEAFS 2 //can be any integer >0

    typedef struct t { //simple tree structure
    int data;
    struct t * leafs[LEAFS];
    } tree;

    /*
    * test for cycles in a tree by using pointers reallignment
    */
    int TestTreeAl(tree **root)
    {
    int i=0;
    int j;
    tree *p;
    if (*root==NULL) return 0;
    else
    {
    j=((int)(*root))%2;
    if (j!=0) return 1; //if a node is marked with odd pointer - cycle
    detected
    p=*root; //remember the correct pointer
    (int)*root=((int)*root)+1; //mark the node
    for (i=0; i<LEAFS; i++) //visit all the leafs
    if (TestTreeAl(&(p)->leafs)==1) return 1;
    }
    return 0;
    }

    /*
    * fix allignment of tree pointers
    */
    void FixTree(tree **root)
    { int i,j;
    if (*root!=NULL)
    {
    j=(int)(*root)%2;
    if (j!=0)
    (int)*root=((int)*root)-1; //unmark previously marked node
    for (i=0; i<LEAFS; i++)
    {
    if ((j!=0) && ((*root)->leafs!=NULL))
    FixTree(&((*root)->leafs));
    }
    }
    }

    /*
    * test linked tree for cycles
    * returns 1 if any cycles were detectet, otherwise it returns 0
    * (almost no additional memory used, only two visits in each tree
    element)
    */
    int TestTree(tree *root)
    {
    int i=TestTreeAl(&root); //testing for tree cycles with pointers
    reallignment
    FixTree(&root);
    return i;
    }

    /*
    * print all the data from the tree (sequence is not important)
    */
    void print_tree_data(tree *root)
    {
    int i;
    if (root!=NULL)
    {
    printf("%d\n",root->data);
    for (i=0; i<LEAFS; i++)
    print_tree_data(root->leafs);
    }
    }

    void main()
    {
    tree *root;
    int i;

    printf("* Example of a fast and memory efficient method \n* for
    finding cycles in a tree structure (by Maciej Huk)\n\n");

    root=NULL; //for NULL tree we will have no cycles
    //make_tree(&root); //You need to define this function yourself

    print_tree_data(root); //if tree was OK, the print makes no problems

    i=TestTree(root);

    printf("Before adding the cycles: ");
    if (i==0) printf("NO CYCLES :)\n");
    else printf("CYCLES DETECTED!\n");

    /*
    * try adding cycles to your tree (beware for the initial tree
    structure!)
    */
    //root->leafs[1]->leafs[0]=root->leafs[0]->leafs[1]; //example of a
    cycle to try
    //root->leafs[0]->leafs[0]->leafs[0]=root; //...and another one

    i=TestTree(root);

    printf("\nAfter adding the cycles: ");
    if (i==0) printf("NO CYCLES :)\n");
    else printf("CYCLES DETECTED!\n");

    if (i==0) print_tree_data(root); //if there is no cycles we can
    easily print the tree

    printf("\n\nPress any key to exit...");
    while (!getch());
    }

    /*
    * END OF THE FILE
    */

    Best regards,
    Maciej
    mac, May 27, 2008
    #1
    1. Advertising

  2. mac <> wrote:
    > I found that with memory allocating techniques used nowadays
    > (addresses alignment, eg. on 32bit machines) one can detect loops in a
    > tree structure very fast, without using extra memory. This is due to a
    > possibility of storing extra information in unused bits of the tree
    > pointers (it works for linked lists too). One can say it is dangerous
    > or obvious, but I haven't seen it anywhere, and maybe it will be
    > useful for someone.


    The trick to use unused bits to store extra information is
    I guess about as old as there are computers - and the prob-
    lems resulting from that kind of being clever also. I still
    remember the Atari ST, where the CPU had 24 only address
    lines but 32 bit wide pointers. So some guys decided to use
    those upper "unused" bits for storing some extra information.
    Worked all well and nicely until the Atari TT came out which
    had 32 bit address lines and where none of these "clever"
    programs did work anymore.

    The whole thing is based on the assumption that the low order
    bit is always 0. This may be the case on your machine but has
    a good chance of being invalid on other architecures. And I
    don't see why it would help to speed up the program. If you
    have a dedicated element in the structure it can easily be
    accessed. With your "trick" you have to do several extra
    operations just to get at it and in the end you also have
    to reset them again to make sure that you get back "legal"
    pointers. All you win is a few bytes of memory for each
    structure. On the other hand you need a pointer width of
    memory in the function for testing the nodes which, if the
    tree is rather one-sided could lead to using actually more
    memory (probaly on the stack instead of in the heap where
    stack memory is often a scarcer resource).

    Finally, some lines of your program are invalid C like

    > (int)*root=((int)*root)+1; //mark the node


    since you can't cast a lvalue. If you insist on doing such
    things do them correctly:

    *root = ( tree * ) ( ( char * ) *root + 1 );

    And an int is not necessarily suitable to store a pointer.
    And the usual: main() is a function that returns an int,
    not void.

    And you probably know that your "test case" doesn't do
    anything at all since you never allocate a single struc-
    ture...
    Regards, Jens
    --
    \ Jens Thoms Toerring ___
    \__________________________ http://toerring.de
    Jens Thoms Toerring, May 27, 2008
    #2
    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. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,096
  2. fool
    Replies:
    14
    Views:
    495
    Barry Schwarz
    Jul 3, 2006
  3. joshd
    Replies:
    12
    Views:
    658
    John Carson
    Oct 2, 2006
  4. Roedy Green
    Replies:
    3
    Views:
    415
    Mike Schilling
    Sep 13, 2008
  5. Isaac Won
    Replies:
    9
    Views:
    354
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page