<commit_before>package hamt32

import (
	"fmt"
	"log"
	"strings"
)

type fullTable struct {
	hashPath uint32 // depth*nBits of hash to get to this location in the Trie
	numEnts  uint
	nodes    [TableCapacity]nodeI
}

func createRootFullTable(leaf leafI) tableI {
	var idx = index(leaf.Hash30(), 0)

	var ft = new(fullTable)
	//ft.hashPath = 0
	ft.numEnts = 1
	ft.nodes[idx] = leaf

	return ft
}

func createFullTable(depth uint, leaf1 leafI, leaf2 flatLeaf) tableI {
	var retTable = new(fullTable)
	retTable.hashPath = leaf1.Hash30() & hashPathMask(depth)

	var curTable = retTable
	var hashPath = retTable.hashPath
	var d uint
	for d = depth; d < MaxDepth; d++ {
		var idx1 = index(leaf1.Hash30(), d)
		var idx2 = index(leaf2.Hash30(), d)

		if idx1 != idx2 {
			curTable.nodes[idx1] = leaf1
			curTable.nodes[idx2] = leaf2

			curTable.numEnts = 2

			break
		}
		// idx1 == idx2 && continue

		hashPath = buildHashPath(hashPath, idx1, d)

		var newTable = new(fullTable)
		newTable.hashPath = hashPath

		curTable.numEnts = 1
		curTable.nodes[idx1] = newTable

		curTable = newTable
	}
	// We either BREAK out of the loop,
	// OR we hit d == MaxDepth.
	if d == MaxDepth {
		var idx1 = index(leaf1.Hash30(), d)
		var idx2 = index(leaf2.Hash30(), d)

		if idx1 != idx2 {
			curTable.nodes[idx1] = leaf1
			curTable.nodes[idx2] = leaf2

			curTable.numEnts = 2

			return retTable
		}
		// idx1 == idx2

		// NOTE: This condition should never result. The condition is
		// leaf1.Hash30() == leaf2.Hash30() all the way to MaxDepth;
		// because Hamt.newTable() is called only once, and after a
		// leaf1.Hash30() == leaf2.Hash30() check. It is here for completeness.
		log.Printf("full_table.go:newFullTable: SHOULD NOT BE CALLED")
		if leaf1.Hash30() != leaf2.Hash30() {
			log.Printf("madDepth=%d; d=%d; idx1=%d; idx2=%d", MaxDepth, d, idx1, idx2)
			log.Panicf("newFullTable: %s != %s", hash30String(leaf1.Hash30()), hash30String(leaf2.Hash30()))
		}
		var newLeaf, _ = leaf1.put(leaf2.key, leaf2.val)
		curTable.insert(idx1, newLeaf)
	}

	return retTable
}

func upgradeToFullTable(hashPath uint32, tabEnts []tableEntry) tableI {
	var ft = new(fullTable)
	ft.hashPath = hashPath
	ft.numEnts = uint(len(tabEnts))

	for _, ent := range tabEnts {
		ft.nodes[ent.idx] = ent.node
	}

	return ft
}

// Hash30() is required for nodeI
func (t fullTable) Hash30() uint32 {
	return t.hashPath
}

// copy() is required for nodeI
func (t fullTable) copy() *fullTable {
	var nt = new(fullTable)
	nt.hashPath = t.hashPath
	nt.numEnts = t.numEnts
	//for i := 0; i < len(t.nodes); i++ {
	//	nt.nodes[i] = t.nodes[i]
	//}
	nt.nodes = t.nodes

	return nt
}

// nentries() is required for tableI
func (t fullTable) nentries() uint {
	return t.numEnts
}

// This function MUST return the slice of tableEntry structs from lowest
// tableEntry.idx to highest tableEntry.idx .
func (t fullTable) entries() []tableEntry {
	var n = t.nentries()
	var ents = make([]tableEntry, n)
	for i, j := uint(0), 0; i < TableCapacity; i++ {
		if t.nodes[i] != nil {
			//The difference with compressedTable is t.nodes[i] vs. t.nodes[j]
			ents[j] = tableEntry{i, t.nodes[i]}
			j++
		}
	}
	return ents
}

// get(uint32) is required for tableI
func (t fullTable) get(idx uint) nodeI {
	return t.nodes[idx]
}

func (t fullTable) insert(idx uint, entry nodeI) tableI {
	// t.nodes[idx] == nil
	var nt = t.copy()
	nt.nodes[idx] = entry
	nt.numEnts++
	return nt
}

func (t fullTable) replace(idx uint, entry nodeI) tableI {
	// t.nodes[idx] != nil
	var nt = t.copy()
	nt.nodes[idx] = entry
	return nt
}

