<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 "link-includes.h"
#include "api-structures.h"
#include "connectors.h"
#include "count.h"
#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;
	unsigned int     hash;
};

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

/* Table of ranges [tracon_id, w) that would yield a zero
 * leftcount/rightcount up to null_count. */
typedef struct Table_lrcnt_s
{
	int tracon_id;
	WordIdx_m w;
	null_count_m null_count;
	unsigned short status;  /* 0: Count would be 0; 1: Count may be nonzero */
} Table_lrcnt;
#define MAX_TABLE_LRCNT_SIZE(s) ((s) * 3 / 4) /* Limit pathological cases */
#define ANY_NULL_COUNT (MAX_SENTENCE + 1)
static Table_lrcnt lrcnt_cache_zero; /* A returned sentinel */

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 */
	unsigned int checktimer;  /* Avoid excess system calls */
	unsigned int table_size;
	unsigned int log2_table_size;
	unsigned int table_available_count;
	unsigned int table_lrcnt_size;
	unsigned int table_lrcnt_available_count;
	Table_connector **table;
	Table_lrcnt *table_lrcnt;
	Resources current_resources;
};
#define MAX_TABLE_SIZE(s) (s / 10) /* Low load factor, for speed */
#define MAX_LOG2_TABLE_SIZE 24     /* 128 on 64-bit systems */

static void free_table(count_context_t *ctxt)
{
	ctxt->table = NULL;
	ctxt->table_size = 0;
}

static void free_kept_table(void);
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 (ctxt == NULL)
	{
		free(kept_table);
		return;
	}

	if (shift == 0)
	{
		/* This is a request to grow the table. */
		shift = ctxt->log2_table_size + 1; /* Double the table size. */
		kept_table = NULL;                 /* Don't free it. */
	}

	/* Keep the table indefinitely (or until exiting), 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 = (1U << shift);
	if ((shift > log2_kept_table_size) || (kept_table == NULL))
	{
		if (log2_kept_table_size == 0) atexit(free_kept_table);
		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);

	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);
}

/**
 * This function is called on program exit so no memory remains allocated.
 * This is not really necessary because even for debug the message on
 * memory that left allocated can be put in an ignore-list.
 *
 * FIXME: Fix thread memory leak resulted by not freeing table memory
 * on thread exit.
 */
static void free_kept_table(void)
{
	table_alloc(NULL, 0);
}

static void init_table(count_context_t *ctxt, size_t sent_len)
{
	if (ctxt->table) free_table(ctxt);

	/* 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_len >= 10)
	{
		shift = 12 + (sent_len) / 4;
	}
	else
	{
		shift = 12;
	}

	if (MAX_LOG2_TABLE_SIZE < shift) shift = MAX_LOG2_TABLE_SIZE;
	lgdebug(+D_COUNT, "Connector table size (1<<%u)*%zu\n", shift, sizeof(Table_connector *));

	table_alloc(ctxt, shift);
}

static void free_table_lrcnt(count_context_t *ctxt)
{
	if (verbosity_level(D_COUNT))
	{
		unsigned int table_usage = MAX_TABLE_LRCNT_SIZE(ctxt->table_lrcnt_size) -
			ctxt->table_lrcnt_available_count;
		unsigned int nonzero = 0;
		unsigned int any_null = 0;
		unsigned int zero = 0;
		unsigned int non_max_null = 0;

		for (unsigned int i = 0; i < ctxt->table_lrcnt_size; i++)
		{
			if (ctxt->table_lrcnt[i].tracon_id == -1) continue;

			if (ctxt->table_lrcnt[i].status == 1)
				nonzero++;
			else if (ctxt->table_lrcnt[i].null_count == ANY_NULL_COUNT)
				any_null++;
			else if (ctxt->sent->null_count > ctxt->table_lrcnt[i].null_count)
				non_max_null++;
			else if (ctxt->sent->null_count == ctxt->table_lrcnt[i].null_count)
				zero++;
		}

		lgdebug(+0, "Usage %u/%u %.2f%% "
		        "(usage = non_max_null %u + other %u, "
		        "other = any_null_zero %u + zero %u + nonzero %u)\n",
		        table_usage, ctxt->table_lrcnt_size,
		        100.0f*table_usage / ctxt->table_lrcnt_size,
		        non_max_null, table_usage-non_max_null, any_null, zero, nonzero);
	}

	free(ctxt->table_lrcnt);
	ctxt->table_lrcnt = NULL;
}

static void init_table_lrcnt(count_context_t *ctxt, Sentence sent)
{

	if (ctxt->table_lrcnt == NULL)
	{
		ctxt->table_lrcnt_size =
			next_power_of_two_up(2048 + sent->num_disjuncts * sent->length / 1.5f);
		ctxt->table_lrcnt = malloc(ctxt->table_lrcnt_size * sizeof(Table_lrcnt));
	}

	for (size_t i = 0; i < ctxt->table_lrcnt_size; i++)
	{
		ctxt->table_lrcnt[i].tracon_id = -1;
	}
	ctxt->table_lrcnt_available_count = MAX_TABLE_LRCNT_SIZE(ctxt->table_lrcnt_size);
}

static size_t table_lrcnt_hash(int tracon_id, int cw, int w)
{
	unsigned int i = tracon_id;
	i = cw + (i << 6) + (i << 16) - i;
	i = w + (i << 6) + (i << 16) - i;

	return i;
}

static Table_lrcnt *table_lrcnt_store(count_context_t *ctxt, int tracon_id,
                                    int cw, int w)
{
	static Table_lrcnt table_full; /* It may get written never read */
	if (ctxt->table_lrcnt_available_count == 0) return &table_full;

	const size_t sizemod = ctxt->table_lrcnt_size-1;
	size_t h = table_lrcnt_hash(tracon_id, cw, w) & sizemod;
	Table_lrcnt *t = ctxt->table_lrcnt;

	while (t[h].tracon_id != -1)
	{
		h = (h+1) & sizemod;
	}

	ctxt->table_lrcnt_available_count--;
	t[h].tracon_id = tracon_id;
	t[h].w = w;
	t[h].null_count = (null_count_m)-1;

	return &t[h];
}

