auto import from //depot/cupcake/@135843
diff --git a/tools/apriori/rangesort.c b/tools/apriori/rangesort.c
new file mode 100644
index 0000000..b0295e8
--- /dev/null
+++ b/tools/apriori/rangesort.c
@@ -0,0 +1,317 @@
+#include <common.h>
+#include <debug.h>
+#include <rangesort.h>
+
+#define PARALLEL_ARRAY_SIZE (5)
+
+struct range_list_t {
+ range_t *array;
+#ifdef DEBUG
+ int is_sorted;
+#endif
+ int array_length;
+ int num_ranges;
+};
+
+range_list_t* init_range_list(void) {
+ range_list_t *ranges = (range_list_t *)MALLOC(sizeof(range_list_t));
+
+ ranges->array = (range_t *)MALLOC(PARALLEL_ARRAY_SIZE*sizeof(range_t));
+ ranges->array_length = PARALLEL_ARRAY_SIZE;
+ ranges->num_ranges = 0;
+#ifdef DEBUG
+ ranges->is_sorted = 0;
+#endif
+ return ranges;
+}
+
+void destroy_range_list(range_list_t *ranges) {
+ int idx;
+ for (idx = 0; idx < ranges->num_ranges; idx++) {
+ if (ranges->array[idx].user_dtor) {
+ ASSERT(ranges->array[idx].user);
+ ranges->array[idx].user_dtor(ranges->array[idx].user);
+ }
+ }
+ FREE(ranges->array);
+ FREE(ranges);
+}
+
+static inline int CONTAINS(range_t *container, range_t *contained) {
+ return container->start <= contained->start && contained->length &&
+ (container->start + container->length >
+ contained->start + contained->length);
+}
+
+static inline int IN_RANGE(range_t *range, GElf_Off point) {
+ return
+ range->start <= point &&
+ point < (range->start + range->length);
+}
+
+static inline int INTERSECT(range_t *left, range_t *right) {
+ return
+ (IN_RANGE(left, right->start) &&
+ IN_RANGE(right, left->start + left->length)) ||
+ (IN_RANGE(right, left->start) &&
+ IN_RANGE(left, right->start + right->length));
+}
+
+static int range_cmp_for_search(const void *l, const void *r) {
+ range_t *left = (range_t *)l, *right = (range_t *)r;
+ if (INTERSECT(left, right) ||
+ CONTAINS(left, right) ||
+ CONTAINS(right, left)) {
+ return 0;
+ }
+ return left->start - right->start;
+}
+
+static inline void run_checks(const void *l, const void *r) {
+ range_t *left = (range_t *)l, *right = (range_t *)r;
+ if (CONTAINS(left, right)) {
+ if (left->err_fn)
+ left->err_fn(ERROR_CONTAINS, left, right);
+ FAILIF(1, "Range sorting error: [%lld, %lld) contains [%lld, %lld)!\n",
+ left->start, left->start + left->length,
+ right->start, right->start + right->length);
+ }
+ if (CONTAINS(right, left)) {
+ if (right->err_fn)
+ right->err_fn(ERROR_CONTAINS, left, right);
+ FAILIF(1, "Range sorting error: [%lld, %lld) contains [%lld, %lld)!\n",
+ right->start, right->start + right->length,
+ left->start, left->start + left->length);
+ }
+ if (INTERSECT(left, right)) {
+ if (left->err_fn)
+ left->err_fn(ERROR_OVERLAPS, left, right);
+ FAILIF(1, "Range sorting error: [%lld, %lld)and [%lld, %lld) intersect!\n",
+ left->start, left->start + left->length,
+ right->start, right->start + right->length);
+ }
+}
+
+static int range_cmp(const void *l, const void *r) {
+ run_checks(l, r);
+ range_t *left = (range_t *)l, *right = (range_t *)r;
+ return left->start - right->start;
+}
+
+void add_unique_range_nosort(
+ range_list_t *ranges,
+ GElf_Off start,
+ GElf_Off length,
+ void *user,
+ void (*err_fn)(range_error_t, range_t *, range_t *),
+ void (*user_dtor)(void * ))
+{
+ if (ranges->num_ranges == ranges->array_length) {
+ ranges->array_length += PARALLEL_ARRAY_SIZE;
+ ranges->array = REALLOC(ranges->array,
+ ranges->array_length*sizeof(range_t));
+ }
+ ranges->array[ranges->num_ranges].start = start;
+ ranges->array[ranges->num_ranges].length = length;
+ ranges->array[ranges->num_ranges].user = user;
+ ranges->array[ranges->num_ranges].err_fn = err_fn;
+ ranges->array[ranges->num_ranges].user_dtor = user_dtor;
+ ranges->num_ranges++;
+}
+
+range_list_t *sort_ranges(range_list_t *ranges) {
+ if (ranges->num_ranges > 1)
+ qsort(ranges->array, ranges->num_ranges, sizeof(range_t), range_cmp);
+ ranges->is_sorted = 1;
+ return ranges;
+}
+
+range_t *find_range(range_list_t *ranges, GElf_Off value) {
+#if 1
+ int i;
+ for (i = 0; i < ranges->num_ranges; i++) {
+ if (ranges->array[i].start <= value &&
+ value < ranges->array[i].start + ranges->array[i].length)
+ return ranges->array + i;
+ }
+ return NULL;
+#else
+ ASSERT(ranges->is_sorted); /* The range list must be sorted */
+ range_t lookup;
+ lookup.start = value;
+ lookup.length = 0;
+ return
+ (range_t *)bsearch(&lookup,
+ ranges->array, ranges->num_ranges, sizeof(range_t),
+ range_cmp_for_search);
+#endif
+}
+
+int get_num_ranges(const range_list_t *ranges)
+{
+ return ranges->num_ranges;
+}
+
+range_t *get_sorted_ranges(const range_list_t *ranges, int *num_ranges) {
+ ASSERT(ranges->is_sorted); /* The range list must be sorted */
+ if (num_ranges) {
+ *num_ranges = ranges->num_ranges;
+ }
+ return ranges->array;
+}
+
+GElf_Off get_last_address(const range_list_t *ranges) {
+ ASSERT(ranges->num_ranges);
+ return
+ ranges->array[ranges->num_ranges-1].start +
+ ranges->array[ranges->num_ranges-1].length;
+}
+
+static void handle_range_error(range_error_t err,
+ range_t *left, range_t *right) {
+ switch (err) {
+ case ERROR_CONTAINS:
+ ERROR("ERROR: section (%lld, %lld bytes) contains "
+ "section (%lld, %lld bytes)\n",
+ left->start, left->length,
+ right->start, right->length);
+ break;
+ case ERROR_OVERLAPS:
+ ERROR("ERROR: Section (%lld, %lld bytes) intersects "
+ "section (%lld, %lld bytes)\n",
+ left->start, left->length,
+ right->start, right->length);
+ break;
+ default:
+ ASSERT(!"Unknown range error code!");
+ }
+
+ FAILIF(1, "Range error.\n");
+}
+
+static void destroy_contiguous_range_info(void *user) {
+ contiguous_range_info_t *info = (contiguous_range_info_t *)user;
+ FREE(info->ranges);
+ FREE(info);
+}
+
+static void handle_contiguous_range_error(range_error_t err,
+ range_t *left,
+ range_t *right)
+{
+ contiguous_range_info_t *left_data =
+ (contiguous_range_info_t *)left->user;
+ ASSERT(left_data);
+ contiguous_range_info_t *right_data =
+ (contiguous_range_info_t *)right->user;
+ ASSERT(right_data);
+
+ PRINT("Contiguous-range overlap error. Printing contained ranges:\n");
+ int cnt;
+ PRINT("\tLeft ranges:\n");
+ for (cnt = 0; cnt < left_data->num_ranges; cnt++) {
+ PRINT("\t\t[%lld, %lld)\n",
+ left_data->ranges[cnt].start,
+ left_data->ranges[cnt].start + left_data->ranges[cnt].length);
+ }
+ PRINT("\tRight ranges:\n");
+ for (cnt = 0; cnt < right_data->num_ranges; cnt++) {
+ PRINT("\t\t[%lld, %lld)\n",
+ right_data->ranges[cnt].start,
+ right_data->ranges[cnt].start + right_data->ranges[cnt].length);
+ }
+
+ handle_range_error(err, left, right);
+}
+
+range_list_t* get_contiguous_ranges(const range_list_t *input)
+{
+ ASSERT(input);
+ FAILIF(!input->is_sorted,
+ "get_contiguous_ranges(): input range list is not sorted!\n");
+
+ range_list_t* ret = init_range_list();
+ int num_ranges;
+ range_t *ranges = get_sorted_ranges(input, &num_ranges);
+
+ int end_idx = 0;
+ while (end_idx < num_ranges) {
+ int start_idx = end_idx++;
+ int old_end_idx = start_idx;
+ int total_length = ranges[start_idx].length;
+ while (end_idx < num_ranges) {
+ if (ranges[old_end_idx].start + ranges[old_end_idx].length !=
+ ranges[end_idx].start)
+ break;
+ old_end_idx = end_idx++;
+ total_length += ranges[old_end_idx].length;
+ }
+
+ contiguous_range_info_t *user =
+ (contiguous_range_info_t *)MALLOC(sizeof(contiguous_range_info_t));
+ user->num_ranges = end_idx - start_idx;
+ user->ranges = (range_t *)MALLOC(user->num_ranges * sizeof(range_t));
+ int i;
+ for (i = 0; i < end_idx - start_idx; i++)
+ user->ranges[i] = ranges[start_idx + i];
+ add_unique_range_nosort(ret,
+ ranges[start_idx].start,
+ total_length,
+ user,
+ handle_contiguous_range_error,
+ destroy_contiguous_range_info);
+ }
+
+ return ret;
+}
+
+range_list_t* subtract_ranges(const range_list_t *r, const range_list_t *s)
+{
+ ASSERT(r); ASSERT(r->is_sorted);
+ ASSERT(s); ASSERT(s->is_sorted);
+
+ range_list_t *result = init_range_list();
+
+ int r_num_ranges, r_idx;
+ range_t *r_ranges = get_sorted_ranges(r, &r_num_ranges);
+ ASSERT(r_ranges);
+
+ int s_num_ranges, s_idx;
+ range_t *s_ranges = get_sorted_ranges(s, &s_num_ranges);
+ ASSERT(s_ranges);
+
+ s_idx = 0;
+ for (r_idx = 0; r_idx < r_num_ranges; r_idx++) {
+ GElf_Off last_start = r_ranges[r_idx].start;
+ for (; s_idx < s_num_ranges; s_idx++) {
+ if (CONTAINS(&r_ranges[r_idx], &s_ranges[s_idx])) {
+ if (last_start ==
+ r_ranges[r_idx].start + r_ranges[r_idx].length) {
+ break;
+ }
+ if (last_start == s_ranges[s_idx].start) {
+ last_start += s_ranges[s_idx].length;
+ continue;
+ }
+ INFO("Adding subtracted range [%lld, %lld)\n",
+ last_start,
+ s_ranges[s_idx].start);
+ add_unique_range_nosort(
+ result,
+ last_start,
+ s_ranges[s_idx].start - last_start,
+ NULL,
+ NULL,
+ NULL);
+ last_start = s_ranges[s_idx].start + s_ranges[s_idx].length;
+ } else {
+ ASSERT(!INTERSECT(&r_ranges[r_idx], &s_ranges[s_idx]));
+ break;
+ }
+ } /* while (s_idx < s_num_ranges) */
+ } /* for (r_idx = 0; r_idx < r_num_ranges; r_idx++) */
+
+ return result;
+}
+
+