In previous Chapter about random file, we access a record with its record number. This is inconvenient. ISAM method allows us to access a record using a key, or part of a key. There are many database subroutines using ISAM available in LINUX.
The Debian Linux I am using includes "dbm" (data base management), "gdbm", "ndbm" etc. (You may view their header files in /usr/include/, e.g. "gdbm.h", "dbm.h", "ndbm.h". Also you may view the table of content of the libraries in /usr/lib/, "libdbm.a", "libgdbm.a", "libndbm.a", with the command
ar -t libdbm.a
I haven't seen the source codes myself, but I believe that they store the data using "binary tree", and also they use "malloc(..)" subroutines or the like.
The above databases allow storage of variable length records.
In commercial applications, the record length is usually fixed. Hence simplification is possible.
Below is a program written by me, using static memory and not memory from "malloc(..)", because I think that would be safer.
I hope it may be useful to you.
/* Author : Wu Siu Yan
You may freely use, or distribute, or sell, or modify this program
PROVIDED you agree with the "copyleft" agreement of
FREE SOFTWARE FOUNDATION, USA. In essence, the agreement :
(1) If you modify the source code, and when you sell or give your new
code to others, you MUST supply him with the original
code here.
(2) When you sell or give this program ( or your modified version ) to others,
you must give him the same right to "freely use, distribute, sell,
or modify " this program or your modified one, as you have received.
Item (2) is added because years ago, when Free Software Foundation gave programs
to others freely, they modified the program, and patented the modified version
for their own!
*/
#include <c.h>
#define BUFSIZE 1000 /* This constant is for char *buffer[BUFSIZE]
for the gets(..) */
#define MATCHSIZE 1000 /* This defines the upper limit for
storing the matched keys */
#define MSIZE 300 /* This defines the total number of records */
#define FUELLOW 100 /* The program will sound warning if Array[..] is left
with this number */
#define LKEY 40 /* Length of Key. One (char) field in structure data
is used for key */
#define LDATA 68 /* Length of Data. This should be the size of the
structure for data */
#define DEBUG 1
typedef int boolean;
typedef struct Isam
{char key[LKEY];
char data[LDATA];
int iactiveflag;
int pright; /* This works the same as struct Isam *pright */
int pleft; /* This works the same as struct Isam *pleft.
Now -1 takes the value of NULL */
} Isamrec;
Isamrec Array[MSIZE]; /* Whole file is stored in memory */
static boolean Inflag=0; /* This flag indicates whether the Nrec,
as well as Array[] are in memory or not. */
static int Nrec, Ipool; /* Nrec is the total number of record.
Ipool is where Array[...] is currently
free */
static FILE *Fmas, *Flog, *Fpara;
static int Isort; /* This is the index for array Isortarray[]
in the tree sort */
static int Isortarray[MSIZE]; /* The sorted indices will be put in this
array */
static Imatch[MATCHSIZE]; /* This array is used to store the
partly matched keys */
/* CUSTOM Part 1 */
static char Filemaster[]="master5", Filelog[]="logfile",
Filepara[]="parafile";
static char Promptmessage[]="Name -> "; /* prompt for key */
typedef struct
{char name[40]; /* As name is 40 bytes, hence LKEY = 40 */
int age;
char tel[24];
} Mrec; /* As this record is 68 bytes long, hence LDATA = 68 */
/* END CUSTOM Part 1 */
/* PROTOTYPES */
void displayrec(Mrec *ptr);
void printrec(Mrec *ptr, FILE *f);
/* This subroutine prompts the user for input data. If the user enters ****,
that indicates "quit" and inputrec() returns 0, else it returns 1.
getnew(..) is for re-input use.
*/
int inputrec(Mrec *ptr);
Mrec getnew(Mrec *ptr);
/* Print screen subroutines */
void printscreen(char *s);
/* This subroutine inserts a record in Array[], which uses a subroutine
db_insert(..) */
boolean insertrec(Mrec *ptr);
boolean db_insert(char *key, char *data);
/* This subroutine replaces a record. */
void db_replace(Isamrec *ptr, char *data);
/* This subroutine checks if the record exists. If it exists,
it returns a pointer to a record in Array[], else it returns NULL.
This subroutine also replaces the function of db_fetch(char *key).
*/
Isamrec *db_exists(char *key);
Isamrec *db_exists2(Isamrec *ptr, char *key);
/* This subroutine writes the Array[] as well as the parameter file.
It then closes both files. In doing so, the data are "flushed"
onto disc. It then reopens the files.
*/
void db_sync(void);
/* These 2 subroutines moves "key", "data" */
static void movekey(char *d, char *s);
static void movedata(char *d, char *s);
/* Note this comparison subroutine is for ascending order.
Returns -1 if a<b, 0 if a=b, 1 if a>b */
static int compare(char *a, char *b);
/* This opens both the master file and the parameter file
The first opens with mode "w".
The second opens with mode "r+"
*/
void openmaster0(void);
void openmaster1(void);
void closemaster(void);
void openlog(void);
void closelog(void);
/* Print a string to a file */
void printmessage(char *message, FILE *f);
/* Main menu subroutine for main(..) */
int menu(void);
/* Asks for confirmation with "message" */
boolean confirm(char *message);
/* This subroutine writes Array[] onto file */
void writearray(void);
/* This subroutine reads Array[] from master file */
void readarray(void);
/* These two subroutines sort the Array[..] using tree-sort */
static void db_sorta(int ip);
static void db_sort(void);
/* This subroutine is used in "change(), delete(), inspect()".
It prompts the user to enter a key, and searches for that record.
On quit (= ****), it returns 0,
Otherwise, it returns 1, together with an Isamrec address
"Isamrec **p" - pointer to an Isamrec pointer, which will store
the address of the record.
It also checks if the record have been deleted.
If the list doesn't contain what the use wants, the user may
quit this with "****". It returns 2 in this case, to start another
prompt.
*/
int promptrec(Isamrec **p);
/* Subroutine to read in master file into Array[..] */
void updateinitialization(void);
/* Main subroutines */
void delete(void);
void change(void);
void add(void);
void create(void);
void inspect(void);
/* END PROTOTYPES */
/* CUSTOMS Part 2 */
void displayrec(Mrec *ptr)
{
printf("Name : %s\n"
"Age : %d\n"
"Tel : %s\n\n", ptr->name, ptr->age, ptr->tel);
return;
}
void printrec(Mrec *ptr, FILE *f)
{ fprintf(f,"%-40s %3d %-24s\n", ptr->name, ptr->age, ptr->tel);
return;
}
/* This subroutine prompts the user for input data. If the user enters ****,
that indicates "quit" and inputrec() returns 0, else it returns 1.
For simplicity sake, no DATA VALIDATION is performed. But for actual
production program, DATA VALIDATION is a must.
*/
int inputrec(Mrec *ptr)
{ char buffer[BUFSIZE];
printf("Enter name\n");
gets(ptr->name);
if (strcmp(ptr->name,"****") == 0)
{return 0;}
printf("Enter age\n");
gets(buffer);
sscanf(buffer,"%d",&(ptr->age) );
printf("Enter telephone no\n");
gets(ptr->tel);
return 1;
}
Mrec getnew(Mrec *ptr)
{ Mrec temp;
char buffer[BUFSIZE];
/* Notice that "structure" may be used assignment statement */
temp = *ptr;
printf("Name : %s\n -> ", ptr->name);
gets(buffer);
if (buffer[0] != '\0') /*This checks if it is an empty string */
{strcpy(temp.name,buffer);
}
printf("Age : %d\n ->", ptr->age);
gets(buffer);
if (buffer[0] != '\0')
{temp.age = atoi(buffer);
/* atoi(..) is a library function in <stdlib.h> */
}
printf("Tel : %s\n ->", ptr->tel);
gets(buffer);
if (buffer[0] != '\0')
{strcpy(temp.tel, buffer);
}
return temp;
}
void printscreen(char *s)
{ printf("%s",s);
return;
}
/* Notice that "key" must be part of Mrec, in this case "name"
serves as a key too. */
boolean insertrec(Mrec *ptr)
{ boolean iret;
iret = db_insert(ptr->name, (char *)ptr);
return iret;
}
/* END CUSTOM Part 2*/
static void movekey(char *d, char *s)
{ int i;
for (i=0; i<LKEY ; i++, d++, s++)
{*d=*s;
}
return;
}
static void movedata(char *d, char *s)
{ int i;
for (i=0; i<LDATA ; i++, d++, s++)
{*d=*s;
}
return;
}
/* Note this comparison subroutine is for ascending order */
static int compare(char *a, char *b)
{ int i, ca, cb;
for (i=0; i<LKEY; i++, a++, b++)
{ca = *a;
cb = *b;
if (ca == '\0')
{if (cb == '\0')
{return 0;
}
else
{return -1;
}
}
if (cb == '\0')
{return 1;
}
if (ca > cb)
{return 1;
}
else if (ca < cb)
{return -1;
}
else
{continue;
}
}
}
void openmaster0(void)
{ int ierror;
ierror=0;
if ( (Fmas=fopen(Filemaster,"w")) == NULL )
{perror("Unable to open master file");
ierror=1;
}
if ( (Fpara=fopen(Filepara,"w")) == NULL )
{perror("Unable to open parameter file");
ierror=1;
}
if (ierror==1)
{exit(1);
}
return;
}
void openmaster1(void)
{ int ierror;
ierror=0;
if ( (Fmas=fopen(Filemaster,"r+")) == NULL )
{perror("Unable to open master file");
ierror=1;
}
if ( (Fpara=fopen(Filepara,"r+")) == NULL )
{perror("Unable to open parameter file");
ierror=1;
}
if (ierror==1)
{exit(1);
}
return;
}
void closemaster(void)
{ fclose(Fmas);
fclose(Fpara);
return;
}
void openlog(void)
{ if ( (Flog=fopen(Filelog,"a+")) == NULL )
{perror("Unable to open log file");
exit(1);
}
return;
}
void closelog(void)
{ fclose(Flog);
return;
}
void printmessage(char *message, FILE *f)
{ fprintf(f,"%s",message);
return;
}
int menu(void)
{ int ichoice;
char buffer[BUFSIZE];
printf("\n\n"
"1 -- make changes\n"
"2 -- add new records\n"
"3 -- delete records\n"
"4 -- inspect records\n"
"9 -- exit\n\n"
"Choice -> ");
L20:
gets(buffer);
sscanf(buffer,"%d",&ichoice);
/* ichoice = -999 means create master file. This is not
shown in order that accidental overwrite of master
file may be avoided
*/
if (ichoice == 1 || ichoice == 2 || ichoice == 3 || ichoice ==4
|| ichoice == 9 || ichoice == -999 )
{return ichoice;
}
else
{printscreen("\n *** 1,2,3 or 9 please *** \nChoice -> ");
goto L20;
}
}
boolean confirm(char *message)
{ char buffer[BUFSIZE];
int c, i;
printf("%s",message);
gets(buffer);
/* This skips over leading blanks in the answer */
for (i=0;i<BUFSIZE;i++)
{c=buffer[i];
if ( c != ' ' )
{goto L20;
}
}
assert(0);
L20:
if (c=='y' || c=='Y')
{return 1;
}
else
{return 0;
}
}
/* This subroutine inserts a record in Array[] */
boolean db_insert(char *key, char *data)
{ Isamrec *ptr, *ptr2, *preturn;
int iret;
preturn = db_exists(key);
if (preturn != NULL)
{if (preturn->iactiveflag == 1) /* Illegal to insert an existing
record */
{return 0;
}
else
{movekey(preturn->key, key); /* Recover a deleted record */
movedata(preturn->data, data);
preturn->iactiveflag = 1;
return 1;
}
}
ptr2 = &(Array[Ipool]);
if (Ipool == 0)
{goto L100;
}
ptr=&(Array[0]);
L20:
iret = compare(ptr->key, key);
if (iret < 0)
{if (ptr->pright == -1)
{ptr->pright = Ipool;
goto L100;
}
else
{ptr = &(Array[ptr->pright]);
goto L20;
}
}
else if (iret > 0)
{if (ptr->pleft == -1)
{ptr->pleft = Ipool;
goto L100;
}
else
{ptr = &(Array[ptr->pleft]);
goto L20;
}
}
else
{assert(0);
}
L100:
movekey(ptr2->key, key);
movedata(ptr2->data, data);
ptr2->iactiveflag = 1;
ptr2->pleft = -1; /* -1 is NULL here */
ptr2->pright = -1;
Ipool++;
Nrec++;
if (Ipool > MSIZE - FUELLOW)
{printscreen("***STATIC MEMORY IS LOW NOW,\n"
"***YOU SHOULD INCREASE MSIZE AND\n"
"***RECOMPILE PROGRAM !!!!\n\n");
fprintf(Flog,"%s\n","***STATIC MEMORY IS LOW NOW,\n"
"***YOU SHOULD INCREASE MSIZE AND\n"
"***RECOMPILE PROGRAM !!!!\n\n");
}
return 1;
}
/* This subroutine replaces a record. */
void db_replace(Isamrec *ptr, char *data)
{ movedata(ptr->data, data);
return;
}
/* This subroutine checks if the record exists. If it exists,
it returns a pointer to a record in Array[],
else it returns NULL.
NOTICE : even if "iactiveflag = 0", yet db_exists(..) will
return the address. User should check "iactiveflag".
*/
Isamrec *db_exists(char *key)
{ Isamrec *ptr, *preturn;
ptr = &(Array[0]);
preturn = db_exists2(ptr, key);
return preturn;
}
Isamrec *db_exists2(Isamrec *ptr, char *key)
{ int ia;
Isamrec *pa, *preturn;
ia = ptr->pleft;
if (ia != -1)
{pa = &(Array[ia]);
preturn = db_exists2(pa, key);
if (preturn != NULL)
{return preturn;
}
}
if (compare(ptr->key, key) == 0)
{return ptr;
}
ia = ptr->pright;
if (ia != -1)
{pa = &(Array[ia]);
preturn = db_exists2(pa, key);
if (preturn != NULL)
{return preturn;
}
}
return NULL;
}
/* This subroutine writes the Array[] as well as the parameter file.
It then closes both files. In doing so, the data are "flushed"
onto disc. It then reopens the files.
*/
void db_sync(void)
{ writearray();
closemaster();
openmaster1();
return;
}
/* This subroutine dumps Array[] onto file */
void writearray(void)
{ int iret;
rewind(Fmas);
iret = fwrite(Array, sizeof(Isamrec), Nrec, Fmas);
assert(iret >= Nrec);
rewind(Fpara);
iret = fprintf(Fpara,"%d %d\n", Nrec, Ipool);
assert(iret>0);
return;
}
/* This subroutine reads Array[] from master file */
void readarray(void)
{ int iret;
rewind(Fpara);
iret = fscanf(Fpara,"%d%d",&Nrec, &Ipool);
#if (DEBUG)
printf("In readarray() : Nrec = %d, Ipool = %d\n",Nrec,Ipool);
#endif
assert(iret>=2);
rewind(Fmas);
iret = fread(Array, sizeof(Isamrec), Nrec, Fmas);
assert(iret >= Nrec);
Inflag = 1;
return;
}
static void db_sorta(int ip)
{ Isamrec *p;
int ia, ib;
p=&(Array[ip]);
ia = p->pleft;
if (ia != -1)
{db_sorta(ia);
}
Isortarray[Isort]= ip;
Isort++;
ib = p->pright;
if (ib != -1)
{db_sorta(ib);
}
return;
}
static void db_sort(void)
{ Isort=0;
db_sorta(0);
return;
}
/* This prompts the user to enter a key.
On quit (= ****), it returns 0,
Otherwise, it returns 1, together with an Isamrec address
"Isamrec *p" - pointer to the record with the
desired key. It also checks if the record have been
deleted.
If the list doesn't contain what the use wants, it
returns 2.
*/
#define LINECOUNT 20
int promptrec(Isamrec **p)
{ char buffer[BUFSIZE], *pchar;
Isamrec *pret;
int i, nmatch, linecount, iwhich;
L20:
printf("( **** = quit )\n%s",Promptmessage);
gets(buffer);
if ( strcmp(buffer,"****") == 0 )
{return 0;
}
if (strlen(buffer)==0)
{goto L20;
}
pret = db_exists(buffer);
if (pret != NULL)
{ if (pret->iactiveflag == 1)
{*p = pret;
return 1;
}
else
{printscreen(" *** RECORD HAVE BEEN DELETED\n\n");
return 0;
}
}
/* If the record doesn't exist, then it searches for all
keys a substring of which matches the input
*/
for (nmatch=0, i=0; i<Nrec; i++)
{if (Array[i].iactiveflag == 0)
{continue;
}
pchar = strstr(Array[i].key, buffer);
#if (DEBUG)
printf("i= %2d (%s) (%s) (%p)\n",i, Array[i].key, buffer, pchar);
#endif
if (pchar != NULL)
{Imatch[nmatch]=i;
nmatch++;
if (nmatch >= MATCHSIZE)
{printscreen(" *** TOO MANY MATCHES, REST DISCARDED\n\n");
break;
}
}
}
if (nmatch == 0)
{printscreen(" *** No such key, or part of such key \n\n");
return 2;
}
if (nmatch == 1)
{*p = &(Array[Imatch[0]]);
return 1;
}
#if (DEBUG)
printf("Imatch array\n");
for (i=0;i<nmatch;i++)
{printf("%4d",Imatch[i]);
}
printf("\n");
#endif
for (linecount=0, i=0; i<nmatch; i++)
{printf("(%5d) %s\n", i, Array[Imatch[i]].key);
linecount++;
if (linecount >= LINECOUNT)
{if (linecount == nmatch)
{break;
}
printf("\n -- More --\n");
gets(buffer);
linecount=0;
}
}
L40:
printf("Enter number (**** = quit) -> ");
gets(buffer);
if (strcmp(buffer,"****") == 0)
{return 2;
}
sscanf(buffer,"%d",&iwhich);
if (!(iwhich >= 0 && iwhich < nmatch))
{printscreen(" *** Number out of range \n\n");
goto L40;
}
#if (DEBUG)
printf("iwhich %d\n",iwhich);
#endif
*p=&(Array[Imatch[iwhich]]);
return 1;
}
void updateinitialization(void)
{ if (Inflag==0)
{openmaster1();
readarray();
}
return;
}
void delete(void)
{ Isamrec *ptr;
Mrec *pp;
int iret;
updateinitialization();
printmessage("\n\nThe following records have been deleted\n\n",Flog);
L20:
iret = promptrec(&ptr);
if (iret == 0)
{return;
}
if (iret == 2)
{goto L20;
}
pp = (Mrec *)ptr->data;
displayrec(pp);
if (confirm("\n *** Are you sure you want to delete this (y,n) ? -> "))
{ptr->iactiveflag = 0;
printrec(pp , Flog);
printf(" *** DELETED *** \n\n");
}
else
{printf(" *** NO CHANGE ***\n\n");
}
goto L20;
}
void add(void)
{ Mrec temp, temp2;
int ireturn;
/* Initialization */
updateinitialization();
printmessage("\n\nThe following records have been added\n\n",Flog);
/* Main loop */
L20:
ireturn = inputrec(&temp);
if (ireturn == 0)
{return;
}
L40:
displayrec(&temp);
if (!confirm(" *** O.K. to write ? (y, n) -> "))
{temp2 = getnew(&temp);
temp = temp2;
goto L40;
}
if (insertrec(&temp))
{printrec(&temp, Flog);
}
else
{printscreen(" *** ERROR : Record with same key already exists\n"
" *** No insertion made \n\n");
}
goto L20;
}
void create()
{ Mrec temp, temp2;
Isamrec *p;
int ireturn, i;
/* Initialization pertaining to master file creation */
Nrec=0;
Ipool=0;
for (i=0; i<MSIZE ; i++)
{p = &(Array[i]);
p->pleft = -1;
p->pright = -1;
}
printmessage("MASTER FILE CREATION\n"
"--------------------\n\n", Flog);
/* Main loop */
L20:
ireturn = inputrec(&temp);
if (ireturn == 0)
{goto L100;
}
L40:
displayrec(&temp);
if (!confirm(" *** O.K. to write ? (y, n) -> "))
{temp2 = getnew(&temp);
temp = temp2;
goto L40;
}
if (insertrec(&temp))
{printrec(&temp, Flog);
}
else
{printscreen(" *** ERROR : Record with same key already exists\n"
" *** No insertion made \n\n");
}
goto L20;
/* Now the whole Array is written onto file */
L100:
openmaster0();
writearray();
closemaster();
closelog();
exit(0);
}
void change(void)
{ Isamrec *ptr;
Mrec temp, temp2, recstore;
int iret;
/* Initialization */
updateinitialization();
printmessage("\n\nThe following records have been changed\n\n",Flog);
L20:
iret = promptrec(&ptr);
if (iret == 0)
{return;
}
if (iret == 2)
{goto L20;
}
movedata((char *) &temp,(char *)ptr->data);
recstore=temp; /*Notice that structure may be used in
assignment statement */
displayrec(&temp);
L40:
temp2 = getnew(&temp);
displayrec(&temp2);
if (!confirm(" *** Satisfied with the change ? (y, n) -> "))
{temp = temp2; /* Note structure assignment */
goto L40;
}
if (confirm(" *** O.K. to write ? (y, n) -> "))
{printmessage("Original :\n",Flog);
printrec(&recstore, Flog);
db_replace(ptr, (char *)&temp2);
printmessage("Changed to :\n", Flog);
printrec(&temp2, Flog);
printscreen(" *** CHANGED ***\n\n");
}
else
{printscreen(" *** NO CHANGE ***\n\n");
}
goto L20;
}
void inspect(void)
{ Isamrec *ptr;
Mrec *pp;
int iret;
updateinitialization();
L20:
iret = promptrec(&ptr);
if (iret == 0)
{return;
}
if (iret == 2)
{goto L20;
}
pp = (Mrec *)ptr->data;
displayrec(pp);
goto L20;
}
int main()
{ int ichoice;
openlog();
L20:
ichoice = menu();
if (ichoice == 1)
{change();
}
else if (ichoice == 2 )
{add();
}
else if (ichoice == 3 )
{delete();
}
else if (ichoice == 4 )
{inspect();
}
else if (ichoice == 9 )
{goto L100;
}
else if (ichoice == -999)
{create();
}
else
{assert(0);
}
goto L20;
L100:
if (Inflag == 1)
{writearray();
closemaster();
}
closelog();
return 0;
}
In these 10 chapters, you can see that C is a very versatile language. Moreover, it is not difficult to learn. Once you have overcome some initial obstacles, you should enjoy writing programs with this language.
It is my opinion that we teach people Qbasic and C. They are not difficult to learn. Once they have learned Qbasic, they are able to write many programs already. When they have learned C, the possibilities are much greater.
If someone learns computer by reading books on commercial packages, they only learn the interfaces, and different designers use different interfaces, and that would be hard and tedious.
But if they learn Qbasic programming, they can write programs after a very short time, and programming would be an enjoyable task !
| [Previous] | [Home] | [Next] |