package descriptor

import (
	
	
)

// Table is a data structure mapping 32 bit descriptor to items.
//
// # Negative keys are invalid.
//
// Negative keys (e.g. -1) are invalid inputs and will return a corresponding
// not-found value. This matches POSIX behavior of file descriptors.
// See https://pubs.opengroup.org/onlinepubs/9699919799/functions/dirfd.html#tag_16_90
//
// # Data structure design
//
// The data structure optimizes for memory density and lookup performance,
// trading off compute at insertion time. This is a useful compromise for the
// use cases we employ it with: items are usually accessed a lot more often
// than they are inserted, each operation requires a table lookup, so we are
// better off spending extra compute to insert items in the table in order to
// get cheaper lookups. Memory efficiency is also crucial to support scaling
// with programs that maintain thousands of items: having a high or non-linear
// memory-to-item ratio could otherwise be used as an attack vector by
// malicious applications attempting to damage performance of the host.
type Table[ ~int32,  any] struct {
	masks []uint64
	items []
}

// Len returns the number of items stored in the table.
func ( *Table[, ]) () ( int) {
	// We could make this a O(1) operation if we cached the number of items in
	// the table. More state usually means more problems, so until we have a
	// clear need for this, the simple implementation may be a better trade off.
	for ,  := range .masks {
		 += bits.OnesCount64()
	}
	return 
}

// grow grows the table by n * 64 items.
func ( *Table[, ]) ( int) {
	 := len(.masks) + 
	.masks = slices.Grow(.masks, )[:]

	 = len(.items) + *64
	.items = slices.Grow(.items, *64)[:]
}

// Insert inserts the given item to the table, returning the key that it is
// mapped to or false if the table was full.
//
// The method does not perform deduplication, it is possible for the same item
// to be inserted multiple times, each insertion will return a different key.
func ( *Table[, ]) ( ) ( ,  bool) {
	 := 0
:
	// Note: this loop could be made a lot more efficient using vectorized
	// operations: 256 bits vector registers would yield a theoretical 4x
	// speed up (e.g. using AVX2).
	for ,  := range .masks[:] {
		if ^ != 0 { // not full?
			 := bits.TrailingZeros64(^)
			 += 
			 = ()*64 + ()
			.items[] = 
			.masks[] =  | uint64(1<<)
			return ,  >= 0
		}
	}

	// No free slot found, grow the table and retry.
	 = len(.masks)
	.grow(1)
	goto 
}

// Lookup returns the item associated with the given key (may be nil).
func ( *Table[, ]) ( ) ( ,  bool) {
	if  < 0 { // invalid key
		return
	}
	if  := int();  >= 0 &&  < len(.items) {
		 := uint() / 64
		 := uint() % 64
		if (.masks[] & (1 << )) != 0 {
			,  = .items[], true
		}
	}
	return
}

// InsertAt inserts the given `item` at the item descriptor `key`. This returns
// false if the insert was impossible due to negative key.
func ( *Table[, ]) ( ,  ) bool {
	if  < 0 {
		return false
	}
	 := uint() / 64
	if  := int() - len(.masks) + 1;  > 0 {
		.grow()
	}
	 := uint() % 64
	.masks[] |= 1 << 
	.items[] = 
	return true
}

// Delete deletes the item stored at the given key from the table.
func ( *Table[, ]) ( ) {
	if  < 0 { // invalid key
		return
	}
	if  := uint() / 64; int() < len(.masks) {
		 := uint() % 64
		 := .masks[]
		if ( & (1 << )) != 0 {
			var  
			.items[] = 
			.masks[] =  & ^uint64(1<<)
		}
	}
}

// Range calls f for each item and its associated key in the table. The function
// f might return false to interupt the iteration.
func ( *Table[, ]) ( func(, ) bool) {
	for ,  := range .masks {
		if  == 0 {
			continue
		}
		for  := (0);  < 64; ++ {
			if ( & (1 << )) == 0 {
				continue
			}
			if  := ()*64 + ; !(, .items[]) {
				return
			}
		}
	}
}

// Reset clears the content of the table.
func ( *Table[, ]) () {
	clear(.masks)
	clear(.items)
}