NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/alt/sources/2537/buffer.c

C/C++ Source or Header | 1992-11-17 | 12.2 KB | 705 lines

/*
 * Copyright 1992 Peter da Silva
 *
 * Permission to use, copy, modify, and distribute this
 * software and its documentation for any purpose and without
 * fee is hereby granted, provided that the above copyright
 * notice appear in all copies.  The author[s] make no representations
 * about the suitability of this software for any purpose.
 * It is provided "as is" without express or implied warranty.
 */

/* Code to handle an editor buffer */
#include <stdio.h>

char *malloc();

#define new(t,n) ((t *)malloc(n * sizeof (t)))

#define MAXBUFS 32
#define MAXMARKS 32

typedef struct {
    int body_length;    /* number of bytes of text in body */
    int text_length;    /* number of bytes of text in body */
    int gap;        /* start of gap */
    int gapsize;        /* length of gap */
    int mark[MAXMARKS];
    int himark;
    char *body;
} buffer;

static buffer *buftab[MAXBUFS];
static int hibuffer;

static char *lastroutine = "NONE";

#define mark2index(m) ((m)-1)
#define index2mark(i) ((i)+1)

/* checkbuf(bufptr, buffer, name)
 *
 * Checks the integrity of a buffer structure. Called from each routine
 * that resolves a buffer into a pointer to make sure the pointer is valid
 * and the buffer hasn't been stepped on.
 */
checkbuf(b,i,n)
buffer *b;
char *n;
{
    if(b->body_length != b->text_length+b->gapsize) {
        fprintf(stderr, "buffer(%d): Inconsistent sizes %d!=%d+%d\n",
            i, b->body_length, b->text_length, b->gapsize);
    } else if(b->gap < 0 || b->gap > b->text_length) {
        fprintf(stderr, "buffer(%d): Gap out of range %d\n",
            i, b->gap);
    } else if(b->himark < 0 || b->himark > MAXMARKS) {
        fprintf(stderr, "buffer(%d): Mark count out of range %d\n",
            i, b->himark);
    } else {
#ifdef TEST
        int index;

        for(index = 0; index < b->himark; index++) {
            if(b->mark[index] < -1
            || b->mark[index] > b->text_length) {
                fprintf(stderr,
                    "buffer(%d): mark(%d) out of range %d\n",
                    i, index2mark(index), b->mark[index]);
                break;
            }
        }
        if(index == b->himark) {
            lastroutine = n;
            return;
        }
#else
        lastroutine = n;
        return;
#endif
    }
    fprintf(stderr, "Error detected in %s called after %s\n",
        n, lastroutine);
    exit(-1);
}

#define CHECK(b,i,n,f) \
    buffer_error = invalid_buffer; \
    if(i >= 0 && i < hibuffer) { \
        b = buftab[i]; \
        if(!b) return f; \
    } else return f; \
    checkbuf(b,i,n)

#define CHECKMARK(b,j,v) \
    if(j < -1 || j > b->himark) { \
        buffer_error = mark_range; \
        return v; \
    } else if(j > 0 && b->mark[mark2index(j)] == -1) { \
        buffer_error = mark_unset; \
        return v; \
    }

static char *invalid_buffer = "Invalid buffer ID";
static char *found_eof = "Beyond end of buffer";
static char *found_bof = "Beyond beginning of buffer";
static char *mark_range = "Mark out of range";
static char *mark_unset = "Mark not set";

char *buffer_error;

int new_buffer()
{
    int i, index;

    for(i = 0; i < hibuffer; i++)
        if(!buftab[i])
            break;
    if(i == hibuffer) {
        if(hibuffer == MAXBUFS) {
            buffer_error = "No more buffers";
            return -1;
        }
        hibuffer++;
    }
    buftab[i] = new(buffer, 1);
    if(!buftab[i]) {
        buffer_error = "Memory allocation failure";
        return -1;
    }
    buftab[i] -> body_length = 0;
    buftab[i] -> text_length = 0;
    buftab[i] -> gapsize = 0;
    buftab[i] -> gap = 0;
    for(index = 0; index < MAXMARKS; index++)
        buftab[i] -> mark[index] = -1;
    buftab[i] -> himark = 0;
    buftab[i] -> body = (char *)0;

    return i;
}

delete_buffer(i)
int i;
{
    buffer *b;

    CHECK(b,i,"delete_buffer",-1);

    if(b->body) free(b->body);

    free(b);

    buftab[i] = 0;

    return 0;
}

int new_mark(i, off)
int i, off;
{
    int index;
    buffer *b;

    CHECK(b,i,"new_mark",-1);

    if(off < 0 || off > b->text_length) {
        buffer_error = mark_range;
        return -1;
    }

    for(index = 0; index < b->himark; index++)
        if(b->mark[index] == -1)
            break;
    if(index == b->himark) {
        if(b->himark == MAXBUFS) {
            buffer_error = "No more marks";
            return -1;
        }
        b->himark++;
    }
    b->mark[index] = off;

    return index2mark(index);
}

int copy_mark(i, j)
int i, j;
{
    int off;

    off = locate_mark(i, j);

    if(off == -1)
        return -1;
    else
        return new_mark(i, off);
}

delete_mark(i, j)
int i;
int j;
{
    buffer *b;

    CHECK(b,i,"delete_mark",-1);
    CHECKMARK(b,j,-1);

    if(j <= 0) {
        buffer_error = "Deleting fixed mark";
        return -1;
    }

    b->mark[mark2index(j)] = -1;

    return 0;
}

move_mark(i, j, off)
int i;
int j;
{
    buffer *b;

    CHECK(b,i,"move_mark",-1);
    CHECKMARK(b,j,-1);

    if(j <= 0) {
        buffer_error = "Moving fixed mark";
        return -1;
    }

    off += b->mark[mark2index(j)];

    if(off > b->text_length) {
        buffer_error = found_eof;
        return -1;
    }

    if(off < 0) {
        buffer_error = found_bof;
        return -1;
    }

    b->mark[mark2index(j)] = off;

    return off;
}

locate_mark(i, j)
int i;
int j;
{
    buffer *b;

    CHECK(b,i,"locate_mark",-1);
    CHECKMARK(b,j,-1);

    if(j == -1)
        return b->text_length;
    else if(j == 0)
        return 0;
    else {
        int off = b->mark[mark2index(j)];
#ifndef TEST
        if(off == -1)
            buffer_error = "Mark not set";
        else if(off < -1 || off > b->text_length) {
            buffer_error = "Internal error: Bad mark";
            return -1;
        }
#endif
        return off;
    }
}

static safecopy(body, to, from, length)
char *body;
int to, from, length;
{
    int i;

    if(to>from)
        for(i = 0; i < length; i++)
            body[to+i] = body[from+i];
    else
        for(i = length-1; i>=0; i--)
            body[to+i] = body[from+i];
}

/* move_gap(buffer, gap_position)
 *
 * Moves the gap to the indicated position in the buffer. This does not change
 * the logical structure of the buffer. It is most often used to move the gap
 * to a mark for deletion or (if space allows) insertion. It's also used to
 * move the gap out of range of a set of marks.
 */
static move_gap(i, newgap)
int i;
int newgap;
{
    buffer *b;

    CHECK(b,i,"move_gap",-1);

    if(newgap > b->gap) {
        safecopy(b->body,
             b->gap,    /* move to beginning of old gap */
             b->gap+b->gapsize,    /* from end of old gap */
             newgap-b->gap);
    } else {
        safecopy(b->body,
             newgap+b->gapsize,    /* move to end of new gap */
             newgap,    /* from beginning of new gap */
             b->gap-newgap);
    }
    b->gap = newgap;

    return 0;
}

/* expand_gap(buffer, space_needed, gap_position)
 *
 * Because the gap usually needs to be moved when it's expanded, I combine the
 * two actions into a single expand_gap. This is more efficient for the common
 * case, though it makes the code a little hard to follow.
 *
 * You are not expected to understand this.
 *
 * I've always wanted to say that. :->
 *
 * I probably need to put conditions on some more of the calls to memcpy to
 * handle the case of the gap being at the beginning or end of the buffer.
 * That's just an optimization, but what the heck.
 */
static expand_gap(i, newsize, newgap)
int i;
int newsize;
int newgap;
{
    buffer *b;
    char *newbody;
    int newlength;

    CHECK(b,i,"expand_gap",-1);

    newlength = b->body_length + newsize;
    newbody = malloc(newlength);
    if(newbody)
        newsize += b->gapsize;
    else {
        newlength = b->text_length + newsize;
        newbody = malloc(newlength);
    }

    if(!newbody) {
        buffer_error = "Memory allocation failure";
        return -1;
    }

    /* Here there be tygers. If you change this code, sit down ahead of
     * time and figure out EXACTLY what the individual moves do.
     */
    if(b->body) {
        if(newgap < b->gap) {
            memcpy(newbody, b->body, newgap);
            memcpy(newbody+newgap+newsize, b->body+newgap,
                b->gap-newgap);
            memcpy(newbody+newsize+b->gap,
                b->body+b->gap+b->gapsize,
                b->text_length-b->gap);
        } else {
            memcpy(newbody, b->body, b->gap);
            if(newgap > b->gap) {
                memcpy(newbody+b->gap,
                    b->body+b->gap+b->gapsize,
                    newgap-b->gap);
            }
            memcpy(newbody+newgap+newsize,
                b->body+b->gapsize+newgap,
                b->text_length-newgap);
        }

        free(b->body);
    }

    b->body = newbody;
    b->gap = newgap;
    b->gapsize = newsize;
    b->body_length = newlength;
    b->text_length = newlength-newsize;

    return b->gapsize;
}

char *text(i, m1, m2, length)
int i;
int m1, m2;
int *length;
{
    buffer *b;
    char *p;
    int o1, o2;
    int start;

    CHECK(b,i,"text",0);

    if ((o1 = locate_mark(i, m1)) == -1
     || (o2 = locate_mark(i, m2)) == -1)
        return 0;

    if(o2 < o1) {
        int tmp = o2;
        o2 = o1;
        o1 = tmp;
    }

    *length = o2 - o1;

    if(o1 < b->gap && o2 > b->gap)
        move_gap(i, o2);

    start = o1;

    if(start > b->gap)
        start += b->gapsize;

    return b->body + start;
}

char *open_text(i, mark, length)
int i;
int mark;
int length;
{
    buffer *b;
    char *p;
    int off;

    CHECK(b,i,"open_text",0);

    if ((off = locate_mark(i, mark)) == -1)
        return 0;

    if(b->gapsize < length) {
        if(expand_gap(i, length, off) < 0)
            return 0;
    }
    else if(off != b->gap)
        move_gap(i, off);

    return b->body + b->gap;
}

close_text(i, length)
int i;
int length;
{
    buffer *b;

    CHECK(b,i,"close_text",-1);

    fix_marks(i, length);

    b->gap += length;
    b->gapsize -= length;
    b->text_length += length;
    return length;
}

copy_text(i, m1, m2, outbuf, length)
int i;
int m1, m2;
char *outbuf;
int length;
{
    char *p;
    int delta;

    p = text(i, m1, m2, &delta);

    if(!p) return -1;

    if(delta > length) {
        buffer_error = "Output string too short";
        return -1;
    }

    memcpy(outbuf, p, delta);

    return delta;
}

cut_text(i, m1, m2, outbuf, length)
int i;
int m1, m2;
char *outbuf;
int length;
{
    if (copy_text(i, m1, m2, outbuf, length) >= 0)
        return delete_text(i, m1, m2);

    return -1;
}

/* fix_marks(buffer, length)
 *
 * This routine readjusts the marks after the gap when text has been added
 * or removed. Marks are considered to be attached to text that follows, so
 * marks right on the gap are moved. In the case of a deletion these marks
 * (and any others in the portion of text that has been deleted) are removed.
 */
static fix_marks(i,length)
int i;
int length;
{
    buffer *b;
    int index;

    CHECK(b,i,"fix_marks",-1);

    for(index = 0; index < b->himark; index++) {
        if(b->mark[index] >= b->gap) {
            b->mark[index] += length;
            if(b->mark[index] < b->gap) {
                b->mark[index] = -1;
            }
        }
    }
}

insert_text(i, mark, text, length)
int i;
int mark;
char *text;
int length;
{
    char *p;

    p = open_text(i, mark, length);
    if(!p) return -1;

    memcpy(p, text, length);

    close_text(i, length);

    return length;
}

delete_text(i, m1, m2)
int i;
int m1, m2;
{
    buffer *b;
    int o1, o2;
    int length;

    CHECK(b,i,"delete_text",-1);

    if ((o1 = locate_mark(i, m1)) == -1
     || (o2 = locate_mark(i, m2)) == -1)
        return -1;

    if(o2 < o1) {
        int tmp = o2;
        o2 = o1;
        o1 = tmp;
        tmp = m2;
        m2 = m1;
        m1 = tmp;
    }

    if(o2 == o1)
        return 0;

    length = o2 - o1;

    if(o1 != b->gap) {
        move_gap(i, o1);
    }

    fix_marks(i, -length);

    b->gapsize += length;
    b->text_length -= length;

    return length;
}

int count_chars(i, m1, m2, c)
int i;
int m1, m2;
char c;
{
    int length, count;
    char *p;

    p = text(i, m1, m2, &length);

    count = 0;
    while(length-- >  0)
        if(*p++ == c)
            count++;

    return count;
}

#ifdef TEST
static dputs(s, l)
char *s;
int l;
{
    while(l>0) {
        char c = *s++;

        if(c & 0x80) {
            printf("%");
            c &= 0x7F;
        }
        if((c < ' ' || c > 127) && c != '\n') {
            putchar('~');
            c ^= '@';
        }
        if(c == '~' || c == '%')
            putchar(c);
        putchar(c);
        l--;
    }
}
#endif

buffer_debug(i)
int i;
{
    buffer *b;
    int index;

    CHECK(b,i,"buffer_debug",-1);

    printf("buffer(%d) length=%d/%d gap=%d gapsize=%d himark=%d\n",
        i, b->body_length, b->text_length,
           b->gap, b->gapsize, b->himark);
    for(index = 0; index < b->himark; index++)
        printf("\tmark(%d) = %d\n", index2mark(index), b->mark[index]);
#ifdef TEST
    if(b->body) {
        printf("body = {");
        dputs(b->body, b->gap);
        printf("} GAP {");
        dputs(b->body+b->gap+b->gapsize, b->text_length-b->gap);
        printf("};\n");
    }
#endif
    fflush(stdout);
}

int search(i, m1, m2, pat)
int i, m1, m2;
char *pat;
{
    char *boyer_moore_search_compile();
    char *boyer_moore_search_execute();
    int patlen;
    int worklen;
    int new_mark;
    char *compiled;
    char *work;
    int dummy;
    char *found;

    patlen = strlen(pat);

    work = text(i, m1, m2, &worklen);
    if(!work)
        return -1;

    if(locate_mark(i, m1) < locate_mark(i, m2))
        new_mark = copy_mark(i, m1);
    else
        new_mark = copy_mark(i, m2);

    if(new_mark <= 0)
        return -1;

    compiled = boyer_moore_search_compile(pat, patlen);
    if(!compiled) {
        delete_mark(i, new_mark);
        buffer_error = "Search string compile failed";
        return -1;
    }

    found = boyer_moore_search_execute(work, worklen, compiled, &dummy);

    free(compiled);

    if(!found) {
        delete_mark(i, new_mark);
        buffer_error = "Search string not found";
        return 0;
    }

    move_mark(i, new_mark, found - work);

    return new_mark;
}