Я сделал намного больше программирования на С ++, чем программирование «простого старого С». Одна вещь, которую я очень скучаю, когда программирование в простой C – это типовые структуры данных, которые предоставляются в C ++ с помощью шаблонов.
Для определенности рассмотрим общий список, связанный по отдельности. В C ++ просто определить свой собственный class шаблонов, а затем создать его для типов, которые вам нужны.
В C я могу придумать несколько способов реализации общего одноуровневого списка:
Мне не нравится вариант 1, поскольку он подрывает систему типов и, вероятно, имеет худшую производительность, чем специализированная реализация типа. Использование единообразного представления структуры данных для всех типов и отбрасывание в / из указателей void, насколько я вижу, требует наличия косвенности, которой будет избегать реализация, специализированная для типа элемента.
Вариант 2 не требует каких-либо дополнительных инструментов, но он чувствует себя несколько неуклюжим и может давать плохие compiler errors при неправильном использовании.
Вариант 3 может дать лучшие сообщения об ошибках компилятора, чем вариант 2, поскольку специализированный код структуры данных будет находиться в расширенной форме, которая может быть открыта в редакторе и проверена программистом (в отличие от кода, созданного макросами препроцессора). Тем не менее, этот вариант является самым тяжелым, своего рода «шаблонами для неимущих». Я использовал этот подход раньше, используя простой скрипт sed, чтобы специализировать «шаблонную» версию некоторого кода на языке C.
Я хотел бы запрограммировать мои будущие «низкоуровневые» проекты на C, а не на C ++, но был напуган мыслью переписать общие структуры данных для каждого конкретного типа.
Какой у людей опыт с этой проблемой? Существуют ли хорошие библиотеки общих структур данных и алгоритмов в C, которые не идут с Вариантом 1 (то есть литье в и из указателей void, которое жертвует безопасностью типа и добавляет уровень косвенности)?
Вариант 1 – это подход, применяемый большинством реализаций общих контейнеров C, которые я вижу. Набор драйверов Windows и kernel Linux используют макрос, чтобы обеспечить возможность привязки ссылок для контейнеров в любой точке структуры, причем макрос используется для получения указателя структуры от указателя на поле ссылки:
list_entry() в Linux CONTAINING_RECORD() в Windows Вариант 2 – это предел, принятый с помощью tree.h BSD и реализации контейнера queue.h:
Я не думаю, что считаю, что любой из этих подходов безопасен. Полезно, но не безопасно.
C имеет для него другой вид красоты, чем C ++, и тип безопасности и возможность всегда видеть, что все, когда трассировка через код без привлечения отбрасываний в вашем отладчике, как правило, не является одним из них.
Красота C отходит от отсутствия безопасности типа, работы вокруг системы типов и на уровне исходного уровня бит и байтов. Из-за этого есть некоторые вещи, которые он может сделать более легко, не сражаясь с языком, например, структурами переменной длины, используя стек даже для массивов, размеры которых определяются во время выполнения и т. Д. Это также, как правило, намного проще сохраните ABI, когда вы работаете на этом более низком уровне.
Таким образом, здесь есть и другая эстетика, а также различные проблемы, и я бы рекомендовал изменить мышление, когда вы работаете на C. Чтобы действительно оценить это, я бы предложил делать то, что многие люди считают само собой разумеющимся в наши дни, например реализуя свой собственный распределитель памяти или драйвер устройства. Когда вы работаете на таком низком уровне, вы не можете не смотреть на все, как на макеты памяти битов и байтов, в отличие от «объектов» с прикрепленными поведением. Кроме того, может возникнуть точка в таком низкоуровневом коде управления бит / байтом, где C становится легче понимать, чем код C ++, замусоренный reinterpret_casts , например
Что касается примера связанного списка, я бы предложил неинтрузивную версию связанного узла (тот, который не требует хранения указателей на список в самом типе элемента, сам T , позволяя разделить логику связанного списка и представление от самого T ), вот так:
struct ListNode { struct ListNode* prev; struct ListNode* next; MAX_ALIGN char element[1]; // Watch out for alignment here. // see your compiler's specific info on // aligning data members. };
Теперь мы можем создать узел списка следующим образом:
struct ListNode* list_new_node(int element_size) { // Watch out for alignment here. return malloc_max_aligned(sizeof(struct ListNode) + element_size - 1); } // create a list node for 'struct Foo' void foo_init(struct Foo*); struct ListNode* foo_node = list_new_node(sizeof(struct Foo)); foo_init(foo_node->element);
Чтобы извлечь элемент из списка как T *:
T* element = list_node->element;
Так как это C, при указании на кастрюлю такого типа нет проверки типов, и это, вероятно, также вызовет у вас беспокойство, если вы исходите из фона C ++.
Трудная часть здесь состоит в том, чтобы убедиться, что этот элемент, element , правильно выровнен для любого типа, который вы хотите сохранить. Когда вы сможете решить эту проблему как можно более мобильно, у вас будет мощное решение для создания эффективных макетов памяти и распределителей. Часто это означает, что вы просто используете максимальное выравнивание для всего, что может показаться расточительным, но обычно это не так, если вы используете соответствующие структуры данных и распределители, которые не оплачивают эти накладные расходы для многочисленных небольших элементов на индивидуальной основе.
Теперь это решение по-прежнему связано с типом литья. Мало что вы можете сделать, если у вас есть отдельная версия кода этого узла списка и соответствующая логика для работы с ним для каждого типа T, который вы хотите поддерживать (за исключением динамического polymorphismа). Однако он не требует дополнительного уровня косвенности, как вы могли подумать, и по-прежнему распределяет весь узел и элемент списка в одном распределении.
И я бы рекомендовал этот простой способ добиться универсальности в C во многих случаях. Просто замените T буфером, который имеет длину, соответствующую sizeof(T) и правильно выровнен. Если у вас достаточно портативный и безопасный способ, который вы можете обобщить для обеспечения правильного выравнивания, у вас будет очень мощный способ работы с памятью, который часто улучшает хиты кеша, уменьшает частоту распределения / освобождения кучи, количество требуемое направление, время сборки и т. д.
Если вам нужна дополнительная автоматизация, например, если list_new_node автоматически инициализирует struct Foo , я бы рекомендовал создать общую структуру таблицы типов, которую вы можете передать, в которой содержится информация, например, как большой T, указатель функции, указывающий на функцию для создания экземпляра по умолчанию T , другой – для копирования T, клонирования T, уничтожения T, компаратора и т. д. В C ++ вы можете автоматически генерировать эту таблицу с использованием шаблонов и встроенных языковых концепций, таких как конструкторы копирования и деструкторы. C требует немного большего ручного усилия, но вы все равно можете немного уменьшить его шаблон с помощью макросов.
Еще один трюк, который может быть полезен, если вы переходите с помощью маршрута генерации большего количества макрокоманд, – это использовать префикс или соглашение об именах с именами на основе суффикса. Например, CLONE (Type, ptr) может быть определен для возврата Type##Clone(ptr) , поэтому CLONE(Foo, foo) может вызывать FooClone(foo) . Это своего рода чит, чтобы получить что-то вроде функции перегрузки в C и полезно при генерации кода навалом (когда CLONE используется для реализации другого макроса) или даже немного копирования и вставки кода шаблонного типа, по крайней мере, улучшить однородность шаблона.
Вариант 1, использующий void * или какой-либо вариант на основе union – это то, что использует большинство программ на C, и оно может дать вам более высокую производительность, чем стиль C ++ / macro, имеющий несколько реализаций для разных типов, поскольку он имеет меньшее дублирование кода и, следовательно, меньше давление icache и меньшее количество промахов icache.
GLib имеет кучу общих структур данных в нем, http://www.gtk.org/
В CCAN есть куча полезных fragmentов и таких http://ccan.ozlabs.org/
Ваш вариант 1 – это то, к чему будут стремиться самые старые программисты времени, возможно, соленые с небольшим количеством 2, чтобы сократить повторяющуюся типизацию, и просто возможно использовать несколько указателей на функцию для вкуса polymorphismа.
Существует общий вариант варианта 1, который более эффективен, поскольку он использует объединения для хранения значений в узлах списка, т. Е. Нет дополнительной косвенности. Недостатком этого является то, что список принимает только значения определенных типов и потенциально отбрасывает некоторую память, если типы имеют разные размеры.
Тем не менее, можно избавиться от union , используя вместо этого гибкий член массива, если вы готовы нарушить строгий псевдоним. Пример кода C99:
#include #include #include #include struct ll_node { struct ll_node *next; long long data[]; // use `long long` for alignment }; extern struct ll_node *ll_unshift( struct ll_node *head, size_t size, void *value); extern void *ll_get(struct ll_node *head, size_t index); #define ll_unshift_value(LIST, TYPE, ...) \ ll_unshift((LIST), sizeof (TYPE), &(TYPE){ __VA_ARGS__ }) #define ll_get_value(LIST, INDEX, TYPE) \ (*(TYPE *)ll_get((LIST), (INDEX))) struct ll_node *ll_unshift(struct ll_node *head, size_t size, void *value) { struct ll_node *node = malloc(sizeof *node + size); if(!node) assert(!"PANIC"); memcpy(node->data, value, size); node->next = head; return node; } void *ll_get(struct ll_node *head, size_t index) { struct ll_node *current = head; while(current && index--) current = current->next; return current ? current->data : NULL; } int main(void) { struct ll_node *head = NULL; head = ll_unshift_value(head, int, 1); head = ll_unshift_value(head, int, 2); head = ll_unshift_value(head, int, 3); printf("%i\n", ll_get_value(head, 0, int)); printf("%i\n", ll_get_value(head, 1, int)); printf("%i\n", ll_get_value(head, 2, int)); return 0; }
Старый вопрос, я знаю, но в случае, если он все еще представляет интерес: я экспериментировал с опцией 2) (macros перед процессором) сегодня, и придумал пример, который я буду вставлять ниже. Немного неуклюже, но не страшно. Код не полностью безопасен по типу, но содержит проверки работоспособности для обеспечения разумного уровня безопасности. И работа с сообщениями об ошибках компилятора при записи была умеренной по сравнению с тем, что я видел при запуске шаблонов C ++. Вероятно, вам лучше всего начать читать это на примере кода использования в «основной» функции.
#include #define LIST_ELEMENT(type) \ struct \ { \ void *pvNext; \ type value; \ } #define ASSERT_POINTER_TO_LIST_ELEMENT(type, pElement) \ do { \ (void)(&(pElement)->value == (type *)&(pElement)->value); \ (void)(sizeof(*(pElement)) == sizeof(LIST_ELEMENT(type))); \ } while(0) #define SET_POINTER_TO_LIST_ELEMENT(type, pDest, pSource) \ do { \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pSource); \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \ void **pvDest = (void **)&(pDest); \ *pvDest = ((void *)(pSource)); \ } while(0) #define LINK_LIST_ELEMENT(type, pDest, pSource) \ do { \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pSource); \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \ (pDest)->pvNext = ((void *)(pSource)); \ } while(0) #define TERMINATE_LIST_AT_ELEMENT(type, pDest) \ do { \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \ (pDest)->pvNext = NULL; \ } while(0) #define ADVANCE_POINTER_TO_LIST_ELEMENT(type, pElement) \ do { \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pElement); \ void **pvElement = (void **)&(pElement); \ *pvElement = (pElement)->pvNext; \ } while(0) typedef struct { int a; int b; } mytype; int main(int argc, char **argv) { LIST_ELEMENT(mytype) el1; LIST_ELEMENT(mytype) el2; LIST_ELEMENT(mytype) *pEl; el1.value.a = 1; el1.value.b = 2; el2.value.a = 3; el2.value.b = 4; LINK_LIST_ELEMENT(mytype, &el1, &el2); TERMINATE_LIST_AT_ELEMENT(mytype, &el2); printf("Testing.\n"); SET_POINTER_TO_LIST_ELEMENT(mytype, pEl, &el1); if (pEl->value.a != 1) printf("pEl->value.a != 1: %d.\n", pEl->value.a); ADVANCE_POINTER_TO_LIST_ELEMENT(mytype, pEl); if (pEl->value.a != 3) printf("pEl->value.a != 3: %d.\n", pEl->value.a); ADVANCE_POINTER_TO_LIST_ELEMENT(mytype, pEl); if (pEl != NULL) printf("pEl != NULL.\n"); printf("Done.\n"); return 0; }
Я использую указатели void (void *) для представления общих структур данных, определенных с помощью structs и typedefs. Ниже я расскажу о своей реализации lib, над которым я работаю.
При такой реализации вы можете думать о каждом новом типе, определенном с помощью typedef, как псевдоclass. Здесь этот псевдоclass – это набор исходного кода (some_type_implementation.c) и его заголовочный файл (some_type_implementation.h).
В исходном коде вам нужно определить структуру, которая будет представлять новый тип. Обратите внимание на структуру в исходном файле «node.c». Там я сделал указатель void на атрибут «info». Этот указатель может нести любой тип указателя (я думаю), но цена, которую вы должны заплатить, является идентификатором типа внутри структуры (тип int) и всеми коммутаторами, чтобы сделать дескриптор подсказки каждого определенного типа. Итак, в файле заголовка node.h «я определил тип« Node »(просто чтобы не набирать каждый раз узел struct), а также мне приходилось определять константы« EMPTY_NODE »,« COMPLEX_NODE »и« MATRIX_NODE » ».
Вы можете выполнить компиляцию вручную с помощью «gcc * .c -lm».
#include #include #define PI M_PI #include "complex.h" #include "matrix.h" #include "node.h" int main() { //testCpx(); //testMtx(); testNode(); return 0; }
#include #include #include #include "node.h" #include "complex.h" #include "matrix.h" #define PI M_PI struct node { int type; void* info; }; Node* newNode(int type,void* info) { Node* newNode = (Node*) malloc(sizeof(Node)); newNode->type = type; if(info != NULL) { switch(type) { case COMPLEX_NODE: newNode->info = (Complex*) info; break; case MATRIX_NODE: newNode->info = (Matrix*) info; break; } } else newNode->info = NULL; return newNode; } int emptyInfoNode(Node* node) { return (node->info == NULL); } void printNode(Node* node) { if(emptyInfoNode(node)) { printf("Type:%d\n",node->type); printf("Empty info\n"); } else { switch(node->type) { case COMPLEX_NODE: printCpx(node->info); break; case MATRIX_NODE: printMtx(node->info); break; } } } void testNode() { Node *node1,*node2, *node3; Complex *Z; Matrix *M; Z = mkCpx(POLAR,5,3*PI/4); M = newMtx(3,4,PI); node1 = newNode(COMPLEX_NODE,Z); node2 = newNode(MATRIX_NODE,M); node3 = newNode(EMPTY_NODE,NULL); printNode(node1); printNode(node2); printNode(node3); }
#define EMPTY_NODE 0 #define COMPLEX_NODE 1 #define MATRIX_NODE 2 typedef struct node Node; Node* newNode(int type,void* info); int emptyInfoNode(Node* node); void printNode(Node* node); void testNode();
#include #include #include #include "matrix.h" struct matrix { // Meta-information about the matrix int rows; int cols; // The elements of the matrix, in the form of a vector double** MTX; }; Matrix* newMtx(int rows,int cols,double value) { register int row , col; Matrix* M = (Matrix*)malloc(sizeof(Matrix)); M->rows = rows; M->cols = cols; M->MTX = (double**) malloc(rows*sizeof(double*)); for(row = 0; row < rows ; row++) { M->MTX[row] = (double*) malloc(cols*sizeof(double)); for(col = 0; col < cols ; col++) M->MTX[row][col] = value; } return M; } Matrix* mkMtx(int rows,int cols,double** MTX) { Matrix* M; if(MTX == NULL) { M = newMtx(rows,cols,0); } else { M = (Matrix*)malloc(sizeof(Matrix)); M->rows = rows; M->cols = cols; M->MTX = MTX; } return M; } double getElemMtx(Matrix* M , int row , int col) { return M->MTX[row][col]; } void printRowMtx(double* row,int cols) { register int j; for(j = 0 ; j < cols ; j++) printf("%g ",row[j]); } void printMtx(Matrix* M) { register int row = 0, col = 0; printf("\vSize\n"); printf("\tRows:%d\n",M->rows); printf("\tCols:%d\n",M->cols); printf("\n"); for(; row < M->rows ; row++) { printRowMtx(M->MTX[row],M->cols); printf("\n"); } printf("\n"); } void testMtx() { Matrix* M = mkMtx(10,10,NULL); printMtx(M); }
typedef struct matrix Matrix; Matrix* newMtx(int rows,int cols,double value); Matrix* mkMatrix(int rows,int cols,double** MTX); void print(Matrix* M); double getMtx(Matrix* M , int row , int col); void printRowMtx(double* row,int cols); void printMtx(Matrix* M); void testMtx();
#include #include #include #include "complex.h" struct complex { int type; double a; double b; }; Complex* mkCpx(int type,double a,double b) { /** Doc - {{{ * This function makes a new Complex number. * * @params: * |-->type: Is an interger that denotes if the number is in * | the analitic or in the polar form. * | ANALITIC:0 * | POLAR :1 * | * |-->a: Is the real part if type = 0 and is the radius if * | type = 1 * | * `-->b: Is the imaginary part if type = 0 and is the argument * if type = 1 * * @return: * Returns the new Complex number initialized with the values * passed *}}} */ Complex* number = (Complex*)malloc(sizeof(Complex)); number->type = type; number->a = a; number->b = b; return number; } void printCpx(Complex* number) { switch(number->type) { case ANALITIC: printf("Re:%g | Im:%g\n",number->a,number->b); break; case POLAR: printf("Radius:%g | Arg:%g\n",number->a,number->b); break; } } void testCpx() { Complex* Z = mkCpx(ANALITIC,3,2); printCpx(Z); }
#define ANALITIC 0 #define POLAR 1 typedef struct complex Complex; Complex* mkCpx(int type,double a,double b); void printCpx(Complex* number); void testCpx();
Надеюсь, я ничего не пропустил.
Я хотел бы запрограммировать мои будущие «низкоуровневые» проекты на C, а не на C ++ …
Зачем? Не хватает ли вашей цели компилятора C ++ или среды выполнения C ++?
Я использую вариант 2 для нескольких высокопроизводительных коллекций, и это занимает очень много времени, работая через объем макро логики, необходимый для того, чтобы сделать что-то действительно компилируемое и общее. Я делаю это исключительно для сырой производительности (игр). Используется подход X-macros .
Болезненная проблема, которая постоянно возникает в варианте 2, заключается в следующем: «Предполагая некоторое конечное число опций, таких как ключи с 8/16/32/64 бит, я делаю указанное значение константой и определяю несколько функций, каждый из которых имеет другой элемент этого набор значений, который может принимать константа, или я просто делаю его переменной-членом? ” Первый означает менее эффективный кеш команд, так как у вас много повторяющихся функций с одним или двумя номерами, а последнее означает, что вам нужно ссылаться на выделенные переменные, которые в худшем случае означают промах кэша данных. Поскольку вариант 1 является чисто динамическим, вы будете делать такие переменные-члены, даже не задумываясь об этом. Это действительно микро-оптимизация.
Также учитывайте компромисс между возвращающими указателями и значениями: последний наиболее эффективен, когда размер элемента данных меньше или равен размеру указателя; тогда как если элемент данных больше, то, скорее всего, лучше возвращать указатели, чем принудительно копировать большой объект, возвращая значение.
Я настоятельно рекомендую перейти к Варианту 1 в любом сценарии, где вы не на 100% уверены, что производительность коллекции будет вашим узким местом. Даже при использовании Варианта 2 моя библиотека коллекций предоставляет «быструю настройку», которая похожа на вариант 1, то есть использование значений void * в моем списке и карте. Этого достаточно для 90%% обстоятельств.