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.
How to guarantee the array is self-increasing? This kind of dynamic arrays have been written by me many times.
The only difficulty is how to program and debug C in Linux.
C.The idea of programTo 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.
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,