src/dpdk/lib/librte_member/rte_member_ht.c
static inline int
make_space_bucket(const struct rte_member_setsum *ss, uint32_t bkt_idx,
			unsigned int *nr_pushes)
{
	unsigned int i, j;
	int ret;
	struct member_ht_bucket *buckets = ss->table;
	uint32_t next_bucket_idx;
	struct member_ht_bucket *next_bkt[RTE_MEMBER_BUCKET_ENTRIES];
	struct member_ht_bucket *bkt = &buckets[bkt_idx];
	/* MSB is set to indicate if an entry has been already pushed */
	member_set_t flag_mask = 1U << (sizeof(member_set_t) * 8 - 1);

	/*
	 * Push existing item (search for bucket with space in
	 * alternative locations) to its alternative location
	 */
	for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
		/* Search for space in alternative locations */
		next_bucket_idx = (bkt->sigs[i] ^ bkt_idx) & ss->bucket_mask;
		next_bkt[i] = &buckets[next_bucket_idx];
		for (j = 0; j < RTE_MEMBER_BUCKET_ENTRIES; j++) {
			if (next_bkt[i]->sets[j] == RTE_MEMBER_NO_MATCH)
				break;
		}

		if (j != RTE_MEMBER_BUCKET_ENTRIES)
			break;
	}

	/* Alternative location has spare room (end of recursive function) */
	if (i != RTE_MEMBER_BUCKET_ENTRIES) {
		next_bkt[i]->sigs[j] = bkt->sigs[i];
		next_bkt[i]->sets[j] = bkt->sets[i];
		return i;
	}

	/* Pick entry that has not been pushed yet */
	for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++)
		if ((bkt->sets[i] & flag_mask) == 0)
			break;

	/* All entries have been pushed, so entry cannot be added */
	if (i == RTE_MEMBER_BUCKET_ENTRIES ||
			++(*nr_pushes) > RTE_MEMBER_MAX_PUSHES)
		return -ENOSPC;

	next_bucket_idx = (bkt->sigs[i] ^ bkt_idx) & ss->bucket_mask;
	/* Set flag to indicate that this entry is going to be pushed */
	bkt->sets[i] |= flag_mask;

	/* Need room in alternative bucket to insert the pushed entry */
	ret = make_space_bucket(ss, next_bucket_idx, nr_pushes);
	/*
	 * After recursive function.
	 * Clear flags and insert the pushed entry
	 * in its alternative location if successful,
	 * or return error
	 */
	bkt->sets[i] &= ~flag_mask;
	if (ret >= 0) {
		next_bkt[i]->sigs[ret] = bkt->sigs[i];
		next_bkt[i]->sets[ret] = bkt->sets[i];
		return i;
	} else
		return ret;
}
/*
 * This function is similar to the cuckoo hash make_space function in hash
 * library
 */
