Hello, everyone!
I have been using list.h's list functions in some userspace code of mine
(no, I'm not including the kernel header file) because I like it so much
(maybe I'm weird, maybe not). While happily coding away, I found that I
could implement some things nicely with a "list_transpose" function;
that is, a function which swaps the position of two list nodes.
I suppose this isn't really relevent to linux-kernel, but it could be
used in the kernel and is based on the kernel's current implementation,
so it could be useful.
I tried to make the implementation as generic as possible, even allowing
swapping of two lists and items that aren't on the same list. After a
few hours of trying to figure out a simple ("natural") way of doing it,
which seemed like a way that should be possible, I gave up and did it the
"well, it needs to do this" way, with a lot of special cases.
I'm currently using it to swap lists, swap nodes in a list, and nodes
between two lists, and it seems to be working fine (so you can think of
this as a contribution as well, I suppose :) ), but I was wondering if
anybody can see an easier way to implement it, or perhaps if somebody has
implemented it before in a cleaner way.
For those of you who are not familiar with the kernel's list.h, it
implements circular doubly linked lists without data pointers (the list
structure is instead placed inside the structures to be strung together
and the location of the structure is inherited). Data pointers would
probably make this an easy thing to implement, but there are none in this
implementation.
Here's what I'm using right now. Note that the first two "if" blocks
were recently added to handle empty lists, making the function even more
complicated.
--------------------------------------------------------------------------
#define SWAP(a,b) do { typeof(a) z = a; a = b; b = z; } while (0)
#define ROR4(a,b,c,d) do { typeof(a) z = d; d = c; c = b; b = a; a = z; } while (0)
#define ROL4(a,b,c,d) do { typeof(a) z = a; a = b; b = c; c = d; d = z; } while (0)
/*
* Transpose (swap) two nodes in the list, or two lists if
* list heads are given, or a list and a node in a list if
* those are given.
*
* This seems to be a lot harder than one might first expect! :)
*
* There must be an easier, simplified way to do this.
* It seems like this should be a natural operation.
*/
static inline void list_transpose(struct list_head *one,struct list_head *two)
{
if (list_empty(one)) {
if (list_empty(two))
/*
* Both empty: do nothing
*/
return;
/*
* "one" is empty, "two" is not
*/
one->next = two->next;
one->prev = two->prev;
one->next->prev = one;
one->prev->next = one;
two->next = two;
two->prev = two;
return;
}
if (list_empty(two)) {
/*
* "two" is empty, "one" is not
*/
two->next = one->next;
two->prev = one->prev;
two->next->prev = two;
two->prev->next = two;
one->next = one;
one->prev = one;
return;
}
if ((one->next != two) &&
(one->prev != two)) {
/*
* Not side-by-side
*/
SWAP(one->prev->next,two->prev->next);
SWAP(one->next->prev,two->next->prev);
SWAP(one->prev,two->prev);
SWAP(one->next,two->next);
return;
}
/*
* Side-by-side
*/
if (one->next == two) {
/*
* One before two, two after one
*/
SWAP(one->prev->next,two->next->prev);
ROR4(one->prev,two->prev,two->next,one->next);
} else {
/*
* One after two, two before one
*/
SWAP(one->next->prev,two->prev->next);
ROL4(one->prev,two->prev,two->next,one->next);
}
}
--------------------------------------------------------------------------
Simon-
[ Stormix Technologies Inc. ][ NetNation Communications Inc. ]
[ sim@stormix.com ][ sim@netnation.com ]
[ Opinions expressed are not necessarily those of my employers. ]
-
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/
This archive was generated by hypermail 2b29 : Sun Jul 23 2000 - 21:00:09 EST