Messages in this thread | | | Date | Mon, 26 Jul 1999 12:04:25 +0200 (MET DST) | From | Jan Bobrowski <> | Subject | (elist) faster hash list scanning |
| |
Changes: + buffer_head hash now use elist (elist-struct.diff). + fast list scanning using elist_find() function. It is about 75% faster than original for long lists (5-element). (dcache, icache and buffer cache use it now)
Patches against 2.3.11 available at: http://wizard.ae.krakow.pl/~jb/patches/elist-def.diff.gz http://wizard.ae.krakow.pl/~jb/patches/elist-struc.diff.gz http://wizard.ae.krakow.pl/~jb/patches/elist-fs.diff.gz
here is elist definition from list.h:
/* * elist * mailto: jb@wizard.ae.krakow.pl * * These lists are terminated by ELIST_END constant instead of NULL. * It speeds up list manipulations because next->pprev is always accessible. * They are anchored by single pointer - it saves 50% of memory * occupied by hashtables. */
struct elist { struct elist* next; struct elist** pprev; };
typedef struct elist * elist_anchor_t;
extern struct elist __elist_end;
#define ELIST_END (&__elist_end) #define ELIST_FREE {&__elist_end, &__elist_end.next}
static inline void elist_add(struct elist *new, elist_anchor_t *list) { struct elist* first = *list; new->pprev = list; *list = new; new->next = first; first->pprev = &new->next; }
static inline struct elist* elist_del(struct elist *entry) { struct elist* next = entry->next; struct elist** pprev = entry->pprev; next->pprev = pprev; *pprev = next; return next; }
static inline void elist_init(struct elist *entry) { entry->next = &__elist_end; entry->pprev = &__elist_end.next; }
static inline struct elist* elist_del_and_init(struct elist *entry) { struct elist* next = entry->next; struct elist** pprev = entry->pprev; entry->next = &__elist_end; entry->pprev = &__elist_end.next; next->pprev = pprev; *pprev = next; return next; }
#define elist_add_after(new, entry) elist_add((new),&(entry)->next) #define elist_add_before(new, entry) elist_add((new),(entry)->pprev)
#define on_elist(entry) ((entry)->pprev != &__elist_end.next) #define elist_empty(list) ((list) == ELIST_END)
#define elist_start(ptr,list,member) ((ptr) = list_entry((list),typeof(*(ptr)),member)) #define elist_next(ptr,member) list_entry((ptr)->member.next,typeof(*(ptr)),member) #define elist_finished(ptr,member) (&(ptr)->member == ELIST_END)
#define forall_elist(ptr,list,member) for ( \ elist_start((ptr),(list),member); \ !elist_finished((ptr),member); \ (ptr) = elist_next((ptr),member) \ )
#define _KEY(p) *(int*)((char*)p+offset)
static inline struct elist *__elist_find(elist_anchor_t ptr, int offset, int key) { struct elist *ptr2;
for(;;) { ptr2 = ptr->next; if (ptr->next == ELIST_END) break; if (_KEY(ptr) == key) goto out; ptr = ptr2->next; if (_KEY(ptr2) == key) goto out2; } if(ptr == ELIST_END || _KEY(ptr) == key) goto out; out2: ptr = ptr2; out: return ptr; } #undef _KEY
#define elist_find(list, key, type, list_member, key_member) \ __elist_find((list), (int)&((type*)0)->key_member \ - (int)&((type*)0)->list_member, (int)(key)) \
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |