<commit_before>/*************************************************************************/
/* Copyright (c) 2004                                                    */
/* <NAME>, <NAME>, and <NAME>                    */
/* Copyright (c) 2013,2014,2015 <NAME>                            */
/* All rights reserved                                                   */
/*                                                                       */
/* Use of the link grammar parsing system is subject to the terms of the */
/* license set forth in the LICENSE file included with this software.    */
/* This license allows free redistribution and use in source and binary  */
/* forms, with or without modification, subject to certain conditions.   */
/*                                                                       */
/*************************************************************************/

#include <limits.h>
#include <inttypes.h>                 // PRIu64
#if HAVE_THREADS_H
#include <threads.h>
#endif /* HAVE_THREADS_H */

#include "link-includes.h"
#include "api-structures.h"
#include "connectors.h"
#include "count.h"
#include "dict-common/dict-common.h"    // IS_GENERATION
#include "disjunct-utils.h"
#include "fast-match.h"
#include "resources.h"
#include "tokenize/word-structures.h" // for Word_struct
#include "utilities.h"

/* This file contains the exhaustive search algorithm. */

#define D_COUNT 5 /* General debug level for this file. */

typedef struct Table_connector_s Table_connector;
struct Table_connector_s
{
	Table_connector  *next;
	int              l_id, r_id;
	Count_bin          count;
	unsigned int     null_count;
	size_t           hash;
};

typedef uint8_t null_count_m;  /* Storage representation of null_count */
typedef uint8_t WordIdx_m;     /* Storage representation of word index */

/* Most of the time, do_count() yields a zero leftcount/rightcount when it
 * parses a word range in which one end is a certain tracon and the other
 * end is a word that is between the nearest_word and farthest_word of the
 * first connector of that tracon (words out of this range are not checked).
 * Memoizing this results in a huge speedup for sentences that are not
 * short.
 *
 * To that end, two cache arrays, one of leftcount and the other for
 * rightcount, indexed by the tracon number (tracon_id), are maintained.
 *
 * Each element of these arrays points to a vector, called here word-vector,
 * with a size equal to abs(nearest_word - farthest_word) + 1.
 *
 * Each element of this vector predicts, in it's status field, whether the
 * expected count is zero for a given null-count (when the word it
 * represents is the end word of the range).
 * This prediction is valid for null-counts up to null_count (or for any
 * null-count if null_count is ANY_NULL_COUNT).
 *
 * The check_next filed indicates the next word to be checked. Each
 * word-vector is updated each time one of its elements gets updated, so
 * check_next skips all the words for which the count is known to be zero. */
typedef struct
{
	null_count_m null_count; /* status==0 valid up to this null count */
	int8_t status;         /* -1: Needs update; 0: No count; 1: Count possible */
	WordIdx_m check_next;    /* Next word to check */
} Table_lrcnt;

/* Using the word-vectors for very short sentences has too much overhead. */
static const size_t min_len_word_vector = 10; /* This is just an estimation. */

/* Special values for Table_lrcnt fields null_count and check_next. */
#define ANY_NULL_COUNT (MAX_SENTENCE + 1)
#define INCREMENT_WORD ((uint8_t)(MAX_SENTENCE+1)) /* last checked word + 1 */

typedef Table_lrcnt *wordvecp;
static Table_lrcnt lrcnt_cache_zero; /* A sentinel for status==0 */

#if defined DEBUG || DEBUG_COUNT_COST
#define COUNT_COST(...) __VA_ARGS__
#else
#define COUNT_COST(...)
#endif

struct count_context_s
{
	fast_matcher_t *mchxt;
	Sentence sent;
	/* int     null_block; */ /* not used, always 1 */
	bool    islands_ok;
	bool    exhausted;
	uint8_t num_growth;       /* Number of table growths, for debug */
	bool    is_short;
	uint8_t log2_table_size;
	uint32_t checktimer;  /* Avoid excess system calls */
	size_t table_size;
	size_t table_mask;
	size_t table_available_count;
	uint32_t table_lrcnt_size[2];
	Table_connector ** table;
	wordvecp *table_lrcnt[2];  /* Per dir wordvec, indexed by tracon_id */
	Resources current_resources;
	COUNT_COST(uint64_t count_cost[3];)
};
#define MAX_TABLE_SIZE(s) (s / 10) /* Low load factor, for speed */
#define MAX_LOG2_TABLE_SIZE ((sizeof(size_t)==4) ? 25 : 34)

#if HAVE_THREADS_H
/* Each thread will get it's own version of the `kept_table`.
 * If the program creates zillions of threads, then there will
 * be a mem-leak if this table is not released when each thread
 * exists. This code arranges so that `free_tls_table` is called
 * when the thread exists.
 */
static void free_tls_table(void* ptr_to_table)
{
	if (NULL == ptr_to_table) return;

	Table_connector** kept_table = *((Table_connector***)ptr_to_table);
	if (NULL == kept_table) return;

	free(kept_table);
	*((Table_connector***) ptr_to_table) = NULL;
}

static tss_t key;
static void make_key(void)
{
	tss_create(&key, free_tls_table);
}
#endif /* HAVE_THREADS_H */

/**
 * Allocate memory for the connector-pair table and initialize table-size
 * related fields (table_size and table_available_count). Reuse the
 * previous table memory if the request is for a table that fits. If this
 * is not a call to grow the table, free it if not reused.
 *
 * @ctxt[in, out] Table info.
 * @param shift log2 table size, or \c 0 for table growth. On table growth,
 * increase the new table size by 2.
 */
static void table_alloc(count_context_t *ctxt, unsigned int shift)
{
	static TLS Table_connector **kept_table = NULL;
	static TLS unsigned int log2_kept_table_size = 0;

#if HAVE_THREADS_H
	// Install a thread-exit handler, to free kept_table on thread-exit.
	static once_flag flag = ONCE_FLAG_INIT;
	call_once(&flag, make_key);

	if (NULL == kept_table)
		tss_set(key, &kept_table);
#endif /* HAVE_THREADS_H */

	if (shift == 0)
		shift = ctxt->log2_table_size + 1; /* Double the table size */
	lgdebug(+D_COUNT, "Connector table log2 size %u\n", shift);

	/* Keep the table indefinitely (until thread-exit), so that it can
	 * be reused. This avoids a large overhead in malloc/free when
	 * large memory blocks are allocated. Large block in Linux trigger
	 * system calls to mmap/munmap that eat up a lot of time.
	 * (Up to 20%, depending on the sentence and CPU.) */
	ctxt->table_size = (1ULL << shift);
	if ((shift > log2_kept_table_size) || (kept_table == NULL))
	{
		log2_kept_table_size = shift;

		if (kept_table) free(kept_table);
		kept_table = malloc(sizeof(Table_connector *) * ctxt->table_size);
	}

	memset(kept_table, 0, sizeof(Table_connector *) * ctxt->table_size);

	/* This is here and not in init_table() because it must be set
	 * also when the table growths. */
	ctxt->log2_table_size = shift;
	ctxt->table_mask = ctxt->table_size - 1;
	ctxt->table = kept_table;

	if (shift >= MAX_LOG2_TABLE_SIZE)
		ctxt->table_available_count = UINT_MAX; /* Prevent growth */
	else
		ctxt->table_available_count = MAX_TABLE_SIZE(ctxt->table_size);
}

/**
 * Allocate the table with a sentence-dependent table size.  Use
 * sent->length as a hint for the initial table size. Usually, this
 * saves on dynamic table growth, which is costly.
 * */
static void init_table(count_context_t *ctxt)
{
	Sentence sent = ctxt->sent;

	/* A piecewise exponential function determines the size of the
	 * hash table. Probably should make use of the actual number of
	 * disjuncts, rather than just the number of words.
	 */
	unsigned int shift;
	if (sent->length >= 16)
	{
		shift = 14 + sent->length / 16;
	}
	else
	{
		shift = 14;
	}
#if 0 /* Not yet */
	shift += (unsigned int)sent->num_disjuncts / (sent->length * 200);
#endif

	if (MAX_LOG2_TABLE_SIZE < shift) shift = MAX_LOG2_TABLE_SIZE;

	table_alloc(ctxt, shift);
}

static void free_table_lrcnt(count_context_t *ctxt)
{
	if (ctxt->is_short) return;

	if (verbosity_level(D_COUNT))
	{
		unsigned int nonzero = 0, any_null = 0, zero = 0, non_max_null = 0;
		Pool_location loc = { 0 };
		Table_lrcnt *t;

		/* Note: Due to a current pool_next() problem for vector elements,
		 * the stats results here may be slightly skewed.  See the comment
		 * on that in memory-pool.h. */
		while ((t = pool_next(ctxt->sent->wordvec_pool, &loc)) != NULL)
		{
			if (t->status == -1) continue;
			if (t->status == 1)
				nonzero++;
			else if (t->null_count == ANY_NULL_COUNT)
				any_null++;
			else if (ctxt->sent->null_count > t->null_count)
				non_max_null++;
			else if (ctxt->sent->null_count == t->null_count)
				zero++;
		}

		const unsigned int num_values = ctxt->sent->wordvec_pool->curr_elements;
		lgdebug(+0, "Values %u (usage = non_max_null %u + other %u, "
		        "other = any_null_zero %u + zero %u + nonzero %u)\n",
		        num_values, non_max_null, num_values-non_max_null,
		        any_null, zero, nonzero);

		for (unsigned int dir = 0; dir < 2; dir++)
		{
			unsigned int table_usage = 0;

			for (size_t i = 0; i < ctxt->table_lrcnt_size[dir]; i++)
			{
				if (ctxt->table_lrcnt[dir][i] != NULL) continue;
				table_usage++;
			}

			lgdebug(+0, "Direction %u: Using %u/%u tracons %.2f%%\n\\",
			        dir, table_usage, ctxt->table_lrcnt_size[dir],
			        100.0f*table_usage / ctxt->table_lrcnt_size[dir]);
		}
	}

	for (unsigned int dir = 0; dir < 2; dir++)
	{
		free(ctxt->table_lrcnt[dir]);
		ctxt->table_lrcnt[dir] = NULL;
	}
}

static void init_table_lrcnt(count_context_t *ctxt)
{
	if (ctxt->is_short) return;
	Sentence sent = ctxt->sent;

	for (unsigned int dir = 0; dir < 2; dir++)
	{
		const size_t sz = sizeof(wordvecp) * ctxt->table_lrcnt_size[dir];
		ctxt->table_lrcnt[dir] = malloc(sz);
		memset(ctxt->table_lrcnt[dir], 0, sz);
	}

	const size_t initial_size = MIN(sent->length/2, 16) *
		                   (ctxt->table_lrcnt_size[0] + ctxt->table_lrcnt_size[1]);


	if (NULL != sent->wordvec_pool)
	{
		pool_reuse(sent->wordvec_pool);
	}
	else
	{
		ctxt->sent->wordvec_pool =
			pool_new(__func__, "Table_lrcnt", /*num_elements*/initial_size,
			         sizeof(Table_lrcnt), /*zero_out*/false,
			         /*align*/false, /*exact*/false);
	}
}

//#define DEBUG_TABLE_STAT
#if defined(DEBUG) || defined(DEBUG_TABLE_STAT)
static uint64_t hit, miss;  /* Table value found/not found */
#define TABLE_STAT(...) __VA_ARGS__
#else
#define TABLE_STAT(...)
#endif

/**
 * Provide data for insights on the effectively of the connector pair table.
 * Hits, misses, chain length, number of elements with zero/nonzero counts.
 */
static void table_stat(count_context_t *ctxt)
{
#ifdef DEBUG_TABLE_STAT
	if (!verbosity_level(+D_COUNT)) return;

	size_t z = 0, nz = 0;  /* Number of entries with zero and non-zero counts */
	size_t c, total_c = 0; /* Chain length */
	size_t N = 0;          /* NULL table slots */
	size_t null_count[256] = { 0 };   /* null_count histogram */
	int chain_length[64] = { 0 };     /* Chain length histogram */
	bool table_stat_entries = test_enabled("count-table-entries");

	for (size_t i = 0; i < ctxt->table_size; i++)
	{
		Table_connector *t = ctxt->table[i];

		c = 0;
		if (t == NULL)
		{
			N++;
		}
		else
		{
			assert(t->hash != 0, "Invalid hash value: 0");
			assert((hist_total(&t->count)>=0)&&(hist_total(&t->count) <= INT_MAX),
			       "Invalid count %"COUNT_FMT, hist_total(&t->count));
			assert(t->l_id < (int)ctxt->sent->length ||
			       ((t->l_id >= 255)&&(t->l_id < (int)ctxt->table_lrcnt_size[0])),
			       "invalid l_id %d", t->l_id);
			assert(t->r_id <= (int)ctxt->sent->length ||
			       ((t->r_id > 255)&&(t->r_id < (int)ctxt->table_lrcnt_size[1])),
			       "invalid r_id %d", t->r_id);
		}
		for (; t != NULL; t = t->next)
		{
			c++;
			if (hist_total(&t->count) == 0)
				z++;
			else
				nz++;
			null_count[t->null_count]++;
		}
		if (c > 0) /* Slot 0 used for length overflow */
		{
			chain_length[c >= (int)ARRAY_SIZE(chain_length) ? 0 : c]++;
			total_c += c;
		}
		//if (c != 0) printf("Connector table [%d] c=%d\n", i, c);
	}

	size_t used_slots = ctxt->table_size-N;
	/* The used= value is TotalValues/TableSize (not UsedSlots/TableSize). */
	printf("Connector table: num_growth=%u msb=%u slots=%6zu/%6zu (%5.2f%%) "
	       "avg-chain=%4.2f values=%6zu (z=%5zu nz=%5zu N=%5zu) used=%5.2f%% "
	       "acc=%"PRIu64" (hit=%"PRIu64" miss=%"PRIu64") (sent_len=%zu dis=%u)\n",
	       ctxt->num_growth, ctxt->log2_table_size, used_slots, ctxt->table_size,
			 100.0f*used_slots/ctxt->table_size, 1.0f*total_c/used_slots,
	       z+nz, z, nz, N, 100.0f*(z+nz)/ctxt->table_size,
	       hit+miss, hit, miss, ctxt->sent->length, ctxt->sent->num_disjuncts);

	printf("Chain length:\n");
	for (size_t i = 1; i < ARRAY_SIZE(chain_length); i++)
		if (chain_length[i] > 0) printf("%zu: %d\n", i, chain_length[i]);
	if (chain_length[0] > 0) printf(">63: %d\n", chain_length[0]);

	if (!((null_count[1] == 1) && (null_count[2] == 0)))
	{
		printf("Null count:\n");
		for (unsigned int nc = 0; nc < ARRAY_SIZE(null_count); nc++)
		{
			if (0 != null_count[nc])
				printf("%u: %zu\n", nc, null_count[nc]);
		}
	}

	if (table_stat_entries)
	{
		for (unsigned int nc = 0; nc < ARRAY_SIZE(null_count); nc++)
		{
			if (0 == null_count[nc]) continue;

			printf("Null count %u:\n", nc);
			for (size_t i = 0; i < ctxt->table_size; i++)
			{
				for (Table_connector *t = ctxt->table[i]; t != NULL; t = t->next)
				{
					if (t->null_count != nc) continue;

					int n = printf("[%zu]", i);
					printf("%*d %5d c=%"COUNT_FMT"\n",  15-n, t->l_id, t->r_id, t->count);
				}
			}
		}
	}

	hit = miss = 0;
#endif /* DEBUG_TABLE_STAT */
}

static void table_grow(count_context_t *ctxt)
{
	table_alloc(ctxt, 0);

	/* Rehash. */
	Table_connector *oe;
	Pool_location loc = { 0 };
	while ((oe = pool_next(ctxt->sent->Table_connector_pool, &loc)) != NULL)
	{
		size_t ni = oe->hash & ctxt->table_mask;

		if (ctxt->table[ni] == NULL) ctxt->table_available_count--;
		oe->next = ctxt->table[ni];
		ctxt->table[ni] = oe;
	}

	ctxt->num_growth++;
}

/**
 * Stores the value in the table.  Assumes it's not already there.
 */
static Count_bin table_store(count_context_t *ctxt,
                           int lw, int rw,
                           const Connector *le, const Connector *re,
                           unsigned int null_count,
                           size_t hash, Count_bin c)
{
	if (ctxt->table_available_count == 0) table_grow(ctxt);

	int l_id = (NULL != le) ? le->tracon_id : lw;
	int r_id = (NULL != re) ? re->tracon_id : rw;
	size_t i = hash & ctxt->table_mask;
	Table_connector *n = pool_alloc(ctxt->sent->Table_connector_pool);

	if (ctxt->table[i] == NULL)
		ctxt->table_available_count--;

	n->l_id = l_id;
	n->r_id = r_id;
	n->null_count = null_count;
	n->next = ctxt->table[i];
	n->count = c;
	n->hash = hash;
	ctxt->table[i] = n;

	return c;
}

/**
 * Return the count for this quintuple if there, NULL otherwise.
 *
 * @param hash[out] If non-null, return the entry hash (undefined if
 * the entry is not found).
 * @return The count for this quintuple if there, NULL otherwise.
 */
inline Count_bin *
table_lookup(count_context_t *ctxt, int lw, int rw,
             const Connector *le, const Connector *re,
             unsigned int null_count, size_t *hash)
{
	int l_id = (NULL != le) ? le->tracon_id : lw;
	int r_id = (NULL != re) ? re->tracon_id : rw;

	size_t h = pair_hash(lw, rw, l_id, r_id, null_count);
	Table_connector *t = ctxt->table[h & ctxt->table_mask];

	for (; t != NULL; t = t->next)
	{
		if ((t->l_id == l_id) && (t->r_id == r_id) &&
		    (t->null_count == null_count))
		{
			TABLE_STAT(hit++);
			return &t->count;
		}
	}
	TABLE_STAT(miss++);

	if (hash != NULL) *hash = h;
	TABLE_STAT(miss++);
	return NULL;
}

extern  Count_bin *
table_lookup(count_context_t *, int, int,
             const Connector *, const Connector *,
             unsigned int, size_t *);

/**
 * Generate a word skip vector.
 * This implements an idea similar to the Boyer-Moore algo for searches.
 */
static void generate_word_skip_vector(count_context_t *ctxt, wordvecp wv,
                                      Connector *le, Connector *re,
                                      int start_word, int end_word,
                                      int lw, int rw)
{
	if (le != NULL)
	{
		int check_word = start_word;
		int i;

		if (wv == NULL) wv = ctxt->table_lrcnt[0][le->tracon_id];
		unsigned int sent_nc = ctxt->sent->null_count;
		for (i = start_word + 1; i < end_word; i++)
		{
			Table_lrcnt *e = &wv[i - le->nearest_word];
			e->check_next = INCREMENT_WORD;
			if((e->status != 0) || (sent_nc > e->null_count))
			{
				wv[check_word - le->nearest_word].check_next = i;
				check_word = i;
			}
		}
		if (check_word <= end_word - 1)
			wv[check_word - le->nearest_word].check_next = end_word;

#if 0
		printf("id %d w(%3d, %3d), se(%3d, %3d) sent_nc %u size %d\n",
		       le->tracon_id, lw, rw, start_word, end_word,
		       ctxt->sent->null_count, le->farthest_word-le->nearest_word+1);
		for (i = start_word; i < end_word; i++)
		{
			Table_lrcnt *e = &wv[i - le->nearest_word];
			printf("\tw%-3d idx %-3d status %d nc %-3u next %d\n",
			       i,  i - le->nearest_word, e->status, e->null_count,
			       e->check_next);
		}
#endif
	}
	else
	{
		int check_word = start_word;
		int i;

		if (wv == NULL) wv = ctxt->table_lrcnt[1][re->tracon_id];
		unsigned int sent_nc = ctxt->sent->null_count;
		for (i = start_word + 1; i < end_word; i++)
		{
			Table_lrcnt *e = &wv[i - re->farthest_word];
			e->check_next = INCREMENT_WORD;
			if((e->status != 0) || (sent_nc > e->null_count))
			{
				wv[check_word - re->farthest_word].check_next = i;
				check_word = i;
			}
		}
		if (check_word <= end_word - 1)
			wv[check_word - re->farthest_word].check_next = end_word;

#if 0
		printf("id %d w(%3d, %3d), se(%3d, %3d) sent_nc %u size %d\n",
		       le->tracon_id, lw, rw, start_word, end_word,
		       ctxt->sent->null_count, re->nearest_word-re->farthest_word+1);
		for (i = start_word; i < end_word; i++)
		{
			Table_lrcnt *e = &wv[i - re->farthest_word];
			printf("\tw%-3d idx %-3d status %d nc %-3u next %d\n",
			       i,  i - re->farthest_word, e->status, e->null_count,
			       e->check_next);
		}
#endif
	}
}

/**
 * Cache lookup:
 * Is the range [c, w) going to yield a nonzero leftcount / rightcount?
 *
 * @param ctxt Count context.
 * @param dir Direction - 0: leftcount; 1: rightcount.
 * @param c The connector that starts the range.
 * @param wordvec_index Word-vector index.
 * @param null_count The current null-count to check.
 *
 * Return these values:
 * @param lnull_start First null count to check (the previous ones can be
 * skipped because the cache indicates they yield a zero count.)
 * @return Cache entry for the given range. Possible values:
 *    NULL - A nonzero count may be encountered for \c null_count>=lnull_start.
 *    lrcnt_cache_zero - A zero count would result.
 *    Cache pointer - An update for \c null_count>=lnull_start is needed.
 */
