[SATYR PATCH 6/6] Type-agnostic distance matrices
Martin Milata
mmilata at redhat.com
Fri Jun 14 18:01:12 UTC 2013
- 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 at 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>
--
1.7.11.7
More information about the Crash-catcher
mailing list