a poor man's linked-list sorting routine:
void
llist_sort(llist* ll)
{
lnode* ln = ll->head;
lnode* n = 0;
lnode* p = 0;
lnode* next = 0;
lnode* prev = 0;
while(ln) {
next = n = ln->next;
if (n) {
while(ll->cb_cmp(ln->data, n->data) > 0) {
n = n->next;
if (!n)
break;
}
if (!n) {
llist_unlink(ll, ln);
ll->lnode_count++;
ln->prev = ll->tail;
ln->next = 0;
ll->tail->next = ln;
ll->tail = ln;
}
else if (n != next) {
llist_unlink(ll, ln);
ll->lnode_count++;
n->prev->next = ln;
ln->prev = n->prev;
n->prev = ln;
ln->next = n;
}
}
prev = p = ln->prev;
if (p) {
while(ll->cb_cmp(ln->data, p->data) < 0) {
p = p->prev;
if (!p)
break;
}
if (!p) {
llist_unlink(ll, ln);
ll->lnode_count++;
ll->head->prev = ln;
ln->next = ll->head;
ln->prev = 0;
ll->head = ln;
}
else if (p != prev) {
llist_unlink(ll, ln);
ll->lnode_count++;
ln->prev = p;
p->next->prev = ln;
ln->next = p->next;
p->next = ln;
}
}
ln = next;
}
}
temporary labourer's statement:
i work in factories and wharehouses, packing, working like a machine, tied
to a machine, performing simple repetitious tasks.
working at a machine has something in common with programming - at a
stretch. i must be efficient in my movements, i must minimise my movements
to only those necessary to perform the job productively and simply. when i
am struggling to keep up with a machine, i must find those ways of doing
the task which mean less movement. i must tune my mind to not fussing on
details. when packing punnets into cardboard boxes, a) i have to tape a
flat-box into a box shape, b) i must place within the box a polythene
liner bag. usually boxes are made while waiting for the machine's next
cycle - but if you are not fast and efficient at making boxes, if you
worry about perfection in your work, making sure the box is properly
square and the seams are seamless, then fast you may not be and then you
get behind the machine cycle and have to catch up with it and the don't
have enough time to make boxes. likewise with placing the polythene liner
bag within the box, a balance has to be struck with throwing it in any-old
how, and placing it carefully so the stacks of punnets slide in without
resistance. if they get stuck on the bag the stack may fall apart and then
you have to spend time re-stacking the punnets in order to get all that
you must get into the box.
with coding, i've forgotten what the likeness was. efficiency. not of
physical movement of typing though that may help. but efficiency of code.
you can overly complexify your code. say you have to perform some specific
function which consists of various sub functions, it may make sense to
split those sub functions into various other functions rather than having
the whole lot as one big function. and, maybe, you can create those
sub-functions in some way which allows other functions to utilize them
also.
not only is the above code fragment for sorting a linked list a poor man's
in terms of the financial situation of the person who wrote the code (yes
me) but also in terms of the efficiency of the code. in the usage case the
code will be put to, this may not matter, but as a list for storing huge
amounts of data ( beyond mega-byte range ) it will prove to be poor indeed
(slow). but sorting routines are not my strongpoint and that was the first
thing i thought of how to do it without doing x and y or z - without
creating a new linked-list and sorting from one to the other for example.
a linked list is a data structure which holds a list of items (in this
case all items are of the same data type) each item links to the item
before it, and the item after it. this is opposed to an array. an array is
more like a box in which items are placed - once the box is full, it is
full (maybe you could tape another box onto it, maybe you could realloc
the array). a linked list is unlimited within reason. in your box you
place a stack of punnets. you find you need to remove one of the damaged
punnets. you must remove all punnets on top of it, take out the damaged
punnet, and replace all the others. a linked list on the other hand, you
just unlink the damaged punnet by setting the two links immediately either
side of it to link to each other bypassing the damaged punnet.
here is a nice pleasing looking function:
inline void*
llist_select_to_array( llist* ll,
datacb_sel sel_cb,
const void* crit,
const void* terminator)
{
lnode* first = llist_pri_select_flags( ll,
LNF_ASELECTED,
sel_cb,
crit );
return llist_pri_to_array( ll,
ll->asel_count,
first,
terminator );
}
it converts a linked list into a box of punnets. first of all, it calls
the linked list's private function (which cannot be accessed outside of
the linkedlist implementation (ie in any code outside of llist.c) to
select items in the list. the selection criteria are unknown to the linked
list, all the list knows is a pointer to a memory location - it does not
even have any idea about what the contents of that memory location are -
all it "knows" (is told) is use call the function that is pointed to by
sel_cb for each item in the list and pass to that function the pointer to
the memory location where some kind of criteria exists that the selection
call back function will understand in god only knows what way.
so it does all that and is given as a reward the first item in the list
which meets the criteria - known by the secret codeword 'first'.
LNF_ASELECTED is the flag to use for selection - (when the GUI is finally
implemented in the distant future) normally LNF_SELECTED flag is used for
selection - this allows two different selections to exist simultaneously -
a public one which way down the line may converge with the user experience
- and a private one which the program keeps to it's self with dirty
pleasure.
so it does all that and it has a selection within the list to convert to
an array - maybe not the whole list, just a part, or maybe the whole list,
it does not matter. so it gives some info to another private function of
llist, llist_pri_to_array which converts the 'private' selection within
the list into an array.
inline void*
llist_to_array(const llist* ll, const void* terminator)
{
return llist_pri_to_array( ll,
ll->lnode_count,
ll->head,
terminator );
}
calls it also, but does not bother with any selection process.
static void*
llist_pri_to_array( const llist* ll,
size_t count,
const lnode* first,
const void* terminator)
{
if (terminator)
++count;
if (!count)
return 0;
void* arr = malloc(ll->data_size * count);
if (!arr)
{
WARNING("out of memory copying llist to array\n");
return 0;
}
void* i = arr;
void* iend = (void*)((char*)i + ll->data_size *
(count - (size_t)(terminator ? 1 : 0)));
const lnode* ln = first;
while(ln && i <= iend)
{
if (ll->cb_copy)
ll->cb_copy(i, ln->data);
else
memcpy(i, ln->data, ll->data_size);
i = (void*)((char*)i + ll->data_size);
ln = ln->next;
}
if (terminator)
{
if (ll->cb_copy)
ll->cb_copy(i, terminator);
else
memcpy(i, terminator, ll->data_size);
}
return arr;
}
you may notice an error in this code. the author assumed that the
selection within the list would be contiguous - an assumption which should
be assumed to be faulty. instead of simply copying everything in the list
within the selection up to count itmes, it should check that the item is
actually selected or not.... but hang on one minute... ok ok, that's not a
problem... here's what the while loop should actually look like:
while(ln && i <= iend)
{
if (ll->cb_copy)
ll->cb_copy(i, ln->data);
else
memcpy(i, ln->data, ll->data_size);
i = (void*)((char*)i + ll->data_size);
ln = ln->next;
}
ok, ok, that's exactly the same. i've not changed a thing, this is because
of an implementation problem caused by a lack of foresight on the part of
the author. yes, you're right to recall that there are two possible
selections. how is the llist_pri_to_array function to know which selection
to use when it is not told which selection to use?
ok, change #1
static void*
llist_pri_to_array( const llist* ll,
size_t count,
const lnode* first,
lnflags lnf, /* <<<---- this! we added this! */
const void* terminator)
oh, but then the array might not be formed from a selection but from the
entire list!?!?
but just pass 0 as lnf in that case as hinty tat in enumeration:
typedef enum LNFLAGS
{
LNF_SELECTED = 0x0001, /* public selection */
LNF_ASELECTED = 0x0002 /* private selection */
} lnflags;
Sooooooooooo:
while(ln && i <= iend)
{
if (!lnf || (ln->flags & lnf))
{
if (ll->cb_copy)
ll->cb_copy(i, ln->data);
else
memcpy(i, ln->data, ll->data_size);
i = (void*)((char*)i + ll->data_size);
}
ln = ln->next;
}
the additional conditional test a) will copy an list item to the array if
no selection is made (ie lnf is zero) - OR - if lnf is LNF_SELECTED or
LNF_ASELECTED and the flags set in a particular list item match.
what the hell does "i = (void*)((char*)i + ll->data_size);" do? I here you
ask? well, recall the list does not know anything other than addresses of
memory locations where data resides - yes? good. therefor, to point to
those addresses there is only one option, a void pointer - this type of
pointer is very special, you can do sod all with it. next to useless to
your C newbie. but it can be used to point to a memory location of *any*
data type. the variable i, is a pointer to the array we're creating of
unknown data types - all we know is their size in bytes - stored in
ll->data_size (because the function to create a linked list insists upon
being told this kind of thing). pointer arithmetic on void pointers is not
quite legal C, so we cast the void pointer to a char pointer and a char is
a single byte (unless you're on some arcane bastard machine platform
specially designed to fuck up everything). yeah, so we 'cast' the void
pointer out to sea temporarily, turn it into a right character in the
process, add some number to it and store the result as the new value
(memory address) of the void pointer - ie the next element in this super
special array.
ooh mrs, what a palava. but a lovely palava i just can't help enjoying.
yes, it kept me occupied while i put-off writing the next part of my
marvellous boxyseq program. the boxy sequencer. pretty coloure boxes
appear in the screens simultaneous with midi messages sent to your
favourite (soft) synth to playu plinkyplankyplonky music.
see also: http://en.wikipedia.org/wiki/Big_O_notation
but i'm too thick to understand that shit.
_______________________________________________
NetBehaviour mailing list
NetBehaviour@netbehaviour.org
http://www.netbehaviour.org/mailman/listinfo/netbehaviour
