Subversion Repositories openrisc

// $G $F.go && $L $F.$A && ./$A.out

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package main

// ----------------------------------------------------------------------------
// Helper functions

func ASSERT(p bool) {
        if !p {
                // panic 0
        }
}


// ----------------------------------------------------------------------------
// Implementation of the HashMap

type KeyType interface {
        Hash() uint32
        Match(other KeyType) bool
}


type ValueType interface {
        // empty interface
}


type Entry struct {
        key KeyType
        value ValueType
}


type Array [1024]Entry

type HashMap struct {
        map_ *Array
        log2_capacity_ uint32
        occupancy_ uint32
}


func (m *HashMap) capacity() uint32 {
        return 1 << m.log2_capacity_
}


func (m *HashMap) Clear() {
        // Mark all entries as empty.
        var i uint32 = m.capacity() - 1
        for i > 0 {
                m.map_[i].key = nil
                i = i - 1
        }
        m.occupancy_ = 0
}


func (m *HashMap) Initialize (initial_log2_capacity uint32) {
        m.log2_capacity_ = initial_log2_capacity
        m.map_ = new(Array)
        m.Clear()
}


func (m *HashMap) Probe (key KeyType) *Entry {
        ASSERT(key != nil)

        var i uint32 = key.Hash() % m.capacity()
        ASSERT(0 <= i && i < m.capacity())

        ASSERT(m.occupancy_ < m.capacity())     // guarantees loop termination
        for m.map_[i].key != nil && !m.map_[i].key.Match(key) {
                i++
                if i >= m.capacity() {
                        i = 0
                }
        }

        return &m.map_[i]
}


func (m *HashMap) Lookup (key KeyType, insert bool) *Entry {
        // Find a matching entry.
        var p *Entry = m.Probe(key)
                if p.key != nil {
                return p
        }

        // No entry found; insert one if necessary.
        if insert {
                p.key = key
                p.value = nil
                m.occupancy_++

                // Grow the map if we reached >= 80% occupancy.
                if m.occupancy_ + m.occupancy_/4 >= m.capacity() {
                        m.Resize()
                        p = m.Probe(key)
                }

                return p
        }

        // No entry found and none inserted.
        return nil
}


func (m *HashMap) Resize() {
        var hmap *Array = m.map_
        var n uint32 = m.occupancy_

        // Allocate a new map of twice the current size.
        m.Initialize(m.log2_capacity_ << 1)

        // Rehash all current entries.
        var i uint32 = 0
        for n > 0 {
                if hmap[i].key != nil {
                        m.Lookup(hmap[i].key, true).value = hmap[i].value
                        n = n - 1
                }
                i++
        }
}


// ----------------------------------------------------------------------------
// Test code

type Number struct {
        x uint32
}


func (n *Number) Hash() uint32 {
        return n.x * 23
}


func (n *Number) Match(other KeyType) bool {
        // var y *Number = other
        // return n.x == y.x
        return false
}


func MakeNumber (x uint32) *Number {
        var n *Number = new(Number)
        n.x = x
        return n
}


func main() {
        // func (n int) int { return n + 1; }(1)

        //print "HashMap - gri 2/8/2008\n"

        var hmap *HashMap = new(HashMap)
        hmap.Initialize(0)

        var x1 *Number = MakeNumber(1001)
        var x2 *Number = MakeNumber(2002)
        var x3 *Number = MakeNumber(3003)
        _, _, _ = x1, x2, x3

        // this doesn't work I think...
        //hmap.Lookup(x1, true)
        //hmap.Lookup(x2, true)
        //hmap.Lookup(x3, true)

        //print "done\n"
}