1package sheet23import "slices"45// An image holds an undo step's before-images of one sheet's cells in6// the form the sheet keeps them (store.go, slot.go): columns of blocks7// of 16-byte slots, the text in a table of strings kept once each, the8// formatting in a table of looks, and whole Cells only for rich cells9// (formulas, notes). A step that clears10// or rewrites a whole sheet so holds about what the sheet does, 20 B11// per number, rather than a Cell per cell. A cell that held nothing12// before the step is a bit in blank.13//14// The columns are indexed by position (occupancy.go), which costs a few15// KB for the first cell far down a sheet, so an image holds its first16// smallImage cells in a list and moves them into columns past that:17// the typical step, one cell or a few, costs what they do.18type image struct {19 small []imageCell // the cells while there are at most smallImage20 few [2]imageCell // small's first cells, without an allocation21 big bool // the cells are in cells and blank instead22 // cells holds the tables of strings, looks and rich cells, and the23 // columns once big; nil until one is needed, as a plain number24 // needs none.25 cells *cellStore26 blank occupancy27 // looks maps the sheet's looks to the image's: entry i is the28 // image's look for the sheet's look i, plus one; 0 for not yet29 // seen. A store's looks are only ever added, so the map holds.30 looks []uint1631}3233// imageCell is a before-image in an image's list: the slot, in the34// image's tables, or blank for a cell that held nothing.35type imageCell struct {36 a Addr37 sl slot38 blank bool39}4041// smallImage is how many cells an image lists before it keeps them in42// columns: a list's linear search stays cheaper than an index up to43// about this many.44const smallImage = 324546// Estimated heap of an image's parts beyond slotBytes a cell, as47// BenchmarkClearMax and BenchmarkHistoryWide measure it.48const (49 blockBytes = 256 // a block of blockRows rows, made for its first cell50 richBytes = 24 // a rich cell's entry in the side table51)5253// seen reports whether the image holds the cell at a, blank or not.54func (img *image) seen(a Addr) bool {55 if img.big {56 return img.cells.stored.has(a) || img.blank.has(a) // big has cells57 }58 for i := range img.small {59 if img.small[i].a == a {60 return true61 }62 }63 return false64}6566// len is the number of cells the image holds, blank ones included.67func (img *image) len() int {68 n := len(img.small) + img.blank.n69 if img.cells != nil {70 n += img.cells.stored.n71 }72 return n73}7475// store is img.cells, made if need be.76func (img *image) store() *cellStore {77 if img.cells == nil {78 img.cells = &cellStore{}79 }80 return img.cells81}8283// tables is img.cells to read from: an empty store when there is none,84// as a slot then refers to no table.85func (img *image) tables() *cellStore {86 if img.cells == nil {87 return &noTables88 }89 return img.cells90}9192// noTables is an empty store, never written.93var noTables cellStore9495// keep records the cell at a of src, the sheet's store, as it stands,96// and returns the heap that adds.97func (img *image) keep(src *cellStore, a Addr) int64 {98 b, i := src.find(a)99 if b == nil {100 return img.put(a, slot{}, true)101 }102 sl := b.vals[i]103 if sl.kind == slotRich {104 return img.keepRich(a, src.rich[sl.ref].c.clone())105 }106 n := int64(slotBytes)107 if sl.look != 0 {108 lk, ok := img.look(src, sl.look)109 if !ok { // the image's table of looks is full110 return img.keepRich(a, src.view(sl))111 }112 sl.look = lk113 }114 if sl.ref != 0 {115 s := src.strs.strs[sl.ref]116 t := &img.store().strs117 sl.ref = t.add(s)118 if t.refs[sl.ref] == 1 {119 n += strBytes + int64(len(s))120 }121 }122 return n + img.put(a, sl, false)123}124125// keepRich records c, a rich cell or one made to stand for a plain one,126// as the before-image at a.127func (img *image) keepRich(a Addr, c *Cell) int64 {128 n := int64(slotBytes+richBytes) + cellSize(c)129 return n + img.put(a, slot{kind: slotRich, ref: img.store().addRich(a, c)}, false)130}131132// put stores sl at a, or a blank there, which the image doesn't hold,133// and returns the heap new blocks take.134func (img *image) put(a Addr, sl slot, blank bool) int64 {135 if !img.big {136 if img.small == nil {137 img.small = img.few[:0]138 }139 if len(img.small) < smallImage {140 img.small = append(img.small, imageCell{a, sl, blank})141 return 0142 }143 n := img.grow()144 return n + img.put(a, sl, blank)145 }146 o := &img.store().stored147 if blank {148 o = &img.blank149 }150 var n int64151 if o.col(a.Col).block(a.Row>>blockShift) == nil {152 n = blockBytes153 }154 b := o.mark(a)155 if !blank {156 i, _ := b.index(a.Row & (blockRows - 1))157 b.vals = slices.Insert(b.vals, i, sl)158 }159 return n160}161162// grow moves the listed cells into columns and returns the heap their163// blocks take.164func (img *image) grow() int64 {165 img.big = true166 var n int64167 for _, ic := range img.small {168 n += img.put(ic.a, ic.sl, ic.blank)169 }170 img.small = nil171 return n172}173174// look is the image's entry for the sheet's look id, added if new, and175// false when the image's table is full.176func (img *image) look(src *cellStore, id uint16) (uint16, bool) {177 if int(id) < len(img.looks) && img.looks[id] != 0 {178 return img.looks[id] - 1, true179 }180 l := src.looks[id]181 lk, ok := img.store().lookID(l)182 if !ok {183 return 0, false184 }185 if int(id) >= len(img.looks) {186 img.looks = slices.Grow(img.looks, int(id)+1-len(img.looks))[:int(id)+1]187 }188 img.looks[id] = lk + 1189 return lk, true190}191192// each calls fn with every cell the image holds and its before-image as193// a Cell to place, nil for blank: a rich cell itself (the image is194// dropped once restored), a plain one made for the caller. fn mustn't195// change the image.196func (img *image) each(fn func(a Addr, c *Cell)) {197 st := img.tables()198 for _, ic := range img.small {199 var c *Cell200 if !ic.blank {201 c = st.cellOf(ic.sl)202 }203 fn(ic.a, c)204 }205 for _, col := range st.stored.colIDs {206 st.stored.colScan(col, 0, MaxRows-1, func(row int) bool {207 a := Addr{Col: col, Row: row}208 b, i := st.find(a)209 fn(a, st.cellOf(b.vals[i]))210 return true211 })212 }213 for _, col := range img.blank.colIDs {214 img.blank.colScan(col, 0, MaxRows-1, func(row int) bool {215 fn(Addr{Col: col, Row: row}, nil)216 return true217 })218 }219}220221// dropBlanks forgets the blank before-images of cells that are still222// blank in s, and returns the heap that frees: the blocks emptied.223func (img *image) dropBlanks(s *Sheet) int64 {224 img.small = slices.DeleteFunc(img.small, func(ic imageCell) bool { return ic.blank && !s.cells.has(ic.a) })225 var drop []Addr226 for _, c := range img.blank.colIDs {227 img.blank.colScan(c, 0, MaxRows-1, func(row int) bool {228 if a := (Addr{Col: c, Row: row}); !s.cells.has(a) {229 drop = append(drop, a)230 }231 return true232 })233 }234 blocks := img.blank.blocks()235 for _, a := range drop {236 img.blank.unmark(a)237 }238 return int64(blocks-img.blank.blocks()) * blockBytes239}240241// blocks is the number of blocks the occupancy holds.242func (o *occupancy) blocks() int {243 n := 0244 for _, c := range o.colIDs {245 n += len(o.cols[c].ids)246 }247 return n248}