// Equivalence test for freelist_bitmap_t (portable next-set-bit scan) vs the
// original "test every ascending index" scan, including cross-word boundaries
// and mutation-during-iteration. Standalone; compile with g++ -std=c++17.
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>

typedef uint64_t uint64;
typedef uint32_t uint32;

// ---- copied verbatim from freelist_iter_tpl.h ----
static inline uint32 freelist_ctz64(uint64 x)
{
#if defined(_MSC_VER)
	unsigned long idx;
#	if defined(_WIN64) || defined(_M_X64) || defined(_M_ARM64)
	_BitScanForward64(&idx, x); return (uint32)idx;
#	else
	if( (uint32)x ) { _BitScanForward(&idx, (uint32)x); return (uint32)idx; }
	_BitScanForward(&idx, (uint32)(x >> 32)); return (uint32)idx + 32u;
#	endif
#else
	return (uint32)__builtin_ctzll(x);
#endif
}

template<size_t N> struct freelist_bitmap_t {
	static const size_t WORDS = (N + 63u) / 64u;
	uint64 words[WORDS];
	void set(size_t i, bool b) {
		if( b ) { words[i >> 6] |=  ((uint64)1 << (i & 63)); }
		else    { words[i >> 6] &= ~((uint64)1 << (i & 63)); }
	}
	bool test(size_t i) const { return (words[i >> 6] >> (i & 63)) & 1; }
	size_t first_from(size_t from) const {
		if( from >= N ) { return N; }
		size_t wi = from >> 6;
		uint64 bits = words[wi] & ((~(uint64)0) << (from & 63));
		while( bits == 0 ) { if( ++wi >= WORDS ) { return N; } bits = words[wi]; }
		const size_t idx = (wi << 6) + freelist_ctz64(bits);
		return idx < N ? idx : N;
	}
	size_t find_first() const { return first_from(0); }
	size_t find_next(size_t i) const { return first_from(i + 1); }
	void clear() { for(size_t k=0;k<WORDS;k++) words[k]=0; }
};
// ---------------------------------------------------

static unsigned long rng = 123456789UL;
static unsigned long myrand() { rng = rng*1103515245UL + 12345UL; return (rng>>16) & 0x7FFF; }

template<size_t N>
void test_static_patterns(int iterations)
{
	for(int it=0; it<iterations; it++) {
		freelist_bitmap_t<N> m; m.clear();
		// random fill
		for(size_t i=0;i<N;i++){ if(myrand()&1) m.set(i,true); }
		// reference: scan every ascending index
		std::vector<size_t> ref;
		for(size_t i=0;i<N;i++){ if(m.test(i)) ref.push_back(i); }
		// candidate: find_first/find_next
		std::vector<size_t> cand;
		for(size_t i=m.find_first(); i<N; i=m.find_next(i)) cand.push_back(i);
		assert(ref==cand);
	}
}

// Mutation during iteration: emulate the sync loop. While processing the current
// index, the object may remove itself (clear its own bit) and/or a later bit may
// be flipped. The two walks must visit the same index sequence given the SAME
// mutation decisions, so decisions are logged during the naive walk and replayed
// verbatim during the find_first/find_next walk.
template<size_t N>
void test_mutation()
{
	struct Dec { bool self; bool flip; size_t j; bool val; };
	for(int it=0; it<20000; it++) {
		freelist_bitmap_t<N> base; base.clear();
		rng = 987654321UL + it; // deterministic per-iteration seed
		for(size_t i=0;i<N;i++){ if(myrand()&1) base.set(i,true); }

		// naive walk: ascending, re-test the live mask at each index; log decisions
		freelist_bitmap_t<N> a = base;
		std::vector<size_t> seqA;
		std::vector<Dec> log;
		for(size_t i=0;i<N;i++){
			if(a.test(i)){
				seqA.push_back(i);
				Dec d; d.self=(myrand()&1); d.flip=false; d.j=0; d.val=false;
				if(d.self) a.set(i,false);
				if((myrand()%4)==0){ size_t j=i+1+(myrand()%N); if(j<N){ d.flip=true; d.j=j; d.val=(myrand()&1); a.set(j,d.val);} }
				log.push_back(d);
			}
		}

		// candidate walk: find_first/find_next on the live mask, replaying the log
		freelist_bitmap_t<N> b = base;
		std::vector<size_t> seqB;
		size_t li=0;
		for(size_t i=b.find_first(); i<N; i=b.find_next(i)){
			seqB.push_back(i);
			const Dec d = log[li++];
			if(d.self) b.set(i,false);
			if(d.flip) b.set(d.j, d.val);
		}
		assert(seqA==seqB);
	}
}

int main()
{
	test_static_patterns<1>(100);
	test_static_patterns<63>(5000);
	test_static_patterns<64>(5000);
	test_static_patterns<65>(5000);
	test_static_patterns<127>(5000);
	test_static_patterns<128>(5000);
	test_static_patterns<161>(20000);   // realistic new_chuck_size
	test_static_patterns<200>(5000);
	test_static_patterns<256>(2000);

	// explicit edge cases
	{
		freelist_bitmap_t<161> m; m.clear();
		assert(m.find_first()==161);            // empty
		m.set(0,true);  assert(m.find_first()==0); assert(m.find_next(0)==161);
		m.clear(); m.set(160,true); assert(m.find_first()==160); assert(m.find_next(160)==161); // last slot
		m.clear(); m.set(63,true); m.set(64,true); // cross-word boundary
		assert(m.find_first()==63); assert(m.find_next(63)==64); assert(m.find_next(64)==161);
		m.clear(); m.set(0,true); m.set(160,true);
		assert(m.find_first()==0); assert(m.find_next(0)==160);
	}

	test_mutation<161>();
	test_mutation<128>();

	printf("ALL FREELIST BITMAP EQUIVALENCE TESTS PASSED\n");
	return 0;
}