Как реализовать ‘string’-y переменной длины в C - PullRequest
Новая
       39

Как реализовать ‘string’-y переменной длины в C

2 голосов
/ 11 февраля 2010

Я немного погуглил, но не могу найти информацию о том, как строки переменной длины обычно реализуются в языках более высокого уровня. Я создаю свой собственный такой язык и не знаю, с чего начать со строк.

У меня есть структура, описывающая тип string, а затем функция create, которая выделяет такую ​​«строку»: 

/* A safer `strcpy()`, using `strncpy()` and `sizeof()` */
#define STRCPY(TO, FROM) \
  strncpy(TO, FROM, sizeof(TO)); TO[sizeof(TO) - 1] = '\0'

struct string {
  // …
  char  native[1024];
};

string String__create(char native[]) {
  string this = malloc(sizeof(struct string));

  // …
  STRCPY(this->native, native);

  return this;
}

Однако, это позволило бы только строки длиной 1 КБ. Это глупо, и в большинстве случаев это огромная трата памяти.

Учитывая, что я должен объявить используемую память каким-то образом ... как мне реализовать строку, которая может (эффективно) хранить (эффективно) неограниченное количество символов?

Ответы [ 5 ]

11 голосов
/ 11 февраля 2010

Многие реализации C ++ std::string теперь используют «Оптимизацию небольших строк». В псевдокоде: 

struct string {
    Int32 length
    union {
        char[12] shortString
        struct {
           char* longerString
           Int32 heapReservedSpace
        }
    }
}

Идея состоит в том, что в массиве shortString хранится строка длиной до 12 символов. Вся строка будет смежной и будет использовать только одну строку кэша. Более длинные строки хранятся в куче. Это оставляет вам 12 свободных байтов в строковом объекте. Указатель не принимает все это, поэтому вы также можете вспомнить, сколько памяти вы выделили в куче (>=length). Это помогает поддерживать сценарии, в которых вы увеличиваете строку небольшими шагами.

4 голосов
/ 11 февраля 2010

В дополнение к тому, что говорили вам другие, я бы также включил понятие «емкость»: Невозможно узнать размер выделенного вектора в памяти, вы должны его сохранить. Если вы сделаете sizeof структуры String, она вернет вам 4 байта * 3 числовых поля = 12 байтов (вероятно, больше из-за заполнения, используемого в структурах). Кроме того, вы не можете получить длину выделенной памяти через sizeof. 

typedef struct _mystring {
        char * native;
        size_t size;
        size_t capacity;
} String;

Таким образом, емкость всегда имеет фактический размер порции, в которой находится ваша строка. Скажите, что ваша строка становится короче: вам не нужно перераспределять, чтобы получить точное соответствие между емкостью и размером вашей строки. Кроме того, вы можете выделить с начала символы, которые вы ожидаете получить в строке, а не символы, которые есть в исходной строке. Наконец, вы можете подражать динамическому вектору строки C ++ и удваивать емкость каждый раз, когда строка выходит за пределы допустимой емкости. Все это сведет к минимуму операции с памятью, что повысит производительность (вы также потратите немного памяти, но не больше 1 КБ). 

String String__create(char native[], size_t capacity) {
  String this;

  this.size = strlen( native );
  if ( capacity < ( this.size + 1 ) )
        this.capacity = this.size + 1;
  else  this.capacity = capacity;

  this.native = (char *) malloc( capacity * sizeof( char ) );
  strcpy( this.native, native );

  return this;
}

String * String__set(String *this, char native[]) {
    this->size = strlen( native );

    if ( this->size >= this->capacity ) {
        do {
            this->capacity <<= 1;
        } while( this->size > this->capacity );

        this->native = realloc( this->native, this->capacity );
    }

    strcpy( this->native, native );

    return this;
}

void String__delete(String *this)
{
    free( this->native );
}
4 голосов
/ 11 февраля 2010

