X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fedit_distance%2Fedit_distance_lev.c;h=352dbd7876ed9b7a49c62dbbc0b60746133c385f;hb=c16c021735d53348b6f5fe119e35feea85e6638e;hp=7638c6dce5bb7c1c49fdd5a2be198ac6452b27b2;hpb=e0663bef2ec73ed33b22e5a029284296495aab87;p=ccan diff --git a/ccan/edit_distance/edit_distance_lev.c b/ccan/edit_distance/edit_distance_lev.c index 7638c6dc..352dbd78 100644 --- a/ccan/edit_distance/edit_distance_lev.c +++ b/ccan/edit_distance/edit_distance_lev.c @@ -13,22 +13,24 @@ ed_dist edit_distance_lev(const ed_elem *src, ed_size slen, const ed_elem *tgt, ed_size tlen) { + ed_size i, j; + /* Optimization: Avoid malloc when row of distance matrix can fit on * the stack. */ - ed_dist stackdist[ED_STACK_ELEMS]; + ed_dist stackdist[ED_STACK_DIST_VALS]; /* One row of the Wagner-Fischer distance matrix. */ - ed_dist *dist = slen < ED_STACK_ELEMS ? stackdist : + ed_dist *dist = slen < ED_STACK_DIST_VALS ? stackdist : malloc((slen + 1) * sizeof(ed_dist)); /* Initialize row with cost to delete src[0..i-1] */ dist[0] = 0; - for (ed_size i = 1; i <= slen; ++i) { + for (i = 1; i <= slen; ++i) { dist[i] = dist[i - 1] + ED_DEL_COST(src[i - 1]); } - for (ed_size j = 1; j <= tlen; ++j) { + for (j = 1; j <= tlen; ++j) { /* Value for dist[j-1][i-1] (one row up, one col left). */ ed_dist diagdist = dist[0]; dist[0] = dist[0] + ED_INS_COST(tgt[j - 1]); @@ -36,7 +38,7 @@ ed_dist edit_distance_lev(const ed_elem *src, ed_size slen, /* Loop invariant: dist[i] is the edit distance between first j * elements of tgt and first i elements of src. */ - for (ed_size i = 1; i <= slen; ++i) { + for (i = 1; i <= slen; ++i) { ed_dist nextdiagdist = dist[i]; if (ED_ELEM_EQUAL(src[i - 1], tgt[j - 1])) {