etcd-io · WIZARD-CXY · Jan 12, 2019
diff --git a/allocate_test.go b/allocate_test.go
@@ -6,7 +6,8 @@ import (
 
 func TestTx_allocatePageStats(t *testing.T) {
 	f := newFreelist()
-	f.ids = []pgid{2, 3}
+	f.spans = []freespan{makeFreespan(2, 2)}
+	f.spansTomap()
 
 	tx := &Tx{
 		db: &DB{
@@ -18,7 +19,7 @@ func TestTx_allocatePageStats(t *testing.T) {
 	}
 
 	prePageCnt := tx.Stats().PageCount
-	allocateCnt := f.free_count()
+	allocateCnt := f.freePageCount()
 
 	if _, err := tx.allocate(allocateCnt); err != nil {
 		t.Fatal(err)

diff --git a/bitmap.go b/bitmap.go
@@ -0,0 +1,112 @@
+package bbolt
+
+import (
+	"bytes"
+	"fmt"
+	"math/bits"
+)
+
+type bitmap struct {
+	words  []uint64
+	length int
+}
+
+func newBitmap() *bitmap {
+	return &bitmap{}
+}
+func (bitmap *bitmap) Has(num int) bool {
+	word, bit := num/64, uint(num%64)
+	return word < len(bitmap.words) && (bitmap.words[word]&(1<<bit)) != 0
+}
+
+func (bitmap *bitmap) Add(num int) {
+	word, bit := num/64, uint(num%64)
+	for word >= len(bitmap.words) {
+		bitmap.words = append(bitmap.words, 0)
+	}
+	// test if num is alreay in the bitmap
+	if bitmap.words[word]&(1<<bit) == 0 {
+		bitmap.words[word] |= 1 << bit
+		bitmap.length++
+	}
+}
+
+func (bitmap *bitmap) Len() int {
+	return bitmap.length
+}
+
+// get the smallest number in this bitmap
+// return -1 means not found
+func (bitmap *bitmap) Get() int {
+	for i, v := range bitmap.words {
+		if v == 0 {
+			continue
+		}
+		if j := getRightMostSetBit(v); j != -1 {
+			return 64*i + int(j)
+		}
+
+	}
+
+	return -1
+}
+
+// return -1 means not found
+func getRightMostSetBit(n uint64) int {
+	if x := bits.TrailingZeros64(n); x != 64 {
+		return x
+	}
+
+	return -1
+}
+
+// Del a number in this map
+func (bitmap *bitmap) Del(num int) {
+	word, bit := num/64, uint(num%64)
+	if word >= len(bitmap.words) {
+		// do not exist for sure
+		return
+	}
+
+	if bitmap.words[word]&(1<<bit) != 0 {
+		bitmap.words[word] &= ^(1 << bit)
+		bitmap.length--
+	}
+
+}
+
+func (bitmap *bitmap) ToIndices() []int {
+	var indices []int
+	for i, v := range bitmap.words {
+		if v == 0 {
+			continue
+		}
+		for j := uint(0); j < 64; j++ {
+			if v&(1<<j) != 0 {
+				indices = append(indices, 64*i+int(j))
+			}
+		}
+	}
+	return indices
+}
+
+func (bitmap *bitmap) String() string {
+	var buf bytes.Buffer
+	buf.WriteByte('{')
+	for i, v := range bitmap.words {
+		if v == 0 {
+			continue
+		}
+		for j := uint(0); j < 64; j++ {
+			if v&(1<<j) != 0 {
+				if buf.Len() > len("{") {
+					buf.WriteByte(' ')
+				}
+				fmt.Fprintf(&buf, "%d", 64*uint(i)+j)
+			}
+		}
+	}
+	buf.WriteByte('}')
+	fmt.Fprintf(&buf, "\nLength: %d\n", bitmap.length)
+	return buf.String()
+}
diff --git a/bitmap_test.go b/bitmap_test.go
@@ -0,0 +1,115 @@
+package bbolt
+
+import (
+	"reflect"
+	"testing"
+)
+
+func Test_bitmap(t *testing.T) {
+	bm := newBitmap()
+	bm.Add(1)
+	bm.Add(2)
+	bm.Add(3)
+	bm.Add(3)
+	bm.Add(300)
+	bm.Add(30)
+	res := []int{1, 2, 3, 30, 300}
+
+	if got := bm.ToIndices(); !reflect.DeepEqual(got, res) {
+		t.Errorf("Test_bitmap1() = %v, want %v", got, res)
+	}
+
+	if got := bm.Get(); got != 1 {
+		t.Errorf("Test_bitmap2() = %v, want %v", got, 1)
+	}
+	bm.Del(1)
+	if got := bm.Get(); got != 2 {
+		t.Errorf("Test_bitmap3() = %v, want %v", got, 2)
+	}
+	bm.Del(2)
+
+	if got := bm.Get(); got != 3 {
+		t.Errorf("Test_bitmap4() = %v, want %v", got, 3)
+	}
+	bm.Del(3)
+
+	if got := bm.Get(); got != 30 {
+		t.Errorf("Test_bitmap5() = %v, want %v", got, 30)
+	}
+
+	bm.Del(30)
+
+	if got := bm.Get(); got != 300 {
+		t.Errorf("Test_bitmap6() = %v, want %v", got, 300)
+	}
+
+	if got := bm.Has(4); got != false {
+		t.Errorf("Test_bitmap7() = %v, want %v", got, false)
+	}
+
+	if got := bm.Has(300); got != true {
+		t.Errorf("Test_bitmap8() = %v, want %v", got, true)
+	}
+
+	bm.Del(300)
+
+	bm.Add(64)
+	if got := bm.Get(); got != 64 {
+		t.Errorf("Test_bitmap9() = %v, want %v", got, 64)
+	}
+	bm.Del(64)
+	bm.Del(43)
+
+	var empty []int
+	if got := bm.ToIndices(); !reflect.DeepEqual(got, empty) {
+		t.Errorf("Test_bitmap10() = %v, want %v", got, empty)
+	}
+
+}
+
+func Test_getRightMostSetBit(t *testing.T) {
+	type args struct {
+		n uint64
+	}
+	tests := []struct {
+		name string
+		args args
+		want int
+	}{
+		{
+			name: "test1",
+			args: args{
+				n: 1,
+			},
+			want: 0,
+		},
+		{
+			name: "test2",
+			args: args{
+				n: 3,
+			},
+			want: 0,
+		},
+		{
+			name: "test3",
+			args: args{
+				n: 4,
+			},
+			want: 2,
+		},
+		{
+			name: "test3",
+			args: args{
+				n: 0,
+			},
+			want: -1,
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			if got := getRightMostSetBit(tt.args.n); got != tt.want {
+				t.Errorf("getRightMostSetBit() = %v, want %v", got, tt.want)
+			}
+		})
+	}
+}
diff --git a/bucket_test.go b/bucket_test.go
@@ -424,6 +424,7 @@ func TestBucket_Delete_FreelistOverflow(t *testing.T) {
 	}); err != nil {
 		t.Fatal(err)
 	}
+	db.MustCheck()
 
 	// Check more than an overflow's worth of pages are freed.
 	stats := db.Stats()

diff --git a/db.go b/db.go
@@ -291,7 +291,7 @@ func (db *DB) loadFreelist() {
 			// Read free list from freelist page.
 			db.freelist.read(db.page(db.meta().freelist))
 		}
-		db.stats.FreePageN = len(db.freelist.ids)
+		db.stats.FreePageN = db.freelist.freePageCount()
 	})
 }
 
@@ -904,10 +904,18 @@ func (db *DB) allocate(txid txid, count int) (*page, error) {
 	p.overflow = uint32(count - 1)
 
 	// Use pages from the freelist if they are available.
+	s := time.Now()
 	if p.id = db.freelist.allocate(txid, count); p.id != 0 {
+		db.statlock.Lock()
+		db.stats.TxStats.FreelistAlloctime += time.Since(s)
+		db.statlock.Unlock()
 		return p, nil
 	}
+	db.statlock.Lock()
+	db.stats.TxStats.FreelistAlloctime += time.Since(s)
+	db.statlock.Unlock()
 
+	s = time.Now()
 	// Resize mmap() if we're at the end.
 	p.id = db.rwtx.meta.pgid
 	var minsz = int((p.id+pgid(count))+1) * db.pageSize
@@ -916,6 +924,9 @@ func (db *DB) allocate(txid txid, count int) (*page, error) {
 			return nil, fmt.Errorf("mmap allocate error: %s", err)
 		}
 	}
+	db.statlock.Lock()
+	db.stats.TxStats.RemapTime += time.Since(s)
+	db.statlock.Unlock()
 
 	// Move the page id high water mark.
 	db.rwtx.meta.pgid += pgid(count)