static Table_lrcnt *find_table_lrcnt_pointer(count_context_t *ctxt,
                                           int tracon_id, int cw, int w)
{
	static Table_lrcnt table_full =
	{
		.null_count = (null_count_m)-1,
		.status = 1,
	};
	/* Disregard caching in case the table is full - this shouldn't happen. */
	if (ctxt->table_lrcnt_available_count == 0) return &table_full;

	/* Panic mode: Return a parse bypass indication if resources are
	 * exhausted.  checktimer is a device to avoid a gazillion system calls
	 * to get the timer value. On circa-2018 machines, it results in
	 * several timer calls per second. */
	ctxt->checktimer ++;
	if (ctxt->exhausted || ((0 == ctxt->checktimer%(1<<22)) &&
	                       (ctxt->current_resources != NULL) &&
	                       //fprintf(stderr, "T") &&
	                       resources_exhausted(ctxt->current_resources)))
	{
		ctxt->exhausted = true;
		return &lrcnt_cache_zero;
	}

	const size_t sizemod = ctxt->table_lrcnt_size-1;
	size_t h = table_lrcnt_hash(tracon_id, cw, w) & sizemod;
	Table_lrcnt *t = ctxt->table_lrcnt;

	while (t[h].tracon_id != -1)
	{
		if ((t[h].tracon_id == tracon_id) && (t[h].w == w)) return &t[h];
		h = (h+1) & sizemod;
	}

	return NULL;
}

