- the code that creates distance matrices was modified to accept array of sr_thread pointers - metrics.c was deleted and the distance matrix code was moved to distance.c (metrics.c contained different implementation of distance functions, probably left over after their rewrite in distance.c) - tests adjusted - python bindings adjusted to compile, the satyr.Distances constructor still only accepts GDB threads though
Related to #63 (does not close it, the python bindings still need more work).
Signed-off-by: Martin Milata mmilata@redhat.com --- include/Makefile.am | 1 - include/distance.h | 94 ++++++++++++ include/metrics.h | 219 ---------------------------- lib/Makefile.am | 1 - lib/cluster.c | 2 +- lib/distance.c | 160 ++++++++++++++++++++ lib/metrics.c | 409 ---------------------------------------------------- python/py_metrics.c | 14 +- satyr.c | 1 - tests/cluster.at | 3 +- tests/metrics.at | 3 +- tests/normalize.at | 1 - 12 files changed, 264 insertions(+), 644 deletions(-) delete mode 100644 include/metrics.h delete mode 100644 lib/metrics.c
diff --git a/include/Makefile.am b/include/Makefile.am index 89e0201..f72ec66 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -5,7 +5,6 @@ mainheaders_HEADERS = \ distance.h \ json.h \ location.h \ - metrics.h \ normalize.h \ operating_system.h \ report.h \ diff --git a/include/distance.h b/include/distance.h index aab94eb..53be6d7 100644 --- a/include/distance.h +++ b/include/distance.h @@ -86,6 +86,100 @@ sr_distance(enum sr_distance_type distance_type, struct sr_thread *thread1, struct sr_thread *thread2);
+/** + * @brief A distance matrix of stack trace threads. + * + * The distances are stored in a m-by-n two-dimensional array, where + * only entries (i, j) where i < j are actually stored. + */ +struct sr_distances +{ + int m; + int n; + float *distances; +}; + +/** + * Creates and initializes a new distances structure. + * @param m + * Number of rows. + * @param n + * Number of columns. + * @returns + * It never returns NULL. The returned pointer must be released by + * calling the function sr_distances_free(). + */ +struct sr_distances * +sr_distances_new(int m, int n); + +/** + * Creates a duplicate of the distances structure. + * @param distances + * It must be non-NULL pointer. The structure is not modified by calling + * this function. + * @returns + * This function never returns NULL. + */ +struct sr_distances * +sr_distances_dup(struct sr_distances *distances); + +/** + * Releases the memory held by the distances structure. + * @param distances + * If the distances is NULL, no operation is performed. + */ +void +sr_distances_free(struct sr_distances *distances); + +/** + * Gets the entry (i, j) from the distance matrix. + * @param distances + * It must be non-NULL pointer. + * @param i + * Row in the matrix. + * @param j + * Column in the matrix. + * @returns + * For entries (i, i) zero distance is returned and values returned for + * entries (i, j) and (j, i) are the same. + */ +float +sr_distances_get_distance(struct sr_distances *distances, int i, int j); + +/** + * Sets the entry (i, j) from the distance matrix. + * @param distances + * It must be non-NULL pointer. + * @param i + * Row in the matrix. + * @param j + * Column in the matrix. + * @param d + * Distance. + */ +void +sr_distances_set_distance(struct sr_distances *distances, + int i, + int j, + float d); + +/** + * Creates a distances structure by comparing threads. + * @param threads + * Array of threads. They are not modified by calling this function. + * @param m + * Compare first m threads from the array with other threads. + * @param n + * Number of threads in the passed array. + * @param dist_func + * Distance function which will be used to compare the threads. It's assumed to + * be symmetric and return zero distance for equal threads. + * @returns + * This function never returns NULL. + */ +struct sr_distances * +sr_threads_compare(struct sr_thread **threads, int m, int n, + enum sr_distance_type dist_type); #ifdef __cplusplus } #endif diff --git a/include/metrics.h b/include/metrics.h deleted file mode 100644 index 9deddf4..0000000 --- a/include/metrics.h +++ /dev/null @@ -1,219 +0,0 @@ -/* - metrics.h - - Copyright (C) 2010 Red Hat, Inc. - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License along - with this program; if not, write to the Free Software Foundation, Inc., - 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. -*/ -#ifndef SATYR_METRICS_H -#define SATYR_METRICS_H - -/** - * @file - * @brief Distance between stack trace threads. - */ - -#ifdef __cplusplus -extern "C" { -#endif - -#include <stdbool.h> - -struct sr_gdb_frame; -struct sr_gdb_thread; - -/* Jaro-Winkler distance: - * - * Gets number of matching function names(match_count) from both - * threads and number of transpositions in place(trans_count) if the - * transpositioned function names are not farther away than - * frame_count/2 - 1. Then computes the Jaro-Winkler distance - * according to the formula. NOTE: The Jaro-Winkler distance is not a - * metric distance as it does not satisfy the triangle inequality. - * Returns a number between 0 and 1: 0 = no similarity, 1 = similar - * threads - */ -float -sr_gdb_thread_jarowinkler_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2); - - -/* Jaccard distance: - * - * Gives a number representing the difference of the size of the - * intersection and union divided by the size of the union of two - * threads. Function names positions in the thread are not taken into - * account. Returns a number between 0 and 1: 0 = similar threads, 1 - * = no similarity - */ -float -sr_gdb_thread_jaccard_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2); - - -/* Levenshtein distance: - * - * Computes the distance of two threads creating a matrix of distances - * between all the frames in each thread. Returns a number - * representing how many function names need to be different in one - * thread to match all the function names in second thread at each - * respective positions or how many function names need to be - * different/transpositioned to have a match if the transposition - * argument is enabled. NOTE: With transpositions enabled the - * triangle inequality does not hold. The distance is always between - * 0 and n, where n is the frame count of longer thread 0 = similar - * threads, n = no similar function names - */ -int -sr_gdb_thread_levenshtein_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - bool transposition); - -/* Levenshtein distance returned with transpositions enabled and - * returned in interval [0, 1]. - */ -float -sr_gdb_thread_levenshtein_distance_f(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2); - -typedef int (*sr_gdb_frame_cmp_type)(struct sr_gdb_frame*, - struct sr_gdb_frame*); - -/* Following three functions are equivalent to the three above except - * that they take frame comparison function as an argument argument - */ -float -sr_gdb_thread_jarowinkler_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - sr_gdb_frame_cmp_type compare_func); - -float -sr_gdb_thread_jaccard_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - sr_gdb_frame_cmp_type compare_func); - -int -sr_gdb_thread_levenshtein_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - bool transposition, - sr_gdb_frame_cmp_type compare_func); - -/** - * @brief A distance matrix of stack trace threads. - * - * The distances are stored in a m-by-n two-dimensional array, where - * only entries (i, j) where i < j are actually stored. - */ -struct sr_distances -{ - int m; - int n; - float *distances; -}; - -/** - * Creates and initializes a new distances structure. - * @param m - * Number of rows. - * @param n - * Number of columns. - * @returns - * It never returns NULL. The returned pointer must be released by - * calling the function sr_distances_free(). - */ -struct sr_distances * -sr_distances_new(int m, int n); - -/** - * Creates a duplicate of the distances structure. - * @param distances - * It must be non-NULL pointer. The structure is not modified by calling - * this function. - * @returns - * This function never returns NULL. - */ -struct sr_distances * -sr_distances_dup(struct sr_distances *distances); - -/** - * Releases the memory held by the distances structure. - * @param distances - * If the distances is NULL, no operation is performed. - */ -void -sr_distances_free(struct sr_distances *distances); - -/** - * Gets the entry (i, j) from the distance matrix. - * @param distances - * It must be non-NULL pointer. - * @param i - * Row in the matrix. - * @param j - * Column in the matrix. - * @returns - * For entries (i, i) zero distance is returned and values returned for - * entries (i, j) and (j, i) are the same. - */ -float -sr_distances_get_distance(struct sr_distances *distances, int i, int j); - -/** - * Sets the entry (i, j) from the distance matrix. - * @param distances - * It must be non-NULL pointer. - * @param i - * Row in the matrix. - * @param j - * Column in the matrix. - * @param d - * Distance. - */ -void -sr_distances_set_distance(struct sr_distances *distances, - int i, - int j, - float d); - -/** - * A function which compares two threads. - */ -typedef float (*sr_dist_thread_type)(struct sr_gdb_thread *, - struct sr_gdb_thread *); - -/** - * Creates a distances structure by comparing threads. - * @param threads - * Array of threads. They are not modified by calling this function. - * @param m - * Compare first m threads from the array with other threads. - * @param n - * Number of threads in the passed array. - * @param dist_func - * Distance function which will be used to compare the threads. It's assumed to - * be symmetric and return zero distance for equal threads. - * @returns - * This function never returns NULL. - */ -struct sr_distances * -sr_gdb_threads_compare(struct sr_gdb_thread **threads, - int m, int n, - sr_dist_thread_type dist_func); - -#ifdef __cplusplus -} -#endif - -#endif diff --git a/lib/Makefile.am b/lib/Makefile.am index 277f53d..9e1db0c 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -38,7 +38,6 @@ libsatyr_la_SOURCES = \ koops_frame.c \ koops_stacktrace.c \ location.c \ - metrics.c \ normalize.c \ operating_system.c \ python_frame.c \ diff --git a/lib/cluster.c b/lib/cluster.c index 75c9f61..92d5304 100644 --- a/lib/cluster.c +++ b/lib/cluster.c @@ -19,7 +19,7 @@ */
#include "cluster.h" -#include "metrics.h" +#include "distance.h" #include "utils.h" #include <stdlib.h> #include <string.h> diff --git a/lib/distance.c b/lib/distance.c index 222572e..0022655 100644 --- a/lib/distance.c +++ b/lib/distance.c @@ -20,8 +20,12 @@ #include "distance.h" #include "thread.h" #include "frame.h" +#include "normalize.h" +#include "utils.h" +#include "gdb/thread.h" #include <stdlib.h> #include <assert.h> +#include <string.h>
float distance_jaro_winkler(struct sr_thread *thread1, @@ -280,3 +284,159 @@ sr_distance(enum sr_distance_type distance_type, return 1.0f; } } + +static int +get_distance_position(const struct sr_distances *distances, int i, int j) +{ + /* The array holds only matrix entries (i, j) where i < j, + * locate the position in the array. */ + assert(i < j && i >= 0 && i < distances->m && j < distances->n); + + int h = distances->n, l = distances->n - i; + + return ((h * h - h) - (l * l - l)) / 2 + j - 1; +} + +struct sr_distances * +sr_distances_new(int m, int n) +{ + struct sr_distances *distances = sr_malloc(sizeof(struct sr_distances)); + + /* The number of rows has to be smaller than columns. */ + if (m >= n) + m = n - 1; + + assert(m > 0 && n > 1 && m < n); + + distances->m = m; + distances->n = n; + distances->distances = sr_malloc(sizeof(*distances->distances) * + (get_distance_position(distances, m - 1, n - 1) + 1)); + + return distances; +} + +struct sr_distances * +sr_distances_dup(struct sr_distances *distances) +{ + struct sr_distances *dup_distances; + + dup_distances = sr_distances_new(distances->m, distances->n); + memcpy(dup_distances->distances, distances->distances, + sizeof(*distances->distances) * + (get_distance_position(distances, distances->m - 1, distances->n - 1) + 1)); + + return dup_distances; +} + +void +sr_distances_free(struct sr_distances *distances) +{ + if (!distances) + return; + + free(distances->distances); + free(distances); +} + +float +sr_distances_get_distance(struct sr_distances *distances, int i, int j) +{ + if (i == j) + return 0.0; + + if (i > j) + { + int x; + x = j, j = i, i = x; + } + + return distances->distances[get_distance_position(distances, i, j)]; +} + +void +sr_distances_set_distance(struct sr_distances *distances, + int i, + int j, + float d) +{ + if (i == j) + return; + + if (i > j) + { + int x; + x = j, j = i, i = x; + } + + distances->distances[get_distance_position(distances, i, j)] = d; +} + +struct sr_distances * +sr_threads_compare(struct sr_thread **threads, + int m, + int n, + enum sr_distance_type dist_type) +{ + struct sr_distances *distances; + int i, j; + float dist; + + distances = sr_distances_new(m, n); + + if (n <= 0) + return distances; + + /* Check that all threads are of the same type */ + enum sr_report_type type, prev_type = threads[0]->type; + for (i = 0; i < n; i++) + { + type = threads[i]->type; + assert(prev_type == type); + prev_type = type; + } + + for (i = 0; i < m; i++) + { + for (j = i + 1; j < n; j++) + { + /* XXX: GDB crashes have a special normalization step for + * clustering. If there's something similar for other types, we can + * generalize it -- meanwhile there's a separate case for GDB here + */ + if (type == SR_REPORT_GDB) + { + struct sr_gdb_thread *thread1 = (struct sr_gdb_thread*)threads[i], + *thread2 = (struct sr_gdb_thread*)threads[j]; + int ok = 0, all = 0; + + sr_gdb_thread_quality_counts(thread1, &ok, &all); + sr_gdb_thread_quality_counts(thread2, &ok, &all); + + if (ok != all) + { + /* There are some unknown function names, try to pair them, but + * the threads need to be copied first. */ + thread1 = sr_gdb_thread_dup(thread1, false); + thread2 = sr_gdb_thread_dup(thread2, false); + sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); + } + + dist = sr_distance(dist_type, (struct sr_thread*)thread1, + (struct sr_thread*)thread2); + + if (ok != all) + { + sr_gdb_thread_free(thread1); + sr_gdb_thread_free(thread2); + } + } + else + dist = sr_distance(dist_type, threads[i], threads[j]); + + distances->distances[get_distance_position(distances, i, j)] = dist; + } + } + + return distances; +} diff --git a/lib/metrics.c b/lib/metrics.c deleted file mode 100644 index 40fa87a..0000000 --- a/lib/metrics.c +++ /dev/null @@ -1,409 +0,0 @@ -/* - metrics.c - - Copyright (C) 2010 Red Hat, Inc. - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License along - with this program; if not, write to the Free Software Foundation, Inc., - 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. -*/ -#include "gdb/thread.h" -#include "gdb/frame.h" -#include "utils.h" -#include "metrics.h" -#include "normalize.h" -#include "thread.h" -#include <stdio.h> -#include <limits.h> -#include <string.h> -#include <assert.h> - -float -sr_gdb_thread_jarowinkler_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - sr_gdb_frame_cmp_type compare_func) -{ - int frame1_count = sr_thread_frame_count((struct sr_thread*) thread1); - int frame2_count = sr_thread_frame_count((struct sr_thread*) thread2); - - if (frame1_count == 0 && frame2_count == 0) - { - return 1.0; - } - - int max_frame_count = (frame2_count > frame1_count ? frame2_count : frame1_count); - int i = 0, j, prefix_len = 0; - bool match, still_prefix = true; - float k, trans_count = 0, match_count = 0, dist_jaro, dist; - - - struct sr_gdb_frame *curr_frame = thread1->frames; - for (i = 1; curr_frame; i++) - { - match = false; - struct sr_gdb_frame *curr_frame2 = thread2->frames; - for (j = 1; !match && curr_frame2; j++) - { - /*whether the prefix continues to be the same for both threads or not*/ - if (i == j && 0 != compare_func(curr_frame, curr_frame2)) - still_prefix = false; - - /*getting a match only if not too far away from each other - and if functions aren't both unpaired unknown functions */ - - if (abs(i - j) <= max_frame_count / 2 - 1 && - 0 == compare_func(curr_frame, curr_frame2)) - { - match = true; - if(i != j)trans_count++; // transposition in place - } - curr_frame2 = curr_frame2->next; - } - - if (still_prefix) - prefix_len++; - - if (match) - match_count++; - - curr_frame = curr_frame->next; - } - - trans_count = trans_count / 2; - - if (prefix_len > 4) - prefix_len = 4; - - if (match_count == 0)return 0; // so as not to divide by 0 - - dist_jaro = (match_count / (float)frame1_count + - match_count / (float)frame2_count + - (match_count - trans_count) / match_count) / 3; - - k = 0.2; /* how much weight we give to having common prefixes - * (always k < 0.25) */ - - dist = dist_jaro + (float)prefix_len * k * (1 - dist_jaro); - - return dist; -} - -static bool -frames_contain(struct sr_gdb_frame *frames, - struct sr_gdb_frame *frame, - sr_gdb_frame_cmp_type compare_func) -{ - while (frames) - { - // checking if functions are the same but not both "??" - if (!compare_func(frames, frame)) - return true; - - frames = frames->next; - } - - return false; -} - -float -sr_gdb_thread_jaccard_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - sr_gdb_frame_cmp_type compare_func) -{ - int union_size, intersection_size = 0, set1_size = 0, set2_size = 0; - float j_distance; - struct sr_gdb_frame *curr_frame; - - for (curr_frame = thread1->frames; curr_frame; curr_frame = curr_frame->next) - { - if (frames_contain(curr_frame->next, curr_frame, compare_func)) - continue; // not last, skip - - set1_size++; - - if (frames_contain(thread2->frames, curr_frame, compare_func)) - intersection_size++; - } - - for (curr_frame = thread2->frames; curr_frame; curr_frame = curr_frame->next) - { - if (frames_contain(curr_frame->next, curr_frame, compare_func)) - continue; // not last, skip - - set2_size++; - } - - union_size = set1_size + set2_size - intersection_size; - if (!union_size) - return 0.0; - - j_distance = 1.0 - intersection_size / (float)union_size; - if (j_distance < 0.0) - j_distance = 0.0; - - return j_distance; -} - - -int -sr_gdb_thread_levenshtein_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - bool transposition, - sr_gdb_frame_cmp_type compare_func) -{ - int m = sr_thread_frame_count((struct sr_thread*) thread1) + 1; - int n = sr_thread_frame_count((struct sr_thread*) thread2) + 1; - - // store only two last rows and columns instead of whole 2D array - int dist[m + n + 1], dist1[m + n + 1], dist2; - - int i, j, l, cost = 0; - - // first row and column having distance equal to their position - for (i = m; i > 0; i--) - dist[m - i] = i; - - for (; i <= n; i++) - dist[m + i] = i; - - struct sr_gdb_frame *curr_frame2 = thread2->frames; - struct sr_gdb_frame *prev_frame = NULL; - struct sr_gdb_frame *prev_frame2 = NULL; - - for (j = 1; curr_frame2; j++) - { - struct sr_gdb_frame *curr_frame = thread1->frames; - for (i = 1; curr_frame; i++) - { - l = m + j - i; - - dist2 = dist1[l]; - dist1[l] = dist[l]; - - /*similar characters have distance equal to the previous one diagonally, - "??" functions aren't taken as similar */ - if (0 == compare_func(curr_frame, curr_frame2)) - cost = 0; - // different ones takes the lowest value of all previous distances - else - { - cost = 1; - dist[l] += 1; - if (dist[l] > dist[l - 1] + 1) - dist[l] = dist[l - 1] + 1; - if (dist[l] > dist[l + 1] + 1) - dist[l] = dist[l + 1] + 1; - } - - /*checking for transposition of two characters in both ways - taking into account that "??" functions are not similar*/ - if (transposition && - (i >= 2 && j >= 2 && dist[l] > dist2 + cost && - 0 == compare_func(curr_frame, prev_frame2) && - 0 == compare_func(prev_frame, curr_frame2))) - { - dist[l] = dist2 + cost; - } - - prev_frame = curr_frame; - curr_frame = curr_frame->next; - } - - prev_frame2 = curr_frame2; - curr_frame2 = curr_frame2->next; - } - - return dist[n]; -} - -float -sr_gdb_thread_jarowinkler_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2) -{ - return sr_gdb_thread_jarowinkler_distance_custom(thread1, - thread2, - sr_gdb_frame_cmp_distance); -} - -float -sr_gdb_thread_jaccard_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2) -{ - return sr_gdb_thread_jaccard_distance_custom(thread1, - thread2, - sr_gdb_frame_cmp_distance); -} - -int -sr_gdb_thread_levenshtein_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - bool transposition) -{ - return sr_gdb_thread_levenshtein_distance_custom(thread1, - thread2, - transposition, - sr_gdb_frame_cmp_distance); -} - -float -sr_gdb_thread_levenshtein_distance_f(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2) -{ - int frame_count1, frame_count2, max_frame_count; - - frame_count1 = sr_thread_frame_count((struct sr_thread*) thread1); - frame_count2 = sr_thread_frame_count((struct sr_thread*) thread2); - max_frame_count = frame_count1 > frame_count2 ? frame_count1 : frame_count2; - - if (!max_frame_count) - return 1.0; - - return (float)sr_gdb_thread_levenshtein_distance_custom(thread1, - thread2, - true, - sr_gdb_frame_cmp_distance) / max_frame_count; -} - -static int -get_distance_position(const struct sr_distances *distances, int i, int j) -{ - /* The array holds only matrix entries (i, j) where i < j, - * locate the position in the array. */ - assert(i < j && i >= 0 && i < distances->m && j < distances->n); - - int h = distances->n, l = distances->n - i; - - return ((h * h - h) - (l * l - l)) / 2 + j - 1; -} - -struct sr_distances * -sr_distances_new(int m, int n) -{ - struct sr_distances *distances = sr_malloc(sizeof(struct sr_distances)); - - /* The number of rows has to be smaller than columns. */ - if (m >= n) - m = n - 1; - - assert(m > 0 && n > 1 && m < n); - - distances->m = m; - distances->n = n; - distances->distances = sr_malloc(sizeof(*distances->distances) * - (get_distance_position(distances, m - 1, n - 1) + 1)); - - return distances; -} - -struct sr_distances * -sr_distances_dup(struct sr_distances *distances) -{ - struct sr_distances *dup_distances; - - dup_distances = sr_distances_new(distances->m, distances->n); - memcpy(dup_distances->distances, distances->distances, - sizeof(*distances->distances) * - (get_distance_position(distances, distances->m - 1, distances->n - 1) + 1)); - - return dup_distances; -} - -void -sr_distances_free(struct sr_distances *distances) -{ - if (!distances) - return; - - free(distances->distances); - free(distances); -} - -float -sr_distances_get_distance(struct sr_distances *distances, int i, int j) -{ - if (i == j) - return 0.0; - - if (i > j) - { - int x; - x = j, j = i, i = x; - } - - return distances->distances[get_distance_position(distances, i, j)]; -} - -void -sr_distances_set_distance(struct sr_distances *distances, - int i, - int j, - float d) -{ - if (i == j) - return; - - if (i > j) - { - int x; - x = j, j = i, i = x; - } - - distances->distances[get_distance_position(distances, i, j)] = d; -} - -struct sr_distances * -sr_gdb_threads_compare(struct sr_gdb_thread **threads, - int m, - int n, - sr_dist_thread_type dist_func) -{ - struct sr_distances *distances; - struct sr_gdb_thread *thread1, *thread2; - int i, j, ok, all; - - distances = sr_distances_new(m, n); - - for (i = 0; i < m; i++) - { - for (j = i + 1; j < n; j++) - { - ok = all = 0; - sr_gdb_thread_quality_counts(threads[i], &ok, &all); - sr_gdb_thread_quality_counts(threads[j], &ok, &all); - - if (ok == all) - { - thread1 = threads[i]; - thread2 = threads[j]; - } - else - { - /* There are some unknown function names, try to pair them, but - * the threads need to be copied first. */ - thread1 = sr_gdb_thread_dup(threads[i], false); - thread2 = sr_gdb_thread_dup(threads[j], false); - sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - } - - distances->distances[get_distance_position(distances, i, j)] = dist_func(thread1, thread2); - - if (ok != all) - { - sr_gdb_thread_free(thread1); - sr_gdb_thread_free(thread2); - } - } - } - - return distances; -} diff --git a/python/py_metrics.c b/python/py_metrics.c index b733b3b..78403b2 100644 --- a/python/py_metrics.c +++ b/python/py_metrics.c @@ -1,7 +1,7 @@ #include "py_metrics.h" #include "py_gdb_thread.h" #include "strbuf.h" -#include "metrics.h" +#include "distance.h"
#define distances_doc "satyr.Distances - class representing distances between objects\n" \ "Usage:\n" \ @@ -103,7 +103,7 @@ sr_py_distances_new(PyTypeObject *object, PyObject *args, PyObject *kwds) if (PyArg_ParseTuple(args, "sO!i", &dist_name, &PyList_Type, &thread_list, &m)) { n = PyList_Size(thread_list); - struct sr_gdb_thread *threads[n]; + struct sr_thread *threads[n];
for (i = 0; i < n; i++) { @@ -119,7 +119,7 @@ sr_py_distances_new(PyTypeObject *object, PyObject *args, PyObject *kwds) { return NULL; } - threads[i] = to->thread; + threads[i] = (struct sr_thread*)to->thread; } if (m < 1 || n < 2) { @@ -127,19 +127,19 @@ sr_py_distances_new(PyTypeObject *object, PyObject *args, PyObject *kwds) return NULL; }
- sr_dist_thread_type dist_func; + enum sr_distance_type dist_type;
if (!strcmp(dist_name, "jaccard")) - dist_func = sr_gdb_thread_jaccard_distance; + dist_type = SR_DISTANCE_JACCARD; else if (!strcmp(dist_name, "levenshtein")) - dist_func = sr_gdb_thread_levenshtein_distance_f; + dist_type = SR_DISTANCE_LEVENSHTEIN; else { PyErr_SetString(PyExc_ValueError, "Unknown name of distance function"); return NULL; }
- o->distances = sr_gdb_threads_compare(threads, m, n, dist_func); + o->distances = sr_threads_compare(threads, m, n, dist_type); } else if (PyArg_ParseTuple(args, "ii", &m, &n)) { diff --git a/satyr.c b/satyr.c index 572ec3c..841ccdc 100644 --- a/satyr.c +++ b/satyr.c @@ -23,7 +23,6 @@ #include "utils.h" #include "location.h" #include "strbuf.h" -#include "metrics.h" #include "cluster.h" #include "normalize.h" #include "report.h" diff --git a/tests/cluster.at b/tests/cluster.at index ad0ddb7..ca5037a 100644 --- a/tests/cluster.at +++ b/tests/cluster.at @@ -2,7 +2,7 @@ AT_BANNER([Clustering])
AT_TESTFUN([sr_distances_cluster_objects], [ -#include "metrics.h" +#include "distance.h" #include "cluster.h" #include <assert.h> #include <stdio.h> @@ -71,7 +71,6 @@ main()
AT_TESTFUN([sr_dendrogram_cut], [ -#include "metrics.h" #include "cluster.h" #include <assert.h> #include <stdio.h> diff --git a/tests/metrics.at b/tests/metrics.at index 7f56fce..0d259aa 100644 --- a/tests/metrics.at +++ b/tests/metrics.at @@ -7,7 +7,6 @@ m4_define([UTILS], #include "utils.h" #include <stdlib.h> #include <assert.h> -#include "metrics.h" #include "normalize.h" #include "distance.h"
@@ -364,7 +363,7 @@ main() threads[[2]] = create_thread(3, "asd", "agd", "??"); threads[[3]] = create_thread(3, "dg", "??", "??");
- struct sr_distances *distances = sr_gdb_threads_compare(threads, 3, 4, sr_gdb_thread_jaccard_distance); + struct sr_distances *distances = sr_threads_compare(threads, 3, 4, SR_DISTANCE_JACCARD); assert(is_dist_equal(0.6, sr_distances_get_distance(distances, 0, 1))); assert(is_dist_equal(0.6, sr_distances_get_distance(distances, 0, 2))); assert(is_dist_equal(1.0, sr_distances_get_distance(distances, 0, 3))); diff --git a/tests/normalize.at b/tests/normalize.at index 4038ec8..d15a4fd 100644 --- a/tests/normalize.at +++ b/tests/normalize.at @@ -7,7 +7,6 @@ m4_define([UTILS], #include "gdb/thread.h" #include "gdb/frame.h" #include "utils.h" -#include "metrics.h" #include "normalize.h" #include <stdlib.h> #include <assert.h>