Generic C для двоичных деревьев

Question

Как можно писать общие c?

Я начал писать коллекцию сбалансированных деревьев (scapegoat, splay, aa и т. Д.) И найти много общего. Пример - функция destroy, найденная ниже.

Может ли такая функция и аналогичная быть определена с помощью указателей void, не вызывая «ошибки указателя void * указателя»?

Пример уничтожить функцию

void splay_node_linked_destroy(SplayNode **this) { 
72 if(*this == NULL) { 
73  return; 
74 } 
75 SplayNode *root = (*this)->root, *previous, *next; 
76 while(root) { 
77  if(previous == root->parent) { 
78  // todo use funcs for comparisons for generic 
79  if(root->left) { 
80   next = root->left; 
81  } else if(root->right) { 
82   next = root->right; 
83  } else { 
84   next = root->parent; 
85  } 
86  } else if(previous == root->left) { 
87  if(root->right) { 
88   next = root->right; 
89  } else { 
90   next = root->parent; 
91  } 
92  } else { 
93  next = root->parent; 
94  } 
95  previous = root; 
96  if(next == root->parent) { 
97  splay_node_destroy(&root); 
98  // todo use callback here to make generic 
99  } 
100  root = next; 
101 } 
102 } 

Answer 1

Вот пример типичного дерева уничтожить:

// GenericTree.h 

void genericTreeDestroy(void *treeNode, void (*fUserFree)(void *)); 

// GenericTree.c 
typedef struct TREE_NODE { 
    struct TREE_NODE *left; 
    struct TREE_NODE *right; 
}; 
void genericTreeDestroy(struct TREE_NODE *treeNode, void (*fUserFree)(void *)) 
{ 
    if (treeNode->left) genericTreeDestroy(treeNode->left, fUserFree); 
    if (treeNode->right) genericTreeDestroy(treeNode->right, fUserFree); 
    if (fUserFree) fUserFree(treeNode); 
    free(treeNode); 
} 

// UserStuff.c 
#include "GenericTree.h" 
typedef struct MY_TREE_NODE { 
    struct MY_TREE_NODE *left; 
    struct MY_TREE_NODE *right; 
    int some_value; 
    char *name; 
}; 
void my_freedata(struct MY_TREE_NODE *node); 

void main(void) 
{ 
    struct MY_TREE_NODE *myTree= calloc(1,sizeof(struct MY_TREE_NODE)); 
    myTree->name= malloc(strlen("Hello world")+1); 
    genericTreeDestroy(myTree, my_freedata); 
} 

void my_freedata(struct MY_TREE_NODE *node) 
{ 
    free(node->name); 
} 

Фокус в том, что ВСЕ деревья должны начинаться с левого и правого элементов. Файл .h определяет genericTreeDestroy с параметром void *, а файл .c определяет его как struct TREE_NODE *. Таким образом, пользователь может передать ему любой тип узла дерева.

Далее пользователь может определить любой тип узла дерева (если он существ с левым и правым элементом) и вызвать общую функцию для ее уничтожения. Генерирующей функции может быть предоставлена ​​функция для любой очистки типа определенного пользователем узла или null, если это не требуется.

Точно так же вы можете определить другие функции. Вот функция поиска:

// .h 
void *generic_tree_search (void *tree, void *value, int (*fUserCmp)(void *value, void *node)); 

// .c 
void *generic_tree_search (struct TREE_NODE *treeNode, void *value, int (*fUserCmp)(void *value, void *node)) 
{ 
    while (treeNode) { 
     switch (fUserCmp(value,treeNode) { 
     case -1: if (treeNode->left) treeNode= treeNode->left; else return(0); break; 
     case 0: return(treeNode); 
     case +1: if (treeNode->right) treeNode= treeNode->right; else return(0); break; 
     } 
    } 
    return(0); 
} 

Answer 2

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

Один трюк состоит в том, чтобы использовать указатели void и создавать API-интерфейсы таким образом, чтобы вы использовали функции-обертки для перевода указателей на их фактические типы и, таким образом, с такой же проверкой типов и безопасности, как это допускает C. Единственная сложная часть заключается в том, что компилятор обычно не помогает вам передавать информацию о типе вашей реализации, хотя некоторые компиляторы поддерживают расширение typeof(), что позволяет писать макросы обертки, которые будут выполнять эту работу за вас.

Некоторые примеры:

Этот пример, как представляется, использовать typeof() так, как я предложил: https://github.com/troydhanson/uthash/tree/master/src

Это интересный препроцессор макросов на основе библиотеки вдохновлен стандартной библиотеки шаблонов: http://sglib.sourceforge.net/

Это, пожалуй, один из наиболее полных примеров общих алгоритмов для общих типов в C, хотя он немного уродлив и очень многословен и, возможно, не так эффективен: http://home.gna.org/gdsl/

Этот ответ дает хороший совет, хотя он использует встроенный union вместо указателя void. union идеально подходит, если вы знаете заранее, что будет все возможные типы данных:
https://stackoverflow.com/a/2891570/816536

Еще один интересный способ создания структур высокого уровня (например, списки) из общих структур данных, что может быть описано как метод наизнанку (мне тоже нравится!). То, что я бы рассмотрел, каноническая реализация этой техники наименьшего изящества находится в 4.4BSD queue(3) и tree(3) макросов с некоторыми более читаемыми объяснениями и примеры здесь:

• http://unixjunkie.blogspot.ca/2006/12/lists-and-queues.html
• http://blog.jasonish.org/2006/08/19/tailq-example/
• http://hackab.it/2014/01/generic-linked-list-in-c/

Этого ответ описывает зависимый метод сильно предварительно процессора, хотя это требует, чтобы вы либо заранее знаете, какие будут все типы объектов, либо заставляют пользователя писать промежуточный заголовок для своего конкретного типа данных: https://stackoverflow.com/a/10430893/816536

Смотрите также ответы:

• https://stackoverflow.com/a/668567/816536
• https://stackoverflow.com/a/13225017/816536
• https://stackoverflow.com/a/28139957/816536
• https://stackoverflow.com/a/649673/816536