Hexo

type Bitmap struct {
	Len int
	Any  bool
	Data []byte
}
/*这里位图设计细节是一个bit位来标记一行,而不是使用一个字节标记的,这样浪费空间了
    比如我有16行,我只需要两个字节就够了
    byte[0] 0 0 0 0 0 0 0 0 (代表0-7行)
    byte[1] 0 0 0 0 0 0 0 0 (代表8-15行)
比如标记第7行的结果为NULL,那么结果就是:
	byte[0] 0 0 0 0 0 0 0 1 (代表0-7行)
    byte[1] 0 0 0 0 0 0 0 0 (代表8-15行)
*/

package bitmap

import "fmt"
//假如我们有n行需要判断,就设计大小为n
func New(n int) *Bitmap {
	return &Bitmap{
		Len:  n,
		Any:  false,
		Data: make([]byte, (n-1)/8+1),
	}
}

func (n *Bitmap) IsEmpty() bool {
	return !n.Any
}
//row>>3等价于row/8, row & 0x7 等价于 row%8
func (n *Bitmap) Add(row uint64) {
	n.Data[row>>3] |= 1 << (row & 0x7)
	n.Any = true
}

func (n *Bitmap) Del(row uint64) {
	n.Data[row>>3] &= ^(uint8(1) << (row & 0x7))
}

func (n *Bitmap) Contains(row uint64) bool {
	return (n.Data[row>>3] & (1 << (row & 0x7))) != 0
}

func (n *Bitmap) Filter(sels []int64) *Bitmap {
	m := New(n.Len)
	for i, sel := range sels {
		if n.Contains(uint64(sel)) {
			m.Add(uint64(i))
		}
	}
	return m
}

func (n *Bitmap) Rows() []uint64 {
	var rows []uint64

	for i, j := uint64(0), uint64(n.Len); i < j; i++ {
		if n.Contains(i) {
			rows = append(rows, i)
		}
	}
	return rows
}

func (n *Bitmap) String() string {
	return fmt.Sprintf("%v", n.Rows())
}

package concurrent_map

import (
	"sync"
)

type innerMap struct {
	m    map[interface{}]interface{}
	lock sync.RWMutex
}

//这个接口用于给用户自己设计key,hash方法也可以自己设计
type Concurrent_Key interface {
	RawKey() interface{}        //原始的key值
	KeyAfterPartitioned() int64 //原始key值经过hash运算后得到的结果
}

type ConcurrentMap struct {
	partitions_map   []*innerMap
	numsOfPartitions int64 //记录分区数量
}

func CreatConcurrentMap(numsOfPartitions int64) *ConcurrentMap {
	var partitions_map []*innerMap
	for i := 0; i < int(numsOfPartitions); i++ {
		partitions_map = append(partitions_map, &innerMap{
			m: make(map[interface{}]interface{}),
		})
	}
	return &ConcurrentMap{
		partitions_map:   partitions_map,
		numsOfPartitions: numsOfPartitions,
	}
}

//下面是concurrentMap的一些基本使用方式,由于innermap是内
//部map,因此它的操作方法都应该首字母小写
func (im *innerMap) get(key Concurrent_Key) (interface{}, bool) {
	im.lock.RLock()
	val, ok := im.m[key.RawKey()]
	im.lock.RUnlock()
	return val, ok
}

func (im *innerMap) set(key Concurrent_Key, val interface{}) {
	im.lock.Lock()
	im.m[key.RawKey()] = val
	im.lock.Unlock()
}

func (im *innerMap) del(key Concurrent_Key) {
	im.lock.Lock()
	delete(im.m, key.RawKey())
	im.lock.Unlock()
}

//这个方法用于获取分区
func (cm *ConcurrentMap) getPartition(key Concurrent_Key) *innerMap {
	return cm.partitions_map[key.KeyAfterPartitioned()%cm.numsOfPartitions]
}

//下面的方法需要大写首字母
func (cm *ConcurrentMap) Get(key Concurrent_Key) (interface{}, bool) {
	im := cm.getPartition(key)
	return im.get(key)
}

func (cm *ConcurrentMap) Set(key Concurrent_Key, val interface{}) {
	im := cm.getPartition(key)
	im.set(key, val)
}

func (cm *ConcurrentMap) Del(key Concurrent_Key) {
	im := cm.getPartition(key)
	im.del(key)
}

type StringPartitionedKey struct {
	val string
}

func (key *StringPartitionedKey) RawKey() interface{} {
	return key.val
}

func (key *StringPartitionedKey) KeyAfterPartitioned() int64{
	return hash(key.val)
}