App-RecordStream

 view release on metacpan or  search on metacpan

src/fast-recs-collate/hash.c  view on Meta::CPAN

	    newtable[chain] = low_chain; 	/* 8 */
	    newtable[chain + hash->nchains] = high_chain;
	}

	hash->table = newtable;			/* 9 */
	hash->mask = mask;
	hash->nchains *= 2;
	hash->lowmark *= 2;
	hash->highmark *= 2;
    }
    assert (hash_verify(hash));
}

/*
 * Cut a table size in half. This is done by folding together adjacent chains
 * and populating the lower half of the table with these chains. The chains are
 * simply spliced together. Once this is done, the whole table is reallocated
 * to a smaller object.
 * Notes:
 * 1.  It is illegal to have a hash table with one slot. This would mean that
 *     hash->shift is equal to hash_val_t_bit, an illegal shift value.

src/fast-recs-collate/hash.c  view on Meta::CPAN

	    assert (hash->table[chain] == NULL);	/* 6 */
    }
    newtable = realloc(hash->table,
	    sizeof *newtable * nchains);		/* 7 */
    if (newtable)					/* 8 */
	hash->table = newtable;
    hash->mask >>= 1;			/* 9 */
    hash->nchains = nchains;
    hash->lowmark /= 2;
    hash->highmark /= 2;
    assert (hash_verify(hash));
}


/*
 * Create a dynamic hash table. Both the hash table structure and the table
 * itself are dynamically allocated. Furthermore, the table is extendible in
 * that it will automatically grow as its load factor increases beyond a
 * certain threshold.
 * Notes:
 * 1. If the number of bits in the hash_val_t type has not been computed yet,

src/fast-recs-collate/hash.c  view on Meta::CPAN

	    hash->nodecount = 0;
	    hash->maxcount = maxcount;
	    hash->compare = compfun ? compfun : hash_comp_default;
	    hash->function = hashfun ? hashfun : hash_fun_default;
	    hash->allocnode = hnode_alloc;
	    hash->freenode = hnode_free;
	    hash->context = NULL;
	    hash->mask = INIT_MASK;
	    hash->dynamic = 1;			/* 7 */
	    clear_table(hash);			/* 8 */
	    assert (hash_verify(hash));
	    return hash;
	} 
	free(hash);
    }

    return NULL;
}

/*
 * Select a different set of node allocator routines.

src/fast-recs-collate/hash.c  view on Meta::CPAN

    hash->table = table;	/* 2 */
    hash->nchains = nchains;
    hash->nodecount = 0;
    hash->maxcount = maxcount;
    hash->compare = compfun ? compfun : hash_comp_default;
    hash->function = hashfun ? hashfun : hash_fun_default;
    hash->dynamic = 0;		/* 3 */
    hash->mask = compute_mask(nchains);	/* 4 */
    clear_table(hash);		/* 5 */

    assert (hash_verify(hash));

    return hash;
}

/*
 * Reset the hash scanner so that the next element retrieved by
 * hash_scan_next() shall be the first element on the first non-empty chain. 
 * Notes:
 * 1. Locate the first non empty chain.
 * 2. If an empty chain is found, remember which one it is and set the next

src/fast-recs-collate/hash.c  view on Meta::CPAN

	    }
	}
    }
    return next;
}

/*
 * Insert a node into the hash table.
 * Notes:
 * 1. It's illegal to insert more than the maximum number of nodes. The client
 *    should verify that the hash table is not full before attempting an
 *    insertion.
 * 2. The same key may not be inserted into a table twice.
 * 3. If the table is dynamic and the load factor is already at >= 2,
 *    grow the table.
 * 4. We take the bottom N bits of the hash value to derive the chain index,
 *    where N is the base 2 logarithm of the size of the hash table. 
 */

void hash_insert(hash_t *hash, hnode_t *node, const void *key)
{

src/fast-recs-collate/hash.c  view on Meta::CPAN

    hkey = hash->function(key);
    chain = hkey & hash->mask;	/* 4 */

    node->key = key;
    node->hkey = hkey;
    node->next = hash->table[chain];
    hash->table[chain] = node;
    hash->nodecount++;

    assert (hash_verify(hash));
}

/*
 * Find a node in the hash table and return a pointer to it.
 * Notes:
 * 1. We hash the key and keep the entire hash value. As an optimization, when
 *    we descend down the chain, we can compare hash values first and only if
 *    hash values match do we perform a full key comparison. 
 * 2. To locate the chain from among 2^N chains, we look at the lower N bits of
 *    the hash value by anding them with the current mask.

src/fast-recs-collate/hash.c  view on Meta::CPAN

    } else {
	while (hptr->next != node) {			/* 5 */
	    assert (hptr != 0);
	    hptr = hptr->next;
	}
	assert (hptr->next == node);
	hptr->next = node->next;
    }
	
    hash->nodecount--;
    assert (hash_verify(hash));

    node->next = NULL;					/* 6 */
    return node;
}

int hash_alloc_insert(hash_t *hash, const void *key, void *data)
{
    hnode_t *node = hash->allocnode(hash->context);

    if (node) {

src/fast-recs-collate/hash.c  view on Meta::CPAN

    if (hptr == node) {
	hash->table[chain] = node->next;
    } else {
	while (hptr->next != node) 
	    hptr = hptr->next;
	hptr->next = node->next;
    }
	
    hash->nodecount--;
    assert (hash_verify(hash));
    node->next = NULL;

    return node;
}

/*
 * Like hash_delete_free but based on hash_scan_delete.
 */

void hash_scan_delfree(hash_t *hash, hnode_t *node)
{
    hash_scan_delete(hash, node);
    hash->freenode(node, hash->context);
}

/*
 * Verify whether the given object is a valid hash table. This means
 * Notes:
 * 1. If the hash table is dynamic, verify whether the high and
 *    low expansion/shrinkage thresholds are powers of two.
 * 2. Count all nodes in the table, and test each hash value
 *    to see whether it is correct for the node's chain.
 */

int hash_verify(hash_t *hash)
{
    hashcount_t count = 0;
    hash_val_t chain;
    hnode_t *hptr;

    if (hash->dynamic) {	/* 1 */
	if (hash->lowmark >= hash->highmark)
	    return 0;
	if (!is_power_of_two(hash->highmark))
	    return 0;

src/fast-recs-collate/hash.h  view on Meta::CPAN

extern hashcount_t hash_size(hash_t *);

extern int hash_isfull(hash_t *);
extern int hash_isempty(hash_t *);

extern void hash_scan_begin(hscan_t *, hash_t *);
extern hnode_t *hash_scan_next(hscan_t *);
extern hnode_t *hash_scan_delete(hash_t *, hnode_t *);
extern void hash_scan_delfree(hash_t *, hnode_t *);

extern int hash_verify(hash_t *);

extern hnode_t *hnode_create(void *);
extern hnode_t *hnode_init(hnode_t *, void *);
extern void hnode_destroy(hnode_t *);

#if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
#ifdef KAZLIB_SIDEEFFECT_DEBUG
#define hash_isfull(H) (SFX_CHECK(H)->hash_nodecount == (H)->hash_maxcount)
#else
#define hash_isfull(H) ((H)->hash_nodecount == (H)->hash_maxcount)