Messages in this thread | | | Date | Tue, 25 May 1999 19:10:46 +0200 (MET DST) | From | Jan Bobrowski <> | Subject | [patch] next/pprev list |
| |
Patch against 2.3.3 is available at http://wizard.ae.krakow.pl/~jb/patches/elist.diff.gz
This patch adds new list structure based of 'next' and 'pprev' pointers. Such a list may be anchored by a single pointer (pointer to the head) while standard kernel lists (based on list_head structure) require two pointers.
This list type is widely used in the kernel but it is not defined explicitly. Patch provides generic interface for such lists.
This implementation has fast, branchless 'add' and 'del' macros of the same speed as standard lists have. Original code has special case during last element processing.
Adventages: 1. uniform interface 2. faster, smaller code 3. all tricks are hidden to the user
There are other places where such lists may be used: eg. dcache use hashtable consisting of list_head structures, but 'prev' pointer is never used. 'd_subdirs' dentry field also wastes place for 'prev' pointer.
This patch works for me. Further testing is needed. Please, check the code. Testing is especially required on Sparc. If you have suggestions feel free to mail me.
Constants and macros:
ELIST_CLEAR initializes elist structure to "not on the list" state ELIST_END anchor initializer; indicates end of a list
elist_add (list, entry) adds entry at the beginning elist_del (entry) removes entry from a list elist_clear (entry) marks entry not being on a list elist_add_after (entry, new) elist_add_before (entry, new)
on_elist (entry) checks whether entry is on a list (was not cleared)
forall_elist (ptr, list, member) forall_elist_ne (ptr, list, member)
Macro 'forall_elist' helps scan whole list. 'ptr' is a pointer to structure containing field 'member' of type 'struct elist'. List is scanned using 'ptr->member' fields.
Macro 'forall_elist_ne' works like do-while. User guarantees that list is not empty.
'elist_del' and 'elist_clear' macros could be merged, but there are many cases when state of entry is not tested after removing it from a list (eg. structure is being freed).
'elist_del' may be used for previously cleared entries. It allows removing entries without checking if the're alredy on a list.
Following kernel structures use next/pprev lists:
buffer_head, file, dquot, user_struct, vm_area_struct, page, task_struct, stripe_head, tcp_bind_bucket, tcp_tw_bucket, sock, ipq
This patch changes only following structures:
task_struct, file, vm_area_struct, user_struct
Jan Bobrowski jb@wizard.ae.krakow.pl
- 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/
| |