//#define DEBUG_TABLE_STAT
#if defined(DEBUG) || defined(DEBUG_TABLE_STAT)
static size_t hit, miss;  /* Table value found/not found */
#undef DEBUG_TABLE_STAT
#define DEBUG_TABLE_STAT(x) x
/**
 * 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)
{
	int z = 0, nz = 0;  /* Number of entries with zero and non-zero counts */
	int c, total_c = 0; /* Chain length */
	int N = 0;          /* NULL table slots */
	int null_count[256] = { 0 };   /* null_count histogram */
	int chain_length[64] = { 0 };  /* Chain length histogram */
	bool table_stat_entries = test_enabled("count-table-entries");
	int n;              /* For printf() pretty printing */

	for (unsigned int i = 0; i < ctxt->table_size; i++)
	{
		c = 0;
		Table_connector *t = ctxt->table[i];
		if (t == NULL) N++;
		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);
	}

	int used_slots = ctxt->table_size-N;
	/* The used= value is TotalValues/TableSize (not UsedSlots/TableSize). */
	printf("Connector table: num_growth=%u msb=%u slots=%6d/%6u (%5.2f%%) "
	       "avg-chain=%4.2f values=%6d (z=%5d nz=%5d N=%5d) used=%5.2f%% "
	       "acc=%zu (hit=%zu miss=%zu) (sent_len=%zu)\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);

	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: %d\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 (unsigned int 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;

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

	hit = miss = 0;
}
#else
#define DEBUG_TABLE_STAT(x)
#endif /* DEBUG  */

/**
 * 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,
                                     unsigned int hash, Count_bin c)
{
	int l_id = (NULL != le) ? le->tracon_id : lw;
	int r_id = (NULL != re) ? re->tracon_id : rw;
	unsigned int i = hash & (ctxt->table_size -1);
	Table_connector *n = pool_alloc(ctxt->sent->Table_connector_pool);

	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;
}

/** returns the pointer to this info, NULL if not there */
static Table_connector *
find_table_pointer(count_context_t *ctxt,
                   int lw, int rw,
                   const Connector *le, const Connector *re,
                   unsigned int null_count, unsigned int *hash)
{
	int l_id = (NULL != le) ? le->tracon_id : lw;
	int r_id = (NULL != re) ? re->tracon_id : rw;

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

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

	if (hash != NULL) *hash = h;
	return t;
}

/** returns the count for this quintuple if there, -1 otherwise */
Count_bin* table_lookup(count_context_t * ctxt,
                       int lw, int rw, Connector *le, Connector *re,
                       unsigned int null_count)
{
	Table_connector *t = find_table_pointer(ctxt, lw, rw, le, re, null_count, NULL);

	if (t == NULL) return NULL; else return &t->count;
}

/**
 * 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 w The word that ends the range.
 * @param null_count The current null_count to check.
 * @param cw The word of this connector.
 *
 * 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:<commit_msg>count.c: Implement a dynamic hash table<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 "link-includes.h"
#include "api-structures.h"
#include "connectors.h"
#include "count.h"
#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;
	unsigned int     hash;
};

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

/* Table of ranges [tracon_id, w) that would yield a zero
 * leftcount/rightcount up to null_count. */
typedef struct Table_lrcnt_s
{
	int tracon_id;
	WordIdx_m w;
	null_count_m null_count;
	unsigned short status;  /* 0: Count would be 0; 1: Count may be nonzero */
} Table_lrcnt;
#define MAX_TABLE_LRCNT_SIZE(s) ((s) * 3 / 4) /* Limit pathological cases */
#define ANY_NULL_COUNT (MAX_SENTENCE + 1)
static Table_lrcnt lrcnt_cache_zero; /* A returned sentinel */

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 */
	unsigned int checktimer;  /* Avoid excess system calls */
	unsigned int table_size;
	unsigned int log2_table_size;
	unsigned int table_available_count;
	unsigned int table_lrcnt_size;
	unsigned int table_lrcnt_available_count;
	Table_connector **table;
	Table_lrcnt *table_lrcnt;
	Resources current_resources;
};
#define MAX_TABLE_SIZE(s) (s / 10) /* Low load factor, for speed */
#define MAX_LOG2_TABLE_SIZE 24     /* 128 on 64-bit systems */

static void free_table(count_context_t *ctxt)
{
	ctxt->table = NULL;
	ctxt->table_size = 0;
}

static void free_kept_table(void);

/**
 * 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, and don't free the previous table.
 */
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 (ctxt == NULL)
	{
		free(kept_table);
		return;
	}

	if (shift == 0)
	{
		/* This is a request to grow the table. */
		shift = ctxt->log2_table_size + 1; /* Double the table size. */
		kept_table = NULL;                 /* Don't free it. */
	}

	/* Keep the table indefinitely (or until exiting), 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 = (1U << shift);
	if ((shift > log2_kept_table_size) || (kept_table == NULL))
	{
		if (log2_kept_table_size == 0) atexit(free_kept_table);
		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 = 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);
}

/**
 * This function is called on program exit so no memory remains allocated.
 * This is not really necessary because even for debug the message on
 * memory that left allocated can be put in an ignore-list.
 *
 * FIXME: Fix thread memory leak resulted by not freeing table memory
 * on thread exit.
 */
static void free_kept_table(void)
{
	table_alloc(NULL, 0);
}

