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

[mac]

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=((in t)*root)+1; //mark the node
for (i=0; i<LEAFS; i++) //visit all the leafs
if (TestTreeAl(&(p )->leafs[i])==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=((in t)*root)-1; //unmark previously marked node
for (i=0; i<LEAFS; i++)
{
if ((j!=0) && ((*root)->leafs[i]!=NULL))
FixTree(&((*roo t)->leafs[i]));
}
}
}

/*
* 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(&r oot); //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",r oot->data);
for (i=0; i<LEAFS; i++)
print_tree_data (root->leafs[i]);
}
}

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\nPre ss any key to exit...");
while (!getch());
}

/*
* END OF THE FILE
*/

Best regards,
Maciej