link-grammar-5.8.0/link-grammar/parse/prune.c
/**
 * Allocates and builds the initial power hash tables.
 * Each word has 2 tables - for its left and right connectors.
 * In these tables, the connectors are hashed according to their
 * uppercase part.
 * In each hash slot, the shallow connectors appear first, so when
 * matching deep connectors to the connectors in a slot, the
 * match loop can stop when there are no more shallow connectors in that
 * slot (since if both are deep, they cannot be matched).
 *
 * Each connector has a refcount filed, which indicates how many times it
 * is memory-shared in the word of its disjunct. Hence, Initially it
 * should always be > 0.
 *
 * There are two code paths for initializing the power tables:
 * 1. When a tracon sharing is not done. The words then are directly
 * scanned for their disjuncts and connectors. Each one is inserted with a
 * refcount set to 1 (because there is no connector memory sharing).
 * 2. Using the tracon list tables (left and right). Each slot is an index
 * into the connector memory block, which is the start of the
 * corresponding tracon. The word number is extracted from the deepest
 * connector (assigned to it by setup_connectors()).
 */
Allocates and builds the initial power hash tables.
Each word has 2 tables - for its left and right connectors.
In these tables, the connectors are hashed according to their
uppercase part.
In each hash slot, the shallow connectors appear first, so when
matching deep connectors to the connectors in a slot, the
match loop can stop when there are no more shallow connectors in that
slot (since if both are deep, they cannot be matched).

Each connector has a refcount filed, which indicates how many times it
is memory-shared in the word of its disjunct. Hence, Initially it
should always be > 0.

