17565519027

Committed 08 Sep 2025 10:10PM UTC coverage: 74.449% (+0.3%) from 74.138%

Build # 17565519027

Build Type

push

Committed by

Commit Message

optimize bitmap

Run Details

56 of 62 new or added lines in 2 files covered. (90.32%)

1 existing line in 1 file now uncovered.

405 of 544 relevant lines covered (74.45%)

36.57 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

85.42

/structs/bitmap/bitmap.go

/*
 *  Copyright (c) 2019-2025 Mikhail Knyazhev <markus621@yandex.com>. All rights reserved.
 *  Use of this source code is governed by a BSD 3-Clause license that can be found in the LICENSE file.
 */

package bitmap

import (
        "sync"
)

const (
        blockSize = 8
        MaxIndex  = uint64(1 << 34)
)

type Bitmap struct {
        bits []byte

        blocks  uint64
        max     uint64
        lockoff bool

        mux sync.RWMutex
}

type Option func(*Bitmap)

func OptDisableLock() Option {
        return func(o *Bitmap) {
                o.lockoff = true
        }
}

func OptMaxIndex(index uint64) Option {
        return func(o *Bitmap) {
                o.max = index
        }
}

func New(opts ...Option) *Bitmap {
        bm := &Bitmap{max: 1}

        for _, opt := range opts {
                opt(bm)
        }

        bm.resize(bm.max)

        return bm
}

func (b *Bitmap) resize(index uint64) {
        size := index / blockSize
        if index-(size%blockSize) > 0 {
                size++
        }

        b.bits = append(b.bits, make([]byte, size-b.blocks)...)
        b.blocks = uint64(len(b.bits))
        b.max = b.blocks*blockSize - 1
}

func (b *Bitmap) getBlock(index uint64) uint64 {
        return index / blockSize
}

func (b *Bitmap) getBit(index uint64) byte {
        return 1 << (index - b.getBlock(index)*blockSize)
}

func (b *Bitmap) Set(index uint64) {
        if index > MaxIndex {
                return
        }

        if !b.lockoff {
                b.mux.Lock()
                defer b.mux.Unlock()
        }

        if index > b.max {
                b.resize(index)
        }

        b.bits[b.getBlock(index)] |= b.getBit(index)
}

func (b *Bitmap) Del(index uint64) {
        if index > b.max || index > MaxIndex {
                return
        }

        if !b.lockoff {
                b.mux.Lock()
                defer b.mux.Unlock()
        }

        b.bits[b.getBlock(index)] &^= b.getBit(index)
}

func (b *Bitmap) Has(index uint64) bool {
        if index > b.max || index > MaxIndex {
                return false
        }

        if !b.lockoff {
                b.mux.RLock()
                defer b.mux.RUnlock()
        }

        return (b.bits[b.getBlock(index)] & b.getBit(index)) > 0
}

func (b *Bitmap) MarshalBinary() ([]byte, error) {
        if !b.lockoff {
                b.mux.RLock()
                defer b.mux.RUnlock()
        }

        out := make([]byte, b.blocks)
        copy(out, b.bits)

        return out, nil
}

func (b *Bitmap) UnmarshalBinary(in []byte) error {
        if !b.lockoff {
                b.mux.Lock()
                defer b.mux.Unlock()
        }

        b.bits = make([]byte, len(in))
        copy(b.bits, in)

        b.blocks = uint64(len(in))
        b.max = b.blocks * blockSize

        return nil
}

func (b *Bitmap) CopyTo(dst *Bitmap) {
        if !b.lockoff {
                b.mux.Lock()
                defer b.mux.Unlock()
        }
        if !dst.lockoff {
                dst.mux.Lock()
                defer dst.mux.Unlock()
        }

        dst.bits = make([]byte, len(b.bits))
        copy(dst.bits, b.bits)
        dst.blocks = b.blocks
        dst.max = b.max
        dst.lockoff = b.lockoff
}

