Несколько вопросов о моем модульном коде с использованием void * как динамический тип данных в C
https://stackoverflow.com/questions/2395216
-
25-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Несколько дней назад я опубликовал этот вопрос и все предложили мне использовать void*, который я сделал. Я думаю, что некоторые из них также указали на несколько вещей, которые мне нужно было позаботиться о том, но я не уверен, что именно они были. Однако у меня есть несколько проблем с этим ...
Я не собираюсь публиковать все свой код, где потому что это довольно большое, вместо этого я опубликую то, что я думаю, важно и, надеюсь, вам достаточно, чтобы вы могли помочь мне.
Моя структура хеш-стола похожа на это:
typedef void * HashKey;
typedef void * HashValue;
typedef struct sHashItem {
HashKey key;
HashValue value;
char status;
} HashItem;
typedef struct sHashTable {
HashItem *items;
int count;
float load;
int size;
Bool (*compare)(HashKey, HashKey);
unsigned (*hash)(void *);
} HashTable;
Подпись для моей функции вставки идет так:
Bool hashInsert(HashTable * const table, HashKey key, HashValue value);
И где-то внутри этой функции, когда я нахожу свободное ведро в хэш-столе, я делаю это:
table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;
Все это представляет несколько проблем:
1) Как вы можете видеть выше, я просто устанавливая каждую клавишу / значение пары свободного ведра в тот же указатель, переданный в виде ключа / значения hashInsert Функциональные аргументы. Это представляет проблему, поскольку вы, возможно, уже заметили ... Например, что-то подобное:
char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);
И если вход - «Keya», а затем «Keyb», оба будут иметь «Keyb» в качестве клавиш ведра. То же самое относится то же самое относится к значению, а не только ключевым ключом, поскольку они в основном тот же тип, потому что я хочу иметь свой код полностью модульной, для любого типа данных.
Как я могу решить это?
Мой первый, чтобы использовать strdup(str) и пропустите это к hashInsert функция. Это решило бы проблему. И так как это было обработано в главном коде, я мог легко использовать malloc() Тоже для любого другого типа данных мне нужно пройти как значение (ключ, вероятно, всегда будет строкой или INT).
Но это решение представляет еще одну проблему ...
2) Как мне освободить эту выделенную память? Конечно, он был распределен «главным программистом», а не «программистом модуля Hash Table Module», так что «главный программист» должен освободить его в главном коде, верно? Однако это не похоже на модульный код для меня.
Мой код также имеет hashDestroy Функция, чтобы освободить всю выделенную память. Но как я могу использовать эту функцию, чтобы освободить все? Я не могу просто повторить каждый ключ / значение и использовать free() на них потому, что, возможно, некоторые из них не были malloc'd любым программистом в первом месте, и мне не нужно их освободить.
Как я могу узнать, какие из них мои hashDestroy Должен бесплатно, а какие это не должно?
3) Чтобы закончить, я думаю, я также могу бросить эту проблему в смесь ... в точке один, мое предложение было использовать strdup() или malloc Чтобы «исправить» эту конкретную проблему (при введении другой) но это также не выглядит очень модульной для меня. Это распределение памяти должно быть выполнено в коде модуля HASH Table, а не в основном коде по «главным программистым».
Как вы предлагаете, я решаю это? Я имею в виду, что типы данных могут быть чем угодно и в то время как использование strdup() Помогает много, он работает только для струн. Что, если мне нужно выделить память для некоторой конкретной структуры или просто int?
Извините за большой пост, но я думаю, что эти вопросы все связаны, и мне нужна помощь, выясняя их, поскольку мое знание C не такая экстремальная. Я только недавно узнал о void* так...
Решение
WOW: Это будет полностью ответить. Тем не менее, один из ключевых вещей, которые вам понадобится, это размер того, что вы обрабатываете - это нормально использовать пустотный указатель, но вам нужно знать, насколько большой объект, адрес которого вы получаете.
...] Каждый предложил мне использовать пустоту *, что я сделал. [...
Моя структура хеш-стола похожа на это:
typedef void * HashKey;
typedef void * HashValue;
typedef struct sHashItem {
HashKey key;
HashValue value;
char status;
} HashItem;
typedef struct sHashTable {
HashItem *items;
int count;
float load;
int size;
Bool (*compare)(HashKey, HashKey);
unsigned (*hash)(void *);
} HashTable;
Вы, вероятно, понадобится size_t key_sz; и а size_t val_sz; член HashItemОтказ Ваш указатель хеш-функции должен будет знать, насколько большой ключ для хеширования.
Я в двух разумах о том, что должен быть хешьяным ключом. Отчасти зависит от того, как вы используете этот материал. Похоже, вы хотите:
- Учитывая это ключевое значение моего выбора,
- Храните / верните эти данные, связанные с ним.
В этом случае вам, вероятно, также нужно хранить номер хеша где-то в HashItem; Это значение, возвращенное вашей функцией HASHING - видимо, без знака без знака. Я не уверен, что подпись на compare функция (указатель функции) должна быть; Я подозрительно, что ему следует либо принимать пару значений Hashkey и размера, либо, возможно, пару указателей Hashitem.
Подпись для моей функции вставки идет так:
Bool hashInsert(HashTable * const table, HashKey key, HashValue value);
И где-то внутри этой функции, когда я нахожу свободное ведро в хэш-столе, я делаю это:
table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;
Все это представляет несколько проблем:
1) Как вы можете видеть выше, я просто устанавливая пару каждую клавишу / значение свободного ведра в тот же указатель, прошедший в качестве клавиши / значения Hashinsert Function Arguments. Это представляет проблему, поскольку вы, возможно, уже заметили ... Например, что-то подобное:
char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);
Ключ к использованию void * это пропустить адреса вокруг. Литье должно быть ненужным в C. Вам также нужно пройти размер вещей. Следовательно:
Bool hashInsert(HashTable * const table, HashKey key, size_t key_sz,
HashValue value, size_t val_sz);
char str[50];
scanf("%s%*c", str);
int value = 5;
hashInsert(t1, str, strlen(str)+1, &value, sizeof(value));
Внутри вы будете копировать данные - не используя «Strdup ()», поскольку вы не знаете, что в нем не интерьер Nul ' 0'.
И если вход - «Keya», а затем «Keyb», оба будут иметь «Keyb» в качестве клавиш ведра. То же самое относится то же самое относится к значению, а не только ключевым ключом, поскольку они в основном тот же тип, потому что я хочу иметь свой код полностью модульной, для любого типа данных.
Как я могу решить это?
Вы должны определить, кто владеет тем, что и ли (и как) контейнер копирует данные. В C ++ контейнеры делают копию того, что они хранят.
Моя первая мысль - использовать Strdup (STR) и пропустите, что к функции Hashinsert. Это решило бы проблему. И поскольку это было обработано в главном коде, я мог легко использовать Malloc () также для любого другого типа данных, который мне нужно пройти как значение (ключ, вероятно, всегда будет строкой или INT).
Вы не можете использовать «Strdup ()», потому что в целом, ни значения, ни ключи не являются строками. Если они всегда строки, почему вы используете «void *» вместо «char * '?
Вы можете решить скопировать значение и ключ - до тех пор, пока вы знаете размеры.
Но это решение представляет еще одну проблему ...
2) Как мне освободить эту выделенную память? Конечно, он был распределен «главным программистом», а не «программистом модуля Hash Table Module», так что «главный программист» должен освободить его в главном коде, верно? Однако это не похоже на модульный код для меня.
Мой код также имеет функцию HASHDESTROY, чтобы освободить всю выделенную память. Но как я могу использовать эту функцию, чтобы освободить все? Я не могу просто повторить каждый ключ / ценность и использовать бесплатные () на них, потому что, возможно, некоторые из них не были Mallocd любой программистом в первом месте, и мне не нужно их освободить.
Как я могу узнать, какие из них мой хэшдеструй должен освободить, а какие это не должно?
Вы не можете. Вы должны определить политику и только в том случае, если эта политика позволяет вам делать уничтожение, если вы это сделаете. Если вы копируете все, у вас легко. Если вы ничего не скопируете, у вас есть другое легко (возможно, проще), но ваши потребители имеют ад, потому что им нужна структура для отслеживания того, что им нужно выпустить - возможно, хешированный список ...
3) Чтобы закончить, я думаю, я также могу выбросить эту проблему в смесь ... в точке один, мое предложение должно было использовать strdup () или malloc, чтобы «исправить» эту конкретную проблему (при введении другой), но также Я выглядишь очень модульно для меня. Это распределение памяти должно быть выполнено в коде модуля HASH Table, а не в основном коде по «главным программистым».
Да ... Это в основном моя рекомендация.
Как вы предлагаете, я решаю это? Я имею в виду, что типы данных могут быть чем угодно, и хотя использование Strdup () много помогает, он работает только для строк. Что, если мне нужно выделить память для некоторой конкретной структуры или просто int?
Обратите внимание, что копирование только делает мелкие копии. Если структуры, которые вы копируете, содержат указатели, то код дублирования будет скопировать только указатель, а не указанный на данные.
Таким образом, общее решение потребует некоторой функции копирования. Возможно, вам придется требовать, чтобы пользователь дал вам функцию «выпуска», которая освобождает память в элементе. Возможно, вам понадобится предоставить вам уже полностью выделенные данные. Вам нужно подумать о том, кому принадлежит то, что возвращает функцию поиска - это все еще 'в таблице хэш или его удалено. Посмотрите на систему C ++ STL - это вообще говоря, делает отличную работу и моделирование ваших требований к тому, что требует, может иметь смысл. Но помните, что C ++ имеет конструкторы и деструкторы, чтобы помочь ему.
Другие советы
Я бы построен все данные, и позволить клиенту файлы хеш-функции регистрируют item_free() Функция при хэш-таблице время инициализации. Таким образом, это зависит от «главного программиста», как это справиться.
Хммм, из того, что я вижу в своем примере, проблема не является тяжелыми столкновениями (хотя вы, кажется, имеете эту проблему), именно то, как управлять памятью элементов, хранящихся в таблице. Я думаю, что стандартный способ выполнения такого рода - заставить пользователя структуры данных (Hashtable) выполнять работу выделения пространства для всех материалов, которые собираются поставить в таблицу. Hashtable должен только беспокоиться о указателях. Предположим, вы делаете выделение, а затем скопируйте в структуру данных: как пользователь узнает, как освободить память, когда элемент удаляется из ужасного?
Существует два общих решения для решения столкновений в хэш-хесфере:
- Вместо этого используйте следующее свободное ведро.
- Ведро хранит связанный список, поэтому несколько элементов могут храниться в одном ведре.
С любым из них вопрос, когда он освобождает то, что никогда не возникает, поскольку все виды данных выделяются либо на хеш-таблице, либо к клиенту HASH Table. Если вы все еще любопытно, краткий ответ на эту дилемму должен использовать умные указатели.
Для реализации хэш-стола нам нужен набор ведер. И поскольку несколько элементов могут хвоститься к тому же ведрю, каждое ведро требует связанного списка.
Делает
HashItem *items;
выполнить второе требование выше?
Из вашего объяснения, его не ясно, если это делает.
Для отличного примера см. В разделе K & R 6.6. связь Где название = hashkey и defn = hashvalue.alt text http://www.goldfish.org/book/the%20c%20programming%20Language%20-%20k&r/pic64.gif.
