Go Back
C - Bubble sort and binary search on disk
The main functions are fbubble and fbinary_search:
unsigned fbubble (FILE* fp , int type_size, int (*fptr)(const void*, const void*)) {
	int pass = 1, i;
	bool swap = True;
	void *var1, *var2;
	int list_size = GetTotalRecords(fp, type_size);
	var1 = (void*)calloc(1,type_size);
	CheckAlloc(var1);
	var2 = (void*)calloc(1,type_size);
	CheckAlloc(var2);
	rewind(fp);
	while (pass < list_size && swap == True) {
		swap = False;
		for (i = 0; i < list_size - pass; i++) {
			seekSet(fp, i, type_size);
			ReadFromFile(fp, var1, type_size,1);
			seekSet(fp, i+1, type_size);
			ReadFromFile(fp, var2, type_size, 1);
			if ( fptr(var1, var2) < 0) {
				seekSet(fp, i, type_size);
				WriteToFile(fp, var2, type_size, 1);
				seekSet(fp, i+1, type_size);
				WriteToFile(fp, var1, type_size, 1);
				swap = True;
			}
		}
		pass++;
	}
	free(var1);
	free(var2);
	return list_size;
}

int fbinary_search(FILE* fp, const void *search_cust, int type_size, int (*fptr)(const void*, const void*)) {
	bool success = False;
	int first = 0, last, mid, index = -1;
	int result;
	void* var;
	int list_size = GetTotalRecords(fp, type_size);
	var = (void*)calloc(1,type_size);
	CheckAlloc(var);
	last = list_size-1;
	seekSet(fp, 0, type_size);
	while (first <= last && (success == False) ) {
		mid = (first +last) / 2;
		seekSet(fp, mid, type_size);
		ReadFromFile(fp, var, type_size,1);
		result = fptr(var, search_cust);
		if (result == 0) {
			index = mid;
			success = True;
		}
		else if (result < 0) {last = mid-1;}
		else first = mid +1;
	}
	free(var);
	return index;
}


Some functions that I used in the funtions above:
unsigned GetTotalRecords(FILE* fp, int TypeSize) {
	fseek(fp,0,SEEK_END);
	return ftell(fp)/TypeSize;
}

void seekSet(FILE* fp, int position, int type_size) {
	if (fseek(fp,position*type_size,SEEK_SET)) {
		perror("fseek failed!");
		exit(FSEEK_ERR);
	}
}

int ReadFromFile(FILE* fp, void* var, int var_size, int count) {
	if (fread(var, var_size, count, fp) != count) {
		if (ferror(fp)) {
			perror("Unable to read file!");
			exit(READ_ERR);
		}else{ return 0; }
	}
	return count;
}

int WriteToFile(FILE* fp, void* var, int var_size, int count) {
	if (fwrite(var, var_size, count, fp) != count) {
		perror("Unable to write file!");
		exit(WRITE_ERR);
	}
	return count;
}

void CheckAlloc(void* var) {
	if (var == NULL) {
		perror("Unable to allocate memory!");
		exit(ALLOC_ERR);
	}
}

int DoSomeChecks(const void* var1, const void* var2) {
	if (((Customer*)var1)->height == ((Customer*)var2)->height) return 0;
	return ((Customer*)var1)->height > ((Customer*)var2)->height ? -1 : 1;
}
All rights reserved to Tovi Levis. DO NOT copy or redistribute any content from this site.
Close