boolmap - crumbmap.go

     1  package boolmap
     2  
     3  // CrumbMap is a map of Crumbs (2-bits, values 0, 1, 2, 3)
     4  type CrumbMap map[uint64]byte
     5  
     6  // NewCrumbMap returns a new, initialised, CrumbMap
     7  func NewCrumbMap() CrumbMap {
     8  	return make(CrumbMap)
     9  }
    10  
    11  // Get returns a crumb from the given position
    12  func (c CrumbMap) Get(p uint64) byte {
    13  	d := c[p>>2]
    14  	switch p & 3 {
    15  	case 1:
    16  		d >>= 2
    17  	case 2:
    18  		d >>= 4
    19  	case 3:
    20  		d >>= 6
    21  	}
    22  	return d & 3
    23  }
    24  
    25  // Set sets the crumb at the given position
    26  func (c CrumbMap) Set(p uint64, d byte) {
    27  	pos := p >> 2
    28  	d &= 3
    29  	oldData, ok := c[pos]
    30  	if !ok && d == 0 {
    31  		return
    32  	}
    33  	switch p & 3 {
    34  	case 0:
    35  		d = oldData&252 | d
    36  	case 1:
    37  		d = oldData&243 | d<<2
    38  	case 2:
    39  		d = oldData&207 | d<<4
    40  	case 3:
    41  		d = oldData&63 | d<<6
    42  	}
    43  	if d == 0 {
    44  		delete(c, pos)
    45  	} else {
    46  		c[pos] = d
    47  	}
    48  }
    49  
    50  // CrumbSlice is a slice of bytes, representing crumbs (2-bits)
    51  type CrumbSlice []byte
    52  
    53  // NewCrumbSlice returns a new, initialised, CrumbSlice
    54  func NewCrumbSlice() *CrumbSlice {
    55  	return NewCrumbSliceSize(1)
    56  }
    57  
    58  // NewCrumbSliceSize returns a new Crumbslice, initialised to the given size
    59  func NewCrumbSliceSize(size uint) *CrumbSlice {
    60  	sliceSize := size >> 2
    61  	if size&3 != 0 {
    62  		sliceSize++
    63  	}
    64  	c := make(CrumbSlice, sliceSize)
    65  	return &c
    66  }
    67  
    68  // Get returns a crumb from the given position
    69  func (c CrumbSlice) Get(p uint) byte {
    70  	pos := p >> 2
    71  	if pos >= uint(len(c)) {
    72  		return 0
    73  	}
    74  	d := c[pos]
    75  	switch p & 3 {
    76  	case 1:
    77  		d >>= 2
    78  	case 2:
    79  		d >>= 4
    80  	case 3:
    81  		d >>= 6
    82  	}
    83  	return d & 3
    84  }
    85  
    86  // Set sets the crumb at the given position
    87  func (c *CrumbSlice) Set(p uint, d byte) {
    88  	pos := p >> 2
    89  	if pos >= uint(len(*c)) {
    90  		if d == 0 {
    91  			return
    92  		}
    93  		if pos < uint(cap(*c)) {
    94  			(*c) = (*c)[:cap(*c)]
    95  		} else {
    96  			var newData CrumbSlice
    97  			if pos < 512 {
    98  				newData = make(CrumbSlice, pos<<1)
    99  			} else {
   100  				newData = make(CrumbSlice, pos+(pos>>2))
   101  			}
   102  			copy(newData, *c)
   103  			*c = newData
   104  		}
   105  	}
   106  	d &= 3
   107  	oldData := (*c)[pos]
   108  	switch p & 3 {
   109  	case 0:
   110  		d = oldData&252 | d
   111  	case 1:
   112  		d = oldData&243 | d<<2
   113  	case 2:
   114  		d = oldData&207 | d<<4
   115  	case 3:
   116  		d = oldData&63 | d<<6
   117  	}
   118  	(*c)[pos] = d
   119  }