Dynamic Pointer Array

A. Second Edition

This is comp444 lab1 and it is concentrated on file operations such as searching, replacing, copying...

I want to keep this simple version for possible future modification. In this version, I rearrange the structure

of "fileBuf" by seperating it from "searchString" module. And add a new dynamic array module.

B.The problem

To simulate a class in C++ by using a structure which book keeps the size of array. To make it general, I design

to ask user to pass its own comparing and display method.

The function pointer type in C is defined like:

typedef returnType funcTypeName(argType1,argType2...);

And when you are using function pointer, you need to declare it as pointer:

returnType realFunction(argType1, funcTypeName* funcPtr);

There is some subtle difference between C++.

It takes me more than two hours to find a simple pointer error with GDB. It is really a pain when you are

starving.

D.The major functions

E.Further improvement

F.File listing

1. myhead.h

2. searchString.h

3. searchString.c

4. main.c

5. errHandle.c

6. fileBuf.h

7. fileBuf.c

8. dynaArray.h

9. dynaArray.c

10. makefile

file name: myhead.h

#ifndef MYHEAD_H
#define MYHEAD_H

#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <dirent.h>
#include <unistd.h>
#include <string.h>
#include <fcntl.h>

typedef int bool;

#define TRUE  1
#define FALSE 0

//for a particular file NAME, NOT path
//const int MaxNameLength=20;
#define MaxNameLength  20 
#define BuffSize   128

void errHandle(char* msg);
	
#endif

file name: searchString.h

#ifndef SEARCHSTRING_H
#define SEARCHSTRING_H

#include "myhead.h"
#include "fileBuf.h"

int findString(char* fileName, char* str);

//search in a file with my own file information struct FileBuf*, 
//target is the string for searching
//repeating call this function and return each location, 
//return -1 indicating end of file
int searchString(FilePtr stream, char* target);


#endif

file name: searchString.c

#include "myhead.h"
#include "searchString.h"
#include "fileBuf.h"

bool findString(char* fileName, char* str)
{
	int fd, n=0;
	FilePtr stream;
	bool result=FALSE;
	if ((fd=open(fileName, O_RDONLY))<0)
	{
		errHandle("cannot open searching files\n");
	}
	if ((stream=openFile(fd))==NULL)
	{
		errHandle("openfile error\n");
	}
	while ((n=searchString(stream, str))!=-1)
	{
		result=TRUE;
		printf("test: find target at %d\n", n);
	}
	return result;
}



//starting a particular file offset and search the target string
//if found return the file offset of target, else return -1
int searchString(FilePtr stream, char* target)
{
	int stringLength=strlen(target);
	char ch;
	int result=-1;//this is the starting offset of word
	//the length of word compared
	int length;
	int mode;
	length=0;
	mode=FindNextWord;//initial status
	//-1 means EOF
	while ((ch=nextChar(stream))!=-1)
	{
		switch (mode)
		{
		case FindNextWord:
			if (isChar(ch))
			{
				//check the very first 
				if (ch==target[0])
				{
					mode=Comparing;
					length=1;//need to compare with next
					result=stream->offset-1;//as it already passed it
				}
				else
				{
					mode=SkipTillNext;
				}				
			}
			//else keep going
			break;
		case SkipTillNext:
			if (isBreak(ch))
			{
				mode=FindNextWord;
			}
			break;				
		case Comparing:
			//it is a match
			if (ch==target[length])
			{
				//a match then keep going
				length++;
			        //a white space
                        	if (length==stringLength)
                        	{
                                	return result;
                        	}
			}
			else
			{
				//it means mis-match
				mode=SkipTillNext;
			}
			break;
		}//switch
	}//while					
	return -1;
}		
						

		
	

		
file name: errHandle.c

#include "myhead.h"


void errHandle(char* msg)
{
	if (msg!=NULL)
	{
		perror(msg);
	}
	else
	{
		strerror(errno);
	}		
	exit(errno);
}
	

file name: fileBuf.h

#ifndef FILEBUF_H
#define FILEBUF_H

#include "myhead.h"


struct FileBuf
{
	int fd;
	int size;
	int offset;
	int cur;
	//char buf[128];
	char buf[BuffSize];
};

typedef struct FileBuf* FilePtr;


//define three mode and it is purely like DFA=Deterministic Finite Automaton
#define FindNextWord   	0
#define SkipTillNext	1
#define Comparing	2


//specify if it is white space char
//notice here, in C, there is no boolean type and I define it
//as alias of int in "myhead.h"
bool isBreak(char ch);

void copyFile(char* source, char* target);

void replace(int fd, int offset, char* str);

//my edition of getc
FilePtr openFile(int fd);

//a-z, A-Z
bool isChar(char ch);