static Table_lrcnt *is_lrcnt(count_context_t *ctxt, int dir, Connector *c,
                             unsigned int wordvec_index,
                             unsigned int null_count, unsigned int *null_start)
{
	if (ctxt->is_short) return NULL;

	wordvecp *wv = &ctxt->table_lrcnt[dir][c->tracon_id];
	if (*wv == NULL)
	{
		if (null_start != NULL)
		{
			/* Create a new cache entry, to be updated by lrcnt_cache_update(). */
			const size_t wordvec_size = abs(c->farthest_word - c->nearest_word) + 1;
			*wv = pool_alloc_vec(ctxt->sent->wordvec_pool, wordvec_size);
			memset(*wv, -1, sizeof(Table_lrcnt) * wordvec_size);

			*null_start = 0;
			assert(wordvec_index < wordvec_size, "Bad wordvec index");
			return &(*wv)[wordvec_index]; /* Needs update */
		}
		return NULL;<commit_msg>is_lrcnt(): Update function description rot<commit_after>/*************************************************************************/
/* Copyright (c) 2004                                                    */
/* <NAME>, <NAME>, and <NAME>                    */
/* Copyright (c) 2013,2014,2015 <NAME>                            */
/* All rights reserved                                                   */
/*                                                                       */
/* Use of the link grammar parsing system is subject to the terms of the */
/* license set forth in the LICENSE file included with this software.    */
/* This license allows free redistribution and use in source and binary  */
/* forms, with or without modification, subject to certain conditions.   */
/*                                                                       */
/*************************************************************************/

#include <limits.h>
#include <inttypes.h>                 // PRIu64
#if HAVE_THREADS_H
#include <threads.h>
#endif /* HAVE_THREADS_H */

#include "link-includes.h"
#include "api-structures.h"
#include "connectors.h"
#include "count.h"
#include "dict-common/dict-common.h"    // IS_GENERATION
#include "disjunct-utils.h"
#include "fast-match.h"
#include "resources.h"
#include "tokenize/word-structures.h" // for Word_struct
#include "utilities.h"

/* This file contains the exhaustive search algorithm. */

#define D_COUNT 5 /* General debug level for this file. */

typedef struct Table_connector_s Table_connector;
struct Table_connector_s
{
	Table_connector  *next;
	int              l_id, r_id;
	Count_bin          count;
	unsigned int     null_count;
	size_t           hash;
};

typedef uint8_t null_count_m;  /* Storage representation of null_count */
typedef uint8_t WordIdx_m;     /* Storage representation of word index */

/* Most of the time, do_count() yields a zero leftcount/rightcount when it
 * parses a word range in which one end is a certain tracon and the other
 * end is a word that is between the nearest_word and farthest_word of the
 * first connector of that tracon (words out of this range are not checked).
 * Memoizing this results in a huge speedup for sentences that are not
 * short.
 *
 * To that end, two cache arrays, one of leftcount and the other for
 * rightcount, indexed by the tracon number (tracon_id), are maintained.
 *
 * Each element of these arrays points to a vector, called here word-vector,
 * with a size equal to abs(nearest_word - farthest_word) + 1.
 *
 * Each element of this vector predicts, in it's status field, whether the
 * expected count is zero for a given null-count (when the word it
 * represents is the end word of the range).
 * This prediction is valid for null-counts up to null_count (or for any
 * null-count if null_count is ANY_NULL_COUNT).
 *
 * The check_next filed indicates the next word to be checked. Each
 * word-vector is updated each time one of its elements gets updated, so
 * check_next skips all the words for which the count is known to be zero. */
typedef struct
{
	null_count_m null_count; /* status==0 valid up to this null count */
	int8_t status;         /* -1: Needs update; 0: No count; 1: Count possible */
	WordIdx_m check_next;    /* Next word to check */
} Table_lrcnt;

/* Using the word-vectors for very short sentences has too much overhead. */
static const size_t min_len_word_vector = 10; /* This is just an estimation. */

/* Special values for Table_lrcnt fields null_count and check_next. */
#define ANY_NULL_COUNT (MAX_SENTENCE + 1)
#define INCREMENT_WORD ((uint8_t)(MAX_SENTENCE+1)) /* last checked word + 1 */

typedef Table_lrcnt *wordvecp;
static Table_lrcnt lrcnt_cache_zero; /* A sentinel for status==0 */

#if defined DEBUG || DEBUG_COUNT_COST
#define COUNT_COST(...) __VA_ARGS__
#else
#define COUNT_COST(...)
#endif

struct count_context_s
{
	fast_matcher_t *mchxt;
	Sentence sent;
	/* int     null_block; */ /* not used, always 1 */
	bool    islands_ok;
	bool    exhausted;
	uint8_t num_growth;       /* Number of table growths, for debug */
	bool    is_short;
	uint8_t log2_table_size;
	uint32_t checktimer;  /* Avoid excess system calls */
	size_t table_size;
	size_t table_mask;
	size_t table_available_count;
	uint32_t table_lrcnt_size[2];
	Table_connector ** table;
	wordvecp *table_lrcnt[2];  /* Per dir wordvec, indexed by tracon_id */
	Resources current_resources;
	COUNT_COST(uint64_t count_cost[3];)
};
#define MAX_TABLE_SIZE(s) (s / 10) /* Low load factor, for speed */
#define MAX_LOG2_TABLE_SIZE ((sizeof(size_t)==4) ? 25 : 34)

#if HAVE_THREADS_H
/* Each thread will get it's own version of the `kept_table`.
 * If the program creates zillions of threads, then there will
 * be a mem-leak if this table is not released when each thread
 * exists. This code arranges so that `free_tls_table` is called
 * when the thread exists.
 */
static void free_tls_table(void* ptr_to_table)
{
	if (NULL == ptr_to_table) return;

	Table_connector** kept_table = *((Table_connector***)ptr_to_table);
	if (NULL == kept_table) return;

	free(kept_table);
	*((Table_connector***) ptr_to_table) = NULL;
}

static tss_t key;
static void make_key(void)
{
	tss_create(&key, free_tls_table);
}
#endif /* HAVE_THREADS_H */

/**
 * Allocate memory for the connector-pair table and initialize table-size
 * related fields (table_size and table_available_count). Reuse the
 * previous table memory if the request is for a table that fits. If this
 * is not a call to grow the table, free it if not reused.
 *
 * @ctxt[in, out] Table info.
 * @param shift log2 table size, or \c 0 for table growth. On table growth,
 * increase the new table size by 2.
 */
static void table_alloc(count_context_t *ctxt, unsigned int shift)
{
	static TLS Table_connector **kept_table = NULL;
	static TLS unsigned int log2_kept_table_size = 0;

#if HAVE_THREADS_H
	// Install a thread-exit handler, to free kept_table on thread-exit.
	static once_flag flag = ONCE_FLAG_INIT;
	call_once(&flag, make_key);

	if (NULL == kept_table)
		tss_set(key, &kept_table);
#endif /* HAVE_THREADS_H */

	if (shift == 0)
		shift = ctxt->log2_table_size + 1; /* Double the table size */
	lgdebug(+D_COUNT, "Connector table log2 size %u\n", shift);

	/* Keep the table indefinitely (until thread-exit), so that it can
	 * be reused. This avoids a large overhead in malloc/free when
	 * large memory blocks are allocated. Large block in Linux trigger
	 * system calls to mmap/munmap that eat up a lot of time.
	 * (Up to 20%, depending on the sentence and CPU.) */
	ctxt->table_size = (1ULL << shift);
	if ((shift > log2_kept_table_size) || (kept_table == NULL))
	{
		log2_kept_table_size = shift;

		if (kept_table) free(kept_table);
		kept_table = malloc(sizeof(Table_connector *) * ctxt->table_size);
	}

	memset(kept_table, 0, sizeof(Table_connector *) * ctxt->table_size);

	/* This is here and not in init_table() because it must be set
	 * also when the table growths. */
	ctxt->log2_table_size = shift;
	ctxt->table_mask = ctxt->table_size - 1;
	ctxt->table = kept_table;

	if (shift >= MAX_LOG2_TABLE_SIZE)
		ctxt->table_available_count = UINT_MAX; /* Prevent growth */
	else
		ctxt->table_available_count = MAX_TABLE_SIZE(ctxt->table_size);
}

/**
 * Allocate the table with a sentence-dependent table size.  Use
 * sent->length as a hint for the initial table size. Usually, this
 * saves on dynamic table growth, which is costly.
 * */
static void init_table(count_context_t *ctxt)
{
	Sentence sent = ctxt->sent;

	/* A piecewise exponential function determines the size of the
	 * hash table. Probably should make use of the actual number of
	 * disjuncts, rather than just the number of words.
	 */
	unsigned int shift;
	if (sent->length >= 16)
	{
		shift = 14 + sent->length / 16;
	}
	else
	{
		shift = 14;
	}
#if 0 /* Not yet */
	shift += (unsigned int)sent->num_disjuncts / (sent->length * 200);
#endif

	if (MAX_LOG2_TABLE_SIZE < shift) shift = MAX_LOG2_TABLE_SIZE;

	table_alloc(ctxt, shift);
}

static void free_table_lrcnt(count_context_t *ctxt)
{
	if (ctxt->is_short) return;

	if (verbosity_level(D_COUNT))
	{
		unsigned int nonzero = 0, any_null = 0, zero = 0, non_max_null = 0;
		Pool_location loc = { 0 };
		Table_lrcnt *t;

		/* Note: Due to a current pool_next() problem for vector elements,
		 * the stats results here may be slightly skewed.  See the comment
		 * on that in memory-pool.h. */
		while ((t = pool_next(ctxt->sent->wordvec_pool, &loc)) != NULL)
		{
			if (t->status == -1) continue;
			if (t->status == 1)
				nonzero++;
			else if (t->null_count == ANY_NULL_COUNT)
				any_null++;
			else if (ctxt->sent->null_count > t->null_count)
				non_max_null++;
			else if (ctxt->sent->null_count == t->null_count)
				zero++;
		}

		const unsigned int num_values = ctxt->sent->wordvec_pool->curr_elements;
		lgdebug(+0, "Values %u (usage = non_max_null %u + other %u, "
		        "other = any_null_zero %u + zero %u + nonzero %u)\n",
		        num_values, non_max_null, num_values-non_max_null,
		        any_null, zero, nonzero);

		for (unsigned int dir = 0; dir < 2; dir++)
		{
			unsigned int table_usage = 0;

			for (size_t i = 0; i < ctxt->table_lrcnt_size[dir]; i++)
			{
				if (ctxt->table_lrcnt[dir][i] != NULL) continue;
				table_usage++;
			}

			lgdebug(+0, "Direction %u: Using %u/%u tracons %.2f%%\n\\",
			        dir, table_usage, ctxt->table_lrcnt_size[dir],
			        100.0f*table_usage / ctxt->table_lrcnt_size[dir]);
		}
	}

	for (unsigned int dir = 0; dir < 2; dir++)
	{
		free(ctxt->table_lrcnt[dir]);
		ctxt->table_lrcnt[dir] = NULL;
	}
}

static void init_table_lrcnt(count_context_t *ctxt)
{
	if (ctxt->is_short) return;
	Sentence sent = ctxt->sent;

	for (unsigned int dir = 0; dir < 2; dir++)
	{
		const size_t sz = sizeof(wordvecp) * ctxt->table_lrcnt_size[dir];
		ctxt->table_lrcnt[dir] = malloc(sz);
		memset(ctxt->table_lrcnt[dir], 0, sz);
	}

	const size_t initial_size = MIN(sent->length/2, 16) *
		                   (ctxt->table_lrcnt_size[0] + ctxt->table_lrcnt_size[1]);


	if (NULL != sent->wordvec_pool)
	{
		pool_reuse(sent->wordvec_pool);
	}
	else
	{
		ctxt->sent->wordvec_pool =
			pool_new(__func__, "Table_lrcnt", /*num_elements*/initial_size,
			         sizeof(Table_lrcnt), /*zero_out*/false,
			         /*align*/false, /*exact*/false);
	}
}

//#define DEBUG_TABLE_STAT
#if defined(DEBUG) || defined(DEBUG_TABLE_STAT)
static uint64_t hit, miss;  /* Table value found/not found */
#define TABLE_STAT(...) __VA_ARGS__
#else
#define TABLE_STAT(...)
#endif

/**
 * Provide data for insights on the effectively of the connector pair table.
 * Hits, misses, chain length, number of elements with zero/nonzero counts.
 */
static void table_stat(count_context_t *ctxt)
{
#ifdef DEBUG_TABLE_STAT
	if (!verbosity_level(+D_COUNT)) return;

	size_t z = 0, nz = 0;  /* Number of entries with zero and non-zero counts */
	size_t c, total_c = 0; /* Chain length */
	size_t N = 0;          /* NULL table slots */
	size_t null_count[256] = { 0 };   /* null_count histogram */
	int chain_length[64] = { 0 };     /* Chain length histogram */
	bool table_stat_entries = test_enabled("count-table-entries");

	for (size_t i = 0; i < ctxt->table_size; i++)
	{
		Table_connector *t = ctxt->table[i];

		c = 0;
		if (t == NULL)
		{
			N++;
		}
		else
		{
			assert(t->hash != 0, "Invalid hash value: 0");
			assert((hist_total(&t->count)>=0)&&(hist_total(&t->count) <= INT_MAX),
			       "Invalid count %"COUNT_FMT, hist_total(&t->count));
			assert(t->l_id < (int)ctxt->sent->length ||
			       ((t->l_id >= 255)&&(t->l_id < (int)ctxt->table_lrcnt_size[0])),
			       "invalid l_id %d", t->l_id);
			assert(t->r_id <= (int)ctxt->sent->length ||
			       ((t->r_id > 255)&&(t->r_id < (int)ctxt->table_lrcnt_size[1])),
			       "invalid r_id %d", t->r_id);
		}
		for (; t != NULL; t = t->next)
		{
			c++;
			if (hist_total(&t->count) == 0)
				z++;
			else
				nz++;
			null_count[t->null_count]++;
		}
		if (c > 0) /* Slot 0 used for length overflow */
		{
			chain_length[c >= (int)ARRAY_SIZE(chain_length) ? 0 : c]++;
			total_c += c;
		}
		//if (c != 0) printf("Connector table [%d] c=%d\n", i, c);
	}

	size_t used_slots = ctxt->table_size-N;
	/* The used= value is TotalValues/TableSize (not UsedSlots/TableSize). */
	printf("Connector table: num_growth=%u msb=%u slots=%6zu/%6zu (%5.2f%%) "
	       "avg-chain=%4.2f values=%6zu (z=%5zu nz=%5zu N=%5zu) used=%5.2f%% "
	       "acc=%"PRIu64" (hit=%"PRIu64" miss=%"PRIu64") (sent_len=%zu dis=%u)\n",
	       ctxt->num_growth, ctxt->log2_table_size, used_slots, ctxt->table_size,
			 100.0f*used_slots/ctxt->table_size, 1.0f*total_c/used_slots,
	       z+nz, z, nz, N, 100.0f*(z+nz)/ctxt->table_size,
	       hit+miss, hit, miss, ctxt->sent->length, ctxt->sent->num_disjuncts);

	printf("Chain length:\n");
	for (size_t i = 1; i < ARRAY_SIZE(chain_length); i++)
		if (chain_length[i] > 0) printf("%zu: %d\n", i, chain_length[i]);
	if (chain_length[0] > 0) printf(">63: %d\n", chain_length[0]);

	if (!((null_count[1] == 1) && (null_count[2] == 0)))
	{
		printf("Null count:\n");
		for (unsigned int nc = 0; nc < ARRAY_SIZE(null_count); nc++)
		{
			if (0 != null_count[nc])
				printf("%u: %zu\n", nc, null_count[nc]);
		}
	}

	if (table_stat_entries)
	{
		for (unsigned int nc = 0; nc < ARRAY_SIZE(null_count); nc++)
		{
			if (0 == null_count[nc]) continue;

			printf("Null count %u:\n", nc);
			for (size_t i = 0; i < ctxt->table_size; i++)
			{
				for (Table_connector *t = ctxt->table[i]; t != NULL; t = t->next)
				{
					if (t->null_count != nc) continue;

					int n = printf("[%zu]", i);
					printf("%*d %5d c=%"COUNT_FMT"\n",  15-n, t->l_id, t->r_id, t->count);
				}
			}
		}
	}

	hit = miss = 0;
#endif /* DEBUG_TABLE_STAT */
}

static void table_grow(count_context_t *ctxt)
{
	table_alloc(ctxt, 0);

	/* Rehash. */
	Table_connector *oe;
	Pool_location loc = { 0 };
	while ((oe = pool_next(ctxt->sent->Table_connector_pool, &loc)) != NULL)
	{
		size_t ni = oe->hash & ctxt->table_mask;

		if (ctxt->table[ni] == NULL) ctxt->table_available_count--;
		oe->next = ctxt->table[ni];
		ctxt->table[ni] = oe;
	}

	ctxt->num_growth++;
}

/**
 * Stores the value in the table.  Assumes it's not already there.
 */
static Count_bin table_store(count_context_t *ctxt,
                           int lw, int rw,
                           const Connector *le, const Connector *re,
                           unsigned int null_count,
                           size_t hash, Count_bin c)
{
	if (ctxt->table_available_count == 0) table_grow(ctxt);

	int l_id = (NULL != le) ? le->tracon_id : lw;
	int r_id = (NULL != re) ? re->tracon_id : rw;
	size_t i = hash & ctxt->table_mask;
	Table_connector *n = pool_alloc(ctxt->sent->Table_connector_pool);

	if (ctxt->table[i] == NULL)
		ctxt->table_available_count--;

	n->l_id = l_id;
	n->r_id = r_id;
	n->null_count = null_count;
	n->next = ctxt->table[i];
	n->count = c;
	n->hash = hash;
	ctxt->table[i] = n;

	return c;
}

/**
 * Return the count for this quintuple if there, NULL otherwise.
 *
 * @param hash[out] If non-null, return the entry hash (undefined if
 * the entry is not found).
 * @return The count for this quintuple if there, NULL otherwise.
 */
inline Count_bin *
table_lookup(count_context_t *ctxt, int lw, int rw,
             const Connector *le, const Connector *re,
             unsigned int null_count, size_t *hash)
{
	int l_id = (NULL != le) ? le->tracon_id : lw;
	int r_id = (NULL != re) ? re->tracon_id : rw;

	size_t h = pair_hash(lw, rw, l_id, r_id, null_count);
	Table_connector *t = ctxt->table[h & ctxt->table_mask];

	for (; t != NULL; t = t->next)
	{
		if ((t->l_id == l_id) && (t->r_id == r_id) &&
		    (t->null_count == null_count))
		{
			TABLE_STAT(hit++);
			return &t->count;
		}
	}
	TABLE_STAT(miss++);

	if (hash != NULL) *hash = h;
	TABLE_STAT(miss++);
	return NULL;
}

extern  Count_bin *
table_lookup(count_context_t *, int, int,
             const Connector *, const Connector *,
             unsigned int, size_t *);

/**
 * Generate a word skip vector.
 * This implements an idea similar to the Boyer-Moore algo for searches.
 */
static void generate_word_skip_vector(count_context_t *ctxt, wordvecp wv,
                                      Connector *le, Connector *re,
                                      int start_word, int end_word,
                                      int lw, int rw)
{
	if (le != NULL)
	{
		int check_word = start_word;
		int i;

		if (wv == NULL) wv = ctxt->table_lrcnt[0][le->tracon_id];
		unsigned int sent_nc = ctxt->sent->null_count;
		for (i = start_word + 1; i < end_word; i++)
		{
			Table_lrcnt *e = &wv[i - le->nearest_word];
			e->check_next = INCREMENT_WORD;
			if((e->status != 0) || (sent_nc > e->null_count))
			{
				wv[check_word - le->nearest_word].check_next = i;
				check_word = i;
			}
		}
		if (check_word <= end_word - 1)
			wv[check_word - le->nearest_word].check_next = end_word;

#if 0
		printf("id %d w(%3d, %3d), se(%3d, %3d) sent_nc %u size %d\n",
		       le->tracon_id, lw, rw, start_word, end_word,
		       ctxt->sent->null_count, le->farthest_word-le->nearest_word+1);
		for (i = start_word; i < end_word; i++)
		{
			Table_lrcnt *e = &wv[i - le->nearest_word];
			printf("\tw%-3d idx %-3d status %d nc %-3u next %d\n",
			       i,  i - le->nearest_word, e->status, e->null_count,
			       e->check_next);
		}
#endif
	}
	else
	{
		int check_word = start_word;
		int i;

		if (wv == NULL) wv = ctxt->table_lrcnt[1][re->tracon_id];
		unsigned int sent_nc = ctxt->sent->null_count;
		for (i = start_word + 1; i < end_word; i++)
		{
			Table_lrcnt *e = &wv[i - re->farthest_word];
			e->check_next = INCREMENT_WORD;
			if((e->status != 0) || (sent_nc > e->null_count))
			{
				wv[check_word - re->farthest_word].check_next = i;
				check_word = i;
			}
		}
		if (check_word <= end_word - 1)
			wv[check_word - re->farthest_word].check_next = end_word;

#if 0
		printf("id %d w(%3d, %3d), se(%3d, %3d) sent_nc %u size %d\n",
		       le->tracon_id, lw, rw, start_word, end_word,
		       ctxt->sent->null_count, re->nearest_word-re->farthest_word+1);
		for (i = start_word; i < end_word; i++)
		{
			Table_lrcnt *e = &wv[i - re->farthest_word];
			printf("\tw%-3d idx %-3d status %d nc %-3u next %d\n",
			       i,  i - re->farthest_word, e->status, e->null_count,
			       e->check_next);
		}
#endif
	}
}

/**
 * Cache lookup:
 * Is the range [c, w) going to yield a nonzero leftcount / rightcount?
 *
 * @param ctxt Count context.
 * @param dir Direction - 0: leftcount; 1: rightcount.
 * @param c The connector that starts the range.
 * @param wordvec_index Word-vector index.
 * @param null_count[in] The current null-count to check.
 *
 * Return these values:
 * @param null_start[out] First null count to check (the previous ones can be
 * skipped because the cache indicates they yield a zero count.)
 * @return Cache entry for the given range. Possible values:
 *    NULL - A nonzero count may be encountered for \c null_count>=null_start.
 *    lrcnt_cache_zero - A zero count would result.
 *    Cache pointer - An update for \c null_count>=null_start is needed.
 */
static Table_lrcnt *is_lrcnt(count_context_t *ctxt, int dir, Connector *c,
                             unsigned int wordvec_index,
                             unsigned int null_count, unsigned int *null_start)
{
	if (ctxt->is_short) return NULL;

	wordvecp *wv = &ctxt->table_lrcnt[dir][c->tracon_id];
	if (*wv == NULL)
	{
		if (null_start != NULL)
		{
			/* Create a new cache entry, to be updated by lrcnt_cache_update(). */
			const size_t wordvec_size = abs(c->farthest_word - c->nearest_word) + 1;
			*wv = pool_alloc_vec(ctxt->sent->wordvec_pool, wordvec_size);
			memset(*wv, -1, sizeof(Table_lrcnt) * wordvec_size);

			*null_start = 0;
			assert(wordvec_index < wordvec_size, "Bad wordvec index");
			return &(*wv)[wordvec_index]; /* Needs update */
		}
		return NULL;
{'fraction_non_alphanumeric': 0.1439576432801365, 'fraction_numerical': 0.011492522332630734, 'mean_word_length': 3.106439979392066, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 393, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7558225', 'n_tokens_mistral': 15243, 'n_tokens_neox': 14169, 'n_words': 4021}