|
|
|
|
|
|
|
|
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.
|
Direct link: http://www.tovilevis.com
|