func (t fullTable) remove(idx uint) tableI {
	// t.nodes[idx] != nil
	var nt = t.copy()
	nt.nodes[idx] = nil
	nt.numEnts--

	if GradeTables && nt.numEnts < DowngradeThreshold {
		return downgradeToCompressedTable(nt.hashPath, nt.entries())
	}

	if nt.numEnts == 0 {
		return nil
	}

	return nt
}

// String() is required for nodeI
func (t fullTable) String() string {
	// fullTable{hashPath:/%d/%d/%d/%d/%d/%d/%d/%d/%d/%d, nentries:%d,}
	return fmt.Sprintf("fullTable{hashPath:%s, nentries()=%d}", hash30String(t.hashPath), t.nentries())
}

// LongString() is required for tableI
func (t fullTable) LongString(indent string, depth uint) string {
	var strs = make([]string, 2+len(t.nodes))

	strs[0] = indent + fmt.Sprintf("fullTable{hashPath:%s, nentries()=%d,", hashPathString(t.hashPath, depth), t.nentries())

	for i, n := range t.nodes {
		if t.nodes[i] == nil {
			strs[1+i] = indent + fmt.Sprintf("\tt.nodes[%d]: nil", i)
		} else {
			if t, ok := t.nodes[i].(tableI); ok {
				strs[1+i] = indent + fmt.Sprintf("\tt.nodes[%d]:\n%s", i, t.LongString(indent+"\t", depth+1))
			} else {
				strs[1+i] = indent + fmt.Sprintf("\tt.nodes[%d]: %s", i, n)
			}
		}
	}

	strs[len(strs)-1] = indent + "}"

	return strings.Join(strs, "\n")
}<commit_msg>* Added depth field to fullTable struct. * Renamed newFullTable() -> createFullTable() * Added depth argument to upgradeToFullTable() function. * Updated call to downgradeToCompressedTable() function. * Fixed fullTable.copy() method. * Exported fullTable.Get() method. * Fixed fullTable.String() method. * Removed depth argument from fullTable.LongString() method. * Fixed fullTable.LongString() method.<commit_after>package hamt32

import (
	"fmt"
	"log"
	"strings"
)

type fullTable struct {
	hashPath uint32 // depth*nBits of hash to get to this location in the Trie
	depth    uint
	numEnts  uint
	nodes    [TableCapacity]nodeI
}

func createRootFullTable(leaf leafI) tableI {
	var idx = index(leaf.Hash30(), 0)

	var ft = new(fullTable)
	//ft.hashPath = 0
	//ft.depth = 0
	ft.numEnts = 1
	ft.nodes[idx] = leaf

	return ft
}

func createFullTable(depth uint, leaf1 leafI, leaf2 flatLeaf) tableI {
	var retTable = new(fullTable)
	retTable.hashPath = leaf1.Hash30() & hashPathMask(depth)
	retTable.depth = depth

	var curTable = retTable
	var hashPath = retTable.hashPath
	var d uint
	for d = depth; d < MaxDepth; d++ {
		var idx1 = index(leaf1.Hash30(), d)
		var idx2 = index(leaf2.Hash30(), d)

		if idx1 != idx2 {
			curTable.nodes[idx1] = leaf1
			curTable.nodes[idx2] = leaf2

			curTable.numEnts = 2

			break
		}
		// idx1 == idx2 && continue

		hashPath = buildHashPath(hashPath, idx1, d+1)

		var newTable = new(fullTable)
		newTable.hashPath = hashPath
		newTable.depth = d + 1

		curTable.numEnts = 1
		curTable.nodes[idx1] = newTable

		curTable = newTable
	}
	// We either BREAK out of the loop,
	// OR we hit d == MaxDepth.
	if d == MaxDepth {
		var idx1 = index(leaf1.Hash30(), d)
		var idx2 = index(leaf2.Hash30(), d)

		if idx1 != idx2 {
			curTable.nodes[idx1] = leaf1
			curTable.nodes[idx2] = leaf2

			curTable.numEnts = 2

			return retTable
		}
		// idx1 == idx2

		// NOTE: This condition should never result. The condition is
		// leaf1.Hash30() == leaf2.Hash30() all the way to MaxDepth;
		// because Hamt.newTable() is called only once, and after a
		// leaf1.Hash30() == leaf2.Hash30() check. It is here for completeness.
		log.Printf("full_table.go:createFullTable: SHOULD NOT BE CALLED")
		if leaf1.Hash30() != leaf2.Hash30() {
			log.Printf("MaxDepth=%d; d=%d; idx1=%d; idx2=%d", MaxDepth, d, idx1, idx2)
			log.Panicf("createFullTable: %s,0x%06x != %s,0x%06x", h30ToString(leaf1.Hash30()), leaf1.Hash30(), h30ToString(leaf2.Hash30()), leaf2.Hash30())
		}
		var newLeaf, _ = leaf1.put(leaf2.key, leaf2.val)
		curTable.insert(idx1, newLeaf)
	}

	return retTable
}

