15946589335

Committed 28 Jun 2025 05:35PM UTC coverage: 85.945% (+2.2%) from 83.785%

Build # 15946589335

Build Type

push

github

Committed by

kelindar

Commit Message

Fix buffer size calculation in asUint16s and streamline runAndBmp function

- Updated the asUint16s function in buffer.go to correctly calculate the size of the uint16 slice based on bitmap data.
- Refactored the runAndBmp function in math_and.go to simplify the logic by directly calling bmpAndBmp, improving code clarity and maintainability.

Run Details

2 of 2 new or added lines in 2 files covered. (100.0%)

61 existing lines in 8 files now uncovered.

1651 of 1921 relevant lines covered (85.94%)

13343.71 hits per line

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

87.69

/container_bitmap.go

// Copyright (c) Roman Atachiants and contributors. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root

package roaring

import (
        "github.com/kelindar/bitmap"
)

// bmp converts the container to a bmp.Bitmap
func (c *container) bmp() bitmap.Bitmap {
        return asBitmap(c.Data)
}

// bmpSet sets a value in a bitmap container
func (c *container) bmpSet(value uint16) bool {
        if b := c.bmp(); !b.Contains(uint32(value)) {
                b.Set(uint32(value))
                c.Size++
                return true
        }
        return false
}

// bmpDel removes a value from a bitmap container
func (c *container) bmpDel(value uint16) bool {
        blkAt := int(value >> 6)
        if size := len(c.bmp()); blkAt >= size {
                return false
        }

        bitAt := int(value % 64)
        blk := &c.bmp()[blkAt]
        if (*blk & (1 << bitAt)) > 0 {
                *blk &^= (1 << bitAt)
                c.Size--
                return true
        }
        return false
}

// bmpHas checks if a value exists in a bitmap container
func (c *container) bmpHas(value uint16) bool {
        return c.bmp().Contains(uint32(value))
}

// bmpOptimize tries to optimize the container
func (c *container) bmpOptimize() {
        switch {
        case c.bmpIsDense():
                c.bmpToRun()
        case c.Size <= arrMinSize:
                c.bmpToArr()
        }
}

// bmpIsDense quickly estimates if converting to run container would be beneficial
func (c *container) bmpIsDense() bool {
        if c.Size == 0 || c.Size < 50 {
                return false
        }

        bmp := c.bmp()
        lo, loOk := bmp.Min()
        hi, hiOk := bmp.Max()
        if !loOk || !hiOk {
                return false
        }

        size := int(c.Size)
        span := int(hi - lo + 1)
        density := float64(size) / float64(span)

        // Quick density filters
        switch {
        case density < 0.1: // Very sparse
                return false
        case density > 0.9: // Very dense
                return true
        }

        // Estimate runs based on density
        runs := size
        if gap := float64(span) / float64(size); gap < 2.0 {
                runs = int(float64(size) * (1.0 - density*0.8))
        }

        // Check if estimated conversion meets our criteria
        sizeAsRunContainer := runs*4 + 2
        return runs <= 10 &&
                sizeAsRunContainer < 8192/4 &&
                sizeAsRunContainer < size
}

// bmpToRun attempts to convert bitmap to run in a single pass
func (c *container) bmpToRun() bool {
        bmp := c.bmp()
        runsData := make([]uint16, 0, 32) // estimate for initial capacity
        var curr, last uint16
        var inRun bool

        // Single iteration: build runs
        bmp.Range(func(value uint32) {
                v := uint16(value)
                switch {
                case !inRun:
                        curr = v
                        last = v
                        inRun = true
                case v == last+1:
                        last = v
                default:
                        runsData = append(runsData, curr, last)
                        curr = v
                        last = v
                }
        })

        // Handle the last run if we were in one
        if inRun {
                runsData = append(runsData, curr, last)
        }

        // Check conversion criteria with the actual run count
        numRuns := len(runsData) / 2
        cardinality := int(c.Size)
        sizeAsRunContainer := 2 + numRuns*4
        sizeAsArrayContainer := cardinality * 2

        // Only convert if run representation is much smaller and we have very few runs
        shouldConvert := numRuns <= 5 &&
                sizeAsRunContainer < 8192/4 &&
                sizeAsRunContainer < sizeAsArrayContainer/2

        if shouldConvert {
                c.Data = runsData
                c.Type = typeRun
                return true
        }

        return false
}

