How to get a block number
 

I have some data files and I want to put them into a raw device.Because of the I/O on raw device based on block,I put every file in some blocks related by block number. The blocks of raw device are Sequentially numbered according to the physical location,i.e. the first block's number is 1 and the second's is 2 until the last block's number is the block count of the raw device.Using the block number I can move the file pointer to a block and read data from or write data to the block conveniently.
The data structure I designed are below.The first two blocks are used for head infomation.

struct block_struct
{
unsigned long block_number;
unsigned long next_block_number;/*point to its next block*/
unsigned long prev_block_number;/*point to its previous block*/
unsigned int length;/*the used byte of the block.*/
char isValid;/*whether the block is valid*/
char *data;
};

The head infomation structure:

struct file_info{/*file structure,representing file infomation in the raw device*/
char* file_name;
unsigned long block_count;/*how many blocks the file used*/
unsigned long first_block_number;/*the file's first block number*/
unsigned long last_block_number;/*the file's last block number*/
unsigned long length;/*the file's length*/
};


struct head_info
{
unsigned long block_count;/*the blocks count of raw device*/
unsigned int block_size;/*the size of a block*/
unsigned int file_count;/*the count of files put in this raw device*/
unsigned int length;/*the used byte of head*/
struct file_info **file_list;/*the file list in the raw device*/
};

Using these structure I can control the files' data in the raw device.When a file is deleted from the raw device,the blocks it used are then idle and should be reused.The problem is the block number.How to get a new block number so that the deleted file's block can be reused? Is there some good algorithm?
Thank you very much!

Well, one way might be to make a singly linked list out of all free blocks. Suppose we have:

struct free_block {
struct free_block *next;
};

struct free_block *free_head;

To free a block, we simply do:

struct free_block *f = (void*)block_to_free;
f->next = free_head;
free_head = f;

To allocate a block, we do:

struct block_struct *b;

if (free_head) {
b = (void*)free_head;
free_head = free_head->next;
} else {
//make more memory somehow
}

That's a simple way to do it. There are likely more efficient ways to do this if locality is an issue.

Also, I don't know how scalable your application needs to be (specifically, how many files you expect to have). Consider the case of having 100,000 files. To find one, you have to traverse, on average, 50,000 links (which might take quite a while due to cache misses and/or seek times). In other words, it takes linear time to find files using this approach.

By contrast, modern filesystems and databases use more efficient data structures called B-trees that can find things in logarithmic time. This means that, with 100,000 files, it would only take, say, 17 steps to find a file. I recommend reading up on binary search trees and B-trees if you haven't learned about those yet. They will change your life.

Also, watch out for endianness. If you don't know what that is, look it up.

You might actually be better off using an existing database solution. For this type of thing, SQLite and tdb (trivial database) are worth looking into.