//my edition of getc
char nextChar(struct FileBuf* stream);


//my version of fclose
void closeFile(FilePtr ptr);


#endif
		

file name: fileBuf.c

#include "fileBuf.h"

//the reason I don't want to combine both copy and replace together is
//that in the possible sorting like quick sort which is not stable sorting method
//the offset to be replaced in one file maybe sorted in different order,
//i.e. foo.txt 169 foo.txt 140 foo.txt 249
//in such situation, it is very unsafe to copy a chunk of file and then 
//replace. So, divide the job into TWO pass is a safe way.

//it is of course low efficiency to first copy and replace, but 
//it is easy to code
void copyFile(char* source, char* target)
{
	int fdOld, fdNew, n;
	char buf[BuffSize];
	if ((fdOld=open(source, O_RDONLY))<0)
	{
		errHandle("open error when copying file\n");
	}
	if ((fdNew=open(target, O_WRONLY|O_CREAT|O_TRUNC, S_IRUSR|S_IWUSR))<0)
	{
		errHandle("open error when copying file\n");
	}
	while ((n=read(fdOld, buf, BuffSize))!=0)
	{
		if (n!=write(fdNew, buf, n))
		{
			errHandle("write error when copying file\n");
		}
	}
}
	
void replace(int fd, int offset, char* str)
{
	int size;
	if (str==NULL)
	{
		printf("cannot replace empty string\n");
		return;
	}
	//strlen is just a function and it will be used more than once
	size=strlen(str);
	if (lseek(fd, offset, SEEK_SET)<0)
	{
		errHandle("lseek error when replacing\n");
	}
	if (size!=write(fd, str, size))
	{
		errHandle("write error when replace\n");
	}
	
}


//my version of fclose
void closeFile(FilePtr ptr)
{
	free(ptr);
}


//my edition of "fopen"
FilePtr openFile(int fd)
{
	FilePtr result=(FilePtr)malloc(sizeof(struct FileBuf));
	if (result==NULL)
	{
		errHandle("cannot allocate memory for FileBuf\n");
	}
	result->fd=fd;
	result->offset=0;
	if ((result->size=read(fd, result->buf, BuffSize))<0)
	{
		free(result);
		return NULL;
	}
	result->cur=0;
	return result;
}

//getc
char nextChar(FilePtr stream)
{
	//if buff is fully read
	if (stream->cur >= stream->size)
	{
		if (stream->size==0)//must be end of file
		{
			return -1;
			//return EOF;
		}
		//if erro happened during reading
		if ((stream->size=read(stream->fd, stream->buf, BuffSize))<0)
		{
			errHandle("read error of file buf\n");
		}
		//reset cur
		stream->cur=0;
	}
	//offset is always inc for each call
	stream->offset++;
	return stream->buf[stream->cur++];
}
	
//what is white space
bool isBreak(char ch)
{
	return (ch==' '||ch=='\t'||ch=='\n');
}