// bmpToArr converts this container from bitmap to array
func (c *container) bmpToArr() {
        src := c.bmp()

        // Pre-allocate array data based on cardinality
        c.Data = make([]uint16, c.Size) // uint16 per element
        c.Type = typeArray

        // Copy all values to the array efficiently
        dst := c.Data
        idx := 0
        src.Range(func(value uint32) {
                dst[idx] = uint16(value)
                idx++
        })
}

// bmpMin returns the smallest value in a bitmap container
func (c *container) bmpMin() (uint16, bool) {
        if min, ok := c.bmp().Min(); ok {
                return uint16(min), true
        }
        return 0, false
}

// bmpMax returns the largest value in a bitmap container
func (c *container) bmpMax() (uint16, bool) {
        if max, ok := c.bmp().Max(); ok {
                return uint16(max), true
        }
        return 0, false
}

// bmpMinZero returns the smallest unset value in a bitmap container
func (c *container) bmpMinZero() (uint16, bool) {
        bmp := c.bmp()
        v, ok := bmp.MinZero()
        if !ok {
                return 0, false
        }
        return uint16(v), true
}

1	// Copyright (c) Roman Atachiants and contributors. All rights reserved.
2	// Licensed under the MIT license. See LICENSE file in the project root
3
4	package roaring
5
6	import (
7	"github.com/kelindar/bitmap"
8	)
9
10	// bmp converts the container to a bmp.Bitmap
11	func (c *container) bmp() bitmap.Bitmap {	205,052✔
12	return asBitmap(c.Data)	205,052✔
13	}	205,052✔
14
15	// bmpSet sets a value in a bitmap container
16	func (c *container) bmpSet(value uint16) bool {	1,840✔
17	if b := c.bmp(); !b.Contains(uint32(value)) {	3,680✔
18	b.Set(uint32(value))	1,840✔
19	c.Size++	1,840✔
20	return true	1,840✔
21	}	1,840✔
UNCOV 22	return false	×
23	}
24
25	// bmpDel removes a value from a bitmap container
26	func (c *container) bmpDel(value uint16) bool {	48,744✔
27	blkAt := int(value >> 6)	48,744✔
28	if size := len(c.bmp()); blkAt >= size {	48,744✔
UNCOV 29	return false	×
UNCOV 30	}	×
31
32	bitAt := int(value % 64)	48,744✔
33	blk := &c.bmp()[blkAt]	48,744✔
34	if (*blk & (1 << bitAt)) > 0 {	97,488✔
35	*blk &^= (1 << bitAt)	48,744✔
36	c.Size--	48,744✔
37	return true	48,744✔
38	}	48,744✔
UNCOV 39	return false	×
40	}
41
42	// bmpHas checks if a value exists in a bitmap container
43	func (c *container) bmpHas(value uint16) bool {	105,000✔
44	return c.bmp().Contains(uint32(value))	105,000✔
45	}	105,000✔
46
47	// bmpOptimize tries to optimize the container
48	func (c *container) bmpOptimize() {	25✔
49	switch {	25✔
50	case c.bmpIsDense():	2✔
51	c.bmpToRun()	2✔
52	case c.Size <= arrMinSize:	1✔
53	c.bmpToArr()	1✔
54	}
55	}
56
57	// bmpIsDense quickly estimates if converting to run container would be beneficial
58	func (c *container) bmpIsDense() bool {	25✔
59	if c.Size == 0 \|\| c.Size < 50 {	25✔
UNCOV 60	return false	×
UNCOV 61	}	×
62
63	bmp := c.bmp()	25✔
64	lo, loOk := bmp.Min()	25✔
65	hi, hiOk := bmp.Max()	25✔
66	if !loOk \|\| !hiOk {	25✔
67	return false	×
UNCOV 68	}	×
69
70	size := int(c.Size)	25✔
71	span := int(hi - lo + 1)	25✔
72	density := float64(size) / float64(span)	25✔
73		25✔
74	// Quick density filters	25✔
75	switch {	25✔
UNCOV 76	case density < 0.1: // Very sparse	×
UNCOV 77	return false	×
78	case density > 0.9: // Very dense	2✔
79	return true	2✔
80	}
81
82	// Estimate runs based on density
83	runs := size	23✔
84	if gap := float64(span) / float64(size); gap < 2.0 {	44✔
85	runs = int(float64(size) * (1.0 - density*0.8))	21✔
86	}	21✔
87
88	// Check if estimated conversion meets our criteria
89	sizeAsRunContainer := runs*4 + 2	23✔
90	return runs <= 10 &&	23✔
91	sizeAsRunContainer < 8192/4 &&	23✔
92	sizeAsRunContainer < size	23✔
93	}
94
95	// bmpToRun attempts to convert bitmap to run in a single pass
96	func (c *container) bmpToRun() bool {	2✔
97	bmp := c.bmp()	2✔
98	runsData := make([]uint16, 0, 32) // estimate for initial capacity	2✔
99	var curr, last uint16	2✔
100	var inRun bool	2✔
101		2✔
102	// Single iteration: build runs	2✔
103	bmp.Range(func(value uint32) {	120,834✔
104	v := uint16(value)	120,832✔
105	switch {	120,832✔
106	case !inRun:	2✔
107	curr = v	2✔
108	last = v	2✔
109	inRun = true	2✔
110	case v == last+1:	110,592✔
111	last = v	110,592✔
112	default:	10,238✔
113	runsData = append(runsData, curr, last)	10,238✔
114	curr = v	10,238✔
115	last = v	10,238✔
116	}
117	})
118
119	// Handle the last run if we were in one
120	if inRun {	4✔
121	runsData = append(runsData, curr, last)	2✔
122	}	2✔
123
124	// Check conversion criteria with the actual run count
125	numRuns := len(runsData) / 2	2✔
126	cardinality := int(c.Size)	2✔
127	sizeAsRunContainer := 2 + numRuns*4	2✔
128	sizeAsArrayContainer := cardinality * 2	2✔
129		2✔
130	// Only convert if run representation is much smaller and we have very few runs	2✔
131	shouldConvert := numRuns <= 5 &&	2✔
132	sizeAsRunContainer < 8192/4 &&	2✔
133	sizeAsRunContainer < sizeAsArrayContainer/2	2✔
134		2✔
135	if shouldConvert {	2✔
UNCOV 136	c.Data = runsData	×
UNCOV 137	c.Type = typeRun	×
UNCOV 138	return true	×
UNCOV 139	}	×
140
141	return false	2✔
142	}
143
144	// bmpToArr converts this container from bitmap to array
145	func (c *container) bmpToArr() {	1✔
146	src := c.bmp()	1✔
147		1✔
148	// Pre-allocate array data based on cardinality	1✔
149	c.Data = make([]uint16, c.Size) // uint16 per element	1✔
150	c.Type = typeArray	1✔
151		1✔
152	// Copy all values to the array efficiently	1✔
153	dst := c.Data	1✔
154	idx := 0	1✔
155	src.Range(func(value uint32) {	1,809✔
156	dst[idx] = uint16(value)	1,808✔
157	idx++	1,808✔
158	})	1,808✔
159	}
160
161	// bmpMin returns the smallest value in a bitmap container
162	func (c *container) bmpMin() (uint16, bool) {	4✔
163	if min, ok := c.bmp().Min(); ok {	7✔
164	return uint16(min), true	3✔
165	}	3✔
166	return 0, false	1✔
167	}
168
169	// bmpMax returns the largest value in a bitmap container
170	func (c *container) bmpMax() (uint16, bool) {	4✔
171	if max, ok := c.bmp().Max(); ok {	7✔
172	return uint16(max), true	3✔
173	}	3✔
174	return 0, false	1✔
175	}
176
177	// bmpMinZero returns the smallest unset value in a bitmap container
178	func (c *container) bmpMinZero() (uint16, bool) {	4✔
179	bmp := c.bmp()	4✔
180	v, ok := bmp.MinZero()	4✔
181	if !ok {	4✔
UNCOV 182	return 0, false	×
UNCOV 183	}	×
184	return uint16(v), true	4✔
185	}

kelindar / roaring / 15946589335

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