static void init_table(count_context_t *ctxt, size_t sent_len)
{
	if (ctxt->table) free_table(ctxt);

	/* 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_len >= 10)
	{
		shift = 12 + (sent_len) / 4;
	}
	else
	{
		shift = 12;
	}

	if (MAX_LOG2_TABLE_SIZE < shift) shift = MAX_LOG2_TABLE_SIZE;
	lgdebug(+D_COUNT, "Connector table size (1<<%u)*%zu\n", shift, sizeof(Table_connector *));

	table_alloc(ctxt, shift);
}

static void free_table_lrcnt(count_context_t *ctxt)
{
	if (verbosity_level(D_COUNT))
	{
		unsigned int table_usage = MAX_TABLE_LRCNT_SIZE(ctxt->table_lrcnt_size) -
			ctxt->table_lrcnt_available_count;
		unsigned int nonzero = 0;
		unsigned int any_null = 0;
		unsigned int zero = 0;
		unsigned int non_max_null = 0;

		for (unsigned int i = 0; i < ctxt->table_lrcnt_size; i++)
		{
			if (ctxt->table_lrcnt[i].tracon_id == -1) continue;

			if (ctxt->table_lrcnt[i].status == 1)
				nonzero++;
			else if (ctxt->table_lrcnt[i].null_count == ANY_NULL_COUNT)
				any_null++;
			else if (ctxt->sent->null_count > ctxt->table_lrcnt[i].null_count)
				non_max_null++;
			else if (ctxt->sent->null_count == ctxt->table_lrcnt[i].null_count)
				zero++;
		}

		lgdebug(+0, "Usage %u/%u %.2f%% "
		        "(usage = non_max_null %u + other %u, "
		        "other = any_null_zero %u + zero %u + nonzero %u)\n",
		        table_usage, ctxt->table_lrcnt_size,
		        100.0f*table_usage / ctxt->table_lrcnt_size,
		        non_max_null, table_usage-non_max_null, any_null, zero, nonzero);
	}

	free(ctxt->table_lrcnt);
	ctxt->table_lrcnt = NULL;
}

static void init_table_lrcnt(count_context_t *ctxt, Sentence sent)
{

	if (ctxt->table_lrcnt == NULL)
	{
		ctxt->table_lrcnt_size =
			next_power_of_two_up(2048 + sent->num_disjuncts * sent->length / 1.5f);
		ctxt->table_lrcnt = malloc(ctxt->table_lrcnt_size * sizeof(Table_lrcnt));
	}

	for (size_t i = 0; i < ctxt->table_lrcnt_size; i++)
	{
		ctxt->table_lrcnt[i].tracon_id = -1;
	}
	ctxt->table_lrcnt_available_count = MAX_TABLE_LRCNT_SIZE(ctxt->table_lrcnt_size);
}

static size_t table_lrcnt_hash(int tracon_id, int cw, int w)
{
	unsigned int i = tracon_id;
	i = cw + (i << 6) + (i << 16) - i;
	i = w + (i << 6) + (i << 16) - i;

	return i;
}

static Table_lrcnt *table_lrcnt_store(count_context_t *ctxt, int tracon_id,
                                    int cw, int w)
{
	static Table_lrcnt table_full; /* It may get written never read */
	if (ctxt->table_lrcnt_available_count == 0) return &table_full;

	const size_t sizemod = ctxt->table_lrcnt_size-1;
	size_t h = table_lrcnt_hash(tracon_id, cw, w) & sizemod;
	Table_lrcnt *t = ctxt->table_lrcnt;

	while (t[h].tracon_id != -1)
	{
		h = (h+1) & sizemod;
	}

	ctxt->table_lrcnt_available_count--;
	t[h].tracon_id = tracon_id;
	t[h].w = w;
	t[h].null_count = (null_count_m)-1;

	return &t[h];
}

