/***** RANDOM ACCESS FILE PROGRAM *****/ #include #include #include #define FILE_SIZE 419 /* slots 0 through 418 */ #define RECORD_SIZE 47 /* 46 + status flag */ #define KEY_SIZE 9 /* 9-digit unique identifier */ #define TOTAL_BYTES ( RECORD_SIZE * FILE_SIZE ) #define INBUFF_SIZE 81 /* size of user buffer */ #define TAKEN 'T' /* slot that holds a record */ #define FREE 'F' /* slot that never held a record */ #define DELETED 'D' /* slot that holds a deleted record */ const int FOUND = 1; const int NOT_FOUND = 0; const char BLANK = ' '; const int DIVISOR = 419; /* used in hashing */ FILE *fptr; const char file[] = "records.dat"; char inbuff[ INBUFF_SIZE ]; /* buffer for user input */ int count; /* count of records in file */ void add_record( void ), find_record( void ), remove_record( void ), initialize( void ), set_count( void ); long get_address( const char *key ); int locate( const char *key ), print_menu( void ); main() { int choice; /* open the file "records.dat" and count the number of records it contains, if it exists; otherwise, create and initialize it */ if ( ( fptr = fopen( file, "r+b" ) ) != NULL ) set_count(); else { fptr = fopen( file, "w+b" ); initialize(); } /* Do file operations until user signals halt. */ while ( ( choice = print_menu() ) != 0 ) switch ( choice ) { case 1: add_record(); break; case 2: find_record(); break; case 3: remove_record(); break; default: printf( "\n\n\t\t\tIllegal choice. " "Please choose again.\n" ); break; } fclose( fptr ); return EXIT_SUCCESS; } /* Create a relative file and indicate that FILE_SIZE record slots are open in it. */ void initialize( void ) { int i; char dummy[ RECORD_SIZE + 1 ]; /* Create a dummy record to store repeatedly in file. */ dummy[ 0 ] = FREE; /* status unoccupied */ for ( i = 1; i < RECORD_SIZE; ++i ) dummy[ i ] = BLANK; dummy[ RECORD_SIZE ] = '\0'; for ( i = 0; i < FILE_SIZE; ++i ) fputs( dummy, fptr ); count = 0; } /* Count occupied slots in file. */ void set_count( void ) { int i; /* For fseek: SEEK_SET means seek from beginning of file */ /* SEEK_CUR means seek from current file marker */ /* SEEK_END means seek from end of file */ /* All three are defined in stdio.h. */ fseek( fptr, 0, SEEK_SET ); for ( i = 0; i < FILE_SIZE; ++i ) { if ( fgetc( fptr ) == TAKEN ) ++count; fseek( fptr, RECORD_SIZE - 1, SEEK_CUR ); } } /* Print a menu of choices and return whichever the user picks. */ int print_menu( void ) { int choice; printf( "\n\n\n\t\t\t" "1 -- add a record\n\t\t\t" "2 -- find a record\n\t\t\t" "3 -- remove a record\n\t\t\t" "0 -- exit the program\n\n\t\t\t" "Please pick a number: " ); fgets( inbuff, INBUFF_SIZE, stdin ); sscanf( inbuff, "%d", &choice ); return choice; } /* Add a record to the file */ void add_record( void ) { char record[ RECORD_SIZE + 1 ]; if ( count >= FILE_SIZE ) { /* full file? */ printf( "\a\n\n\n\nFile is full.\n" ); } else { do { printf( "\n\nPlease enter new record's key: " ); fgets( inbuff, INBUFF_SIZE, stdin ); /* input must be KEY_SIZE + newline */ if ( strlen( inbuff ) != KEY_SIZE + 1 ) printf( "\aKey size must be %d", KEY_SIZE ); } while ( strlen( inbuff ) != KEY_SIZE + 1 ); if ( locate( inbuff ) == FOUND ) { printf( "\aThere is already a record with " "the key: %s\n", inbuff ); return; } strncpy( &record[ 1 ], inbuff, KEY_SIZE ); /* copy key */ do { printf( "\nPlease enter data: " ); fgets( inbuff, INBUFF_SIZE, stdin ); /* input must be less than or equal to RECORD_SIZE - KEY_SIZE - 1 counting the newline */ if ( strlen( inbuff ) > RECORD_SIZE - KEY_SIZE - 1 ) printf( "\aRecord size must be less than" " or equal to %d" " counting the newline\n", RECORD_SIZE - KEY_SIZE - 1 ); } while ( strlen( inbuff ) > RECORD_SIZE - KEY_SIZE - 1 ); strcpy( &record[ 1 + KEY_SIZE ], inbuff ); record[ 0 ] = TAKEN; /* mark status as taken */ fputs( record, fptr ); /* store record */ ++count; } } /* Return address to which a key hashes. */ long get_address( const char *key ) { long int_key, address; int_key = atol( key ); /* convert */ address = ( int_key % DIVISOR ) * RECORD_SIZE; /* hash */ return address; } /* Remove a record from the file by marking its slot DELETED. */ void remove_record( void ) { char key[ KEY_SIZE + 1 ]; printf( "\n\nPlease enter record's key: " ); fgets( inbuff, INBUFF_SIZE, stdin ); strncpy( key, inbuff, KEY_SIZE ); key[ KEY_SIZE ] = '\0'; if ( locate( key ) != FOUND ) printf( "\a\nThere is no record with the key: %s\n", key ); else { --count; fputc( DELETED, fptr ); printf( "\nRecord has been deleted.\n" ); } } /* Find a record with a given key and print it. */ void find_record( void ) { char key[ KEY_SIZE + 1 ], record[ RECORD_SIZE + 1 ]; printf( "\n\nPlease enter record's key: " ); fgets( inbuff, INBUFF_SIZE, stdin ); strncpy( key, inbuff, KEY_SIZE ); key[ KEY_SIZE ] = '\0'; if ( locate( key ) == NOT_FOUND ) printf( "\aThere is no record with the key: %s", key ); else { fgets( record, RECORD_SIZE + 1, fptr ); /* read it */ printf( "Record: %s", record + KEY_SIZE + 1 ); } } /* locate searches for the record with given key. locate returns 1 if the record is found and 0 if the record is not found. Furthermore, if the record is found, locate sets the file position marker to the found record. If the record is not found, locate sets the file position marker to the unoccupied slot (DELETED or FREE), if any, to which key hashes, using linear probing to find such a slot if necessary. If the record is not found and the file is full, locate sets the file position marker to the hash address of key. */ int locate( const char *key ) { long address, /* current offset in file */ start_address, /* initial (hash) offset in file */ unocc_address; /* first DELETED offset in file, if any; otherwise, equal to start_address */ int delete_flag = 0; /* 0 if no DELETED slot found; 1 otherwise */ char stored_key[ KEY_SIZE + 1 ]; address = get_address( key ); /* hash to address */ unocc_address = start_address = address; do { fseek( fptr, address, SEEK_SET ); /* find slot */ switch ( fgetc( fptr ) ) { /* check status */ case DELETED: /* if first visit to a DELETED slot, mark its location and set flag */ if ( !delete_flag ) { unocc_address = address; delete_flag = 1; } break; case FREE: /* end of search. if first unoccupied slot is a DELETED slot, reset file position marker to that slot; otherwise, reset file position marker to present FREE slot which is the first unoccupied slot. */ if ( delete_flag ) fseek( fptr, unocc_address, SEEK_SET ); else fseek( fptr, address, SEEK_SET ); return NOT_FOUND; case TAKEN: /* extract key */ fseek( fptr, address + 1, SEEK_SET ); fgets( stored_key, KEY_SIZE + 1, fptr ); /* key equals stored_key? */ if ( strncmp( key, stored_key, KEY_SIZE ) == 0 ) { /* restore file position marker */ fseek( fptr, address, SEEK_SET ); return FOUND; } break; } /* probe */ address = ( address + RECORD_SIZE ) % TOTAL_BYTES; } while ( address != start_address ); /* reset file position marker to first DELETED slot or to initial slot */ fseek( fptr, unocc_address, SEEK_SET ); return NOT_FOUND; }