From 088bc4628bbf6bdc005adf8054549e3798306f74 Mon Sep 17 00:00:00 2001 From: Steven Barth Date: Mon, 2 Jun 2008 15:35:22 +0000 Subject: [PATCH] add the fastindex module --- libs/fastindex/Makefile | 12 + libs/fastindex/src/fastindex.c | 380 +++++++++++++++++++++ libs/fastindex/src/list.h | 601 +++++++++++++++++++++++++++++++++ 3 files changed, 993 insertions(+) create mode 100644 libs/fastindex/Makefile create mode 100644 libs/fastindex/src/fastindex.c create mode 100644 libs/fastindex/src/list.h diff --git a/libs/fastindex/Makefile b/libs/fastindex/Makefile new file mode 100644 index 000000000..560a35283 --- /dev/null +++ b/libs/fastindex/Makefile @@ -0,0 +1,12 @@ +include ../../build/config.mk +include ../../build/gccconfig.mk + +%.o: %.c + $(COMPILE) $(LUA_CFLAGS) $(FPIC) -c -o $@ $< + +compile: src/fastindex.o + mkdir -p dist/usr/lib/lua/luci + $(LINK) $(SHLIB_FLAGS) -o dist/usr/lib/lua/luci/fastindex.so src/fastindex.o $(LUA_SHLIBS) + +clean: + rm -f src/*.o diff --git a/libs/fastindex/src/fastindex.c b/libs/fastindex/src/fastindex.c new file mode 100644 index 000000000..ab78c0935 --- /dev/null +++ b/libs/fastindex/src/fastindex.c @@ -0,0 +1,380 @@ +/* + * fastindex - fast lua module indexing plugin + * Copyright (C) 2008 Felix Fietkau + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 + * as published by the Free Software Foundation + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + */ + +#include +#include +#include + +#ifndef _POSIX_C_SOURCE +#define _POSIX_C_SOURCE /* XXX: portability hack for timestamp */ +#endif + +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include "list.h" + +#define MODNAME "fastindex" +#define PATTERN "/*.lua" +#define DEFAULT_BUFLEN 1024 + +//#define DEBUG 1 + +#ifdef DEBUG +#define DPRINTF(...) fprintf(stderr, __VA_ARGS__) +#else +#define DPRINTF(...) do {} while (0) +#endif + +/** + * list_for_each_offset - iterate over a list, start with the provided pointer + * @pos: the &struct list_head to use as a loop cursor. + * @head: the head for your list. + */ +#define list_for_each_offset(pos, head, offset) \ + for (pos = (offset)->next; pos != (offset); \ + pos = ((pos->next == (head)) && ((offset) != (head)) ? (head)->next : pos->next)) + +static char *namespace = NULL; + +struct fastindex_entry { + struct list_head list; + time_t timestamp; + int checked; + char *name; +}; + +struct fastindex_pattern { + struct list_head list; + char pattern[]; +}; + +struct fastindex { + lua_State *L; + int checked; + char *func; + struct list_head patterns; + struct list_head *last; + struct list_head entries; + int ofs; + char *buf; + int buflen; +}; + +static inline struct fastindex * +to_fastindex(struct lua_State *L) +{ + struct fastindex *f; + lua_getfield(L, lua_upvalueindex(1), "__data"); + f = lua_touserdata(L, -1); + lua_pop(L, 1); + return f; +} + +static int +fastindex_module(lua_State *L) +{ + const char *s; + s = luaL_checkstring(L, 1); + + if (s) { + if (namespace) + free(namespace); + namespace = strdup(s); + } + + return 0; +} + +static struct fastindex_entry * +find_entry(struct fastindex *f, char *name) +{ + struct list_head *p; + + if (!f->last) + f->last = &f->entries; + + list_for_each_offset(p, &f->entries, f->last) { + struct fastindex_entry *e; + e = container_of(p, struct fastindex_entry, list); + if (!strcmp(e->name, name)) + return e; + } + return NULL; +} + +static struct fastindex_entry * +new_entry(struct fastindex *f, char *name) +{ + struct fastindex_entry *e; + + e = malloc(sizeof(struct fastindex_entry)); + if (!e) + goto error; + + memset(e, 0, sizeof(struct fastindex_entry)); + e->name = strdup(name); + if (!e->name) { + free(e); + goto error; + } + INIT_LIST_HEAD(&e->list); + + return e; + +error: + return NULL; +} + +static void free_entry(struct fastindex_entry *e) +{ + list_del(&e->list); + free(e->name); + free(e); +} + +int bufferwriter(lua_State *L, const void *p, size_t sz, void *ud) +{ + struct fastindex *f = ud; + + while (f->ofs + sz > f->buflen) { + char *b = f->buf; + f->buflen *= 2; + f->buf = realloc(f->buf, f->buflen); + if (!f->buf) { + free(b); + return 1; + } + } + memcpy(f->buf + f->ofs, p, sz); + f->ofs += sz; + return 0; +} + +static void +load_index(struct fastindex *f, struct fastindex_entry *e) +{ + lua_State *L; + + DPRINTF("Loading module: %s\n", e->name); + + if (!f->buf) + f->buf = malloc(f->buflen); + + if (!f->buf) + luaL_error(f->L, "Out of memory!\n"); + + f->ofs = 0; + L = luaL_newstate(); + if (!L) + return; + + namespace = NULL; + luaL_openlibs(L); + lua_pushcfunction(L, fastindex_module); + lua_setfield(L, LUA_GLOBALSINDEX, "module"); + + do { + if (luaL_dofile(L, e->name)) { + DPRINTF("Warning: unable to open module '%s'\n", e->name); + break; + } + + lua_getglobal(L, f->func); + lua_dump(L, bufferwriter, f); + DPRINTF("Got %d bytes\n", f->ofs); + if (f->ofs == 0) + break; + lua_createtable(f->L, (namespace ? 2 : 1), 0); + luaL_loadbuffer(f->L, f->buf, f->ofs, "tmp"); + lua_rawseti(f->L, -2, 1); + if (namespace) { + DPRINTF("Module has namespace '%s'\n", namespace); + lua_pushstring(f->L, namespace); + lua_rawseti(f->L, -2, 2); + free(namespace); + namespace = NULL; + } + lua_setfield(f->L, -2, e->name); + } while (0); + + lua_close(L); +} + + +static int +fastindex_scan(lua_State *L) +{ + struct list_head *tmp, *p; + struct fastindex *f; + glob_t gl; + int i; + int gl_flags = GLOB_NOESCAPE | GLOB_NOSORT | GLOB_MARK; + + f = to_fastindex(L); + f->checked++; + + + if (list_empty(&f->patterns)) + return 0; + + lua_getfield(L, lua_upvalueindex(1), "indexes"); + list_for_each(p, &f->patterns) { + struct fastindex_pattern *pt = container_of(p, struct fastindex_pattern, list); + glob(pt->pattern, gl_flags, NULL, &gl); + gl_flags |= GLOB_APPEND; + } + for (i = 0; i < gl.gl_pathc; i++) { + struct fastindex_entry *e; + struct stat st; + + if (stat(gl.gl_pathv[i], &st)) + continue; + + if ((st.st_mode & S_IFMT) != S_IFREG) + continue; + + e = find_entry(f, gl.gl_pathv[i]); + if (!e) { + e = new_entry(f, gl.gl_pathv[i]); + list_add_tail(&e->list, &f->entries); + } + + e->checked = f->checked; + if ((e->timestamp < st.st_mtime)) { + load_index(f, e); + e->timestamp = st.st_mtime; + } + } + globfree(&gl); + list_for_each_safe(p, tmp, &f->entries) { + struct fastindex_entry *e = container_of(p, struct fastindex_entry, list); + if (e->checked < f->checked) { + lua_pushnil(f->L); + lua_setfield(f->L, -2, e->name); + free_entry(e); + } + } + lua_pop(L, 1); + + return 0; +} + +static int +fastindex_free(lua_State *L) +{ + struct fastindex *f; + struct list_head *p, *tmp; + + f = lua_touserdata(L, -1); + list_for_each_safe(p, tmp, &f->patterns) { + struct fastindex_pattern *pt; + pt = container_of(p, struct fastindex_pattern, list); + list_del(p); + free(pt); + } + list_for_each_safe(p, tmp, &f->entries) { + struct fastindex_entry *e; + e = container_of(p, struct fastindex_entry, list); + free_entry(e); + } + return 0; +} + +static int +fastindex_add(lua_State *L) +{ + struct fastindex_pattern *pt; + struct fastindex *f; + const char *str; + + f = to_fastindex(L); + str = luaL_checkstring(L, 1); + if (!str) + luaL_error(L, "Invalid argument"); + + pt = malloc(sizeof(struct fastindex_pattern) + strlen(str) + 1); + if (!pt) + luaL_error(L, "Out of memory"); + + INIT_LIST_HEAD(&pt->list); + strcpy(pt->pattern, str); + list_add(&pt->list, &f->patterns); + + return 0; +} + +static const luaL_Reg fastindex_m[] = { + { "add", fastindex_add }, + { "scan", fastindex_scan }, + { NULL, NULL } +}; + +static int +fastindex_new(lua_State *L) +{ + struct fastindex *f; + const char *func; + + func = luaL_checkstring(L, 1); + + f = lua_newuserdata(L, sizeof(struct fastindex)); + lua_createtable(L, 0, 2); + lua_pushvalue(L, -1); + lua_setfield(L, -2, "__index"); + lua_pushcfunction(L, fastindex_free); + lua_setfield(L, -2, "__gc"); + lua_pushvalue(L, -1); + lua_setmetatable(L, -3); + lua_pushvalue(L, -2); + lua_setfield(L, -2, "__data"); + lua_createtable(L, 0, 1); + lua_setfield(L, -2, "indexes"); + lua_pushvalue(L, -2); + luaI_openlib(L, NULL, fastindex_m, 1); + + memset(f, 0, sizeof(struct fastindex)); + f->L = L; + f->buflen = DEFAULT_BUFLEN; + INIT_LIST_HEAD(&f->entries); + INIT_LIST_HEAD(&f->patterns); + + f->func = strdup(func); + if (!f->func) { + if (f->func) + free(f->func); + luaL_error(L, "Out of memory\n"); + } + + return 1; +} + +static const luaL_Reg fastindex[] = { + { "new", fastindex_new }, + { NULL, NULL }, +}; + +int +luaopen_fastindex(lua_State *L) +{ + luaL_register(L, MODNAME, fastindex); + return 0; +} diff --git a/libs/fastindex/src/list.h b/libs/fastindex/src/list.h new file mode 100644 index 000000000..2959a061d --- /dev/null +++ b/libs/fastindex/src/list.h @@ -0,0 +1,601 @@ +#ifndef _LINUX_LIST_H +#define _LINUX_LIST_H + +#include +/** + * container_of - cast a member of a structure out to the containing structure + * @ptr: the pointer to the member. + * @type: the type of the container struct this is embedded in. + * @member: the name of the member within the struct. + * + */ +#ifndef container_of +#define container_of(ptr, type, member) ( \ + (type *)( (char *)ptr - offsetof(type,member) )) +#endif + + +/* + * Simple doubly linked list implementation. + * + * Some of the internal functions ("__xxx") are useful when + * manipulating whole lists rather than single entries, as + * sometimes we already know the next/prev entries and we can + * generate better code by using them directly rather than + * using the generic single-entry routines. + */ + +struct list_head { + struct list_head *next, *prev; +}; + +#define LIST_HEAD_INIT(name) { &(name), &(name) } + +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +static inline void INIT_LIST_HEAD(struct list_head *list) +{ + list->next = list; + list->prev = list; +} + +/* + * Insert a new entry between two known consecutive entries. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __list_add(struct list_head *new, + struct list_head *prev, + struct list_head *next) +{ + next->prev = new; + new->next = next; + new->prev = prev; + prev->next = new; +} + +/** + * list_add - add a new entry + * @new: new entry to be added + * @head: list head to add it after + * + * Insert a new entry after the specified head. + * This is good for implementing stacks. + */ +static inline void list_add(struct list_head *new, struct list_head *head) +{ + __list_add(new, head, head->next); +} + + +/** + * list_add_tail - add a new entry + * @new: new entry to be added + * @head: list head to add it before + * + * Insert a new entry before the specified head. + * This is useful for implementing queues. + */ +static inline void list_add_tail(struct list_head *new, struct list_head *head) +{ + __list_add(new, head->prev, head); +} + + +/* + * Delete a list entry by making the prev/next entries + * point to each other. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __list_del(struct list_head * prev, struct list_head * next) +{ + next->prev = prev; + prev->next = next; +} + +/** + * list_del - deletes entry from list. + * @entry: the element to delete from the list. + * Note: list_empty() on entry does not return true after this, the entry is + * in an undefined state. + */ +static inline void list_del(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + entry->next = NULL; + entry->prev = NULL; +} + +/** + * list_replace - replace old entry by new one + * @old : the element to be replaced + * @new : the new element to insert + * + * If @old was empty, it will be overwritten. + */ +static inline void list_replace(struct list_head *old, + struct list_head *new) +{ + new->next = old->next; + new->next->prev = new; + new->prev = old->prev; + new->prev->next = new; +} + +static inline void list_replace_init(struct list_head *old, + struct list_head *new) +{ + list_replace(old, new); + INIT_LIST_HEAD(old); +} + +/** + * list_del_init - deletes entry from list and reinitialize it. + * @entry: the element to delete from the list. + */ +static inline void list_del_init(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + INIT_LIST_HEAD(entry); +} + +/** + * list_move - delete from one list and add as another's head + * @list: the entry to move + * @head: the head that will precede our entry + */ +static inline void list_move(struct list_head *list, struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add(list, head); +} + +/** + * list_move_tail - delete from one list and add as another's tail + * @list: the entry to move + * @head: the head that will follow our entry + */ +static inline void list_move_tail(struct list_head *list, + struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add_tail(list, head); +} + +/** + * list_is_last - tests whether @list is the last entry in list @head + * @list: the entry to test + * @head: the head of the list + */ +static inline int list_is_last(const struct list_head *list, + const struct list_head *head) +{ + return list->next == head; +} + +/** + * list_empty - tests whether a list is empty + * @head: the list to test. + */ +static inline int list_empty(const struct list_head *head) +{ + return head->next == head; +} + +/** + * list_empty_careful - tests whether a list is empty and not being modified + * @head: the list to test + * + * Description: + * tests whether a list is empty _and_ checks that no other CPU might be + * in the process of modifying either member (next or prev) + * + * NOTE: using list_empty_careful() without synchronization + * can only be safe if the only activity that can happen + * to the list entry is list_del_init(). Eg. it cannot be used + * if another CPU could re-list_add() it. + */ +static inline int list_empty_careful(const struct list_head *head) +{ + struct list_head *next = head->next; + return (next == head) && (next == head->prev); +} + +static inline void __list_splice(struct list_head *list, + struct list_head *head) +{ + struct list_head *first = list->next; + struct list_head *last = list->prev; + struct list_head *at = head->next; + + first->prev = head; + head->next = first; + + last->next = at; + at->prev = last; +} + +/** + * list_splice - join two lists + * @list: the new list to add. + * @head: the place to add it in the first list. + */ +static inline void list_splice(struct list_head *list, struct list_head *head) +{ + if (!list_empty(list)) + __list_splice(list, head); +} + +/** + * list_splice_init - join two lists and reinitialise the emptied list. + * @list: the new list to add. + * @head: the place to add it in the first list. + * + * The list at @list is reinitialised + */ +static inline void list_splice_init(struct list_head *list, + struct list_head *head) +{ + if (!list_empty(list)) { + __list_splice(list, head); + INIT_LIST_HEAD(list); + } +} + +/** + * list_entry - get the struct for this entry + * @ptr: the &struct list_head pointer. + * @type: the type of the struct this is embedded in. + * @member: the name of the list_struct within the struct. + */ +#define list_entry(ptr, type, member) \ + container_of(ptr, type, member) + +/** + * list_first_entry - get the first element from a list + * @ptr: the list head to take the element from. + * @type: the type of the struct this is embedded in. + * @member: the name of the list_struct within the struct. + * + * Note, that list is expected to be not empty. + */ +#define list_first_entry(ptr, type, member) \ + list_entry((ptr)->next, type, member) + +/** + * list_for_each - iterate over a list + * @pos: the &struct list_head to use as a loop cursor. + * @head: the head for your list. + */ +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); \ + pos = pos->next) + +/** + * __list_for_each - iterate over a list + * @pos: the &struct list_head to use as a loop cursor. + * @head: the head for your list. + * + * This variant differs from list_for_each() in that it's the + * simplest possible list iteration code, no prefetching is done. + * Use this for code that knows the list to be very short (empty + * or 1 entry) most of the time. + */ +#define __list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); pos = pos->next) + +/** + * list_for_each_prev - iterate over a list backwards + * @pos: the &struct list_head to use as a loop cursor. + * @head: the head for your list. + */ +#define list_for_each_prev(pos, head) \ + for (pos = (head)->prev; pos != (head); \ + pos = pos->prev) + +/** + * list_for_each_safe - iterate over a list safe against removal of list entry + * @pos: the &struct list_head to use as a loop cursor. + * @n: another &struct list_head to use as temporary storage + * @head: the head for your list. + */ +#define list_for_each_safe(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (head); \ + pos = n, n = pos->next) + +/** + * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry + * @pos: the &struct list_head to use as a loop cursor. + * @n: another &struct list_head to use as temporary storage + * @head: the head for your list. + */ +#define list_for_each_prev_safe(pos, n, head) \ + for (pos = (head)->prev, n = pos->prev; \ + pos != (head); \ + pos = n, n = pos->prev) + +/** + * list_for_each_entry - iterate over list of given type + * @pos: the type * to use as a loop cursor. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +/** + * list_for_each_entry_reverse - iterate backwards over list of given type. + * @pos: the type * to use as a loop cursor. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_reverse(pos, head, member) \ + for (pos = list_entry((head)->prev, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.prev, typeof(*pos), member)) + +/** + * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue() + * @pos: the type * to use as a start point + * @head: the head of the list + * @member: the name of the list_struct within the struct. + * + * Prepares a pos entry for use as a start point in list_for_each_entry_continue(). + */ +#define list_prepare_entry(pos, head, member) \ + ((pos) ? : list_entry(head, typeof(*pos), member)) + +/** + * list_for_each_entry_continue - continue iteration over list of given type + * @pos: the type * to use as a loop cursor. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + * + * Continue to iterate over list of given type, continuing after + * the current position. + */ +#define list_for_each_entry_continue(pos, head, member) \ + for (pos = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +/** + * list_for_each_entry_continue_reverse - iterate backwards from the given point + * @pos: the type * to use as a loop cursor. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + * + * Start to iterate over list of given type backwards, continuing after + * the current position. + */ +#define list_for_each_entry_continue_reverse(pos, head, member) \ + for (pos = list_entry(pos->member.prev, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.prev, typeof(*pos), member)) + +/** + * list_for_each_entry_from - iterate over list of given type from the current point + * @pos: the type * to use as a loop cursor. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + * + * Iterate over list of given type, continuing from current position. + */ +#define list_for_each_entry_from(pos, head, member) \ + for (; &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +/** + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry + * @pos: the type * to use as a loop cursor. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) + +/** + * list_for_each_entry_safe_continue + * @pos: the type * to use as a loop cursor. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + * + * Iterate over list of given type, continuing after current point, + * safe against removal of list entry. + */ +#define list_for_each_entry_safe_continue(pos, n, head, member) \ + for (pos = list_entry(pos->member.next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) + +/** + * list_for_each_entry_safe_from + * @pos: the type * to use as a loop cursor. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + * + * Iterate over list of given type from current point, safe against + * removal of list entry. + */ +#define list_for_each_entry_safe_from(pos, n, head, member) \ + for (n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) + +/** + * list_for_each_entry_safe_reverse + * @pos: the type * to use as a loop cursor. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + * + * Iterate backwards over list of given type, safe against removal + * of list entry. + */ +#define list_for_each_entry_safe_reverse(pos, n, head, member) \ + for (pos = list_entry((head)->prev, typeof(*pos), member), \ + n = list_entry(pos->member.prev, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.prev, typeof(*n), member)) + +/* + * Double linked lists with a single pointer list head. + * Mostly useful for hash tables where the two pointer list head is + * too wasteful. + * You lose the ability to access the tail in O(1). + */ + +struct hlist_head { + struct hlist_node *first; +}; + +struct hlist_node { + struct hlist_node *next, **pprev; +}; + +#define HLIST_HEAD_INIT { .first = NULL } +#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } +#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) +static inline void INIT_HLIST_NODE(struct hlist_node *h) +{ + h->next = NULL; + h->pprev = NULL; +} + +static inline int hlist_unhashed(const struct hlist_node *h) +{ + return !h->pprev; +} + +static inline int hlist_empty(const struct hlist_head *h) +{ + return !h->first; +} + +static inline void __hlist_del(struct hlist_node *n) +{ + struct hlist_node *next = n->next; + struct hlist_node **pprev = n->pprev; + *pprev = next; + if (next) + next->pprev = pprev; +} + +static inline void hlist_del(struct hlist_node *n) +{ + __hlist_del(n); + n->next = NULL; + n->pprev = NULL; +} + +static inline void hlist_del_init(struct hlist_node *n) +{ + if (!hlist_unhashed(n)) { + __hlist_del(n); + INIT_HLIST_NODE(n); + } +} + + +static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) +{ + struct hlist_node *first = h->first; + n->next = first; + if (first) + first->pprev = &n->next; + h->first = n; + n->pprev = &h->first; +} + + +/* next must be != NULL */ +static inline void hlist_add_before(struct hlist_node *n, + struct hlist_node *next) +{ + n->pprev = next->pprev; + n->next = next; + next->pprev = &n->next; + *(n->pprev) = n; +} + +static inline void hlist_add_after(struct hlist_node *n, + struct hlist_node *next) +{ + next->next = n->next; + n->next = next; + next->pprev = &n->next; + + if(next->next) + next->next->pprev = &next->next; +} + +#define hlist_entry(ptr, type, member) container_of(ptr,type,member) + +#define hlist_for_each(pos, head) \ + for (pos = (head)->first; pos; pos = pos->next) + +#define hlist_for_each_safe(pos, n, head) \ + for (pos = (head)->first; pos; pos = n) + +/** + * hlist_for_each_entry - iterate over list of given type + * @tpos: the type * to use as a loop cursor. + * @pos: the &struct hlist_node to use as a loop cursor. + * @head: the head for your list. + * @member: the name of the hlist_node within the struct. + */ +#define hlist_for_each_entry(tpos, pos, head, member) \ + for (pos = (head)->first; pos && \ + ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ + pos = pos->next) + +/** + * hlist_for_each_entry_continue - iterate over a hlist continuing after current point + * @tpos: the type * to use as a loop cursor. + * @pos: the &struct hlist_node to use as a loop cursor. + * @member: the name of the hlist_node within the struct. + */ +#define hlist_for_each_entry_continue(tpos, pos, member) \ + for (pos = (pos)->next; pos && \ + ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ + pos = pos->next) + +/** + * hlist_for_each_entry_from - iterate over a hlist continuing from current point + * @tpos: the type * to use as a loop cursor. + * @pos: the &struct hlist_node to use as a loop cursor. + * @member: the name of the hlist_node within the struct. + */ +#define hlist_for_each_entry_from(tpos, pos, member) \ + for (; pos && \ + ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ + pos = pos->next) + +/** + * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry + * @tpos: the type * to use as a loop cursor. + * @pos: the &struct hlist_node to use as a loop cursor. + * @n: another &struct hlist_node to use as temporary storage + * @head: the head for your list. + * @member: the name of the hlist_node within the struct. + */ +#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \ + for (pos = (head)->first; \ + pos && ({ n = pos->next; 1; }) && \ + ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ + pos = n) + +#endif -- 2.25.1