## Расширение структур и словарей
### Реализация словаря
Заголовок - открытый интерфейс класса ключей и значений
keyval.h
```
typedef struct keyval
{
char *key;
void *value;
} keyval;
keyval *keyval_new(char *key, void *value);
keyval *keyval_copy(keyval const *in);
void keyval_free(keyval *in);
int keyval_matches(keyval const *in, char const *key);
```
Типичный шаблон кода объекта : структура плюс функции создания, копирования и освобождения
keyval.c
```
#include <stdlib.h> //malloc
#include <strings.h> //strcasecmp
#include "keyval.h"
keyval *keyval_new(char *key, void *value)
{
keyval *out = malloc(sizeof(keyval));
*out = (keyval){.key = key, .value = value};
return out;
}
/** Copy a key/value pair. The new pair has pointers to
the values in the old pair, not copies of their data. */
keyval *keyval_copy(keyval const *in)
{
keyval *out = malloc(sizeof(keyval));
*out = *in;
return out;
}
void keyval_free(keyval *in) { free(in); }
int keyval_matches(keyval const *in, char const *key)
{
return !strcasecmp(in->key, key);
}
```
Открытый интерфейс словаря (dict.h)
```
#include "keyval.h"
/*
Это признак, возвращаемый, когда ключ не найден в словаре. Он должен быть открытым.
*/
extern void *dictionary_not_found;
typedef struct dictionary
{
keyval **pairs;
int length;
} dictionary;
dictionary *dictionary_new(void);
dictionary *dictionary_copy(dictionary *in);
void dictionary_free(dictionary *in);
void dictionary_add(dictionary *in, char *key, void *value);
void *dictionary_find(dictionary const *in, char const *key);
```
Реал изация словаря dict.c
```
#include <stdio.h>
#include <stdlib.h>
#include "dict.h"
void *dictionary_not_found;
dictionary *dictionary_new(void)
{
//Нужен уникальный признак, обозначающий отсутствие ключа. Мы не знаем, где в памяти хранится переменная dnf, но ее адрес заведомо уникален
static int dnf;
if (!dictionary_not_found)
dictionary_not_found = &dnf;
dictionary *out = malloc(sizeof(dictionary));
*out = (dictionary){};
return out;
}
// функция, помеченная ключевым словом static, не видна вне файла, так что это еще одно напоминание о том, что она является закрытой частью реализации.
static void dictionary_add_keyval(dictionary *in, keyval *kv)
{
in->length++;
in->pairs = realloc(in->pairs, sizeof(keyval *) * in->length);
in->pairs[in->length - 1] = kv;
}
void dictionary_add(dictionary *in, char *key, void *value)
{
if (!key)
{
fprintf(stderr, "NULL is not a valid key.\n");
abort();
}
dictionary_add_keyval(in, keyval_new(key, value));
}
void *dictionary_find(dictionary const *in, char const *key)
{
for (int i = 0; i < in->length; i++)
if (keyval_matches(in->pairs[i], key))
return in->pairs[i]->value;
return dictionary_not_found;
}
dictionary *dictionary_copy(dictionary *in)
{
dictionary *out = dictionary_new();
for (int i = 0; i < in->length; i++)
dictionary_add_keyval(out, keyval_copy(in->pairs[i]));
return out;
}
void dictionary_free(dictionary *in)
{
for (int i = 0; i < in->length; i++)
keyval_free(in->pairs[i]);
free(in);
}
```
Пример использования словарного объекта(dict_use.c)
```
/* Compile with:
mkdir -p hash
cp dict_use.c dict.h dict.c keyval.c keyval.h dict_test.c hash
cp dict.automake hash/Makefile.am
cd hash
touch NEWS README AUTHORS ChangeLog #still cheating
autoscan
sed -e 's/FULL-PACKAGE-NAME/hashdict/' \
-e 's/VERSION/1/' \
-e 's|BUG-REPORT-ADDRESS|/dev/null|' \
-e '12i\
AM_INIT_AUTOMAKE' \
-e '13i\
LT_INIT' \
-e '14i\
AC_CHECK_LIB([glib-2.0],[g_free])' \
-e 's|PROG_CC|PROG_CC_C99|' \
< configure.scan > configure.ac
autoreconf -i > /dev/null
./configure
make distcheck
make
*/
#include <stdio.h>
#include "dict.h"
int main()
{
int zero = 0;
float one = 1.0;
char two[] = "two";
dictionary *d = dictionary_new();
dictionary_add(d, "an int", &zero);
dictionary_add(d, "a float", &one);
dictionary_add(d, "a string", &two);
printf("The integer I recorded was: %i\n", *(int *)dictionary_find(d, "an int"));
printf("The string was: %s\n", (char *)dictionary_find(d, "a string"));
dictionary_free(d);
}
```
Таким образом, написания структуры с функциями new /сору /free и прочими
оказалось достаточно для обеспечения нужного уровня инкапсуляции: словарю безразлично внутреннее устройство пары ключ/значение, а приложение может не думать об устройстве словаря.
### С без зазоров
В языке С единственный способ добавить новые элементы в структуру - обернуть ее другой структурой
В С11 использование вложенных структур упрощено благодаря разрешению
включать в структуру анонимные элементы. И хотя в стандарт эта возможность была добавлена только в декабре 2011 года, в компиляторе Microsoft она была реализована гораздо раньше, а в gcc для ее активации нужно задать флаг `--ms-extensions` в командной строке.
```
/* Compile with:
make LDLIBS='-lm' CFLAGS="-g -Wall -std=gnu11 --ms-extensions" seamlessone
*/
#include <stdio.h>
#include <math.h>
typedef struct point
{
double x, y;
} point;
typedef struct
{
struct point; // Это анонимная подструктура
double z;
} threepoint;
double threelength(threepoint p)
{
return sqrt(p.x * p.x + p.y * p.y + p.z * p.z);
}
int main()
{
threepoint p = {.x = 3, .y = 0, .z = 4};
printf("p is %g units from the origin\n", threelength(p));
}
```
А теперь о приеме, благодаря которому этот механизм становится действительно полезным. В исходном объекте point, скорее всего, имелся набор интерфейсных функций, потенциально все еще полезных, например функция length, возвращающая длину от точки до начала координат. Как воспользоваться этой функцией, если у части большей структуры нет имени?
Решение простое: взять анонимное объединение структур с именованной и
неименованной частями point. Поскольку структуры идентичны, то вес их поля
занимают в точности одинаковые позиции в объединении и отличаются только
именами. Когда требуется вызвать функцию, работающую с исходной структурой, мы будем пользоваться именованной частью, а для органичного встраивания подструктуры в объемлющую структуру - анонимной.
```
/* Compile with:
make LDLIBS='-lm' CFLAGS="-g -Wall -std=gnu11 --ms-extensions" seamlesstwo
*/
#include <stdio.h>
#include <math.h>
typedef struct point
{
double x, y;
} point;
typedef struct
{
union
{
struct point; //Это анонимная структура
point p2; //Это именованная структура
};
double z;
} threepoint;
double length(point p)
{
return sqrt(p.x * p.x + p.y * p.y);
}
double threelength(threepoint p)
{
return sqrt(p.x * p.x + p.y * p.y + p.z * p.z);
}
int main()
{
threepoint p = {.x = 3, .y = 0, .z = 4};
printf("p is %g units from the origin\n", threelength(p));
double xylength = length(p.p2);
printf("Its projection onto the XY plane is %g units from the origin\n", xylength);
}
```
Наследование нескольких структур таким способом - вещь рискованная. Выберите какую-нибудь одну структуру, которая станет базой расширения, воспользовавшись трюком с объединением, а остальные расширяйте с помощью обычных подструктур.
### Стройте код на основе указателей на объекты
На самом деле есл и вы работаете с обычной структурой, то функции пew/copy/free получаются автоматически:
new
Пользуйтесь позиционными инициализаторами в первой же строке той части кода,где необходима структура. Дополнительный бонус: структуры можно объявлять на этапе ком пиляци и, так что они становятся доступны сразу же, без обращения к функции инициализации.
сору
Для копирования достаточно знака равенства.
free
Не о чем беспокоиться, скоро структура покинет область видимости .
Таким образом , работая с указател я м и , мы сами усложняем себе жизнь. И тем не менее есть общее мнение, что именно указатели следует класть в основу дизайна программ . Перечислим их преимущества.
* Копирование указателя обходится деш евле коп и рования структуры целиком , поэтому мы экономимм икросекунду на каждом обращении к функци и , принимающей структуру. Разумеется , это становится ощутимо только после нескольких м иллиардов обращений .
*Все библиотеки для работы со структурами данных ( к примеру, деревья м и и связанными списками) написаны в расчете на указатели.
* Когда мы заполняем дерево или список, автоматическое уничтожение структуры по выходе из области видимости , в которой она была создана, отнюдь не всегда желательно.
* Многие функции, принимающие структуру, модифицируют ее содержимое, а это означает, что без передач и указателя все равно не обойтись. Когда одни функции принимают структуру, а другие - указатель на структуру, возникает путаница, поэтому лучше уж всегда передавать указатель.
* Если какое-то поле структуры содержит указатель на данные, то все преимущества использования обычных структур улетучиваются : для выполнения глубокого копирования ( когда копируются не только указатели , но и данные, на которые они указывают) потребуется функция копирования и, скорее всего, также функция освобождения, гарантирующая уничтожение внутренних данных.
* Не существует п равил использования структур, пригодных на все случаи жизни. Когда в процессе эволюции одноразовая структура, созданная для упрощения внутренних операций, становится основой организации данных, достоинства указателей выходят на первый план, а достоинства структур как таковых отступают.
## Функции в структурах