This function is similar to the cuckoo hash make_space function in hash
library
This function is similar to the cuckoo hash make_space function in hash library
static inline int
make_space_bucket(const struct rte_member_setsum *ss, uint32_t bkt_idx,
			unsigned int *nr_pushes)
{
	unsigned int i, j;
	int ret;
	struct member_ht_bucket *buckets = ss->table;
	uint32_t next_bucket_idx;
	struct member_ht_bucket *next_bkt[RTE_MEMBER_BUCKET_ENTRIES];
	struct member_ht_bucket *bkt = &buckets[bkt_idx];
	member_set_t flag_mask = 1U << (sizeof(member_set_t) * 8 - 1);
	for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
		next_bucket_idx = (bkt->sigs[i] ^ bkt_idx) & ss->bucket_mask;
		next_bkt[i] = &buckets[next_bucket_idx];
		for (j = 0; j < RTE_MEMBER_BUCKET_ENTRIES; j++) {
			if (next_bkt[i]->sets[j] == RTE_MEMBER_NO_MATCH)
				break;
		}
		if (j != RTE_MEMBER_BUCKET_ENTRIES)
			break;
	}
	if (i != RTE_MEMBER_BUCKET_ENTRIES) {
		next_bkt[i]->sigs[j] = bkt->sigs[i];
		next_bkt[i]->sets[j] = bkt->sets[i];
		return i;
	}
	for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++)
		if ((bkt->sets[i] & flag_mask) == 0)
			break;
	if (i == RTE_MEMBER_BUCKET_ENTRIES ||
			++(*nr_pushes) > RTE_MEMBER_MAX_PUSHES)
		return -ENOSPC;
	next_bucket_idx = (bkt->sigs[i] ^ bkt_idx) & ss->bucket_mask;
	bkt->sets[i] |= flag_mask;
	ret = make_space_bucket(ss, next_bucket_idx, nr_pushes);
	bkt->sets[i] &= ~flag_mask;
	if (ret >= 0) {
		next_bkt[i]->sigs[ret] = bkt->sigs[i];
		next_bkt[i]->sets[ret] = bkt->sets[i];
		return i;
	} else
		return ret;
}
static inline int make_space_bucket ( const struct rte_member_setsum * ss , uint32_t bkt_idx , unsigned int * nr_pushes ) { unsigned int i , j ; int ret ; struct member_ht_bucket * buckets = ss -> table ; uint32_t next_bucket_idx ; struct member_ht_bucket * next_bkt [ RTE_MEMBER_BUCKET_ENTRIES ] ; struct member_ht_bucket * bkt = & buckets [ bkt_idx ] ; member_set_t flag_mask = 1U << ( sizeof ( member_set_t ) * 8 - 1 ) ; for ( i = 0 ; i < RTE_MEMBER_BUCKET_ENTRIES ; i ++ ) { next_bucket_idx = ( bkt -> sigs [ i ] ^ bkt_idx ) & ss -> bucket_mask ; next_bkt [ i ] = & buckets [ next_bucket_idx ] ; for ( j = 0 ; j < RTE_MEMBER_BUCKET_ENTRIES ; j ++ ) { if ( next_bkt [ i ] -> sets [ j ] == RTE_MEMBER_NO_MATCH ) break ; } if ( j != RTE_MEMBER_BUCKET_ENTRIES ) break ; } if ( i != RTE_MEMBER_BUCKET_ENTRIES ) { next_bkt [ i ] -> sigs [ j ] = bkt -> sigs [ i ] ; next_bkt [ i ] -> sets [ j ] = bkt -> sets [ i ] ; return i ; } for ( i = 0 ; i < RTE_MEMBER_BUCKET_ENTRIES ; i ++ ) if ( ( bkt -> sets [ i ] & flag_mask ) == 0 ) break ; if ( i == RTE_MEMBER_BUCKET_ENTRIES || ++ ( * nr_pushes ) > RTE_MEMBER_MAX_PUSHES ) return - ENOSPC ; next_bucket_idx = ( bkt -> sigs [ i ] ^ bkt_idx ) & ss -> bucket_mask ; bkt -> sets [ i ] |= flag_mask ; ret = make_space_bucket ( ss , next_bucket_idx , nr_pushes ) ; bkt -> sets [ i ] &= ~ flag_mask ; if ( ret >= 0 ) { next_bkt [ i ] -> sigs [ ret ] = bkt -> sigs [ i ] ; next_bkt [ i ] -> sets [ ret ] = bkt -> sets [ i ] ; return i ; } else return ret ; }
This function is similar to the cuckoo hash make_space function in hash
 library
This function is similar to the cuckoo hash make_space function in hash library
/* MSB is set to indicate if an entry has been already pushed */ /*
	 * Push existing item (search for bucket with space in
	 * alternative locations) to its alternative location
	 */ /* Search for space in alternative locations */ /* Alternative location has spare room (end of recursive function) */ /* Pick entry that has not been pushed yet */ /* All entries have been pushed, so entry cannot be added */ /* Set flag to indicate that this entry is going to be pushed */ /* Need room in alternative bucket to insert the pushed entry */ /*
	 * After recursive function.
	 * Clear flags and insert the pushed entry
	 * in its alternative location if successful,
	 * or return error
	 */