Общий подход состоит в том, чтобы иметь поле для длины и указатель на динамически выделенную область памяти для хранения символов. 

typedef struct string {
    size_t length;
    unsigned char *native;
} string_t;

string_t String__create(char native[]) {
    string_t this;
    this.length = strlen(native);
    this.native = malloc(this.length+1);
    if (this.native) {
        strncpy(this.native, native, this.length+1);
    } else {
        this.length = 0;
    }
    return this;
}

Если вы хотите динамически выделить string_t: 

string_t* String__create(char native[]) {
    string_t* this;
    if (this = malloc(sizeof(*this))) {
        this->length = strlen(native);
        this->native = malloc(this->length+1);
        if (this->native) {
            strncpy(this->native, native, this->length+1);
        } else {
            free(this);
            this=NULL;
        }
    }
    return this;
}
void String__delete(string_t** str) {
    free((*str)->native);
    free((*str));
    *str=NULL;
}
2 голосов
/ 11 февраля 2010

realloc переместит вашу память в больший буфер - простое использование этой команды позволит вам изменить размер вашей строки. Используйте следующую структуру для вашей строки: 

struct mystring
{
    char * string;
    size_t size;
};

Важной частью является отслеживание размера вашей строки и проверка каждой функции обработки строк, если размер имеет смысл.

Вы можете предварительно выделить большой буфер и продолжать добавлять к нему, и только realloc, когда указанный буфер заполнен - ​​вы должны реализовать все функции для этого. Желательно (гораздо менее подверженный ошибкам и более безопасный) изменять строку, перемещаясь из одной immutable string в другую (используя семантику realoc).

0 голосов
/ 03 июня 2011

Некоторые люди предпочитают использовать структуру данных «веревка» для хранения строки символов неограниченной длины, а не непрерывной строки (строка C).

Упрощенная банка веревкибыть определено что-то вроде: 

#include <stdio.h>

struct non_leaf_rope_node{
    char zero;
    union rope* left_substring;
    union rope* right_substring;
    // real rope implementations have a few more items here
};
#define rope_leaf_max ( sizeof( struct non_leaf_rope_node ) )

typedef union rope {
    char rope_data[ rope_leaf_max ];
    struct non_leaf_rope_node pointers;
} rope;

void print( union rope *node ){
    if( node->rope_data[0] != '\0' ){
        // short literal data
        fputs( node->rope_data, stdout );
    }else{
        // non-root node
        print( node->pointers.left_substring );
        print( node->pointers.right_substring );
    };
};
// other details involving malloc() and free() go here

int main(void){
    rope left = { "Hello," };
    rope right = { " World!" };
    rope root = {0,0,0};
    root.pointers.left_substring = &left;
    root.pointers.right_substring = &right;
    print( &root );

    return 0;
};

Веревка, содержащая меньше символов Rope_leaf_max, хранится так же, как строка C с нулевым символом в конце.Веревка, содержащая более чем символ Rope_leaf_max, сохраняется как корневой non_leaf_rope_node, указывающий на левую и правую подстроки (которые могут, в свою очередь, указывать на левую и правую подстроки), в конечном итоге указывающие на конечные узлы и конечные узлыкаждый из них содержит хотя бы один символ полной строки.

В веревке всегда хранится хотя бы один символ, поэтому мы всегда можем сказать: если первый байт узла веревки не равен нулю, этот узел является листомузел хранения буквенных символов.Если первый байт узла веревки равен нулю, этот узел хранит указатели на левую и правую подстроки.(Реальные реализации веревки часто имеют третий тип узла веревки).

Часто использование веревок требует меньше общего пространства ОЗУ, чем использование строк С.(Узел, содержащий фразу, такую ​​как «Нью-Йорк», может многократно использоваться в одной веревке или в некоторых реализациях, совместно используемых двумя веревками).Иногда использование веревок быстрее, чем использование строк С.

...