[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