bool isChar(char ch)
{
	return ((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z'));
}

file name: dynaArray.h

#ifndef DYNAARRAY_H
#define DYNAARRAY_H

#include "myhead.h"

#define DefaultLength  20

//each is a pointer
struct DynaArray
{
	void** ptr;
	int len;//max size, the index of last node
	int cur;//current position, relative index of last node
	int fold;
};

typedef struct DynaArray* DynaArrayPtr;

//define a function pointer for comparing in sorting
typedef bool CompFunc(void* first, void* second);

//define a show func type
typedef void ShowFunc(void* ptr); 

//create with default length and fold is 1
DynaArrayPtr createArray();

//this can be only called internally after a node is added
void expand(DynaArrayPtr arrayPtr);


//this is typical C++ member function, 
void addEnd(DynaArrayPtr arrayPtr, void* ptr);//without sorting

//user need to supply with comp function, return true for first '<' second
//it must be strictly smaller, as equal used to indicate it is a copy
//the addOne function should return the index of node inserted, -1 if already there
int addOne(DynaArrayPtr arrayPtr, void* ptr, CompFunc* compFunc);

void displayArray(DynaArrayPtr arrayPtr, ShowFunc* showFunc); 
		
#endif	

file name: dynaArray.c

#include "dynaArray.h"

//user need to supply with comp function, return true for first '<' second
//it must be strictly smaller, as equal used to indicate it is a copy
//the addOne function should return the index of node inserted, -1 if already there
int addOne(DynaArrayPtr arrayPtr, void* ptr, CompFunc* compFunc)
{
	int pos=0, i;
	//1st case, there is no node in array
	while (pos<arrayPtr->len)
	{
		if (!compFunc(ptr, arrayPtr->ptr[pos]))
		{
			pos++;
		}
		else
		{
			if (ptr==arrayPtr->ptr[pos])
			{
				//2nd case, it is already there
				return -1;//it is a copy
			}
			//should insert here, and there must have space, shift first
			for (i=arrayPtr->len; i>pos; i--)
			{
				arrayPtr->ptr[i]=arrayPtr->ptr[i-1];
			}
			//3rd case, it is shifted first
			break;
		}
	}	
	arrayPtr->ptr[pos]=ptr;//insert
	arrayPtr->len++;
	arrayPtr->cur++;
	if (arrayPtr->cur==DefaultLength)
	{
		expand(arrayPtr);
	}		
}
		
//create with default length and fold is 1
DynaArrayPtr createArray()
{
	DynaArrayPtr result;
	if ((result=(DynaArrayPtr)malloc(DefaultLength*sizeof(void*)))==NULL)
	{
		errHandle("cannot alloc memory for dyna array creation\n");
	}
	result->len=0;//the actual number of pointers in array
	result->cur=0;//internal use only
	result->fold=1;
	
	if ((result->ptr=(void**)malloc(DefaultLength*sizeof(void*)))==NULL)
	{
		errHandle("cannot alloc memory for dyna array\n");
	}
	return result;
}

//user must pass a user-defined function pointer for displaying struct
void displayArray(DynaArrayPtr arrayPtr, ShowFunc* showFunc)
{
	int i;
	for (i=0; i<arrayPtr->len; i++)
	{
		showFunc(arrayPtr->ptr[i]);
	}
}


//this is typical C++ member function, 
void addEnd(DynaArrayPtr arrayPtr, void* ptr)
{
	arrayPtr->ptr[arrayPtr->len++]=ptr;
	arrayPtr->cur++;
	if (arrayPtr->cur==DefaultLength)
        {
                expand(arrayPtr);
        }

}

void expand(DynaArrayPtr arrayPtr)
{
	arrayPtr->fold++;
	if ((arrayPtr->ptr=realloc(arrayPtr->ptr, arrayPtr->fold*DefaultLength*sizeof(void*)))==NULL)
	{
		errHandle("expand error for dyna array\n");
	}
	arrayPtr->cur=0;//it should be
}	

file name: makefile

all:    main.o 
	@echo "make complete for main.o "

fileBuf.o : fileBuf.c fileBuf.h myhead.h
	@echo "compiling fileBuf.o..."
	gcc -g -c fileBuf.c -o fileBuf.o

errHandle.o : errHandle.c myhead.h
	@echo "compiling errHanle module..."
	gcc -g -c errHandle.c -o errHandle.o

main.o : searchString.o main.c errHandle.o myhead.h fileBuf.o dynaArray.o
	@echo "compiling main.o..." 
	gcc -g main.c searchString.o errHandle.o fileBuf.o dynaArray.o -o main.o

searchString.o : searchString.h searchString.c myhead.h
	@echo "compiling searchString.o..."
	gcc -g -c searchString.c -o searchString.o

dynaArray.o : dynaArray.h dynaArray.c myhead.h
	@echo "compiling dynaArray.o..."
	gcc -g -c dynaArray.c -o dynaArray.o

clear :
	@echo "clear up...\n"
	rm *.o

How to run?

1. Just run make and main.o

[qingz_hu@alamanni ~/lab1] % make
compiling main.o...
gcc -g main.c searchString.o errHandle.o fileBuf.o dynaArray.o -o main.o
make complete for main.o 
[qingz_hu@alamanni ~/lab1] % ./main.o
the following is the random generated array
84, 87, 78, 16, 94, 36, 87, 93, 50, 22, 63, 28, 91, 60, 64, 27, 41, 27, 73, 37, 12, 69, 68, 30, 83, 31, 63, 24, 68, 36, 30, 3, 

23, 59, 70, 68, 94, 57, 12, 43, 30, 74, 22, 20, 85, 38, 99, 25, 16, 71, 14, 27, 92, 81, 57, 74, 63, 71, 97, 82, 6, 26, 85, 28, 

37, 6, 47, 30, 14, 58, 25, 96, 83, 46, 15, 68, 35, 65, 44, 51, 88, 9, 77, 79, 89, 85, 4, 52, 55, 100, 33, 61, 77, 69, 40, 13, 

27, 87, 95, 40, 
now display the sorted array
3,4,6,6,9,12,12,13,14,14,15,16,16,20,22,22,23,24,25,25,26,27,27,27,27,28,28,30,30,30,30,31,33,35,36,36,37,37,38,40,40,41,43,

44,46,47,50,51,52,55,57,57,58,59,60,61,63,63,63,64,65,68,68,68,68,69,69,70,71,71,73,74,74,77,77,78,79,81,82,83,83,84,85,85,85,

87,87,87,88,89,91,92,93,94,94,95,96,97,99,100,