Очень простая карта implemention в C (для кэширования цели)?
Обновление : Как сказано в комментариях, Hal не поддерживается в недавних дистрибутивах, стандарт теперь является udev, Вот небольшой пример, который использует бойкий цикл и udev, я сохраняю версию Hal по историческим причинам.
Это в основном , пример в pyudev документации , адаптированный для работы с более старыми версиями, и с бойким циклом, замечает, что фильтр должен быть настроен для определенной необходимости:
import glib
from pyudev import Context, Monitor
try:
from pyudev.glib import MonitorObserver
def device_event(observer, device):
print 'event {0} on device {1}'.format(device.action, device)
except:
from pyudev.glib import GUDevMonitorObserver as MonitorObserver
def device_event(observer, action, device):
print 'event {0} on device {1}'.format(action, device)
context = Context()
monitor = Monitor.from_netlink(context)
monitor.filter_by(subsystem='usb')
observer = MonitorObserver(monitor)
observer.connect('device-event', device_event)
monitor.start()
glib.MainLoop().run()
Старая версия с Hal и d-шиной:
можно использовать привязку D-шины и слушать DeviceAdded и DeviceRemoved сигналы. Необходимо будет проверить возможности Добавленного устройства для выбора устройств хранения только.
Вот небольшой пример, можно удалить комментарии и попробовать его.
import dbus
import gobject
class DeviceAddedListener:
def __init__(self):
необходимо соединиться с Hal Manager, использующим Системную шину.
self.bus = dbus.SystemBus()
self.hal_manager_obj = self.bus.get_object(
"org.freedesktop.Hal",
"/org/freedesktop/Hal/Manager")
self.hal_manager = dbus.Interface(self.hal_manager_obj,
"org.freedesktop.Hal.Manager")
И необходимо соединить слушателя сигналов, Вам интересно на, в этом случае DeviceAdded.
self.hal_manager.connect_to_signal("DeviceAdded", self._filter)
я использую фильтр на основе возможностей. Это примет любой volume и будет звонить do_something с тем, если, можно прочитать документацию Hal для нахождения более подходящих запросов для потребностей или большей информации о свойствах устройств Hal.
def _filter(self, udi):
device_obj = self.bus.get_object ("org.freedesktop.Hal", udi)
device = dbus.Interface(device_obj, "org.freedesktop.Hal.Device")
if device.QueryCapability("volume"):
return self.do_something(device)
функция В качестве примера, которая показывает некоторую информацию об объеме:
def do_something(self, volume):
device_file = volume.GetProperty("block.device")
label = volume.GetProperty("volume.label")
fstype = volume.GetProperty("volume.fstype")
mounted = volume.GetProperty("volume.is_mounted")
mount_point = volume.GetProperty("volume.mount_point")
try:
size = volume.GetProperty("volume.size")
except:
size = 0
print "New storage device detectec:"
print " device_file: %s" % device_file
print " label: %s" % label
print " fstype: %s" % fstype
if mounted:
print " mount_point: %s" % mount_point
else:
print " not mounted"
print " size: %s (%.2fGB)" % (size, float(size) / 1024**3)
if __name__ == '__main__':
from dbus.mainloop.glib import DBusGMainLoop
DBusGMainLoop(set_as_default=True)
loop = gobject.MainLoop()
DeviceAddedListener()
loop.run()
7 ответов
Вот очень простой и наивный вариант
- Фиксированный размер сегмента
- Без операции удаления
- вставляет заменяет ключ и значение и может при желании освободить их
:
#include <string.h>
#include <stdlib.h>
#define NR_BUCKETS 1024
struct StrHashNode {
char *key;
void *value;
struct StrHashNode *next;
};
struct StrHashTable {
struct StrHashNode *buckets[NR_BUCKETS];
void (*free_key)(char *);
void (*free_value)(void*);
unsigned int (*hash)(const char *key);
int (*cmp)(const char *first,const char *second);
};
void *get(struct StrHashTable *table,const char *key)
{
unsigned int bucket = table->hash(key)%NR_BUCKETS;
struct StrHashNode *node;
node = table->buckets[bucket];
while(node) {
if(table->cmp(key,node->key) == 0)
return node->value;
node = node->next;
}
return NULL;
}
int insert(struct StrHashTable *table,char *key,void *value)
{
unsigned int bucket = table->hash(key)%NR_BUCKETS;
struct StrHashNode **tmp;
struct StrHashNode *node ;
tmp = &table->buckets[bucket];
while(*tmp) {
if(table->cmp(key,(*tmp)->key) == 0)
break;
tmp = &(*tmp)->next;
}
if(*tmp) {
if(table->free_key != NULL)
table->free_key((*tmp)->key);
if(table->free_value != NULL)
table->free_value((*tmp)->value);
node = *tmp;
} else {
node = malloc(sizeof *node);
if(node == NULL)
return -1;
node->next = NULL;
*tmp = node;
}
node->key = key;
node->value = value;
return 0;
}
unsigned int foo_strhash(const char *str)
{
unsigned int hash = 0;
for(; *str; str++)
hash = 31*hash + *str;
return hash;
}
#include <stdio.h>
int main(int argc,char *argv[])
{
struct StrHashTable tbl = {{0},NULL,NULL,foo_strhash,strcmp};
insert(&tbl,"Test","TestValue");
insert(&tbl,"Test2","TestValue2");
puts(get(&tbl,"Test"));
insert(&tbl,"Test","TestValueReplaced");
puts(get(&tbl,"Test"));
return 0;
}
Реализация хеш-таблицы Кристопера Кларка очень проста. Это более 100 строк, но ненамного.
Код Кларка, кажется, попал в Библиотеку параллелизма Google в качестве примера распараллеливания.
std :: map в C ++ - это красно-черное дерево под капотом; как насчет использования существующей реализации красно-черного дерева в C ? Тот, который я связал, больше похож на 700 LOC, но он довольно хорошо прокомментирован и выглядит нормальным после беглого взгляда, который я на него бросил. Вы, наверное, сможете найти других; это было первое попадание в Google для "красно-черного дерева C".
Если вы не требовательны к производительности, вы также можете использовать несбалансированное двоичное дерево или минимальную кучу или что-то в этом роде. Со сбалансированным двоичным деревом вам гарантирован поиск O (log n); с несбалансированным деревом наихудший случай поиска - O (n) (для патологического случая, когда узлы вставляются по порядку,
Не фрагмент кода, а высокопроизводительный механизм распределенного кэширования.
Интерфейсы и реализации C Дейва Хэнсона включают красивую хеш-таблицу, а также множество других полезных модулей. Хеш-таблица занимает 150 строк, но это включает управление памятью, функцию сопоставления более высокого порядка и преобразование в массив. Программа бесплатна, и книгу стоит покупать.
Здесь нашел реализацию: файл c и файл h , которые довольно близки к тому, что вы просили. Лицензия W3C
Не ленив, но очень разумно избегать написания этого материала.
Как эта библиотека никогда не использовал ее сам, но, похоже, она заявляет, что делает то, о чем вы просите.
1128097]