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 (list_head) lists have. It eliminates 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 and
inode cache use hashtable consisting of list_head structures, but 'prev'
pointer is never (?) used. 'd_subdirs' and 'i_dentry' fields also waste
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/