2 * Copyright (c) 2009 Jiri Svoboda
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 * @brief Prototype implementation of Sheet data structure.
36 * The sheet is an abstract data structure representing a piece of text.
37 * On top of this data structure we can implement a text editor. It is
38 * possible to implement the sheet such that the editor can make small
39 * changes to large files or files containing long lines efficiently.
41 * The sheet structure allows basic operations of text insertion, deletion,
42 * retrieval and mapping of coordinates to position in the file and vice
43 * versa. The text that is inserted or deleted can contain tabs and newlines
44 * which are interpreted and properly acted upon.
46 * This is a trivial implementation with poor efficiency with O(N+n)
47 * insertion and deletion and O(N) mapping (in both directions), where
48 * N is the size of the file and n is the size of the inserted/deleted text.
59 #include "sheet_impl.h"
64 /** Initial of dat buffer in bytes */
68 /** Initialize an empty sheet. */
69 errno_t
sheet_create(sheet_t
**rsh
)
73 sh
= calloc(1, sizeof(sheet_t
));
77 sh
->dbuf_size
= INITIAL_SIZE
;
80 sh
->data
= malloc(sh
->dbuf_size
);
84 list_initialize(&sh
->tags
);
90 /** Insert text into sheet.
92 * @param sh Sheet to insert to.
93 * @param pos Point where to insert.
94 * @param dir Whether to insert before or after the point (affects tags).
95 * @param str The text to insert (printable characters, tabs, newlines).
97 * @return EOK on success or an error code.
99 * @note @a dir affects which way tags that were placed on @a pos will
100 * move. If @a dir is @c dir_before, the tags will move forward
103 errno_t
sheet_insert(sheet_t
*sh
, spt_t
*pos
, enum dir_spec dir
, char *str
)
110 if (sh
->text_size
+ sz
> sh
->dbuf_size
) {
111 /* Enlarge data buffer. */
112 newp
= realloc(sh
->data
, sh
->dbuf_size
* 2);
117 sh
->dbuf_size
= sh
->dbuf_size
* 2;
120 ipp
= sh
->data
+ pos
->b_off
;
123 memmove(ipp
+ sz
, ipp
, sh
->text_size
- pos
->b_off
);
124 memcpy(ipp
, str
, sz
);
129 list_foreach(sh
->tags
, link
, tag_t
, tag
) {
130 if (tag
->b_off
> pos
->b_off
)
132 else if (tag
->b_off
== pos
->b_off
&& dir
== dir_before
)
139 /** Delete text from sheet.
141 * Deletes the range of text between two points from the sheet.
143 * @param sh Sheet to delete from.
144 * @param spos Starting point.
145 * @param epos Ending point.
147 * @return EOK on success or an error code.
149 errno_t
sheet_delete(sheet_t
*sh
, spt_t
*spos
, spt_t
*epos
)
156 spp
= sh
->data
+ spos
->b_off
;
157 sz
= epos
->b_off
- spos
->b_off
;
159 memmove(spp
, spp
+ sz
, sh
->text_size
- (spos
->b_off
+ sz
));
163 list_foreach(sh
->tags
, link
, tag_t
, tag
) {
164 if (tag
->b_off
>= epos
->b_off
)
166 else if (tag
->b_off
>= spos
->b_off
)
167 tag
->b_off
= spos
->b_off
;
170 /* See if we should free up some memory. */
171 shrink_size
= max(sh
->dbuf_size
/ 4, INITIAL_SIZE
);
172 if (sh
->text_size
<= shrink_size
&& sh
->dbuf_size
> INITIAL_SIZE
) {
173 /* Shrink data buffer. */
174 newp
= realloc(sh
->data
, shrink_size
);
176 /* Failed to shrink buffer... no matter. */
181 sh
->dbuf_size
= shrink_size
;
187 /** Read text from sheet. */
188 void sheet_copy_out(sheet_t
*sh
, spt_t
const *spos
, spt_t
const *epos
,
189 char *buf
, size_t bufsize
, spt_t
*fpos
)
197 spp
= sh
->data
+ spos
->b_off
;
198 range_sz
= epos
->b_off
- spos
->b_off
;
199 copy_sz
= (range_sz
< bufsize
- 1) ? range_sz
: bufsize
- 1;
204 c
= str_decode(spp
, &off
, copy_sz
);
207 /* Crop copy_sz down to the last full character. */
210 memcpy(buf
, spp
, copy_sz
);
213 fpos
->b_off
= spos
->b_off
+ copy_sz
;
217 /** Get point preceding or following character cell. */
218 void sheet_get_cell_pt(sheet_t
*sh
, coord_t
const *coord
, enum dir_spec dir
,
221 size_t cur_pos
, prev_pos
;
225 cc
.row
= cc
.column
= 1;
226 cur_pos
= prev_pos
= 0;
228 if (prev_pos
>= sh
->text_size
) {
229 /* Cannot advance any further. */
233 if ((cc
.row
>= coord
->row
&& cc
.column
> coord
->column
) ||
234 cc
.row
> coord
->row
) {
235 /* We are past the requested coordinates. */
241 c
= str_decode(sh
->data
, &cur_pos
, sh
->text_size
);
245 } else if (c
== '\t') {
246 cc
.column
= 1 + ALIGN_UP(cc
.column
, TAB_WIDTH
);
253 pt
->b_off
= (dir
== dir_before
) ? prev_pos
: cur_pos
;
256 /** Get the number of character cells a row occupies. */
257 void sheet_get_row_width(sheet_t
*sh
, int row
, int *length
)
262 /* Especially nasty hack */
264 coord
.column
= 65536;
266 sheet_get_cell_pt(sh
, &coord
, dir_before
, &pt
);
267 spt_get_coord(&pt
, &coord
);
268 *length
= coord
.column
;
271 /** Get the number of rows in a sheet. */
272 void sheet_get_num_rows(sheet_t
*sh
, int *rows
)
278 for (bo
= 0; bo
< sh
->dbuf_size
; ++bo
) {
279 if (sh
->data
[bo
] == '\n')
286 /** Get the coordinates of an s-point. */
287 void spt_get_coord(spt_t
const *pos
, coord_t
*coord
)
295 cc
.row
= cc
.column
= 1;
298 while (off
< pos
->b_off
&& off
< sh
->text_size
) {
299 c
= str_decode(sh
->data
, &off
, sh
->text_size
);
303 } else if (c
== '\t') {
304 cc
.column
= 1 + ALIGN_UP(cc
.column
, TAB_WIDTH
);
313 /** Test if two s-points are equal. */
314 bool spt_equal(spt_t
const *a
, spt_t
const *b
)
316 return a
->b_off
== b
->b_off
;
319 /** Get a character at spt and return next spt */
320 wchar_t spt_next_char(spt_t spt
, spt_t
*next
)
322 wchar_t ch
= str_decode(spt
.sh
->data
, &spt
.b_off
, spt
.sh
->text_size
);
328 wchar_t spt_prev_char(spt_t spt
, spt_t
*prev
)
330 wchar_t ch
= str_decode_reverse(spt
.sh
->data
, &spt
.b_off
, spt
.sh
->text_size
);
336 /** Place a tag on the specified s-point. */
337 void sheet_place_tag(sheet_t
*sh
, spt_t
const *pt
, tag_t
*tag
)
339 tag
->b_off
= pt
->b_off
;
341 list_append(&tag
->link
, &sh
->tags
);
344 /** Remove a tag from the sheet. */
345 void sheet_remove_tag(sheet_t
*sh
, tag_t
*tag
)
347 list_remove(&tag
->link
);
350 /** Get s-point on which the tag is located right now. */
351 void tag_get_pt(tag_t
const *tag
, spt_t
*pt
)
353 pt
->b_off
= tag
->b_off
;