#include <apr.h>
#include <apr_pools.h>
#include <apr_general.h>
#include "diff.h"
typedef struct svn_diff__snake_t svn_diff__snake_t;
struct svn_diff__snake_t
{
apr_off_t y;
svn_diff__lcs_t *lcs;
svn_diff__position_t *position[2];
};
static APR_INLINE void
svn_diff__snake(svn_diff__snake_t *fp_k,
svn_diff__token_index_t *token_counts[2],
svn_diff__lcs_t **freelist,
apr_pool_t *pool)
{
svn_diff__position_t *start_position[2];
svn_diff__position_t *position[2];
svn_diff__lcs_t *lcs;
svn_diff__lcs_t *previous_lcs;
lcs = fp_k[0].lcs;
while (lcs)
{
lcs->refcount--;
if (lcs->refcount)
break;
previous_lcs = lcs->next;
lcs->next = *freelist;
*freelist = lcs;
lcs = previous_lcs;
}
if (fp_k[-1].y >= fp_k[1].y)
{
start_position[0] = fp_k[-1].position[0];
start_position[1] = fp_k[-1].position[1]->next;
previous_lcs = fp_k[-1].lcs;
}
else
{
start_position[0] = fp_k[1].position[0]->next;
start_position[1] = fp_k[1].position[1];
previous_lcs = fp_k[1].lcs;
}
if (previous_lcs)
{
previous_lcs->refcount++;
}
position[0] = start_position[0];
position[1] = start_position[1];
while (1)
{
while (position[0]->token_index == position[1]->token_index)
{
position[0] = position[0]->next;
position[1] = position[1]->next;
}
if (position[1] != start_position[1])
{
lcs = *freelist;
if (lcs)
{
*freelist = lcs->next;
}
else
{
lcs = apr_palloc(pool, sizeof(*lcs));
}
lcs->position[0] = start_position[0];
lcs->position[1] = start_position[1];
lcs->length = position[1]->offset - start_position[1]->offset;
lcs->next = previous_lcs;
lcs->refcount = 1;
previous_lcs = lcs;
start_position[0] = position[0];
start_position[1] = position[1];
}
if (position[0]->token_index >= 0
&& token_counts[1][position[0]->token_index] == 0)
start_position[0] = position[0] = position[0]->next;
else if (position[1]->token_index >= 0
&& token_counts[0][position[1]->token_index] == 0)
start_position[1] = position[1] = position[1]->next;
else
break;
}
fp_k[0].lcs = previous_lcs;
fp_k[0].position[0] = position[0];
fp_k[0].position[1] = position[1];
fp_k[0].y = position[1]->offset;
}
static svn_diff__lcs_t *
svn_diff__lcs_reverse(svn_diff__lcs_t *lcs)
{
svn_diff__lcs_t *next;
svn_diff__lcs_t *prev;
next = NULL;
while (lcs != NULL)
{
prev = lcs->next;
lcs->next = next;
next = lcs;
lcs = prev;
}
return next;
}
static svn_diff__lcs_t *
prepend_lcs(svn_diff__lcs_t *lcs, apr_off_t lines,
apr_off_t pos0_offset, apr_off_t pos1_offset,
apr_pool_t *pool)
{
svn_diff__lcs_t *new_lcs;
SVN_ERR_ASSERT_NO_RETURN(lines > 0);
new_lcs = apr_palloc(pool, sizeof(*new_lcs));
new_lcs->position[0] = apr_pcalloc(pool, sizeof(*new_lcs->position[0]));
new_lcs->position[0]->offset = pos0_offset;
new_lcs->position[1] = apr_pcalloc(pool, sizeof(*new_lcs->position[1]));
new_lcs->position[1]->offset = pos1_offset;
new_lcs->length = lines;
new_lcs->refcount = 1;
new_lcs->next = lcs;
return new_lcs;
}
svn_diff__lcs_t *
svn_diff__lcs(svn_diff__position_t *position_list1,
svn_diff__position_t *position_list2,
svn_diff__token_index_t *token_counts_list1,
svn_diff__token_index_t *token_counts_list2,
svn_diff__token_index_t num_tokens,
apr_off_t prefix_lines,
apr_off_t suffix_lines,
apr_pool_t *pool)
{
apr_off_t length[2];
svn_diff__token_index_t *token_counts[2];
svn_diff__token_index_t unique_count[2];
svn_diff__token_index_t token_index;
svn_diff__snake_t *fp;
apr_off_t d;
apr_off_t k;
apr_off_t p = 0;
svn_diff__lcs_t *lcs, *lcs_freelist = NULL;
svn_diff__position_t sentinel_position[2];
lcs = apr_palloc(pool, sizeof(*lcs));
lcs->position[0] = apr_pcalloc(pool, sizeof(*lcs->position[0]));
lcs->position[0]->offset = position_list1
? position_list1->offset + suffix_lines + 1
: prefix_lines + suffix_lines + 1;
lcs->position[1] = apr_pcalloc(pool, sizeof(*lcs->position[1]));
lcs->position[1]->offset = position_list2
? position_list2->offset + suffix_lines + 1
: prefix_lines + suffix_lines + 1;
lcs->length = 0;
lcs->refcount = 1;
lcs->next = NULL;
if (position_list1 == NULL || position_list2 == NULL)
{
if (suffix_lines)
lcs = prepend_lcs(lcs, suffix_lines,
lcs->position[0]->offset - suffix_lines,
lcs->position[1]->offset - suffix_lines,
pool);
if (prefix_lines)
lcs = prepend_lcs(lcs, prefix_lines, 1, 1, pool);
return lcs;
}
unique_count[1] = unique_count[0] = 0;
for (token_index = 0; token_index < num_tokens; token_index++)
{
if (token_counts_list1[token_index] == 0)
unique_count[1] += token_counts_list2[token_index];
if (token_counts_list2[token_index] == 0)
unique_count[0] += token_counts_list1[token_index];
}
length[0] = position_list1->offset - position_list1->next->offset + 1
- unique_count[0];
length[1] = position_list2->offset - position_list2->next->offset + 1
- unique_count[1];
fp = apr_pcalloc(pool,
sizeof(*fp) * (apr_size_t)(length[0] + length[1] + 3));
fp += length[1] + 1;
sentinel_position[0].next = position_list1->next;
position_list1->next = &sentinel_position[0];
sentinel_position[0].offset = position_list1->offset + 1;
token_counts[0] = token_counts_list1;
sentinel_position[1].next = position_list2->next;
position_list2->next = &sentinel_position[1];
sentinel_position[1].offset = position_list2->offset + 1;
token_counts[1] = token_counts_list2;
sentinel_position[0].token_index = -1;
sentinel_position[1].token_index = -2;
d = length[0] - length[1];
fp[d - 1].position[0] = sentinel_position[0].next;
fp[d - 1].position[1] = &sentinel_position[1];
p = 0;
do
{
for (k = (d < 0 ? d : 0) - p; k < 0; k++)
{
svn_diff__snake(fp + k, token_counts, &lcs_freelist, pool);
}
for (k = (d > 0 ? d : 0) + p; k >= 0; k--)
{
svn_diff__snake(fp + k, token_counts, &lcs_freelist, pool);
}
p++;
}
while (fp[0].position[1] != &sentinel_position[1]);
if (suffix_lines)
lcs->next = prepend_lcs(fp[0].lcs, suffix_lines,
lcs->position[0]->offset - suffix_lines,
lcs->position[1]->offset - suffix_lines,
pool);
else
lcs->next = fp[0].lcs;
lcs = svn_diff__lcs_reverse(lcs);
position_list1->next = sentinel_position[0].next;
position_list2->next = sentinel_position[1].next;
if (prefix_lines)
return prepend_lcs(lcs, prefix_lines, 1, 1, pool);
else
return lcs;
}