Thread: Hash Table with Simple record in files

Originally Posted by laserlight

What is a hash table? What ideas do you have concerning implementing a hash table in C?

Am going to use ISAM concept (Indexed Sequential Access method ).
This going to have Two files. One Index file and another one master file.
Index file will have two keys.
1. Record key
2. Storage address

and master file will have key related records.

I hope you understand my problem. How can i implement this in c. Am using only Flat files not but relational data base. in flat file retrieving data is very big problem. so only am planning to go about hash table and ISAM concepts. Please first tell me how to store and retrieve the records in files using this concepts.

What information is in each record... and why do you think you want to use flat (ascii?) files?

Sequential access... even when indexed can be very slow... Struct based random access files will be much faster, and you can index them as well.

ya...ascii files only..not binary files...okie....how can i implement struct based random access files?? can u explain me about the concept?? how can i implement it in c to store and retrieve data?

Here's a little example you can copy, paste and compile... it's pretty trivial but it does show how random access filing works...

Code:

//random access file demo
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <ctype.h>
#include <string.h>

#define FNAME "random.dat"

// test data struct
struct t_Record
  { int randnum;
    char word[16]; }
  Record;



///////////////////////////////////////////////////////
// Random Access File Handlers
//

// open or create the file
FILE *FileOpen(char* Filename)
  { FILE* pFile;
    pFile = fopen(Filename,"rb+");
    if (!pFile)
      pFile = fopen(Filename,"wb+");
    return pFile; }


// Write a record to the file
int WriteRecord(FILE *File, int RecNum)
  { if( fseek(File, RecNum * sizeof(Record), SEEK_SET) == 0 )
      if ( fwrite(&Record,sizeof(Record),1,File) )
        return 1;
    return 0; }


// read a record from the file
int ReadRecord(FILE *File, int RecNum)
  { if( fseek(File, RecNum * sizeof(Record), SEEK_SET) == 0 )
      if ( fread(&Record,sizeof(Record),1,File) )
        return 1;
    return 0; }



////////////////////////////////////////////////////////
// this is for demonstration purposes only
// you would not do this in a real program
void InitFile(FILE* File)
 { int x, y;
   memset(&Record,sizeof(Record),0);
   for (x = 0; x < 1000; x++)
      { Record.randnum = rand();
        for (y = 0; y < ((Record.randnum % 15) + 1); y++)
          Record.word[y] = (rand() % 26) + 'a';
        Record.word[y] = 0;
        if (! WriteRecord(File,x))
          printf("Oh drat!");  } }
 

 
//////////////////////////////////////////////////////////
// program mains
//
int main (void)
  { FILE *File;
    int Quit = 0;
    int Rec = 0; // record number

    srand(time(NULL));

    File = FileOpen(FNAME); 
    if (!File)
      { printf("Curses foiled again!\n\n");
        exit(-1); }

    // write out 1000 test records  
    printf("Create a new file? (y/n)  ");
    if ( toupper( getchar() ) == 'Y')
      InitFile(File);
  
    // lets peek
    do
      { printf("Enter a record number (0 - 999) to load : ");
        if (! scanf("%d",&Rec) )
          Quit = 1;  // enter any letter to quit
        else 
          { // read and display the record 
           if (! ReadRecord(File,Rec) ) 
              printf("Could not read record %d\n",Rec);
            else
              { printf("-----\n");
                printf("Record Number : %d\n",Rec);
                printf("Number Value  : %d\n",Record.randnum);
                printf("Record Name   : %s\n",Record.word);
                printf("-----\n"); 
                getchar();
                printf("Do you want to rename this record (y/n)? ");
                if ( toupper( getchar() ) == 'Y')
                  { printf("Enter a new name : ");
                    if ( scanf("%s",Record.word) )
                      WriteRecord(File,Rec);  } } }
      } while (! Quit); 


    fclose(File);
    return 0; }

The beauty of this is that you have fixed size records in your file so you can mathematically calculate their start positions and seek directly to them... lightning fast. Some setups use the record numbers as account numbers or part numbers, meaning that when the operator keys in a client's account number, they've actually entered their record location in the disk file... again lightning fast access.

Another advantage is that, like this example, you can have enormous files, with only one struct (record) in memory to access everything. Beats the pants off linked lists...

Still another advantage is the records in the file are reusable... that if if a customer closes their account you can simply mark the record as "reuseable" and stuff your next new account in there, keeping the file contiguous and removing the need for constant maintenance.

I have a couple of inventory systems I wrote this way, one stores over 100,000 part numbers (description, re-order info etc.) and the access time is such that the record is always on screen before the operator gets their finger off the Enter key...

If you want portability though, writing structs directly to files isn't a very good idea. Due to structure padding, endianness, variable sizes etc. chances are that if the code is compiled using a different compiler, or using different compiler options (that could alter struct layouts), it won't be able to read back the same information again.

Originally Posted by CommonTater

Portable smortable... When is the last time you saw any corporate environment where they actually demanded only "mutiplatform ready" code?

For the most part these kinds of filing systems are one-offs, used only on the company's standard OS (almost always windows) and served up from a central location on their LAN. Portability means next to nothing in these situations...

If you want portable you use SQL or one of it's dialects... you don't write a custom filing system.

I see it every day at work actually :-)

I agree that a lot of the time it is not necessary, but I think it's good to least know about it so one can make an educated decision on which way to go when it comes to storing data.

Who are you asking?

Wait another 16 messages and you can PM whoever you like...

Originally Posted by iceaway

If you want portability though, writing structs directly to files isn't a very good idea. Due to structure padding, endianness, variable sizes etc. chances are that if the code is compiled using a different compiler, or using different compiler options (that could alter struct layouts), it won't be able to read back the same information again.

Given the source code, portability won't be an issue unless one tried to read the output of a different compiler. Why do that when the source code and the ascii inputs are at hand.

Originally Posted by itCbitC

Given the source code, portability won't be an issue unless one tried to read the output of a different compiler. Why do that when the source code and the ascii inputs are at hand.

For ascii-files it won't be an issue, but writing structs to a file is a problem if the same file is written/read on different platforms with different endianness (in which case it is probably compiled using a different compiler anyway).

Originally Posted by iceaway

For ascii-files it won't be an issue, but writing structs to a file is a problem if the same file is written/read on different platforms with different endianness (in which case it is probably compiled using a different compiler anyway).

Ascii files are a royal pain in the backside... you spend more time converting data with scanf() etc. than you do actually processing it... structs are simple, clean and elegant... which is why I recommended it. Decoding and encoding then indexing and maintaining variable length records is just a monumental waste of time...

Originally Posted by iceaway

For ascii-files it won't be an issue, but writing structs to a file is a problem if the same file is written/read on different platforms with different endianness (in which case it is probably compiled using a different compiler anyway).

Exactly my point.

Why would someone ftp the binary output to another system and read it there when the right thing is to move source code and ascii input files, and re-compiling; unless someone isn't well versed with block I/O.