From 2d4251b17d81f774e1c00dff3bdbae73d2251295 Mon Sep 17 00:00:00 2001 From: John Hawthorn Date: Fri, 27 Dec 2019 18:39:01 -0800 Subject: Reduce memory and avoid VLA in match() When we're matching without recording positions, we only need to keep two rows in memory at a time. --- src/match.c | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) diff --git a/src/match.c b/src/match.c index 8dd98c3..6cf9c3a 100644 --- a/src/match.c +++ b/src/match.c @@ -28,6 +28,8 @@ int has_match(const char *needle, const char *haystack) { return 1; } +#define SWAP(x, y, T) do { T SWAP = x; x = y; y = SWAP; } while (0) + #define max(a, b) (((a) > (b)) ? (a) : (b)) #ifdef DEBUG_VERBOSE @@ -159,22 +161,24 @@ score_t match(const char *needle, const char *haystack) { * D[][] Stores the best score for this position ending with a match. * M[][] Stores the best possible score at this position. */ - score_t D[n][m], M[n][m]; + score_t D[2][MATCH_MAX_LEN], M[2][MATCH_MAX_LEN]; score_t *last_D, *last_M; score_t *curr_D, *curr_M; - for (int i = 0; i < n; i++) { - curr_D = &D[i][0]; - curr_M = &M[i][0]; + last_D = D[0]; + last_M = M[0]; + curr_D = D[1]; + curr_M = M[1]; + for (int i = 0; i < n; i++) { match_row(&match, i, curr_D, curr_M, last_D, last_M); - last_D = curr_D; - last_M = curr_M; + SWAP(curr_D, last_D, score_t *); + SWAP(curr_M, last_M, score_t *); } - return M[n - 1][m - 1]; + return last_M[m - 1]; } score_t match_positions(const char *needle, const char *haystack, size_t *positions) { -- cgit v1.2.3