Intereting Posts
Поместите операнды сначала в getopt () Buildroot: создайте только один пакет как общий, так и статический lib, все остальные доступны только Как протестировать ввод является нормальным Как получить указатель на двоичный раздел в MSVC? Могу ли я полагаться на% (modulo) оператора в C для отрицательных чисел? Инструмент для объяснения кода C найти heapified массив при преобразовании его в отсортированный массив, общее количество обменов максимально возможно Использование make для кросс-платформенной компиляции Как создать образ загрузочного компакт-диска с моим kernelм? Как работает унарное дополнение на C-указателях? Использование структур с атрибутом, упакованным при анализе двоичных данных Есть ли простой способ повысить производительность этой функции спин-блокировки? Пример Android NDK Wi-Fi Байт Count для Struct, не представляющий правильную сумму. Объяснение алгоритма для установки, очистки и тестирования одного бита

Типовые общие структуры данных в обычном C?

Я сделал намного больше программирования на С ++, чем программирование «простого старого С». Одна вещь, которую я очень скучаю, когда программирование в простой C – это типовые структуры данных, которые предоставляются в C ++ с помощью шаблонов.

Для определенности рассмотрим общий список, связанный по отдельности. В C ++ просто определить свой собственный class шаблонов, а затем создать его для типов, которые вам нужны.

В C я могу придумать несколько способов реализации общего одноуровневого списка:

  1. Запишите типы связанных ссылок и поддерживающие процедуры один раз, используя указатели void, чтобы обойти систему типов.
  2. Запишите macros препроцессора, введя необходимые имена типов и т. Д., Чтобы создать версию структуры данных и поддерживающие процедуры типа.
  3. Используйте более сложный автономный инструмент для генерации кода для типов, которые вам нужны.

Мне не нравится вариант 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».

Исходный файл main.c

 #include  #include  #define PI M_PI #include "complex.h" #include "matrix.h" #include "node.h" int main() { //testCpx(); //testMtx(); testNode(); return 0; } 

Исходный файл node.c

 #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); } 

Файл заголовка node.h

 #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(); 

исходный файл matrix.c

 #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); } 

Файл заголовка matrix.h

 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(); 

Исходный файл complex.c

 #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); } 

complex.h Файл заголовка

 #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%% обстоятельств.