func upgradeToFullTable(hashPath uint32, depth uint, tabEnts []tableEntry) tableI {
	var ft = new(fullTable)
	ft.hashPath = hashPath
	ft.depth = depth
	ft.numEnts = uint(len(tabEnts))

	for _, ent := range tabEnts {
		ft.nodes[ent.idx] = ent.node
	}

	return ft
}

// Hash30() is required for nodeI
func (t fullTable) Hash30() uint32 {
	return t.hashPath
}

// copy() is required for nodeI
func (t fullTable) copy() *fullTable {
	var nt = new(fullTable)
	nt.hashPath = t.hashPath
	nt.depth = t.depth
	nt.numEnts = t.numEnts
	//for i := 0; i < len(t.nodes); i++ {
	//	nt.nodes[i] = t.nodes[i]
	//}
	nt.nodes = t.nodes

	return nt
}

// nentries() is required for tableI
func (t fullTable) nentries() uint {
	return t.numEnts
}

// This function MUST return the slice of tableEntry structs from lowest
// tableEntry.idx to highest tableEntry.idx .
func (t fullTable) entries() []tableEntry {
	var n = t.nentries()
	var ents = make([]tableEntry, n)
	for i, j := uint(0), 0; i < TableCapacity; i++ {
		if t.nodes[i] != nil {
			//The difference with compressedTable is t.nodes[i] vs. t.nodes[j]
			ents[j] = tableEntry{i, t.nodes[i]}
			j++
		}
	}
	return ents
}

// Get(uint32) is required for tableI
func (t fullTable) Get(idx uint) nodeI {
	return t.nodes[idx]
}

func (t fullTable) insert(idx uint, entry nodeI) tableI {
	// t.nodes[idx] == nil
	var nt = t.copy()
	nt.nodes[idx] = entry
	nt.numEnts++
	return nt
}

func (t fullTable) replace(idx uint, entry nodeI) tableI {
	// t.nodes[idx] != nil
	var nt = t.copy()
	nt.nodes[idx] = entry
	return nt
}

func (t fullTable) remove(idx uint) tableI {
	// t.nodes[idx] != nil
	var nt = t.copy()
	nt.nodes[idx] = nil
	nt.numEnts--

	if GradeTables && nt.numEnts < DowngradeThreshold {
		return downgradeToCompressedTable(nt.hashPath, nt.depth, nt.entries())
	}

	if nt.numEnts == 0 {
		return nil
	}

	return nt
}

// String() is required for nodeI
func (t fullTable) String() string {
	// fullTable{hashPath:/%d/%d/%d/%d/%d/%d, nentries:%d,}
	return fmt.Sprintf("fullTable{hashPath:%s, nentries()=%d, depth=%d}", hashPathString(t.hashPath, t.depth), t.nentries(), t.depth)
}

// LongString() is required for tableI
func (t fullTable) LongString(indent string) string {
	//var strs = make([]string, 2+len(t.nodes))
	var strs = make([]string, 2+t.nentries())

	strs[0] = indent + fmt.Sprintf("fullTable{hashPath:%s, nentries()=%d, t.depth=%d,", hashPathString(t.hashPath, t.depth), t.nentries(), t.depth)

	var j int
	for i, n := range t.nodes {
		//if n == nil {
		//	strs[1+i] = indent + fmt.Sprintf(HalfIndent+"t.nodes[%d]: nil", i)
		//} else {
		if n != nil {
			if tt, ok := n.(tableI); ok {
				strs[1+j] = indent + fmt.Sprintf(HalfIndent+"t.nodes[%d]:\n%s", i, tt.LongString(indent+"\t"))
			} else {
				strs[1+j] = indent + fmt.Sprintf(HalfIndent+"t.nodes[%d]: %s", i, n)
			}
			j++
		}
	}

	strs[len(strs)-1] = indent + "}"

	return strings.Join(strs, "\n")
}
{'fraction_non_alphanumeric': 0.15533604493511524, 'fraction_numerical': 0.022564400542320357, 'mean_word_length': 3.5313734093900835, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4782726', 'n_tokens_mistral': 4267, 'n_tokens_neox': 3952, 'n_words': 1045}