c - 文件路径字符串的数据结构查找插入删除
问题描述
我监视文件系统事件,并使用路径作为键存储事件,当发生路径的多个事件时,我需要找到前一个事件并将它们合并。
根据路径存储和查找文件系统事件的数据结构和算法。
解决方案
我将使用一个结构来描述每个事件,包括作为 C99 灵活数组成员的路径:
struct event {
/* Event queue pointers */
struct event *queue_prev;
struct event *queue_next;
/* Event identifying bit mask */
size_t mask;
/* Path hash table */
struct event *hash_next;
size_t hash;
unsigned char path[];
};
事件队列本身是一个双向链表,以避免在根据路径删除事件时必须遍历整个链表。
每个哈希表槽是一个单链事件列表。这是因为我们希望这些链很短,否则哈希表效率不高。
我不确定哪个哈希函数效果最好,但我会从好的旧 DJB2 开始:
size_t djb2(const unsigned char *src)
{
size_t hash = 5381;
while (*src)
hash = ((hash << 5) + hash) ^ (*(src++));
return hash;
}
事件队列和路径哈希表将使用
struct event_queue {
/* Event queue */
size_t events;
struct event *first; /* First event in queue */
struct event *last; /* Last event in queue */
/* Path hash table */
size_t slots;
struct event *slot;
};
由于每个路径哈希表槽的成本只是一个指针,因此最好从一个相对较大的哈希表开始,比如 256 个槽。这不是限制;它只是变得更慢(因为需要遍历插槽链)。它可能应该是一个可配置的设置。要初始化事件队列,我会使用
int event_queue_init(struct event_queue *queue, size_t slots)
{
if (!queue || slots < 1)
return errno = EINVAL;
/* The queue itself is empty. */
queue->events = 0;
queue->first = NULL;
queue->last = NULL;
queue->slots = slots;
queue->slot = calloc(slots, sizeof queue->slot[0]);
/* Note: In Linux, queue->slot is now full of NULL pointers.
This may not be true on other OSes! */
if (!queue->slot)
return errno = ENOMEM;
}
在运行时调整哈希表的大小可能是一个好主意,即使它不是绝对必要的:
int event_queue_resize(struct event_queue *queue, size_t slots)
{
size_t i, n;
if (!queue || slots < 1)
return errno = EINVAL;
struct event *slot[] = calloc(slots, sizeof slot[0]);
if (!slot)
return errno = ENOMEM;
/* Note: In Linux, slot is now full of NULL pointers.
This may not be true on all OSes! */
n = 0;
i = queue->slots;
while (i-->0) {
struct event *next = queue->slot[i];
queue->slot[i] = NULL;
while (next) {
struct event *curr = next;
size_t slotnum = curr->hash % slots;
next = next->hash_next;
n++;
curr->hash_next = slot[slotnum];
slot[slotnum] = curr;
}
}
free(queue->slot);
queue->slots = slots;
queue->slot = slot;
queue->events = n;
}
即使有排队的事件,调整哈希表的大小也是安全的,因为事件队列指针不受哈希表调整大小的影响。
要将事件附加到队列中,如果已排队,请修改相同路径的现有事件:
int event_append(struct event_queue *queue,
const unsigned char *path,
size_t mask)
{
if (!queue || !path)
return errno = EINVAL;
const size_t hash = djb2(path);
const size_t slotnum = hash % queue->slots;
struct event *ev = queue->slot[slotnum];
while (ev) {
if (ev->hash == hash && !strcmp(ev->path, path)) {
/* Event already queued. */
ev->mask |= mask;
return 0;
} else {
ev = ev->hash_next;
}
}
const size_t pathlen = strlen(path);
ev = malloc(sizeof (struct event) + pathlen + 1);
if (!ev)
return errno = ENOMEM;
memcpy(ev->path, path, pathlen + 1); /* Include '\0' at end */
ev->hash = hash;
ev->mask = mask;
/* Prepend to hash table */
ev->hash_next = queue->slot[slotnum];
queue->slot[slotnum] = ev;
/* Append to queue */
if (!queue->first) {
ev->queue_prev = NULL;
ev->queue_next = NULL;
queue->first = ev;
queue->last = ev;
queue->events = 1;
} else {
ev->queue_prev = queue->last;
ev->queue_next = NULL;
queue->last->queue_next = ev;
queue->last = ev;
queue->events++;
}
return 0;
}
要弹出队列中的下一个事件:
struct event *event_next(struct event_queue *queue)
{
if (!queue)
return NULL;
struct event *ev = queue->first;
if (!ev)
return NULL;
queue->first = ev->queue_next;
if (!queue->first) {
queue->last = NULL;
queue->events = 0;
} else {
queue->first->queue_prev = NULL;
}
ev->queue_prev = NULL;
ev->queue_next = NULL;
queue->events--;
/* Remove from the hash table */
struct event **ptr = queue->slot + ev->hash % queue->slots;
struct event *evt = *ptr;
while (evt) {
if (evt == ev) {
*ptr = ev->hash_next;
break;
} else {
ptr = &(evt->hash_next);
evt = *ptr;
}
}
return ev;
}
要取消特定路径上的事件:
struct event *event_dequeue(struct event_queue *queue,
const unsigned char *path)
{
if (!queue || !path)
return NULL;
const size_t hash = djb2(path);
const size_t slotnum = hash % queue->slots;
struct event **ptr = queue->slot + slotnum;
struct event *ev = *ptr;
while (ev) {
if (ev->hash == hash && !strcmp(ev->path, path)) {
/* Remove from event queue */
if (ev->queue_prev)
ev->queue_prev->queue_next = ev->queue_next;
if (ev->queue_next)
ev->queue_next->queue_prev = ev->queue_prev;
if (queue->first == ev)
queue->first = ev->queue_next;
if (queue->last == ev)
queue->last = ev->queue_prev;
queue->events--;
/* Remove from hash table slot */
*ptr = ev->next;
/* Done. */
return ev;
}
ptr = &(ev->next);
ev = *ptr;
}
return NULL;
}
这些只是向您展示想法的即兴实现;我相信你可以更好地实现它们。
值得注意的是,您可以仅使用queue_prev
和指针在队列中向上/向下移动事件,但如果您更改其中任何一个queue_next
,您还需要更新队列first
和指针。last
对于线程安全操作,我会在 , 中使用 apthread_mutex_t
在struct event_queue
操作期间持有。每个操作(哈希表调整大小除外)花费的时间太少,以至于增加的代码复杂性允许并发访问是不值得的。
推荐阅读
- dart - TextStyle 未应用于 ListView itemBuilder
- c++ - 识别 C++ 中的特殊字符
- reactjs - 如何在使用 Express/Webpack/React 应用程序部署到 Heroku 后修复“bundle.js 404(未找到)”?
- php - php上的多输入foreach
- r - 在 R 中保存文件
- c++ - 分段错误(核心转储) - 线程二叉搜索树
- javascript - 高图表。角。在事件点击时使用新系列重绘图表
- ios - 在 Swift 4 中使用 draw-move for 循环制作动画
- sql - SQL Server:如何使用 select top (@number) 语法?
- xamarin.forms - 为什么在使用 ReactiveContentPage 时会出现“不一致的可访问性”问题?