There are two code paths for initializing the power tables:
1. When a tracon sharing is not done. The words then are directly
scanned for their disjuncts and connectors. Each one is inserted with a
refcount set to 1 (because there is no connector memory sharing).
2. Using the tracon list tables (left and right). Each slot is an index
into the connector memory block, which is the start of the
corresponding tracon. The word number is extracted from the deepest
connector (assigned to it by setup_connectors()).
Allocates and builds the initial power hash tables . Each word has 2 tables - for its left and right connectors . In these tables the connectors are hashed according to their uppercase part . In each hash slot the shallow connectors appear first so when matching deep connectors to the connectors in a slot the match loop can stop when there are no more shallow connectors in that slot ( since if both are deep they cannot be matched ) . Each connector has a refcount filed which indicates how many times it is memory - shared in the word of its disjunct . Hence Initially it should always be > 0 . There are two code paths for initializing the power tables : 1 . When a tracon sharing is not done . The words then are directly scanned for their disjuncts and connectors . Each one is inserted with a refcount set to 1 ( because there is no connector memory sharing ) . 2 . Using the tracon list tables ( left and right ) . Each slot is an index into the connector memory block which is the start of the corresponding tracon . The word number is extracted from the deepest connector ( assigned to it by setup_connectors () ) .
static void power_table_init(Sentence sent, Tracon_sharing *ts, power_table *pt)
{
	Tracon_list *tl = ts->tracon_list;
	unsigned int i;
#define TOPSZ 32768
	size_t lr_table_max_usage = MIN(sent->dict->contable.num_con, TOPSZ);
	power_table_alloc(sent, pt);
	Pool_desc *mp = pt->memory_pool = pool_new(__func__, "C_list",
	                   2048, sizeof(C_list),
	                   false, false, false);
	for (WordIdx w = 0; w < sent->length; w++)
	{
		size_t l_size, r_size;
		C_list **l_t, **r_t;
		size_t len;
		if (NULL != tl)
			len = tl->num_cnctrs_per_word[0][w];
		else
			len = left_connector_count(sent->word[w].d);
		len++; 
		l_size = next_power_of_two_up(MIN(len, lr_table_max_usage));
		pt->l_table_size[w] = l_size;
		l_t = pt->l_table[w] = (C_list **) xalloc(l_size * sizeof(C_list *));
		for (i=0; i<l_size; i++) l_t[i] = NULL;
		if (NULL != tl)
			len = tl->num_cnctrs_per_word[1][w];
		else
			len = right_connector_count(sent->word[w].d);
		len++;
		r_size = next_power_of_two_up(MIN(len, lr_table_max_usage));
		pt->r_table_size[w] = r_size;
		r_t = pt->r_table[w] = (C_list **) xalloc(r_size * sizeof(C_list *));
		for (i=0; i<r_size; i++) r_t[i] = NULL;
		if (NULL == tl)
		{
			for (Disjunct *d = sent->word[w].d; d != NULL; d = d->next)
			{
				Connector *c;
				c = d->right;
				if (c != NULL)
				{
					for (c = c->next; c != NULL; c = c->next)
					{
						put_into_power_table(mp, r_size, r_t, c);
					}
				}
				c = d->left;
				if (c != NULL)
				{
					for (c = c->next; c != NULL; c = c->next)
					{
						put_into_power_table(mp, l_size, l_t, c);
					}
				}
			}
			for (Disjunct *d = sent->word[w].d; d != NULL; d = d->next)
			{
				Connector *c;
				c = d->right;
				if (c != NULL)
				{
					put_into_power_table(mp, r_size, r_t, c);
				}
				c = d->left;
				if (c != NULL)
				{
					put_into_power_table(mp, l_size, l_t, c);
				}
			}
		}
	}
	if (NULL != tl)
	{
		for (int dir = 0; dir < 2; dir++)
		{
			C_list ***tp;
			unsigned int *sizep;
			unsigned int sid_entries = tl->entries[dir];
			if (dir == 0)
			{
				tp = pt->l_table;
				sizep = pt->l_table_size;
			}
			else
			{
				tp = pt->r_table;
				sizep = pt->r_table_size;
			}
			for (int shallow = 0; shallow < 2; shallow++)
			{
				for (unsigned int id = 0; id < sid_entries; id++)
				{
					Connector *c = get_tracon(ts, dir, id);
					if (!!shallow != c->shallow) continue;
					int w = get_tracon_word_number(c, dir);
					put_into_power_table(mp, sizep[w], tp[w], c);
				}
			}
		}
	}
}
static void power_table_init ( Sentence sent , Tracon_sharing * ts , power_table * pt ) { Tracon_list * tl = ts -> tracon_list ; unsigned int i ; #define TOPSZ  32768 size_t lr_table_max_usage = MIN ( sent -> dict -> contable . num_con , TOPSZ ) ; power_table_alloc ( sent , pt ) ; Pool_desc * mp = pt -> memory_pool = pool_new ( __func__ , " " , 2048 , sizeof ( C_list ) , false , false , false ) ; for ( WordIdx w = 0 ; w < sent -> length ; w ++ ) { size_t l_size , r_size ; C_list * * l_t , * * r_t ; size_t len ; if ( NULL != tl ) len = tl -> num_cnctrs_per_word [ 0 ] [ w ] ; else len = left_connector_count ( sent -> word [ w ] . d ) ; len ++ ; l_size = next_power_of_two_up ( MIN ( len , lr_table_max_usage ) ) ; pt -> l_table_size [ w ] = l_size ; l_t = pt -> l_table [ w ] = ( C_list * * ) xalloc ( l_size * sizeof ( C_list * ) ) ; for ( i = 0 ; i < l_size ; i ++ ) l_t [ i ] = NULL ; if ( NULL != tl ) len = tl -> num_cnctrs_per_word [ 1 ] [ w ] ; else len = right_connector_count ( sent -> word [ w ] . d ) ; len ++ ; r_size = next_power_of_two_up ( MIN ( len , lr_table_max_usage ) ) ; pt -> r_table_size [ w ] = r_size ; r_t = pt -> r_table [ w ] = ( C_list * * ) xalloc ( r_size * sizeof ( C_list * ) ) ; for ( i = 0 ; i < r_size ; i ++ ) r_t [ i ] = NULL ; if ( NULL == tl ) { for ( Disjunct * d = sent -> word [ w ] . d ; d != NULL ; d = d -> next ) { Connector * c ; c = d -> right ; if ( c != NULL ) { for ( c = c -> next ; c != NULL ; c = c -> next ) { put_into_power_table ( mp , r_size , r_t , c ) ; } } c = d -> left ; if ( c != NULL ) { for ( c = c -> next ; c != NULL ; c = c -> next ) { put_into_power_table ( mp , l_size , l_t , c ) ; } } } for ( Disjunct * d = sent -> word [ w ] . d ; d != NULL ; d = d -> next ) { Connector * c ; c = d -> right ; if ( c != NULL ) { put_into_power_table ( mp , r_size , r_t , c ) ; } c = d -> left ; if ( c != NULL ) { put_into_power_table ( mp , l_size , l_t , c ) ; } } } } if ( NULL != tl ) { for ( int dir = 0 ; dir < 2 ; dir ++ ) { C_list * * * tp ; unsigned int * sizep ; unsigned int sid_entries = tl -> entries [ dir ] ; if ( dir == 0 ) { tp = pt -> l_table ; sizep = pt -> l_table_size ; } else { tp = pt -> r_table ; sizep = pt -> r_table_size ; } for ( int shallow = 0 ; shallow < 2 ; shallow ++ ) { for ( unsigned int id = 0 ; id < sid_entries ; id ++ ) { Connector * c = get_tracon ( ts , dir , id ) ; if ( ! ! shallow != c -> shallow ) continue ; int w = get_tracon_word_number ( c , dir ) ; put_into_power_table ( mp , sizep [ w ] , tp [ w ] , c ) ; } } } } }
Allocates and builds the initial power hash tables.
Allocates and builds the initial power hash tables .
/*num_elements*/ /*zero_out*/ /*align*/ /*exact*/ /* The below uses variable-sized hash tables. This seems to
		 * provide performance that is equal or better than the best
		 * fixed-size performance.
		 * The best fixed-size performance seems to come at about
		 * a 1K table size, for both English and Russian. (Both have
		 * about 100 fixed link-types, and many thousands of auto-genned
		 * link types (IDxxx idioms for both, LLxxx suffix links for
		 * Russian).  Pluses and minuses:
		 * + small fixed tables are faster to initialize.
		 * - small fixed tables have more collisions
		 * - variable-size tables require counting connectors.
		 *   (and the more complex code to go with)
		 * CPU cache-size effects ...
		 */ /* Ensure at least one empty entry for get_power_table_entry(). */ /* Insert the deep connectors. */ /* Insert the shallow connectors. */ /* Bulk insertion with reference count. */ /* Insert the deep connectors, then the shallow ones. */