#include #include "piece-table.h" static piece *make_piece() { return malloc(sizeof(piece)); } static piece *make_sentinel() { piece *p = make_piece(); p->length = 0; p->next = NULL; p->prev = NULL; p->start = NULL; return p; } bool init_piece_table(piece_table *pt, char *orig) { piece *pc, *sentinel; init_growable_buffer(&pt->add); init_fixed_buffer(&pt->orig, orig); pt->length = pt->orig.size; pc = make_piece(); if(pc == NULL){ return false; } sentinel = make_sentinel(); if(sentinel == NULL){ return false; } pc->start = pt->orig.content; pc->length = pt->orig.size; pc->prev = sentinel; pc->next = sentinel; pt->cached_offset = 0; pt->cached = pc; return true; } static void free_piece_list(piece *p) { piece *cur, *next; assert(p != NULL); for ( cur = p; cur != p; cur = next ) { next = cur->next; free( cur ); } } void free_piece_table(piece_table *pt) { free_growable_buffer(&pt->add); free_fixed_buffer(&pt->orig); free_piece_list(pt->sentinel); pt->sentinel = NULL; pt->cached = NULL; pt->cached_offset = 0; pt->length = 0; } static void find_piece_by_pos(piece_table *pt, size_t pos) { piece *cur; assert(pos < pt->length); if ( pos >= pt->cached_offset ) { /* Search forward */ for ( cur = pt->cached; ; cur = cur->next ) { if ( pt->cached_offset + pt->length > pos ) { pt->cached = cur; assert(pt->cached != pt->sentinel); return; } pt->cached_offset += cur->length; } } else { /* Search backwards */ for ( cur = pt->cached->prev; ; cur = cur->prev ) { pt->cached_offset -= cur->length; if ( pt->cached_offset < pos ) { pt->cached = cur; assert(pt->cached != pt->sentinel); return; } } } } char index_piece_table(piece_table *pt, size_t pos) { assert(pos < pt->length); find_piece_by_pos(pt, pos); return pt->cached->start[pos - pt->cached_offset]; } void insert_piece_table(piece_table *pt, char val, size_t pos) { /* At the moment inserts only one char */ append_growable_buffer(&pt->add, &val, 1); find_piece_by_pos(pt, pos); // TODO } void delete_piece_table(piece_table *pt, size_t pos, size_t len) { }