Merge from vendor branch NTPD:
[dragonfly.git] / contrib / libio / editbuf.cc
1 /* This is part of libio/iostream, providing -*- C++ -*- input/output.
2 Copyright (C) 1993 Free Software Foundation
3
4 This file is part of the GNU IO Library.  This library is free
5 software; you can redistribute it and/or modify it under the
6 terms of the GNU General Public License as published by the
7 Free Software Foundation; either version 2, or (at your option)
8 any later version.
9
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this library; see the file COPYING.  If not, write to the Free
17 Software Foundation, 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18
19 As a special exception, if you link this library with files
20 compiled with a GNU compiler to produce an executable, this does not cause
21 the resulting executable to be covered by the GNU General Public License.
22 This exception does not however invalidate any other reasons why
23 the executable file might be covered by the GNU General Public License.
24
25 Written by Per Bothner (bothner@cygnus.com). */
26
27 #ifdef __GNUG__
28 #pragma implementation
29 #endif
30 #include "libioP.h"
31 #include "editbuf.h"
32 #include <stddef.h>
33 #include <stdlib.h>
34
35 /* NOTE: Some of the code here is taken from GNU emacs */
36 /* Hence this file falls under the GNU License! */
37
38 // Invariants for edit_streambuf:
39 // An edit_streambuf is associated with a specific edit_string,
40 // which again is a sub-string of a specific edit_buffer.
41 // An edit_streambuf is always in either get mode or put mode, never both.
42 // In get mode, gptr() is the current position,
43 // and pbase(), pptr(), and epptr() are all NULL.
44 // In put mode, pptr() is the current position,
45 // and eback(), gptr(), and egptr() are all NULL.
46 // Any edit_streambuf that is actively doing insertion (as opposed to
47 // replacing) // must have its pptr() pointing to the start of the gap.
48 // Only one edit_streambuf can be actively inserting into a specific
49 // edit_buffer; the edit_buffer's _writer field points to that edit_streambuf.
50 // That edit_streambuf "owns" the gap, and the actual start of the
51 // gap is the pptr() of the edit_streambuf; the edit_buffer::_gap_start pointer
52 // will only be updated on an edit_streambuf::overflow().
53
54 int edit_streambuf::truncate()
55 {
56     str->buffer->delete_range(str->buffer->tell((buf_char*)pptr()),
57                               str->buffer->tell(str->end));
58     return 0;
59 }
60
61 #ifdef OLD_STDIO
62 inline void  disconnect_gap_from_file(edit_buffer* buffer, FILE* fp)
63 {
64     if (buffer->gap_start_ptr != &fp->__bufp)
65         return;
66     buffer->gap_start_normal = fp->__bufp;
67     buffer->gap_start_ptr = &buffer->gap_start_normal;
68 }
69 #endif
70
71 void edit_streambuf::flush_to_buffer(edit_buffer* buffer)
72 {
73     if (pptr() > buffer->_gap_start && pptr() < buffer->gap_end())
74         buffer->_gap_start = pptr();
75 }
76
77 void edit_streambuf::disconnect_gap_from_file(edit_buffer* buffer)
78 {
79     if (buffer->_writer != this) return;
80     flush_to_buffer(buffer);
81     setp(pptr(),pptr());
82     buffer->_writer = NULL;    
83 }
84
85 buf_index edit_buffer::tell(buf_char *ptr)
86 {
87     if (ptr <= gap_start())
88         return ptr - data;
89     else
90         return ptr - gap_end() + size1();
91 }
92
93 #if 0
94 buf_index buf_cookie::tell()
95 {
96     return str->buffer->tell(file->__bufp);
97 }
98 #endif
99
100 buf_index edit_buffer::tell(edit_mark*mark)
101 {
102     return tell(data + mark->index_in_buffer(this));
103 }
104
105 // adjust the position of the gap
106
107 void edit_buffer::move_gap(buf_offset pos)
108 {
109   if (pos < size1())
110     gap_left (pos);
111   else if (pos > size1())
112     gap_right (pos);
113 }
114
115 void edit_buffer::gap_left (int pos)
116 {
117   register buf_char *to, *from;
118   register int i;
119   int new_s1;
120
121   i = size1();
122   from = gap_start();
123   to = from + gap_size();
124   new_s1 = size1();
125
126   /* Now copy the characters.  To move the gap down,
127      copy characters up.  */
128
129   for (;;)
130     {
131       /* I gets number of characters left to copy.  */
132       i = new_s1 - pos;
133       if (i == 0)
134         break;
135 #if 0
136       /* If a quit is requested, stop copying now.
137          Change POS to be where we have actually moved the gap to.  */
138       if (QUITP)
139         {
140           pos = new_s1;
141           break;
142         }
143 #endif
144       /* Move at most 32000 chars before checking again for a quit.  */
145       if (i > 32000)
146         i = 32000;
147       new_s1 -= i;
148       while (--i >= 0)
149         *--to = *--from;
150     }
151
152   /* Adjust markers, and buffer data structure, to put the gap at POS.
153      POS is where the loop above stopped, which may be what was specified
154      or may be where a quit was detected.  */
155   adjust_markers (pos << 1, size1() << 1, gap_size(), data);
156 #ifndef OLD_STDIO
157   _gap_start = data + pos;
158 #else
159   if (gap_start_ptr == &gap_start_normal)
160         gap_start_normal = data + pos;
161 #endif
162   __gap_end_pos = to - data;
163 /*  QUIT;*/
164 }
165
166 void edit_buffer::gap_right (int pos)
167 {
168   register buf_char *to, *from;
169   register int i;
170   int new_s1;
171
172   i = size1();
173   to = gap_start();
174   from = i + gap_end();
175   new_s1 = i;
176
177   /* Now copy the characters.  To move the gap up,
178      copy characters down.  */
179
180   while (1)
181     {
182       /* I gets number of characters left to copy.  */
183       i = pos - new_s1;
184       if (i == 0)
185         break;
186 #if 0
187       /* If a quit is requested, stop copying now.
188          Change POS to be where we have actually moved the gap to.  */
189       if (QUITP)
190         {
191           pos = new_s1;
192           break;
193         }
194 #endif
195       /* Move at most 32000 chars before checking again for a quit.  */
196       if (i > 32000)
197         i = 32000;
198       new_s1 += i;
199       while (--i >= 0)
200         *to++ = *from++;
201     }
202
203   adjust_markers ((size1() + gap_size()) << 1, (pos + gap_size()) << 1,
204         - gap_size(), data);
205 #ifndef OLD_STDIO
206   _gap_start = data+pos;
207 #else
208   if (gap_start_ptr == &gap_start_normal)
209         gap_start_normal = data + pos;
210 #endif
211   __gap_end_pos = from - data;
212 /*  QUIT;*/
213 }
214
215 /* make sure that the gap in the current buffer is at least k
216    characters wide */
217
218 void edit_buffer::make_gap(buf_offset k)
219 {
220   register buf_char *p1, *p2, *lim;
221   buf_char *old_data = data;
222   int s1 = size1();
223
224   if (gap_size() >= k)
225     return;
226
227   /* Get more than just enough */
228   if (buf_size > 1000) k += 2000;
229   else k += /*200;*/ 20; // for testing!
230
231   p1 = (buf_char *) realloc (data, s1 + size2() + k);
232   if (p1 == 0)
233     abort(); /*memory_full ();*/
234
235   k -= gap_size();                      /* Amount of increase.  */
236
237   /* Record new location of text */
238   data = p1;
239
240   /* Transfer the new free space from the end to the gap
241      by shifting the second segment upward */
242   p2 = data + buf_size;
243   p1 = p2 + k;
244   lim = p2 - size2();
245   while (lim < p2)
246     *--p1 = *--p2;
247
248   /* Finish updating text location data */
249   __gap_end_pos += k;
250
251 #ifndef OLD_STDIO
252   _gap_start = data + s1;
253 #else
254   if (gap_start_ptr == &gap_start_normal)
255         gap_start_normal = data + s1;
256 #endif
257
258   /* adjust markers */
259   adjust_markers (s1 << 1, (buf_size << 1) + 1, k, old_data);
260   buf_size += k;
261 }
262
263 /* Add `amount' to the position of every marker in the current buffer
264    whose current position is between `from' (exclusive) and `to' (inclusive).
265    Also, any markers past the outside of that interval, in the direction
266    of adjustment, are first moved back to the near end of the interval
267    and then adjusted by `amount'.  */
268
269 void edit_buffer::adjust_markers(register mark_pointer low,
270                                  register mark_pointer high,
271                                  int amount, buf_char *old_data)
272 {
273   register struct edit_mark *m;
274   register mark_pointer mpos;
275   /* convert to mark_pointer */
276   amount <<= 1;
277
278   if (_writer)
279       _writer->disconnect_gap_from_file(this);
280
281   for (m = mark_list(); m != NULL; m = m->chain)
282     {
283       mpos = m->_pos;
284       if (amount > 0)
285         {
286           if (mpos > high && mpos < high + amount)
287             mpos = high + amount;
288         }
289       else
290         {
291           if (mpos > low + amount && mpos <= low)
292             mpos = low + amount;
293         }
294       if (mpos > low && mpos <= high)
295         mpos += amount;
296       m->_pos = mpos;
297     }
298
299     // Now adjust files
300     edit_streambuf *file;
301
302     for (file = files; file != NULL; file = file->next) {
303         mpos = file->current() - old_data;
304         if (amount > 0)
305         {
306           if (mpos > high && mpos < high + amount)
307             mpos = high + amount;
308         }
309         else
310         {
311           if (mpos > low + amount && mpos <= low)
312             mpos = low + amount;
313         }
314         if (mpos > low && mpos <= high)
315             mpos += amount;
316         char* new_pos = data + mpos;
317         file->set_current(new_pos, file->is_reading());
318     }
319 }
320
321 #if 0
322 stdio_
323    __off == index at start of buffer (need only be valid after seek ? )
324    __buf ==
325
326 if read/read_delete/overwrite mode:
327      __endp <= min(*gap_start_ptr, edit_string->end->ptr(buffer))
328
329 if inserting:
330      must have *gap_start_ptr == __bufp && *gap_start_ptr+gap == __endp
331      file->edit_string->end->ptr(buffer) == *gap_start_ptr+end
332 if write_mode:
333      if before gap
334 #endif
335
336 int edit_streambuf::underflow()
337 {
338     if (!(_mode & ios::in))
339         return EOF;
340     struct edit_buffer *buffer = str->buffer;
341     if (!is_reading()) { // Must switch from put to get mode.
342         disconnect_gap_from_file(buffer);
343         set_current(pptr(), 1);
344     }
345     buf_char *str_end = str->end->ptr(buffer);
346   retry:
347     if (gptr() < egptr()) {
348         return *gptr();
349     }
350     if ((buf_char*)gptr() == str_end)
351         return EOF;
352     if (str_end <= buffer->gap_start()) {
353         setg(eback(), gptr(), str_end);
354         goto retry;
355     }
356     if (gptr() < buffer->gap_start()) {
357         setg(eback(), gptr(), buffer->gap_start());
358         goto retry;
359     }
360     if (gptr() == buffer->gap_start()) {
361         disconnect_gap_from_file(buffer);
362 //      fp->__offset += fp->__bufp - fp->__buffer;
363         setg(buffer->gap_end(), buffer->gap_end(), str_end);
364     }
365     else
366         setg(eback(), gptr(), str_end);
367     goto retry;
368 }
369
370 int edit_streambuf::overflow(int ch)
371 {
372     if (_mode == ios::in)
373         return EOF;
374     struct edit_buffer *buffer = str->buffer;
375     flush_to_buffer(buffer);
376     if (ch == EOF)
377         return 0;
378     if (is_reading()) { // Must switch from get to put mode.
379         set_current(gptr(), 0);
380     }
381     buf_char *str_end = str->end->ptr(buffer);
382   retry:
383     if (pptr() < epptr()) {
384         *pptr() = ch;
385         pbump(1);
386         return (unsigned char)ch;
387     }
388     if ((buf_char*)pptr() == str_end || inserting()) {
389         /* insert instead */
390         if (buffer->_writer)
391             buffer->_writer->flush_to_buffer(); // Redundant?
392         buffer->_writer = NULL;
393         if  (pptr() >= buffer->gap_end())
394             buffer->move_gap(pptr() - buffer->gap_size());
395         else
396             buffer->move_gap(pptr());
397         buffer->make_gap(1);
398         setp(buffer->gap_start(), buffer->gap_end());
399         buffer->_writer = this;
400         *pptr() = ch;
401         pbump(1);
402         return (unsigned char)ch;
403     }
404     if (str_end <= buffer->gap_start()) {
405         // Entire string is left of gap.
406         setp(pptr(), str_end);
407     }
408     else if (pptr() < buffer->gap_start()) {
409         // Current pos is left of gap.
410         setp(pptr(), buffer->gap_start());
411         goto retry;
412     }
413     else if (pptr() == buffer->gap_start()) {
414         // Current pos is at start of gap; move to end of gap.
415 //      disconnect_gap_from_file(buffer);
416         setp(buffer->gap_end(), str_end);
417 //      __offset += __bufp - __buffer;
418     }
419     else {
420         // Otherwise, current pos is right of gap.
421         setp(pptr(), str_end);
422     }
423     goto retry;
424 }
425
426 void edit_streambuf::set_current(char *new_pos, int reading)
427 {
428     if (reading) {
429         setg(new_pos, new_pos, new_pos);
430         setp(NULL, NULL);
431     }
432     else {
433         setg(NULL, NULL, NULL);
434         setp(new_pos, new_pos);
435     }
436 }
437
438 // Called by fseek(fp, pos, whence) if fp is bound to a edit_buffer.
439
440 streampos edit_streambuf::seekoff(streamoff offset, _seek_dir dir,
441                                   int /* =ios::in|ios::out*/)
442 {
443     struct edit_buffer *buffer = str->buffer;
444     disconnect_gap_from_file(buffer);
445     buf_index cur_pos = buffer->tell((buf_char*)current());;
446     buf_index start_pos = buffer->tell(str->start);
447     buf_index end_pos = buffer->tell(str->end);
448     switch (dir) {
449       case ios::beg:
450         offset += start_pos;
451         break;
452       case ios::cur:
453         offset += cur_pos;
454         break;
455       case ios::end:
456         offset += end_pos;
457         break;
458     }
459     if (offset < start_pos || offset > end_pos)
460         return EOF;
461     buf_char *new_pos = buffer->data + offset;
462     buf_char* gap_start = buffer->gap_start();
463     if (new_pos > gap_start) {
464         buf_char* gap_end = buffer->gap_end();
465         new_pos += gap_end - gap_start;
466         if (new_pos >= buffer->data + buffer->buf_size) abort(); // Paranoia.
467     }
468     set_current(new_pos, is_reading());
469     return EOF;
470 }
471
472 #if 0
473 int buf_seek(void *arg_cookie, fpos_t * pos, int whence)
474 {
475     struct buf_cookie *cookie = arg_cookie;
476     FILE *file = cookie->file;
477     struct edit_buffer *buffer = cookie->str->buffer;
478     buf_char *str_start = cookie->str->start->ptr(buffer);
479     disconnect_gap_from_file(buffer, cookie->file);
480     fpos_t cur_pos, new_pos;
481     if (file->__bufp <= *buffer->gap_start_ptr
482         || str_start >= buffer->__gap_end)
483         cur_pos = str_start - file->__bufp;
484     else
485         cur_pos =
486             (*buffer->gap_start_ptr - str_start) + (file->__bufp - __gap_end);
487     end_pos = ...;
488     switch (whence) {
489       case SEEK_SET:
490         new_pos = *pos;
491         break;
492       case SEEK_CUR:
493         new_pos = cur_pos + *pos;
494         break;
495       case SEEK_END:
496         new_pos = end_pos + *pos;
497         break;
498     }
499     if (new_pos > end_pos) {
500         seek to end_pos;
501         insert_nulls(new_pos - end_pos);
502         return;
503     }
504     if (str_start + new_pos <= *gap_start_ptr &* *gap_start_ptr < end) {
505         __buffer = str_start;
506         __off = 0;
507         __bufp = str_start + new_pos;
508         file->__get_limit =
509             *buffer->gap_start_ptr; /* what if gap_start_ptr == &bufp ??? */
510     } else if () {
511         
512     }
513     *pos = new_pos;
514 }
515 #endif
516
517 /* Delete characters from `from' up to (but not incl) `to' */
518
519 void edit_buffer::delete_range (buf_index from, buf_index to)
520 {
521   register int numdel;
522
523   if ((numdel = to - from) <= 0)
524     return;
525
526   /* Make sure the gap is somewhere in or next to what we are deleting */
527   if (from > size1())
528     gap_right (from);
529   if (to < size1())
530     gap_left (to);
531
532   /* Relocate all markers pointing into the new, larger gap
533      to point at the end of the text before the gap.  */
534   adjust_markers ((to + gap_size()) << 1, (to + gap_size()) << 1,
535         - numdel - gap_size(), data);
536
537    __gap_end_pos = to + gap_size();
538   _gap_start = data + from;
539 }
540
541 void edit_buffer::delete_range(struct edit_mark *start, struct edit_mark *end)
542 {
543     delete_range(tell(start), tell(end));
544 }
545
546 void buf_delete_chars(struct edit_buffer *, struct edit_mark *, size_t)
547 {
548  abort();
549 }
550
551 edit_streambuf::edit_streambuf(edit_string* bstr, int mode)
552 {
553     _mode = mode;
554     str = bstr;
555     edit_buffer* buffer = bstr->buffer;
556     next = buffer->files;
557     buffer->files = this;
558     char* buf_ptr = bstr->start->ptr(buffer);
559     _inserting = 0;
560 //    setb(buf_ptr, buf_ptr, 0);
561     set_current(buf_ptr, !(mode & ios::out+ios::trunc+ios::app));
562     if (_mode & ios::trunc)
563         truncate();
564     if (_mode & ios::ate)
565         seekoff(0, ios::end);
566 }
567
568 // Called by fclose(fp) if fp is bound to a edit_buffer.
569
570 #if 0
571 static int buf_close(void *arg)
572 {
573     register struct buf_cookie *cookie = arg;
574     struct edit_buffer *buffer = cookie->str->buffer;
575     struct buf_cookie **ptr;
576     for (ptr = &buffer->files; *ptr != cookie; ptr = &(*ptr)->next) ;
577     *ptr = cookie->next;
578     disconnect_gap_from_file(buffer, cookie->file);
579     free (cookie);
580     return 0;
581 }
582 #endif
583
584 edit_streambuf::~edit_streambuf()
585 {
586     if (_mode == ios::out)
587         truncate();
588     // Unlink this from list of files associated with bstr->buffer.
589     edit_streambuf **ptr = &str->buffer->files;
590     for (; *ptr != this; ptr = &(*ptr)->next) { }
591     *ptr = next;
592
593     disconnect_gap_from_file(str->buffer);
594 }
595
596 edit_buffer::edit_buffer()
597 {
598     buf_size = /*200;*/ 15; /* for testing! */
599     data = (buf_char*)malloc(buf_size);
600     files = NULL;
601 #ifndef OLD_STDIO
602     _gap_start = data;
603     _writer = NULL;
604 #else
605     gap_start_normal = data;
606     gap_start_ptr = &gap_start_normal;
607 #endif
608     __gap_end_pos = buf_size;
609     start_mark.chain = &end_mark;
610     start_mark._pos = 0;
611     end_mark.chain = NULL;
612     end_mark._pos = 2 * buf_size + 1;
613 }
614
615 // Allocate a new mark, which is adjusted by 'delta' bytes from 'this'.
616 // Restrict new mark to lie within 'str'.
617
618 edit_mark::edit_mark(struct edit_string *str, long delta)
619 {
620     struct edit_buffer *buf = str->buffer;
621     chain = buf->start_mark.chain;
622     buf->start_mark.chain = this;
623     mark_pointer size1 = buf->size1() << 1;
624     int gap_size = buf->gap_size() << 1;
625     delta <<= 1;
626
627     // check if new and old marks are opposite sides of gap
628     if (_pos <= size1 && _pos + delta > size1)
629         delta += gap_size;
630     else if (_pos >= size1 + gap_size && _pos + delta < size1 + gap_size)
631         delta -= gap_size;
632
633     _pos = _pos + delta;
634     if (_pos < str->start->_pos & ~1)
635         _pos = (str->start->_pos & ~ 1) + (_pos & 1);
636     else if (_pos >= str->end->_pos)
637         _pos = (str->end->_pos & ~ 1) + (_pos & 1);
638 }
639
640 // A (slow) way to find the buffer a mark belongs to.
641
642 edit_buffer * edit_mark::buffer()
643 {
644     struct edit_mark *mark;
645     for (mark = this; mark->chain != NULL; mark = mark->chain) ;
646     // Assume that the last mark on the chain is the end_mark.
647     return (edit_buffer *)((char*)mark - offsetof(edit_buffer, end_mark));
648 }
649
650 edit_mark::~edit_mark()
651 {
652     // Must unlink mark from chain of owning buffer
653     struct edit_buffer *buf = buffer();
654     if (this == &buf->start_mark || this == &buf->end_mark) abort();
655     edit_mark **ptr;
656     for (ptr = &buf->start_mark.chain; *ptr != this; ptr = &(*ptr)->chain) ;
657     *ptr = this->chain;
658 }
659
660 int edit_string::length() const
661 {
662     ptrdiff_t delta = end->ptr(buffer) - start->ptr(buffer);
663     if (end->ptr(buffer) <= buffer->gap_start() ||
664         start->ptr(buffer) >= buffer->gap_end())
665         return delta;
666     return delta - buffer->gap_size();
667 }
668
669 buf_char * edit_string::copy_bytes(int *lenp) const
670 {
671     char *new_str;
672     int len1, len2;
673     buf_char *start1, *start2;
674     start1 = start->ptr(buffer);
675     if (end->ptr(buffer) <= buffer->gap_start()
676         || start->ptr(buffer) >= buffer->gap_end()) {
677         len1 = end->ptr(buffer) - start1;
678         len2 = 0;
679         start2 = NULL; // To avoid a warning from g++.
680     }
681     else {
682         len1 = buffer->gap_start() - start1;
683         start2 = buffer->gap_end();
684         len2 = end->ptr(buffer) - start2;
685     }
686     new_str = (char*)malloc(len1 + len2 + 1);
687     memcpy(new_str, start1, len1);
688     if (len2 > 0) memcpy(new_str + len1, start2, len2);
689     new_str[len1+len2] = '\0';
690     *lenp = len1+len2;
691     return new_str;
692 }
693
694 // Replace the buf_chars in 'this' with ones from 'src'.
695 // Equivalent to deleting this, then inserting src, except tries
696 // to leave marks in place: Marks whose offset from the start
697 // of 'this' is less than 'src->length()' will still have the
698 // same offset in 'this' when done.
699
700 void edit_string::assign(struct edit_string *src)
701 {
702     edit_streambuf dst_file(this, ios::out);
703     if (buffer == src->buffer /*&& ???*/) { /* overly conservative */
704         int src_len;
705         buf_char *new_str;
706         new_str = src->copy_bytes(&src_len);
707         dst_file.sputn(new_str, src_len);
708         free (new_str);
709     } else {
710         edit_streambuf src_file(src, ios::in);
711         for ( ; ; ) {
712             int ch = src_file.sbumpc();
713             if (ch == EOF) break;
714             dst_file.sputc(ch);
715         }
716     }
717 }