| chsalvia@gmail.com 2007-06-15, 4:20 am |
| I'm trying to implement a basic external merge sort in C/C++. I've
put together the following draft of the function. It's not complete
(there is no return value checking or memory freeing, etc.) For
testing purposes, it tries to sort a 10MB file reading in 1MB at a
time. The file is simply a large array of random integers.
(See http://en.wikipedia.org/wiki/External_sort for the basic
algorithm I'm trying to implement.)
The algorithm seems fairly simple, and the code I wrote seems to work
fine until the last phase, when it has to perform n-way merge sorts on
multiple lists. But after that something goes wrong. The output file
is not properly sorted. I've gone over it a number of times, but
can't figure out the problem.
Here is the code:
#define EXT_MERGE_CHUNK_SIZE 1048576
/* Struct used to perform n-way merge sort */
struct merge_iterator {
int* ptr;
void* end;
};
/* Input buffer struct */
struct ibuffer_s {
int* storage;
uint64_t offset;
uint64_t end;
};
/* Return index of largest element in array */
inline uint32_t merge_sort_compare(merge_iterator* array, int n) {
register unsigned int i = 0, result = *array[0].ptr, idx = 0;
for (i = 0; i < n; ++i) {
if (*array[i].ptr < result) {
result = *array[i].ptr;
idx = i;
}
}
return idx;
}
int external_mergesort(char* path)
{
int src_fd = open(path, O_RDWR);
struct stat file_info;
fstat(src_fd, &file_info);
const size_t chunk_size = prev_mult(sizeof(int),
EXT_MERGE_CHUNK_SIZE);
const uint64_t file_size = file_info.st_size;
const uint32_t nchunks = (uint32_t) ceil((float) file_size/
chunk_size);
if (file_size % sizeof(int) != 0) {
close(src_fd);
return -1;
}
int* buffer = (int*) malloc(chunk_size);
/* Sort each chunk in source file and write back to disk */
size_t read_size = MINVAL(chunk_size, file_size), nelem, offset
= 0;
ssize_t read_bytes;
for (unsigned i = 0; i < nchunks; ++i) {
read_size = MINVAL(read_size, file_size - offset);
nelem = read_size/sizeof(int);
pread(src_fd, buffer, read_size, offset);
qsort(buffer, nelem, sizeof(int), compare);
pwrite(src_fd, buffer, read_size, offset);
offset += read_size;
}
/* Second phase: create a single sorted file */
int dest_fd = open("/test/output", O_WRONLY | O_APPEND | O_CREAT
| O_TRUNC);
const size_t ibuffer_length = prev_mult(sizeof(int), chunk_size/
(nchunks-1));
const size_t ibuffer_nelems = ibuffer_length/sizeof(int);
ibuffer_s* ibuffer = (ibuffer_s*) malloc(sizeof(ibuffer_s) *
nchunks);
size_t ibuffer_size = nchunks;
size_t poffset = 0;
for (unsigned i = 0; i < nchunks; ++i) {
ibuffer[i].storage = (int*) malloc(ibuffer_length);
ibuffer[i].offset = poffset;
poffset += chunk_size;
ibuffer[i].end = MINVAL(poffset, file_size -
ibuffer[i].end);
}
merge_iterator* p_array = (merge_iterator*)
malloc(sizeof(merge_iterator) * nchunks);
size_t p_array_size = nchunks;
register int* out = buffer;
const void* end_out = (byte*) buffer + chunk_size;
size_t idx, npending = nchunks;
/* Read in mini-chunks of each chunk of file */
for (; npending > 0; ) {
p_array.reserve(npending);
for (unsigned i = 0; i < npending; ) {
read_size = MINVAL(ibuffer_length, ibuffer[i].end -
ibuffer[i].offset);
if (read_size == 0) {
--npending;
remove_element(ibuffer, sizeof(ibuffer_s),
ibuffer_size)
remove_element(p_array,
sizeof(merge_iterator), p_array_size)
continue;
}
p_array[i].ptr = ibuffer[i].storage;
p_array[i].end = (byte*) ibuffer[i].storage +
MINVAL(ibuffer_length, ibuffer[i].end - ibuffer[i].offset);
ibuffer[i].offset += pread(src_fd,
ibuffer[i].storage, read_size, ibuffer[i].offset);
++i;
}
/* Perform n-way merge sort of all input buffers and
output to sorted file */
while (p_array_size > 0) {
idx = merge_sort_compare(p_array.data(),
p_array.size());
*out = *(p_array[idx].ptr++);
if (p_array[idx].ptr >= p_array[idx].end)
remove_element(p_array,
sizeof(merge_iterator), p_array_size)
if (out >= end_out) {
write(dest_fd, buffer, (byte*) out - (byte*)
buffer);
out = buffer;
}
}
write(dest_fd, buffer, (byte*) out - (byte*)
buffer);
out = buffer;
}
}
|