1	/*
2	* Copyright (c) 2019-2025 Mikhail Knyazhev <markus621@yandex.com>. All rights reserved.
3	* Use of this source code is governed by a BSD 3-Clause license that can be found in the LICENSE file.
4	*/
5
6	package bitmap
7
8	import (
9	"sync"
10	)
11
12	const (
13	blockSize = 8
14	MaxIndex = uint64(1 << 34)
15	)
16
17	type Bitmap struct {
18	bits []byte
19
20	blocks uint64
21	max uint64
22	lockoff bool
23
24	mux sync.RWMutex
25	}
26
27	type Option func(*Bitmap)
28
NEW 29	func OptDisableLock() Option {	×
30	return func(o *Bitmap) {	×
31	o.lockoff = true	×
32	}	×
33	}
34
NEW 35	func OptMaxIndex(index uint64) Option {	×
NEW 36	return func(o *Bitmap) {	×
NEW 37	o.max = index	×
UNCOV 38	}	×
39	}
40
41	func New(opts ...Option) *Bitmap {	3✔
42	bm := &Bitmap{max: 1}	3✔
43		3✔
44	for _, opt := range opts {	3✔
45	opt(bm)	×
46	}	×
47
48	bm.resize(bm.max)	3✔
49		3✔
50	return bm	3✔
51	}
52
53	func (b *Bitmap) resize(index uint64) {	12✔
54	size := index / blockSize	12✔
55	if index-(size%blockSize) > 0 {	24✔
56	size++	12✔
57	}	12✔
58
59	b.bits = append(b.bits, make([]byte, size-b.blocks)...)	12✔
60	b.blocks = uint64(len(b.bits))	12✔
61	b.max = b.blocks*blockSize - 1	12✔
62	}
63
64	func (b *Bitmap) getBlock(index uint64) uint64 {	1,178✔
65	return index / blockSize	1,178✔
66	}	1,178✔
67
68	func (b *Bitmap) getBit(index uint64) byte {	589✔
69	return 1 << (index - b.getBlock(index)*blockSize)	589✔
70	}	589✔
71
72	func (b *Bitmap) Set(index uint64) {	69✔
73	if index > MaxIndex {	69✔
74	return	×
75	}	×
76
77	if !b.lockoff {	138✔
78	b.mux.Lock()	69✔
79	defer b.mux.Unlock()	69✔
80	}	69✔
81
82	if index > b.max {	78✔
83	b.resize(index)	9✔
84	}	9✔
85
86	b.bits[b.getBlock(index)] \|= b.getBit(index)	69✔
87	}
88
89	func (b *Bitmap) Del(index uint64) {	66✔
90	if index > b.max \|\| index > MaxIndex {	66✔
91	return	×
92	}	×
93
94	if !b.lockoff {	132✔
95	b.mux.Lock()	66✔
96	defer b.mux.Unlock()	66✔
97	}	66✔
98
99	b.bits[b.getBlock(index)] &^= b.getBit(index)	66✔
100	}
101
102	func (b *Bitmap) Has(index uint64) bool {	462✔
103	if index > b.max \|\| index > MaxIndex {	470✔
104	return false	8✔
105	}	8✔
106
107	if !b.lockoff {	908✔
108	b.mux.RLock()	454✔
109	defer b.mux.RUnlock()	454✔
110	}	454✔
111
112	return (b.bits[b.getBlock(index)] & b.getBit(index)) > 0	454✔
113	}
114
115	func (b *Bitmap) MarshalBinary() ([]byte, error) {	1✔
116	if !b.lockoff {	2✔
117	b.mux.RLock()	1✔
118	defer b.mux.RUnlock()	1✔
119	}	1✔
120
121	out := make([]byte, b.blocks)	1✔
122	copy(out, b.bits)	1✔
123		1✔
124	return out, nil	1✔
125	}
126
127	func (b *Bitmap) UnmarshalBinary(in []byte) error {	2✔
128	if !b.lockoff {	4✔
129	b.mux.Lock()	2✔
130	defer b.mux.Unlock()	2✔
131	}	2✔
132
133	b.bits = make([]byte, len(in))	2✔
134	copy(b.bits, in)	2✔
135		2✔
136	b.blocks = uint64(len(in))	2✔
137	b.max = b.blocks * blockSize	2✔
138		2✔
139	return nil	2✔
140	}
141
142	func (b Bitmap) CopyTo(dst Bitmap) {	1✔
143	if !b.lockoff {	2✔
144	b.mux.Lock()	1✔
145	defer b.mux.Unlock()	1✔
146	}	1✔
147	if !dst.lockoff {	2✔
148	dst.mux.Lock()	1✔
149	defer dst.mux.Unlock()	1✔
150	}	1✔
151
152	dst.bits = make([]byte, len(b.bits))	1✔
153	copy(dst.bits, b.bits)	1✔
154	dst.blocks = b.blocks	1✔
155	dst.max = b.max	1✔
156	dst.lockoff = b.lockoff	1✔
157	}

osspkg / go-algorithms / 17565519027

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous