2 Editor text keep buffer.
5 The Free Software Foundation, Inc.
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/>.
27 * \brief Source: editor text keep buffer.
28 * \author Andrew Borodin
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 /* --------------------------------------------------------------------------------------------- */
48 * here's a quick sketch of the layout: (don't run this through indent.)
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 * ______________________________________|______________________________________
54 * ... | b2[2] | b2[1] | b2[0] | b1[0] | b1[1] | b1[2] | ...
55 * |-> |-> |-> |-> |-> |-> |
57 * _<------------------------->|<----------------->_
63 * file end|||file beginning
72 * This is called a "gab buffer".
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
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.
114 edit_buffer_get_byte_ptr (const edit_buffer_t
* buf
, off_t byte_index
)
118 if (byte_index
>= (buf
->curs1
+ buf
->curs2
) || byte_index
< 0)
121 if (byte_index
>= buf
->curs1
)
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
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);
156 /* --------------------------------------------------------------------------------------------- */
158 * Clean editor buffers.
160 * @param buf pointer to editor buffer
164 edit_buffer_clean (edit_buffer_t
* buf
)
168 g_ptr_array_foreach (buf
->b1
, (GFunc
) g_free
, NULL
);
169 g_ptr_array_free (buf
->b1
, TRUE
);
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
)
194 p
= edit_buffer_get_byte_ptr (buf
, byte_index
);
196 return (p
!= NULL
) ? *(unsigned char *) p
: '\n';
199 /* --------------------------------------------------------------------------------------------- */
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
)
220 gchar
*next_ch
= NULL
;
222 if (byte_index
>= (buf
->curs1
+ buf
->curs2
) || byte_index
< 0)
228 str
= edit_buffer_get_byte_ptr (buf
, byte_index
);
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 */
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
);
245 res
= g_utf8_get_char_validated (utf8_buf
, -1);
248 if (res
== (gunichar
) (-2) || res
== (gunichar
) (-1))
256 /* Calculate UTF-8 char width */
257 next_ch
= g_utf8_next_char (str
);
259 *char_width
= next_ch
- str
;
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
)
287 gchar utf8_buf
[3 * UTF8_CHAR_LEN
+ 1];
289 gchar
*cursor_buf_ptr
;
292 if (byte_index
> (buf
->curs1
+ buf
->curs2
) || byte_index
<= 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
));
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
)
308 return *(cursor_buf_ptr
- 1);
311 res
= g_utf8_get_char_validated (str
, -1);
312 if (res
== (gunichar
) (-2) || res
== (gunichar
) (-1))
315 return *(cursor_buf_ptr
- 1);
318 *char_width
= cursor_buf_ptr
- str
;
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
335 edit_buffer_count_lines (const edit_buffer_t
* buf
, off_t first
, off_t last
)
339 first
= max (first
, 0);
340 last
= min (last
, buf
->size
);
343 if (edit_buffer_get_byte (buf
, first
++) == '\n')
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
360 edit_buffer_get_bol (const edit_buffer_t
* buf
, off_t current
)
365 for (; edit_buffer_get_byte (buf
, current
- 1) != '\n'; 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
382 edit_buffer_get_eol (const edit_buffer_t
* buf
, off_t current
)
384 if (current
>= buf
->size
)
387 for (; edit_buffer_get_byte (buf
, current
) != '\n'; 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
402 * @return word as newly allocated object
406 edit_buffer_get_word_from_pos (const edit_buffer_t
* buf
, off_t start_pos
, off_t
* start
,
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')
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'));
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
449 edit_buffer_insert (edit_buffer_t
* buf
, int c
)
454 i
= buf
->curs1
& M_EDIT_BUF_SIZE
;
456 /* add a new buffer if we've reached the end of the last one */
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 */
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
478 edit_buffer_insert_ahead (edit_buffer_t
* buf
, int c
)
483 i
= buf
->curs2
& M_EDIT_BUF_SIZE
;
485 /* add a new buffer if we've reached the end of the last one */
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 */
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
)
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
);
522 i
= buf
->b2
->len
- 1;
523 b
= g_ptr_array_index (buf
->b2
, i
);
524 g_ptr_array_remove_index (buf
->b2
, i
);
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
)
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
);
558 i
= buf
->b1
->len
- 1;
559 b
= g_ptr_array_index (buf
->b1
, i
);
560 g_ptr_array_remove_index (buf
->b1
, i
);
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
585 edit_buffer_move_forward (const edit_buffer_t
* buf
, off_t current
, long lines
, off_t upto
)
588 return (off_t
) edit_buffer_count_lines (buf
, current
, upto
);
590 lines
= max (lines
, 0);
596 next
= edit_buffer_get_eol (buf
, current
) + 1;
597 if (next
> buf
->size
)
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.
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);
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
640 edit_buffer_read_file (edit_buffer_t
* buf
, int fd
, off_t size
)
649 i
= buf
->curs2
>> S_EDIT_BUF_SIZE
;
651 /* fill last part of b2 */
652 data_size
= buf
->curs2
& M_EDIT_BUF_SIZE
;
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
);
661 for (j
= 0; j
< ret
; j
++)
662 if (*((char *) b
+ j
) == '\n')
665 if (ret
< 0 || ret
!= data_size
)
669 /* fulfill other parts of b2 from end to begin */
670 data_size
= EDIT_BUF_SIZE
;
671 for (--i
; i
>= 0; i
--)
675 b
= g_malloc0 (data_size
);
676 g_ptr_array_add (buf
->b2
, b
);
677 sz
= mc_read (fd
, b
, data_size
);
682 for (j
= 0; j
< sz
; j
++)
683 if (*((char *) b
+ j
) == '\n')
691 for (i
= 0; i
< (off_t
) buf
->b2
->len
/ 2; i
++)
695 b1
= &g_ptr_array_index (buf
->b2
, i
);
696 b2
= &g_ptr_array_index (buf
->b2
, buf
->b2
->len
- 1 - i
);
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
717 edit_buffer_write_file (edit_buffer_t
* buf
, int fd
)
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
);
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
);
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
);
763 /* write other fulfilled parts of b2 from end to begin */
764 data_size
= EDIT_BUF_SIZE
;
767 b
= g_ptr_array_index (buf
->b2
, i
);
768 sz
= mc_write (fd
, b
, data_size
);
780 /* --------------------------------------------------------------------------------------------- */