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=((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

 

[Jens Thoms Toerring]

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