Link List

Go To Last Post
5 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Write guys, this code is throwing out rubbish.  Output is:

 

	fat->cluster_nr = 0x1234; dir_insert_cluster(fat);
	fat->cluster_nr = 0x4321; dir_insert_cluster(fat);
	fat->cluster_nr = 0x5678; dir_insert_cluster(fat);

	printf("\n\rNr1 %x", dir_remove_cluster(fat));
	printf("\n\rNr2 %x", dir_remove_cluster(fat));
	printf("\n\rNr3 %x", dir_remove_cluster(fat));

OUPUT!!!!!

 

Nr1 78
Nr2 21
Nr3 404

 

The Link list is last in first out.

 

The Code is listed below..

 

/**
 *
 * @param file - file stream pointer
 * @return	new cluster number
 */
unsigned char dir_remove_cluster(struct ff_file * file){

	// remove current directory
	struct directories * dir = file->dir_clusters->dir_chain->prev;

	int cluster = dir->cluster_nr;

	if( file->dir_clusters->dir_nr == 1){
		file->dir_clusters->dir_nr = 0;
	}
	else
	{
		file->dir_clusters->dir_nr--;
		if(file->dir_clusters->dir_chain == dir){
			file->dir_clusters->dir_chain = dir->next;
		}
		dir->prev->next = dir->next;
		dir->next->prev = dir->prev;
	}

	safe_free(dir);
	return(cluster);
}

/**
 *
 * @param file stream pointer
 * @return ignore
 */
unsigned char dir_insert_cluster(struct ff_file * file){


	// allocate memory for new link node
	struct directories * dir = safe_malloc(sizeof(struct directories));

	// log cluster number
	dir->cluster_nr = file->cluster_nr;


	if( file->dir_clusters->dir_nr == 0){
		file->dir_clusters->dir_chain 	= dir;
		dir->next						= dir;
		dir->prev						= dir;
		file->dir_clusters->dir_nr		= 1;
	}
	else{
		file->dir_clusters->dir_nr++;
		dir->next = file->dir_clusters->dir_chain;
		dir->prev = file->dir_clusters->dir_chain->prev;
		file->dir_clusters->dir_chain->prev->next = dir;
		file->dir_clusters->dir_chain->prev = dir;
	}
	return 1;
}
struct directories{

	unsigned int cluster_nr;

	struct directories * next;
	struct directories * prev;
};

struct chain{

	int dir_nr;
	struct directories * dir_chain;
};

Any views on this lads?

This topic has a solution.
Last Edited: Thu. Sep 19, 2019 - 09:34 PM
This reply has been marked as the solution. 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Are you meant to be updating the 'head' at some point when inserting (I'm guessing 'head' is file->dir_clusters->dir_chain) ?

Do you really need what looks like circular double linked list?

Fianawarrior wrote:

The Link list is last in first out.

So a stack.

Can this not be done with simple single linked list, add/remove from head ?

 

Also, if you want to return cluster as int, then don't return as unsigned char

unsigned char dir_remove_cluster(struct ff_file * file){

 

Last Edited: Thu. Sep 19, 2019 - 09:29 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MrKendo wrote:

Are you meant to be updating the 'head' at some point when inserting (I'm guessing 'head' is file->dir_clusters->dir_chain) ?

Do you really need what looks like circular double linked list?

Fianawarrior wrote:

The Link list is last in first out.

So a stack.

Can this not be done with simple single linked list, add/remove from head ?

 

Also, if you want to return cluster as int, then don't return as unsigned char

unsigned char dir_remove_cluster(struct ff_file * file){

 

 

 

Jesus, a char return.  I'm blind!  Happens when you look at your code sometimes you miss the obvious.

Thanks MrKendo!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The insert and remove functions still look suspect.

I was thinking you would always update the head after insert so the head always points to the new entry

ie. always do

file->dir_clusters->dir_chain 	= dir

When removing you would then remove the head entry.

Unles it is doing something clever (I haven't worked it all through, you seem to be leaving dir_chain always pointing to the first one inserted).

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MrKendo wrote:

The insert and remove functions still look suspect.

I was thinking you would always update the head after insert so the head always points to the new entry

ie. always do

file->dir_clusters->dir_chain 	= dir

When removing you would then remove the head entry.

Unles it is doing something clever (I haven't worked it all through, you seem to be leaving dir_chain always pointing to the first one inserted).

 

 

Your quit correct, it is just easy to go to the last in by going to the previous directory entry.  I know it can be done better but the link list is an old friend of mine that I use when required making basic changes to suit the application.