src/editor/editbuffer.c: typo.
[midnight-commander.git] / src / editor / editbuffer.c
blob751a36dff352f7609c2e587e03041d9c7ef0d07e
1 /*
2 Editor text keep buffer.
4 Copyright (C) 2013
5 The Free Software Foundation, Inc.
7 Written by:
8 Andrew Borodin <aborodin@vmail.ru> 2013
10 This file is part of the Midnight Commander.
12 The Midnight Commander is free software: you can redistribute it
13 and/or modify it under the terms of the GNU General Public License as
14 published by the Free Software Foundation, either version 3 of the License,
15 or (at your option) any later version.
17 The Midnight Commander is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License for more details.
22 You should have received a copy of the GNU General Public License
23 along with this program. If not, see <http://www.gnu.org/licenses/>.
26 /** \file
27 * \brief Source: editor text keep buffer.
28 * \author Andrew Borodin
29 * \date 2013
32 #include <config.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include <sys/types.h>
38 #include "lib/global.h"
40 #include "lib/vfs/vfs.h"
42 #include "edit-impl.h"
43 #include "editbuffer.h"
45 /* --------------------------------------------------------------------------------------------- */
46 /*-
48 * here's a quick sketch of the layout: (don't run this through indent.)
50 * |
51 * \0\0\0\0\0m e _ f i l e . \nf i n . \n|T h i s _ i s _ s o\0\0\0\0\0\0\0\0\0
52 * ______________________________________|______________________________________
53 * |
54 * ... | b2[2] | b2[1] | b2[0] | b1[0] | b1[1] | b1[2] | ...
55 * |-> |-> |-> |-> |-> |-> |
56 * |
57 * _<------------------------->|<----------------->_
58 * curs2 | curs1
59 * ^ | ^
60 * | ^|^ |
61 * cursor ||| cursor
62 * |||
63 * file end|||file beginning
64 * |
65 * |
67 * _
68 * This_is_some_file
69 * fin.
72 * This is called a "gab buffer".
73 * See also:
74 * http://en.wikipedia.org/wiki/Gap_buffer
75 * http://stackoverflow.com/questions/4199694/data-structure-for-text-editor
78 /*** global variables ****************************************************************************/
80 /*** file scope macro definitions ****************************************************************/
83 * The editor keeps data in two arrays of buffers.
84 * All buffers have the same size, which must be a power of 2.
87 /* Configurable: log2 of the buffer size in bytes */
88 #ifndef S_EDIT_BUF_SIZE
89 #define S_EDIT_BUF_SIZE 16
90 #endif
92 /* Size of the buffer */
93 #define EDIT_BUF_SIZE (((off_t) 1) << S_EDIT_BUF_SIZE)
95 /* Buffer mask (used to find cursor position relative to the buffer) */
96 #define M_EDIT_BUF_SIZE (EDIT_BUF_SIZE - 1)
98 /*** file scope type declarations ****************************************************************/
100 /*** file scope variables ************************************************************************/
102 /* --------------------------------------------------------------------------------------------- */
103 /*** file scope functions ************************************************************************/
104 /* --------------------------------------------------------------------------------------------- */
106 * Get pointer to byte at specified index
108 * @param buf pointer to editor buffer
109 * @param byte_index byte index
111 * @return NULL if byte_index is negative or larger than file size; pointer to byte otherwise.
113 static char *
114 edit_buffer_get_byte_ptr (const edit_buffer_t * buf, off_t byte_index)
116 void *b;
118 if (byte_index >= (buf->curs1 + buf->curs2) || byte_index < 0)
119 return NULL;
121 if (byte_index >= buf->curs1)
123 off_t p;
125 p = buf->curs1 + buf->curs2 - byte_index - 1;
126 b = g_ptr_array_index (buf->b2, p >> S_EDIT_BUF_SIZE);
127 return (char *) b + EDIT_BUF_SIZE - 1 - (p & M_EDIT_BUF_SIZE);
130 b = g_ptr_array_index (buf->b1, byte_index >> S_EDIT_BUF_SIZE);
131 return (char *) b + (byte_index & M_EDIT_BUF_SIZE);
134 /* --------------------------------------------------------------------------------------------- */
135 /*** public functions ****************************************************************************/
136 /* --------------------------------------------------------------------------------------------- */
138 * Initialize editor buffers.
140 * @param buf pointer to editor buffer
143 void
144 edit_buffer_init (edit_buffer_t * buf, off_t size)
146 buf->b1 = g_ptr_array_sized_new (32);
147 buf->b2 = g_ptr_array_sized_new (32);
149 buf->curs1 = 0;
150 buf->curs2 = 0;
152 buf->size = size;
153 buf->lines = 0;
156 /* --------------------------------------------------------------------------------------------- */
158 * Clean editor buffers.
160 * @param buf pointer to editor buffer
163 void
164 edit_buffer_clean (edit_buffer_t * buf)
166 if (buf->b1 != NULL)
168 g_ptr_array_foreach (buf->b1, (GFunc) g_free, NULL);
169 g_ptr_array_free (buf->b1, TRUE);
172 if (buf->b2 != NULL)
174 g_ptr_array_foreach (buf->b2, (GFunc) g_free, NULL);
175 g_ptr_array_free (buf->b2, TRUE);
179 /* --------------------------------------------------------------------------------------------- */
181 * Get byte at specified index
183 * @param buf pointer to editor buffer
184 * @param byte_index byte index
186 * @return '\n' if byte_index is negative or larger than file size; byte at byte_index otherwise.
190 edit_buffer_get_byte (const edit_buffer_t * buf, off_t byte_index)
192 char *p;
194 p = edit_buffer_get_byte_ptr (buf, byte_index);
196 return (p != NULL) ? *(unsigned char *) p : '\n';
199 /* --------------------------------------------------------------------------------------------- */
201 #ifdef HAVE_CHARSET
203 * Get utf-8 symbol at specified index
205 * @param buf pointer to editor buffer
206 * @param byte_index byte index
207 * @param char_width width of returned symbol
209 * @return '\n' if byte_index is negative or larger than file size;
210 * 0 if utf-8 symbol at specified index is invalid;
211 * utf-8 symbol otherwise
215 edit_buffer_get_utf (const edit_buffer_t * buf, off_t byte_index, int *char_width)
217 gchar *str = NULL;
218 gunichar res;
219 gunichar ch;
220 gchar *next_ch = NULL;
222 if (byte_index >= (buf->curs1 + buf->curs2) || byte_index < 0)
224 *char_width = 0;
225 return '\n';
228 str = edit_buffer_get_byte_ptr (buf, byte_index);
229 if (str == NULL)
231 *char_width = 0;
232 return 0;
235 res = g_utf8_get_char_validated (str, -1);
236 if (res == (gunichar) (-2) || res == (gunichar) (-1))
238 /* Retry with explicit bytes to make sure it's not a buffer boundary */
239 size_t i;
240 gchar utf8_buf[UTF8_CHAR_LEN + 1];
242 for (i = 0; i < UTF8_CHAR_LEN; i++)
243 utf8_buf[i] = edit_buffer_get_byte (buf, byte_index + i);
244 utf8_buf[i] = '\0';
245 res = g_utf8_get_char_validated (utf8_buf, -1);
248 if (res == (gunichar) (-2) || res == (gunichar) (-1))
250 ch = *str;
251 *char_width = 0;
253 else
255 ch = res;
256 /* Calculate UTF-8 char width */
257 next_ch = g_utf8_next_char (str);
258 if (next_ch != NULL)
259 *char_width = next_ch - str;
260 else
262 ch = 0;
263 *char_width = 0;
267 return (int) ch;
270 /* --------------------------------------------------------------------------------------------- */
272 * Get utf-8 symbol before specified index
274 * @param buf pointer to editor buffer
275 * @param byte_index byte index
276 * @param char_width width of returned symbol
278 * @return 0 if byte_index is negative or larger than file size;
279 * 1-byte value before specified index if utf-8 symbol before specified index is invalid;
280 * utf-8 symbol otherwise
284 edit_buffer_get_prev_utf (const edit_buffer_t * buf, off_t byte_index, int *char_width)
286 size_t i;
287 gchar utf8_buf[3 * UTF8_CHAR_LEN + 1];
288 gchar *str;
289 gchar *cursor_buf_ptr;
290 gunichar res;
292 if (byte_index > (buf->curs1 + buf->curs2) || byte_index <= 0)
294 *char_width = 0;
295 return 0;
298 for (i = 0; i < (3 * UTF8_CHAR_LEN); i++)
299 utf8_buf[i] = edit_buffer_get_byte (buf, byte_index + i - (2 * UTF8_CHAR_LEN));
300 utf8_buf[i] = '\0';
302 cursor_buf_ptr = utf8_buf + (2 * UTF8_CHAR_LEN);
303 str = g_utf8_find_prev_char (utf8_buf, cursor_buf_ptr);
305 if (str == NULL || g_utf8_next_char (str) != cursor_buf_ptr)
307 *char_width = 1;
308 return *(cursor_buf_ptr - 1);
311 res = g_utf8_get_char_validated (str, -1);
312 if (res == (gunichar) (-2) || res == (gunichar) (-1))
314 *char_width = 1;
315 return *(cursor_buf_ptr - 1);
318 *char_width = cursor_buf_ptr - str;
319 return (int) res;
321 #endif /* HAVE_CHARSET */
323 /* --------------------------------------------------------------------------------------------- */
325 * Count lines in editor buffer.
327 * @param buf editor buffer
328 * @param first start byte offset
329 * @param last finish byte offset
331 * @return line numbers between "first" and "last" bytes
334 long
335 edit_buffer_count_lines (const edit_buffer_t * buf, off_t first, off_t last)
337 long lines = 0;
339 first = max (first, 0);
340 last = min (last, buf->size);
342 while (first < last)
343 if (edit_buffer_get_byte (buf, first++) == '\n')
344 lines++;
346 return lines;
349 /* --------------------------------------------------------------------------------------------- */
351 * Get "begin-of-line" offset of line contained specified byte offset
353 * @param buf editor buffer
354 * @param current byte offset
356 * @return index of first char of line
359 off_t
360 edit_buffer_get_bol (const edit_buffer_t * buf, off_t current)
362 if (current <= 0)
363 return 0;
365 for (; edit_buffer_get_byte (buf, current - 1) != '\n'; current--)
368 return current;
371 /* --------------------------------------------------------------------------------------------- */
373 * Get "end-of-line" offset of line contained specified byte offset
375 * @param buf editor buffer
376 * @param current byte offset
378 * @return index of last char of line + 1
381 off_t
382 edit_buffer_get_eol (const edit_buffer_t * buf, off_t current)
384 if (current >= buf->size)
385 return buf->size;
387 for (; edit_buffer_get_byte (buf, current) != '\n'; current++)
390 return current;
393 /* --------------------------------------------------------------------------------------------- */
395 * Get word from specified offset.
397 * @param buf editor buffer
398 * @param current start_pos offset
399 * @param start actual start word ofset
400 * @param cut
402 * @return word as newly allocated object
405 GString *
406 edit_buffer_get_word_from_pos (const edit_buffer_t * buf, off_t start_pos, off_t * start,
407 gsize * cut)
409 off_t word_start;
410 long cut_len = 0;
411 GString *match_expr;
412 int c1, c2;
414 for (word_start = start_pos; word_start != 0; word_start--, cut_len++)
416 c1 = edit_buffer_get_byte (buf, word_start);
417 c2 = edit_buffer_get_byte (buf, word_start - 1);
419 if (is_break_char (c1) != is_break_char (c2) || c1 == '\n' || c2 == '\n')
420 break;
423 match_expr = g_string_sized_new (16);
427 c1 = edit_buffer_get_byte (buf, word_start + match_expr->len);
428 c2 = edit_buffer_get_byte (buf, word_start + match_expr->len + 1);
429 g_string_append_c (match_expr, c1);
431 while (!(is_break_char (c1) != is_break_char (c2) || c1 == '\n' || c2 == '\n'));
433 *start = word_start;
434 *cut = cut_len;
436 return match_expr;
439 /* --------------------------------------------------------------------------------------------- */
441 * Basic low level single character buffer alterations and movements at the cursor: insert character
442 * at the cursor position and move right.
444 * @param buf pointer to editor buffer
445 * @param c character to insert
448 void
449 edit_buffer_insert (edit_buffer_t * buf, int c)
451 void *b;
452 off_t i;
454 i = buf->curs1 & M_EDIT_BUF_SIZE;
456 /* add a new buffer if we've reached the end of the last one */
457 if (i == 0)
458 g_ptr_array_add (buf->b1, g_malloc0 (EDIT_BUF_SIZE));
460 /* perform the insertion */
461 b = g_ptr_array_index (buf->b1, buf->curs1 >> S_EDIT_BUF_SIZE);
462 *((unsigned char *) b + i) = (unsigned char) c;
464 /* update cursor position */
465 buf->curs1++;
468 /* --------------------------------------------------------------------------------------------- */
470 * Basic low level single character buffer alterations and movements at the cursor: insert character
471 * at the cursor position and move left.
473 * @param buf pointer to editor buffer
474 * @param c character to insert
477 void
478 edit_buffer_insert_ahead (edit_buffer_t * buf, int c)
480 void *b;
481 off_t i;
483 i = buf->curs2 & M_EDIT_BUF_SIZE;
485 /* add a new buffer if we've reached the end of the last one */
486 if (i == 0)
487 g_ptr_array_add (buf->b2, g_malloc0 (EDIT_BUF_SIZE));
489 /* perform the insertion */
490 b = g_ptr_array_index (buf->b2, buf->curs2 >> S_EDIT_BUF_SIZE);
491 *((unsigned char *) b + EDIT_BUF_SIZE - 1 - i) = (unsigned char) c;
493 /* update cursor position */
494 buf->curs2++;
497 /* --------------------------------------------------------------------------------------------- */
499 * Basic low level single character buffer alterations and movements at the cursor: delete character
500 * at the cursor position.
502 * @param buf pointer to editor buffer
503 * @param c character to insert
507 edit_buffer_delete (edit_buffer_t * buf)
509 void *b;
510 unsigned char c;
511 off_t prev;
512 off_t i;
514 prev = buf->curs2 - 1;
516 b = g_ptr_array_index (buf->b2, prev >> S_EDIT_BUF_SIZE);
517 i = prev & M_EDIT_BUF_SIZE;
518 c = *((unsigned char *) b + EDIT_BUF_SIZE - 1 - i);
520 if (i == 0)
522 i = buf->b2->len - 1;
523 b = g_ptr_array_index (buf->b2, i);
524 g_ptr_array_remove_index (buf->b2, i);
525 g_free (b);
528 buf->curs2 = prev;
530 return c;
533 /* --------------------------------------------------------------------------------------------- */
535 * Basic low level single character buffer alterations and movements at the cursor: delete character
536 * before the cursor position and move left.
538 * @param buf pointer to editor buffer
539 * @param c character to insert
543 edit_buffer_backspace (edit_buffer_t * buf)
545 void *b;
546 unsigned char c;
547 off_t prev;
548 off_t i;
550 prev = buf->curs1 - 1;
552 b = g_ptr_array_index (buf->b1, prev >> S_EDIT_BUF_SIZE);
553 i = prev & M_EDIT_BUF_SIZE;
554 c = *((unsigned char *) b + i);
556 if (i == 0)
558 i = buf->b1->len - 1;
559 b = g_ptr_array_index (buf->b1, i);
560 g_ptr_array_remove_index (buf->b1, i);
561 g_free (b);
564 buf->curs1 = prev;
566 return c;
570 /* --------------------------------------------------------------------------------------------- */
572 * Calculate forward offset with specified number of lines.
574 * @param buf editor buffer
575 * @param current current offset
576 * @param lines number of lines to move forward
577 * @param upto offset to count lines between current and upto.
579 * @return If lines is zero returns the count of lines from current to upto.
580 * If upto is zero returns offset of lines forward current.
581 * Else returns forward offset with specified number of lines
584 off_t
585 edit_buffer_move_forward (const edit_buffer_t * buf, off_t current, long lines, off_t upto)
587 if (upto != 0)
588 return (off_t) edit_buffer_count_lines (buf, current, upto);
590 lines = max (lines, 0);
592 while (lines-- != 0)
594 long next;
596 next = edit_buffer_get_eol (buf, current) + 1;
597 if (next > buf->size)
598 break;
599 current = next;
602 return current;
605 /* --------------------------------------------------------------------------------------------- */
607 * Calculate backward offset with specified number of lines.
609 * @param buf editor buffer
610 * @param current current offset
611 * @param lines number of lines to move backward
613 * @return backward offset with specified number of lines.
616 off_t
617 edit_buffer_move_backward (const edit_buffer_t * buf, off_t current, long lines)
619 lines = max (lines, 0);
620 current = edit_buffer_get_bol (buf, current);
622 while (lines-- != 0 && current != 0)
623 current = edit_buffer_get_bol (buf, current - 1);
625 return current;
628 /* --------------------------------------------------------------------------------------------- */
630 * Load file into editor buffer
632 * @param buf pointer to editor buffer
633 * @param fd file descriptor
634 * @param size file size
636 * @return number of read bytes
639 off_t
640 edit_buffer_read_file (edit_buffer_t * buf, int fd, off_t size)
642 off_t ret = 0;
643 off_t i, j;
644 off_t data_size;
645 void *b;
647 buf->lines = 0;
648 buf->curs2 = size;
649 i = buf->curs2 >> S_EDIT_BUF_SIZE;
651 /* fill last part of b2 */
652 data_size = buf->curs2 & M_EDIT_BUF_SIZE;
653 if (data_size != 0)
655 b = g_malloc0 (EDIT_BUF_SIZE);
656 g_ptr_array_add (buf->b2, b);
657 b = (char *) b + EDIT_BUF_SIZE - data_size;
658 ret = mc_read (fd, b, data_size);
660 /* count lines */
661 for (j = 0; j < ret; j++)
662 if (*((char *) b + j) == '\n')
663 buf->lines++;
665 if (ret < 0 || ret != data_size)
666 return ret;
669 /* fulfill other parts of b2 from end to begin */
670 data_size = EDIT_BUF_SIZE;
671 for (--i; i >= 0; i--)
673 off_t sz;
675 b = g_malloc0 (data_size);
676 g_ptr_array_add (buf->b2, b);
677 sz = mc_read (fd, b, data_size);
678 if (sz >= 0)
679 ret += sz;
681 /* count lines */
682 for (j = 0; j < sz; j++)
683 if (*((char *) b + j) == '\n')
684 buf->lines++;
686 if (sz != data_size)
687 break;
690 /* reverse buffer */
691 for (i = 0; i < (off_t) buf->b2->len / 2; i++)
693 void **b1, **b2;
695 b1 = &g_ptr_array_index (buf->b2, i);
696 b2 = &g_ptr_array_index (buf->b2, buf->b2->len - 1 - i);
698 b = *b1;
699 *b1 = *b2;
700 *b2 = b;
703 return ret;
706 /* --------------------------------------------------------------------------------------------- */
708 * Write editor buffer content to file
710 * @param buf pointer to editor buffer
711 * @param fd file descriptor
713 * @return number of written bytes
716 off_t
717 edit_buffer_write_file (edit_buffer_t * buf, int fd)
719 off_t ret = 0;
720 off_t i;
721 off_t data_size, sz;
722 void *b;
724 /* write all fulfilled parts of b1 from begin to end */
725 if (buf->b1->len != 0)
727 data_size = EDIT_BUF_SIZE;
728 for (i = 0; i < (off_t) buf->b1->len - 1; i++)
730 b = g_ptr_array_index (buf->b1, i);
731 sz = mc_write (fd, b, data_size);
732 if (sz >= 0)
733 ret += sz;
734 else if (i == 0)
735 ret = sz;
736 if (sz != data_size)
737 return ret;
740 /* write last partially filled part of b1 */
741 data_size = ((buf->curs1 - 1) & M_EDIT_BUF_SIZE) + 1;
742 b = g_ptr_array_index (buf->b1, i);
743 sz = mc_write (fd, b, data_size);
744 if (sz >= 0)
745 ret += sz;
746 if (sz != data_size)
747 return ret;
750 /* write b2 from end to begin, if b2 contains some data */
751 if (buf->b2->len != 0)
753 /* write last partially filled part of b2 */
754 i = buf->b2->len - 1;
755 b = g_ptr_array_index (buf->b2, i);
756 data_size = ((buf->curs2 - 1) & M_EDIT_BUF_SIZE) + 1;
757 sz = mc_write (fd, (char *) b + EDIT_BUF_SIZE - data_size, data_size);
758 if (sz >= 0)
759 ret += sz;
761 if (sz == data_size)
763 /* write other fulfilled parts of b2 from end to begin */
764 data_size = EDIT_BUF_SIZE;
765 while (--i >= 0)
767 b = g_ptr_array_index (buf->b2, i);
768 sz = mc_write (fd, b, data_size);
769 if (sz >= 0)
770 ret += sz;
771 if (sz != data_size)
772 break;
777 return ret;
780 /* --------------------------------------------------------------------------------------------- */