Язык C был создан почти полвека назад; несмотря на то, что он и сегодня остаётся "вполне себе ничего", его всё больше "тянет вниз" груз технических решений, которые на момент их принятия казались создателям оптимальными. Одним из таких решений стало использование нулевого байта для обозначения конца строки вместо хранения её длины. За счёт выигрыша в виде пары-тройки байт памяти на строку, что было вполне рациональным решением в то время, сейчас мы получаем:

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

Все эти проблемы (и некоторые другие) описаны в замечательной статье The Most Expensive One-byte Mistake. К сожалению, мы ничего не может с этим поделать, не отказавшись от полувековой истории и тысяч легаси-приложений. Или всё-таки можем?

Ещё одна реализация строк

В среде C/C++ программистов очень популярно развлечение, состоящее в написании своих типов строк, призванных решить вышеописанные проблемы и добавить новые плюшки (типа поддержки Юникода). Результаты разнятся от кривых велосипедов до entreprise-level библиотек типа GLib и ICU. Не будем оставаться в стороне и напишем свой (кривой) вариант:

  struct string {
    uint32_t len;
    char *buf;
  };

  struct string *string(const char *s) {
    struct string *str = malloc(sizeof(struct string));
    str->len = strlen(s);
    str->buf = malloc(str->len + 1);
    memcpy(str->buf, s, str->len + 1);
    return str;
  }

  void string_free(struct string *str) {
    free(str->buf);
    free(str);
  }

  struct string *append(struct string *dest, const struct string *str) {
    uint32_t len = dest->len + str->len;
    dest->buf = realloc(dest->buf, len + 1);
    memcpy(dest->buf + dest->len, str->buf, str->len + 1);
    dest->len = len;
    return dest;
  }

Посмотрим на код, который будет работать с нашей реализацией:

  struct string *hello = string("hello ");
  struct string *world = string("world");
  append(hello, world);

  /* ... */

  string_free(hello);
  string_free(world);

So far, so good! Мы можем создавать, удалять, соединять строки; словом, у нас есть консистентное API. Всё это смотрится вполне натурально… пока мы не захотим вывести нашу строку на экран.

images/sad-kitty.jpg
"А всё так хорошо начиналось…"

Конечно, мы можем написать свою функцию печати, либо печатать сам буфер: puts(hello->buf);. Однако, при этом теряется прозрачность. Тут нам на помощь приходят fat pointers.

Fat pointers

Взглянем сначала на интерфейс гипотетической строковой библиотеки, основанной на "толстых" указателях:

  char *string(const char *s);
  void string_free(char *str);
  char *append(char *dest, const char *str);

На первый взгляд покажется, что эти функции работают с обычными строками. Так почему же их назвали "толстыми"?

images/im-not-fat-im-fluffy.jpg
На самом деле нет

Дело в том, для "толстые" указатели вместе с самими данными, которые используются обычными функциями, хранят некоторые метаданные, при этом память выделяется одним куском. Сначала идут метаданные, потом сами данные, указатель на которые передаются в функции. Рассмотрим для примера, как размещается в памяти "толстая" строка s, полученная с помощью функции string:



               +----------------+
               |       5        |<----- указатель на длину строки
               +----------------+
  char *s ---->|      'h'       |<----- указатель, который передаётся в функции
               +----------------+
               |      'e'       |
               +----------------+
               |      'l'       |
               +----------------+
               |      'l'       |
               +----------------+
               |      'o'       |
               +----------------+
               |       0        |
               +----------------+

Таким образом, с этим типом данных смогут работать все стандартные строковые функции, которые не выделяют или освобождают память. При этом мы сможем легко (O(1)) получить длину строки, просто обратившись к данным, которые хранятся в памяти прямо перед ней.

Вот сам код "библиотеки":

  #define LEN(str) (*((uint32_t *) ((str) - sizeof(char))))

  char *string(const char *s) {
    uint32_t len = strlen(s);
    /* Выделяем память строку и её длину */
    char *buf = malloc(sizeof(uint32_t) + len + 1);

    /* Записываем длину строки */
    *((uint32_t *) buf) = len;
    /* Записываем строку по смещению */
    memcpy(buf + sizeof(uint32_t), s, len + 1);
    /* Возвращаем указатель на строку */
    return buf + sizeof(uint32_t);
  }

  void string_free(char *s) {
    free(s - sizeof(uint32_t));
  }

  char *append(char *dest, const char *str) {
    uint32_t dest_len = LEN(dest);
    uint32_t str_len = LEN(str);
    uint32_t len = dest_len + str_len;
    LEN(dest) = len;
    char *base = dest - sizeof(uint32_t);
    base = realloc(base, sizeof(uint32_t) + len + 1);
    memcpy(dest + dest_len, str, str_len + 1);
    return dest;
  }

Пример использования:

  char *hello = string("hello ");
  char *world = string("world");
  append(hello, world);

  puts(hello);

  string_free(hello);
  string_free(world);

Cello

"Толстые" указатели активно используются в одной довольно интересной библиотеке под названием Cello, которая привносит в C некоторые фичи из таких высокоуровневых языков, как Python и Haskell, как бы странно это не звучало. Cello добавляет в C некоторое подобие рантайма, который используюет метаданные, добавляемые к обычным сишным структурам и типам и доступные во время выполнения. Метаданные хранятся вместе с самими структурами в виде "толстых" указателей, что позволяет прозрачно использовать эти структуры со стандартным сишным кодом:

  #include <Cello.h>

  /* Обычная C-структура... */
  struct Point {
    double x, y;
  };

  /* ...на стероидах!  */
  var Point = Cello(Point);

  void swap_fields(struct Point *p) {
    double tmp = p->x;
    p->x = p->y;
    p->y = tmp;
  }

  int main(int argc, char *argv[]) {
    /* Выделяем структуру на стеке */
    struct Point *p0 = $(Point, 0., 1.);
    /* Делаем копию в куче */
    struct Point *p1 = copy(p0);

    /* fat pointers совместимы с обычными структурами! */
    swap_fields(p0);

    print("p0: %$ x=%$, y=%$\n"
          "p1: %$ x=%$, y=%$\n",
          p0, $F(p0->x), $F(p0->y),
          p1, $F(p1->x), $F(p1->y));

    return 0;
  }

Подробнее почитать про то, как устроена библиотека Cello, можно по ссылке.