From 8a27889d505b07d91ecd03ad1cfeb818b9b440f7 Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Wed, 29 Oct 2014 20:32:33 -0500 Subject: Add instrumentation Track the number of comparisons, swaps, and rotations performed in each part of the sorting algorithm. --- grailsort.c | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'grailsort.c') diff --git a/grailsort.c b/grailsort.c index 6f63701..9eff4d6 100644 --- a/grailsort.c +++ b/grailsort.c @@ -6,6 +6,7 @@ #include "sorters.h" #include "common.h" +#include "counts.h" static inline void *tail(char *base, size_t nmel, size_t width) { @@ -15,13 +16,19 @@ static inline void *tail(char *base, size_t nmel, size_t width) /* get index of last block whose head is less than the previous block's tail */ static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t width, cmpfun cmp) { + struct counts snapshot = counts[CURRENT]; + for (char *cur = tail(base, bcount, bwidth); --bcount; cur -= bwidth) if (cmp(cur - width, cur) > 0) break; + + add_counts(counts + LAST_OVERLAP, &snapshot); return bcount; } size_t merge(char *buf, char *a, char *b, size_t bufnmel, size_t anmel, size_t bnmel, size_t width, cmpfun cmp) { + struct counts snapshot = counts[CURRENT]; + while (bnmel) { char *a_tail = tail(a, anmel, width); char *b_tail = tail(b, bnmel, width); @@ -36,6 +43,8 @@ size_t merge(char *buf, char *a, char *b, size_t bufnmel, size_t anmel, size_t b } bufnmel--; } + + add_counts(counts + MERGE, &snapshot); return anmel; } @@ -81,7 +90,10 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) blocks = overlap; } + struct counts snapshot = counts[CURRENT]; rotate(base, buf-base + bufnmel*width, buf-base); + add_counts(counts + MOVE_BUFFER, &snapshot); + grailsort(base, bufnmel, width, cmp); distribute_buffer(base, bufnmel, nmel - bufnmel, width, cmp); } -- cgit v1.2.3