lkml.org 
[lkml]   [1999]   [May]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
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/

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.025 / U:0.040 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site