static Table_lrcnt *find_table_lrcnt_pointer(count_context_t *ctxt,
                                           int tracon_id, int cw, int w)
{
	static Table_lrcnt table_full =
	{
		.null_count = (null_count_m)-1,
		.status = 1,
	};
	/* Disregard caching in case the table is full - this shouldn't happen. */
	if (ctxt->table_lrcnt_available_count == 0) return &table_full;

	/* Panic mode: Return a parse bypass indication if resources are
	 * exhausted.  checktimer is a device to avoid a gazillion system calls
	 * to get the timer value. On circa-2018 machines, it results in
	 * several timer calls per second. */
	ctxt->checktimer ++;
	if (ctxt->exhausted || ((0 == ctxt->checktimer%(1<<22)) &&
	                       (ctxt->current_resources != NULL) &&
	                       //fprintf(stderr, "T") &&
	                       resources_exhausted(ctxt->current_resources)))
	{
		ctxt->exhausted = true;
		return &lrcnt_cache_zero;
	}

	const size_t sizemod = ctxt->table_lrcnt_size-1;
	size_t h = table_lrcnt_hash(tracon_id, cw, w) & sizemod;
	Table_lrcnt *t = ctxt->table_lrcnt;

	while (t[h].tracon_id != -1)
	{
		if ((t[h].tracon_id == tracon_id) && (t[h].w == w)) return &t[h];
		h = (h+1) & sizemod;
	}

	return NULL;
}

//#define DEBUG_TABLE_STAT
#if defined(DEBUG) || defined(DEBUG_TABLE_STAT)
static size_t hit, miss;  /* Table value found/not found */
#undef DEBUG_TABLE_STAT
#define DEBUG_TABLE_STAT(x) x
/**
 * 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)
{
	int z = 0, nz = 0;  /* Number of entries with zero and non-zero counts */
	int c, total_c = 0; /* Chain length */
	int N = 0;          /* NULL table slots */
	int null_count[256] = { 0 };   /* null_count histogram */
	int chain_length[64] = { 0 };  /* Chain length histogram */
	bool table_stat_entries = test_enabled("count-table-entries");
	int n;              /* For printf() pretty printing */

	for (unsigned int i = 0; i < ctxt->table_size; i++)
	{
		c = 0;
		Table_connector *t = ctxt->table[i];
		if (t == NULL) N++;
		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);
	}

	int used_slots = ctxt->table_size-N;
	/* The used= value is TotalValues/TableSize (not UsedSlots/TableSize). */
	printf("Connector table: num_growth=%u msb=%u slots=%6d/%6u (%5.2f%%) "
	       "avg-chain=%4.2f values=%6d (z=%5d nz=%5d N=%5d) used=%5.2f%% "
	       "acc=%zu (hit=%zu miss=%zu) (sent_len=%zu)\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);

	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: %d\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 (unsigned int 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;

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

	hit = miss = 0;
}
#else
#define DEBUG_TABLE_STAT(x)
#endif /* DEBUG  */

static void table_grow(count_context_t *ctxt)
{
	Table_connector **old_table = ctxt->table;
	const int old_table_size = ctxt->table_size;

	table_alloc(ctxt, 0);

	/* Rehash. */
	for (int oi = 0; oi < old_table_size; oi++)
	{
		Table_connector *onext;
		for (Table_connector *oe = old_table[oi]; oe != NULL; oe = onext)
		{
			unsigned int ni = oe->hash & (ctxt->table_size-1);

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

	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,
                                     unsigned int 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;
	unsigned int i = hash & (ctxt->table_size -1);
	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;
}

/** returns the pointer to this info, NULL if not there */
static Table_connector *
find_table_pointer(count_context_t *ctxt,
                   int lw, int rw,
                   const Connector *le, const Connector *re,
                   unsigned int null_count, unsigned int *hash)
{
	int l_id = (NULL != le) ? le->tracon_id : lw;
	int r_id = (NULL != re) ? re->tracon_id : rw;

	unsigned int h = pair_hash(lw, rw, l_id, r_id, null_count);
	Table_connector *t = ctxt->table[h & (ctxt->table_size-1)];

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

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

/** returns the count for this quintuple if there, -1 otherwise */
Count_bin* table_lookup(count_context_t * ctxt,
                       int lw, int rw, Connector *le, Connector *re,
                       unsigned int null_count)
{
	Table_connector *t = find_table_pointer(ctxt, lw, rw, le, re, null_count, NULL);

	if (t == NULL) return NULL; else return &t->count;
}

/**
 * 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 w The word that ends the range.
 * @param null_count The current null_count to check.
 * @param cw The word of this connector.
 *
 * 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:
{'fraction_non_alphanumeric': 0.14158962375969386, 'fraction_numerical': 0.012157540045379119, 'mean_word_length': 3.0336019669444063, 'pattern_counts': {'":': 0, '<': 58, '<?xml version=': 0, '>': 229, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 40, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5800947', 'n_tokens_mistral': 11194, 'n_tokens_neox': 10494, 'n_words': 2919}