Good evening again, ladies and gentlemen!
I hope you are all doing well, your health to be the best, your wallet full of money and your love life better than ever! Also I wish you to be in a good shape to spot mistakes because tonight I'm gonna 'bug' you again and kindly ask for your help!
So, let's say we have a network. Every node of the network is a treenode of the Binary Search Tree above. We can add and remove network nodes. But!
Nodes can also store files, and every node holds a pointer to the head of a singly linked list of files (that's the docnode I mentioned previously). Supposing that we have 3 nodes with ids 5, 9, 12, (no files yet) if i want to store the file with file_id=9, i should put it in the node 9. For file with file_id=10, the corresponding treenode is the node 12. The file with file_id=1 will go to node 5. And finally (this point is very important), the file with file_id=20 will be stored to node 5, too.
To make th elong story short, that means: every file with file_id > node_max_id will be stored to the node with the minimum id instead.
At the same time, if i want to add a new treenode at my network, let's say with id = 25, Then the file with file_id=20 must be moved to node 25. And guess what: If i want to remove a node from the network, I must firstly put the files store there to another node that completes the criteria ...
So, let's say that my list is a structure like this:
Code:
typedef struct docnodeT docnodeT;
struct docnodeT
{
int id;
int type; /* Available types 1, 2, 3 */
docnodeT *next; /* Used to point to next node */
};
and the files such a list holds are presorted.
Then I 've written some functions to add/remove/search a node in the list etc, and two special functions:
The first funcion gets as an argument an initial list of this kind, splits the list in two, comparing the files to a given key, and returns the part that contains all files with file_id less or equal to the key, while the initial list must contain only the rest of files (if any).
Code:
docnodeT *DocListSplit(docnodeT *oldlist, int key)
{
docnodeT *newlist = NULL;
docnodeT *index;
docnodeT *hold;
/* Nothing to split so far */
if (oldlist == NULL) return newlist;
/* All the files have already file_id > key, so no need to move them */
if (oldlist->id > key) return newlist;
/* If I reached this point, it means that there are files to move! */
newlist = oldlist; /* At least the first file of oldhead belongs to newhead */
index = oldlist;
while (( index != NULL ) && (index->id <= key))
{
hold = index; /* This var will hold the last file of our newlist */
index = index->next; /* This var will hold the first file of our old list */
}
hold->next = NULL; /* The last file of our new list must point to NULL */
oldlist = index; /* if this var is NULL, means that all files moves to newlist */
return newlist;
}
The second function gets as arguments to lists, headto and headfrom. What it does is to move all the contents of headfrom to headto, and return headto. And this is exactly how it does it:
Code:
docnodeT *DocListMerge(docnodeT *listto, docnodeT *listfrom)
{
docnodeT *newlist;
docnodeT *indexfrom;
docnodeT *indexto;
docnodeT *newlistindex;
/* Whatever there is in listto, there is nothing to be merged with */
if (listfrom == NULL) return listto;
if (listto == NULL) /* The destination list is empty, */
{
newlist = listfrom;
listto = newlist; /* we 'exchange' it with the source list, */
listfrom = NULL; /* then make the source list point to NULL. */
return listto;
}
/* If we reach this point, it means that both lists have at list an item */
/* Now we need to add all the files in one list, but in the correct order */
/* The destination list must begin with the file with the smallest id */
if (listto->id < listfrom->id)
{
newlist = listto;
indexto = listto->next; /* indexto will point us to the first unused file of listto */
indexfrom = listfrom; /* indexfrom will point us to the first unused file of listfrom */
}
else if (listfrom->id < listto->id)
{
newlist = listfrom;
indexto = listto;
indexfrom = listfrom->next;
}
newlistindex = newlist; /* This index will always point us to the last file of the newlist */
/* Now we have to check simultaneously both of our indexes for the next file */
while ((indexto != NULL) && (indexfrom != NULL))
{
assert(indexto->id != indexfrom->id);
/* at this point the world explodes and green monkeys take over the planet */
if (indexto->id < indexfrom->id)
{
newlistindex->next = indexto;
indexto = indexto->next;
newlistindex = newlistindex->next;
}
else if (indexfrom->id < indexto->id)
{
newlistindex->next = indexfrom;
indexfrom = indexfrom->next;
newlistindex = newlistindex->next;
}
}
/* If we reach this point, it means that one of indexto,indexfrom is NULL */
/* We find it and then continue adding files from the other one */
/* These indexes can't be NULL simultaneously */
if (indexfrom == NULL)
{
assert (indexto != NULL);
while (indexto != NULL)
{
newlistindex = indexto;
indexto = indexto->next;
newlistindex = newlistindex->next;
}
}
else if (indexto == NULL)
{
assert (indexfrom != NULL);
while (indexfrom != NULL)
{
newlistindex->next = indexfrom;
indexfrom = indexfrom->next;
newlistindex = newlistindex->next;
}
}
/* at this point, both our indexto, indexfrom must be NULL */
assert (indexto == NULL);
assert (indexfrom == NULL);
/* now we re setting our last node of the destination list to be NULL */
newlistindex->next = NULL;
listto = newlist; /* Source1 list is set to be the Destination list */
listfrom = NULL; /* and source2 list is set to NULL */
return listto;
}
I'm gonna right down the functions I use when I join a new node to the network! That will be sometime in the near future, but in the meanwhile, does anyone see something which is not quite obvious to me?
Thank you again in advance not only for your will to help,
oh great Gods and Godesses of programming, (ok enough ..kissing for today!)
but also for your patience, if you manage to read it all!
E.