hacks

(tidier examples of) random scripts from throughout the years
Log | Files | Refs | README

gap.c (4544B)

      1 /**
      2  * Editor's note: A simple program that demonstrates how a gap buffer works.
      3  * I wrote this in order to have a visual demo for my 15-122 TA interview!
      4  * Written around the fall of 2023.
      5  *
      6  * Fun fact (and another demo I did during my interview): you can see how a
      7  * gap buffer is used in Emacs by calling the functions (gap-position) and
      8  * (gap-size). I recommend using the `lively` package to see how they
      9  * update as you edit the buffer.
     10  */
     11 
     12 #include <stddef.h>
     13 #include <stdbool.h>
     14 #include <assert.h>
     15 #include <stdlib.h>
     16 #include <string.h>
     17 #include <stdio.h>
     18 
     19 #define abs(x) ((x > 0) ? x : -x)
     20 
     21 #define REQUIRES(expr) assert(expr)
     22 #define ENSURES(expr) assert(expr)
     23 
     24 struct gap_buf {
     25     char* buf;
     26     size_t size;
     27     size_t gap_start;
     28     size_t gap_size;
     29 };
     30 
     31 typedef struct gap_buf* gapbuf_t;
     32 
     33 bool gb_gap_in_bounds(gapbuf_t gb, size_t gap_start) {
     34     return (gap_start <= gb->size) &&
     35         (gap_start + gb->gap_size) <= gb->size;
     36 }
     37 
     38 bool is_gap_buf(gapbuf_t gb) {
     39     if (gb == NULL) return false;
     40        
     41     bool buf_nonnull = gb->buf != NULL;
     42     bool gap_in_bounds = gb_gap_in_bounds(gb, gb->gap_start);
     43     // Redundant, but nice to be explicit 
     44     bool gap_size_sane = (gb->gap_size <= gb->size);
     45     
     46     return buf_nonnull && gap_in_bounds && gap_size_sane;
     47 }
     48 
     49 gapbuf_t gb_new(size_t size) {
     50     gapbuf_t out = malloc(sizeof(struct gap_buf));
     51     out->buf = malloc(sizeof(char)*size);
     52     out->size = size;
     53     out->gap_start = 0;
     54     out->gap_size = size;
     55     ENSURES(is_gap_buf(out));
     56     return out;
     57 }
     58 
     59 char* gb_start(const gapbuf_t gb) {
     60     return gb->buf + gb->gap_start;
     61 }
     62 
     63 char* gb_end(const gapbuf_t gb) {
     64     return gb->buf + gb->gap_start + gb->gap_size;
     65 }
     66 
     67 void gb_resize(gapbuf_t gb) { // O(n)
     68     REQUIRES(is_gap_buf(gb));
     69     gb->gap_size = gb->size;
     70     gb->size *= 2;
     71     
     72     char* old = gb->buf;
     73     gb->buf = malloc(sizeof(char)*gb->size);
     74     memcpy(gb->buf, old, gb->size/2);    
     75     memcpy(gb_end(gb), gb->buf + gb->gap_start,
     76            gb->size/2 - gb->gap_start);
     77     free(old);
     78     ENSURES(gb->gap_size != 0);
     79     ENSURES(is_gap_buf(gb));
     80 }
     81 
     82 void gb_print(gapbuf_t gb) { 
     83     REQUIRES(is_gap_buf(gb));
     84     for (size_t i = 0; i < gb->size; i++) {
     85         char* ptr = gb->buf + i;
     86         
     87         if (i == gb->gap_start) {
     88             if (gb->gap_size == 1) printf("[]");
     89             else printf("[");
     90         } else if (i == gb->gap_start + gb->gap_size - 1) {
     91             printf(" ]");
     92         } else if (i > gb->gap_start &&
     93                    i < gb->gap_start + gb->gap_size - 1) {
     94             printf(" ");
     95         } else {
     96             printf("%c", *ptr);
     97         }
     98     }
     99     printf("\n");
    100 }
    101 
    102 void gb_insert(gapbuf_t gb, char c) { // O(1) amt
    103     REQUIRES(is_gap_buf(gb));
    104     gb->buf[gb->gap_start] = c;
    105     gb->gap_start++;
    106     gb->gap_size--;
    107     if (gb->gap_size == 0) gb_resize(gb);
    108     ENSURES(is_gap_buf(gb));
    109 }
    110 
    111 void gb_insert_many(gapbuf_t gb, char* s) { // O(len(s)) amt 
    112     REQUIRES(is_gap_buf(gb));
    113     for (size_t i = 0; i < strlen(s); i++) {
    114         gb_insert(gb, s[i]);
    115         gb_print(gb);
    116     }
    117     ENSURES(is_gap_buf(gb));
    118 }
    119 
    120 void gb_del(gapbuf_t gb) { // O(1)
    121     REQUIRES(is_gap_buf(gb));
    122     REQUIRES(gb_gap_in_bounds(gb, gb->gap_start - 1));
    123     gb->gap_start--;
    124     gb->gap_size++;
    125     ENSURES(is_gap_buf(gb));
    126 }
    127 
    128 void gb_move(gapbuf_t gb, ptrdiff_t off) { // O(off)
    129     REQUIRES(off != 0);
    130     REQUIRES(gb_gap_in_bounds(gb, gb->gap_start + off));
    131     gb->gap_start += off;
    132     size_t to_move = abs(off);
    133     if (off < 0) {
    134         memcpy(gb_end(gb), gb_start(gb), to_move);
    135     } else {
    136         memcpy(gb_start(gb)-off,
    137                gb_start(gb)+gb->gap_size-off,
    138                to_move);	
    139     }
    140     ENSURES(is_gap_buf(gb));
    141 }
    142 
    143 
    144 int main() {
    145     printf("INIT\n");
    146     gapbuf_t gb = gb_new(8);
    147     gb_print(gb);
    148     printf("\nINSERT 'int main();'\n");
    149     gb_insert_many(gb, "int main();");
    150     printf("\nMOVE -3\n");
    151     gb_move(gb, -3);
    152     gb_print(gb);
    153     printf("\nINSERT '/* questionable comment */'\n");
    154     gb_insert_many(gb, "/* questionable comment */");
    155     printf("\nMOVE +3\n");
    156     gb_move(gb, 3);
    157     gb_print(gb);
    158     printf("\nDELETE\n");
    159     gb_del(gb);
    160     gb_print(gb);
    161     printf("\nINSERT ';'\n");
    162     gb_insert(gb, ';');
    163     gb_print(gb);
    164     printf("\nMOVE -34\n");
    165     gb_move(gb, -34);
    166     gb_print(gb);
    167     printf("\nDELETE 3\n");
    168     gb_del(gb);  gb_del(gb); gb_del(gb);
    169     gb_print(gb);
    170     printf("\nINSERT 'bool'\n");
    171     gb_insert_many(gb, "bool");
    172     printf("\nMOVE +34\n");
    173     gb_move(gb, 34);
    174     gb_print(gb);
    175 }