Line oriented text comparison (Myers shortest edit script). More...

#include "nilorea/n_diff.h"
#include "nilorea/n_common.h"
#include "nilorea/n_log.h"
#include <limits.h>
#include <stdio.h>
#include <string.h>

Include dependency graph for n_diff.c:

Data Structures
struct	DIFF_OUT
	growing output buffer fed by write_and_fit_ex More...
struct	DIFF_TEXT
	a text split into lines, all pointing into one owned buffer More...

Macros
#define	DIFF_HEADER_BUF 128
	widest "@@ -a,b +c,d @@" header we can produce
#define	DIFF_OUT_PADDING 256
	growth headroom so consecutive short appends share one realloc

Functions
static int	_emit (N_DIFF_RESULT result, int op, const char text, size_t line_a, size_t line_b)
	prepend one line to the script, which is built back to front.
static void	_line_free (void *ptr)
	destructor for the N_DIFF_LINE entries of N_DIFF_RESULT.lines
static int	_myers (N_DIFF_RESULT result, char a, int n, char *b, int m, size_t base_a, size_t base_b, int max_edits)
	Myers greedy forward pass with a stored trace, then a backtrack emitting the script in reverse.
static char	_op_char (int op)
	unified diff marker for an operation
static N_STR *	_out_finish (DIFF_OUT *o)
	hand the buffer over to a new N_STR (no copy); the DIFF_OUT is emptied
static int	_out_line (DIFF_OUT o, const N_DIFF_LINE line)
	append one script line as "<marker>text\n", TRUE on success
static int	_out_mem (DIFF_OUT o, const char s, size_t n)
	append n bytes of s to the output, TRUE on success
static int	_out_str (DIFF_OUT o, const char s)
	append a NULL terminated string to the output, TRUE on success
static void	_text_free (DIFF_TEXT *t)
	release a DIFF_TEXT, leaving it empty
static int	_text_load (DIFF_TEXT t, const char text)
	split text into lines.
N_DIFF_RESULT *	n_diff_lines (const char text_a, const char text_b, size_t max_edits)
	Compare two texts line by line.
void	n_diff_result_free (N_DIFF_RESULT **result)
	Free an edit script and every line it holds.
N_STR *	n_diff_to_unified (const N_DIFF_RESULT *result, size_t context)
	Render an edit script as unified diff text.

Detailed Description

Line oriented text comparison (Myers shortest edit script).

Author: Castagnier Mickael

Version: 1.0

Date: 31/07/2026

Definition in file n_diff.c.

Data Structure Documentation

◆ DIFF_OUT

struct DIFF_OUT

growing output buffer fed by write_and_fit_ex

Definition at line 342 of file n_diff.c.

Collaboration diagram for DIFF_OUT:

Data Fields
char *	buf	buffer, reallocated on growth
NSTRBYTE	size	total allocation in bytes
NSTRBYTE	written	meaningful bytes, excluding the terminating '\0'

◆ DIFF_TEXT

struct DIFF_TEXT

a text split into lines, all pointing into one owned buffer

Definition at line 42 of file n_diff.c.

Collaboration diagram for DIFF_TEXT:

Data Fields
char *	buf	copy of the input with every ' ' turned into '\0'
size_t	count	number of lines
char **	line	start of each line inside buf

Macro Definition Documentation

◆ DIFF_HEADER_BUF

#define DIFF_HEADER_BUF 128

widest "@@ -a,b +c,d @@" header we can produce

Definition at line 39 of file n_diff.c.

Referenced by n_diff_to_unified().

◆ DIFF_OUT_PADDING

#define DIFF_OUT_PADDING 256

growth headroom so consecutive short appends share one realloc

Definition at line 37 of file n_diff.c.

Referenced by _out_mem().

Function Documentation

◆ _emit()

int _emit	(	N_DIFF_RESULT *	result,
		int	op,
		const char *	text,
		size_t	line_a,
		size_t	line_b )

static

prepend one line to the script, which is built back to front.

TRUE on success, FALSE on allocation failure.

Definition at line 110 of file n_diff.c.

References _line_free(), FreeNoLog, line(), N_DIFF_RESULT::lines, list_unshift(), Malloc, N_DIFF_COMMON, N_DIFF_DELETE, N_DIFF_RESULT::nb_common, N_DIFF_RESULT::nb_deleted, and N_DIFF_RESULT::nb_inserted.

Referenced by _myers(), and n_diff_lines().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _line_free()

void _line_free ( void * ptr )

static

destructor for the N_DIFF_LINE entries of N_DIFF_RESULT.lines

Definition at line 101 of file n_diff.c.

References FreeNoLog, and line().

Referenced by _emit().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _myers()

int _myers	(	N_DIFF_RESULT *	result,
		char **	a,
		int	n,
		char **	b,
		int	m,
		size_t	base_a,
		size_t	base_b,
		int	max_edits )

static

Myers greedy forward pass with a stored trace, then a backtrack emitting the script in reverse.

base_a / base_b are added to the emitted line numbers so a trimmed middle still reports positions in the whole text. Returns 1 when a script was emitted, 0 when the texts are further apart than max_edits (nothing emitted), -1 on allocation failure.

Definition at line 144 of file n_diff.c.

References _emit(), FreeNoLog, LOG_ERR, Malloc, N_DIFF_COMMON, N_DIFF_DELETE, N_DIFF_INSERT, N_DIFF_NO_LINE, and n_log.

Referenced by n_diff_lines().

Here is the call graph for this function: