1// MIT License
2
3// Copyright (c) 2017 Vadim Grigoruk @nesbox // grigoruk@gmail.com
4
5// Permission is hereby granted, free of charge, to any person obtaining a copy
6// of this software and associated documentation files (the "Software"), to deal
7// in the Software without restriction, including without limitation the rights
8// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9// copies of the Software, and to permit persons to whom the Software is
10// furnished to do so, subject to the following conditions:
11
12// The above copyright notice and this permission notice shall be included in all
13// copies or substantial portions of the Software.
14
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21// SOFTWARE.
22
23#include "history.h"
24
25#include <stdlib.h>
26#include <stdio.h>
27#include <string.h>
28
29typedef struct
30{
31 u8* buffer;
32 u32 start;
33 u32 end;
34} Data;
35
36typedef struct Item Item;
37
38struct Item
39{
40 Item* next;
41 Item* prev;
42
43 Data data;
44};
45
46static void list_delete(Item* list, Item* from)
47{
48 Item* it = from;
49
50 while(it)
51 {
52 Item* next = it->next;
53
54 if(it->data.buffer) free(it->data.buffer);
55
56 free(it);
57
58 it = next;
59 }
60}
61
62static Item* list_insert(Item* list, Data* data)
63{
64 Item* item = (Item*)malloc(sizeof(Item));
65 item->next = NULL;
66 item->prev = NULL;
67 item->data = *data;
68
69 if(list)
70 {
71 list_delete(list, list->next);
72
73 list->next = item;
74 item->prev = list;
75 }
76
77 return item;
78}
79
80static Item* list_first(Item* list)
81{
82 Item* it = list;
83 while(it->prev) it = it->prev;
84
85 return it;
86}
87
88struct History
89{
90 Item* list;
91
92 u32 size;
93 u8* state;
94
95 void* data;
96};
97
98History* history_create(void* data, u32 size)
99{
100 History* history = (History*)malloc(sizeof(History));
101 history->data = data;
102
103 history->list = NULL;
104 history->size = size;
105
106 history->state = malloc(size);
107 memcpy(history->state, data, history->size);
108
109 // empty diff
110 history->list = list_insert(history->list, &(Data){NULL, 0, 0});
111
112 return history;
113}
114
115void history_delete(History* history)
116{
117 if(history)
118 {
119 free(history->state);
120
121 list_delete(history->list, list_first(history->list));
122
123 free(history);
124 }
125}
126
127static void history_diff(History* history, Data* data)
128{
129 for (u32 i = data->start, k = 0; i < data->end; ++i, ++k)
130 history->state[i] ^= data->buffer[k];
131}
132
133static u32 trim_left(u8* data, u32 size)
134{
135 for(u32 i = 0; i < size; i++)
136 if(data[i]) return i;
137
138 return size;
139}
140
141static u32 trim_right(u8* data, u32 size)
142{
143 for(u32 i = 0; i < size; i++)
144 if(data[size - i - 1]) return size - i;
145
146 return 0;
147}
148
149bool history_add(History* history)
150{
151 if (memcmp(history->state, history->data, history->size) == 0) return false;
152
153 history_diff(history, &(Data){history->data, 0, history->size});
154
155 {
156 Data data;
157 data.start = trim_left(history->state, history->size);
158 data.end = trim_right(history->state, history->size);
159 u32 size = data.end - data.start;
160 data.buffer = malloc(size);
161
162 memcpy(data.buffer, (u8*)history->state + data.start, size);
163
164 history->list = list_insert(history->list, &data);
165 }
166
167 memcpy(history->state, history->data, history->size);
168
169 return true;
170}
171
172void history_undo(History* history)
173{
174 if(history->list->prev)
175 {
176 history_diff(history, &history->list->data);
177
178 history->list = history->list->prev;
179 }
180
181 memcpy(history->data, history->state, history->size);
182}
183
184void history_redo(History* history)
185{
186 if(history->list->next)
187 {
188 history->list = history->list->next;
189
190 history_diff(history, &history->list->data);
191 }
192
193 memcpy(history->data, history->state, history->size);
194}
195