Array of Linked lists on disk

Question

I am trying to find how to store and process (search, add, remove) an array of linked lists on disk. For example in memory, it would like

struct list {
 int a;
 struct list *next;
}LIST

LIST *array[ARRAY_SIZE]

int main{
...
 LIST *foo = array[pointer];
 /* Search */
 while(foo!=NULL){
   ...
   foo=foo->next
 }
}

1. I believe that by using fseek() I can point to a specific element/structure of the array in the file. But I cannot understand if all previous elements need to have been written or not.
2. Can this be done with dynamic allocation on disk?
3. How will I link on element to another one in the linked list? Any example would certainly help!

Answer 1

Okay, as Amardeep says, this sounds like the sort of thing that would best be done practically using some kind of database, like, or, Berkeley DB. But let's answer the questions anyway.

1. you can indeed use fseek (or its system call, lseek) to determine where something is on the disk and find it later. If you use some method of computing the offset, you're implementing what we used to call a direct file; otherwise you might store an index, which leads you off toward the indexed sequential method.

2. whether it can be done with dynamic allocation sort of depends on the file system. Many UNIX file systems support * sparse* allocation, which means that if you allocate block 365 it doesn't have to allocate blocks 0 through 364. Some dont.

3. Let's say that you have a structure with a length k that looks more or less like this:

(trick the parse)

struct blk { 
    // some stuff declared here
    long next;  // the block number of the next item
};

You create the first item; set its block number to 0. Set next to some distinguished value, say -1.

// Warning, this is off the cuff code, not compiled.
struct blk * b = malloc(sizeof(struct blk));
// also, you should really consider the case where malloc returns null.

// do some stuff with it, including setting the block next to 1.
lseek(file, 0, SEEK_SET);  // set the pointer at the front of the file
write(file, sizeof(struct blk), b);  // write it.
free(b);

// make a new block item
malloc(sizeof(struct blk));
// Do some stuff with it, and set next to 2.
lseek(file, 0, SEEK_CUR);  // leave the pointer where it was, end of item 0
write(file, sizeof(struct blk), b);  // write it.
free(b);

You now have two items on disk. keep this up and you'll eventually have a thousand items on disk. Now, to find item # 513, you just

lseek(file, (sizeof(struct blk)*513), SEEK_SET);

You need a buffer; since we freed the previous ones we'll make another

b = malloc(sizeof(struck blk);

Read that many bytes

read(file, sizeof(struct blk), b);

And poof record 513 is in memory pointed to by b. Get the record following with

lseek(file, (sizeof(struct blk)*b->next), SEEK_SET);