From 2887d66a939b3b8d7e84d9c71c0a86d5132b5e54 Mon Sep 17 00:00:00 2001 From: n-peugnet Date: Tue, 21 Sep 2021 16:29:44 +0200 Subject: change recipe into a generic slice patch/diff package --- TODO.md | 9 ++++++- recipe.go | 74 ----------------------------------------------------- recipe_test.go | 24 ----------------- slice/slice.go | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++++ slice/slice_test.go | 21 +++++++++++++++ 5 files changed, 103 insertions(+), 99 deletions(-) delete mode 100644 recipe.go delete mode 100644 recipe_test.go create mode 100644 slice/slice.go create mode 100644 slice/slice_test.go diff --git a/TODO.md b/TODO.md index f48af79..6a6c52b 100644 --- a/TODO.md +++ b/TODO.md @@ -46,7 +46,14 @@ priority 2 reunion 7/09 ------------ - [ ] save recipe consecutive chunks as extents -- [ ] **TODO: Priority 1** store recipe and files incrementally. +- [ ] **TODO: Priority 1** store recipe incrementally. + - [x] patch and diff for recipes + - [ ] store recipe updates per version. + - [ ] load all recipes incrementally. +- [ ] **TODO: Priority 2** store file list incrementally. + - [ ] patch and diff for slices + - [ ] store file lists updates per version. + - [ ] load all file lists incrementally. - [x] compress recipe - [x] compress file list - [ ] make size comparison between recipe and chunks with some datasets diff --git a/recipe.go b/recipe.go deleted file mode 100644 index 92385d9..0000000 --- a/recipe.go +++ /dev/null @@ -1,74 +0,0 @@ -package main - -import "reflect" - -type Recipe []Chunk - -type RecipeDel int - -type RecipeIns struct { - Idx int - Value []Chunk -} - -type RecipePatch struct { - Del []RecipeDel - Ins []RecipeIns -} - -func patchRecipe(source Recipe, patch RecipePatch) (target Recipe) { - // apply Del part from patch to source into temp - size := len(source) - len(patch.Del) - temp := make(Recipe, size) - fill := 0 - prev := 0 - for _, del := range patch.Del { - di := int(del) - copy(temp[fill:], source[prev:di]) - fill += di - prev - prev = di + 1 - } - copy(temp[fill:], source[prev:]) - // apply Ins part from patch to temp into target - for _, ins := range patch.Ins { - size += len(ins.Value) - } - target = make(Recipe, size) - fill = 0 - prev = 0 - tpos := 0 - for _, ins := range patch.Ins { - offset := ins.Idx - prev - copy(target[fill:], temp[tpos:tpos+offset]) - fill += offset - tpos += offset - copy(target[fill:], ins.Value) - fill += len(ins.Value) - prev = ins.Idx + len(ins.Value) - } - return -} - -func diffRecipe(source Recipe, target Recipe) (patch RecipePatch) { - var si, ti int - var found bool - for ; si < len(source); si++ { - for i := ti; i < len(target); i++ { - found = reflect.DeepEqual(target[i], source[si]) - if found { - if i != ti { - patch.Ins = append(patch.Ins, RecipeIns{ti, target[ti:i]}) - } - ti = i + 1 - break - } - } - if !found { - patch.Del = append(patch.Del, RecipeDel(si)) - } - } - if ti < len(target) { - patch.Ins = append(patch.Ins, RecipeIns{ti, target[ti:]}) - } - return -} diff --git a/recipe_test.go b/recipe_test.go deleted file mode 100644 index f5c9b29..0000000 --- a/recipe_test.go +++ /dev/null @@ -1,24 +0,0 @@ -package main - -import "testing" - -func TestRecipe(t *testing.T) { - c1 := &StoredChunk{Id: &ChunkId{0, 1}} - c2 := &StoredChunk{Id: &ChunkId{0, 2}} - c3 := &StoredChunk{Id: &ChunkId{0, 3}} - c4 := &StoredChunk{Id: &ChunkId{0, 4}} - c5 := &StoredChunk{Id: &ChunkId{0, 5}} - c6 := &StoredChunk{Id: &ChunkId{0, 6}} - c7 := &StoredChunk{Id: &ChunkId{0, 7}} - source := Recipe{c1, c2, c3, c4} - target := Recipe{c2, c5, c3, c6, c4, c7} - patch := diffRecipe(source, target) - assertSame(t, []RecipeDel{0}, patch.Del, "Patch del part") - assertSame(t, []RecipeIns{ - {1, []Chunk{c5}}, - {3, []Chunk{c6}}, - {5, []Chunk{c7}}, - }, patch.Ins, "Patch ins part") - actual := patchRecipe(source, patch) - assertSame(t, target, actual, "Target obtained from patch application") -} diff --git a/slice/slice.go b/slice/slice.go new file mode 100644 index 0000000..15be5dd --- /dev/null +++ b/slice/slice.go @@ -0,0 +1,74 @@ +package slice + +import "reflect" + +type Slice []interface{} + +type SliceDel int + +type SliceIns struct { + Idx int + Value []interface{} +} + +type SlicePatch struct { + Del []SliceDel + Ins []SliceIns +} + +func PatchSlice(source Slice, patch SlicePatch) (target Slice) { + // apply Del part from patch to source into temp + size := len(source) - len(patch.Del) + temp := make(Slice, size) + fill := 0 + prev := 0 + for _, del := range patch.Del { + di := int(del) + copy(temp[fill:], source[prev:di]) + fill += di - prev + prev = di + 1 + } + copy(temp[fill:], source[prev:]) + // apply Ins part from patch to temp into target + for _, ins := range patch.Ins { + size += len(ins.Value) + } + target = make(Slice, size) + fill = 0 + prev = 0 + tpos := 0 + for _, ins := range patch.Ins { + offset := ins.Idx - prev + copy(target[fill:], temp[tpos:tpos+offset]) + fill += offset + tpos += offset + copy(target[fill:], ins.Value) + fill += len(ins.Value) + prev = ins.Idx + len(ins.Value) + } + return +} + +func DiffSlice(source Slice, target Slice) (patch SlicePatch) { + var si, ti int + var found bool + for ; si < len(source); si++ { + for i := ti; i < len(target); i++ { + found = reflect.DeepEqual(target[i], source[si]) + if found { + if i != ti { + patch.Ins = append(patch.Ins, SliceIns{ti, target[ti:i]}) + } + ti = i + 1 + break + } + } + if !found { + patch.Del = append(patch.Del, SliceDel(si)) + } + } + if ti < len(target) { + patch.Ins = append(patch.Ins, SliceIns{ti, target[ti:]}) + } + return +} diff --git a/slice/slice_test.go b/slice/slice_test.go new file mode 100644 index 0000000..b73946e --- /dev/null +++ b/slice/slice_test.go @@ -0,0 +1,21 @@ +package slice + +import ( + "testing" + + "github.com/n-peugnet/dna-backup/testutils" +) + +func TestPatch(t *testing.T) { + source := Slice{1, 2, 3, 4} + target := Slice{2, 5, 3, 6, 4, 7, 8} + patch := DiffSlice(source, target) + testutils.AssertSame(t, []SliceDel{0}, patch.Del, "Patch del part") + testutils.AssertSame(t, []SliceIns{ + {1, Slice{5}}, + {3, Slice{6}}, + {5, Slice{7, 8}}, + }, patch.Ins, "Patch ins part") + actual := PatchSlice(source, patch) + testutils.AssertSame(t, target, actual, "Target obtained from patch application") +} -- cgit v1.2.3