D
Don Bruder
Subject tries to say it tersely, maybe doesn't do well...
I've got a double-linked list of entries - looks similar to this:
typedef struct ListEntry
{
Boolean Used;
// elide approximately two dozen more fields of various types
// for the sake of post brevity
// ...
struct ListEntry *Prev;
struct ListEntry *Next;
} ListEntries;
Elsewhere in the code, I set up a "root" ListEntry, like so:
ListEntries *ListRoot = calloc(1, sizeof(ListEntries));
ListRoot->Next = NULL;
ListRoot->Prev = NULL;
Everything else that happens operates against ListRoot.
I stuff it with (unpredictably variable from run to run, hence the use
of a linked list rather than an array of struct pointers) a number of
entries. That part is all good - everything associated with it works
exactly as intended.
As part of the handling of this list, one of the things I need to do is
select a random sub-group of "PickCount" entries from the list.
Currently, I do so like this:
// Select PickCount entries from List, returning them as a second list.
ListEntries *PickSomeEntries(int PickCount, ListEntries *List)
{
int Limit = CountEntries(List); // Should be self explanatory...
int Index = 0;
int Selected = 0;
ListEntries *Pointer = NULL;
// CList will be a sub-list of List to be returned to caller
ListEntries *CList = calloc(1, sizeof(ListEntries));
ListEntries *Pointer2 = CList;
srandomdev();
for (Index = 0;Index < PickCount; Index++)
{
Selected = random() % Limit; // Pick a number from 0 to Limit
// Yes, I realize mod-ing a random number is relatively poor
// practice. However, since this code doesn't need
// "crypto-strong" randoms - just a reasonably random sub-set
// of a list - I deem it acceptable.
Pointer = List; // Start at the first entry in the list and
// step through the list "Selected" times to reach the
// "Selected"th list entry
while (Selected)
{
Pointer = Pointer->Next;
Selected--;
}
// So Pointer now points at the "Selected"th entry of List.
// Copy it to the CList via Pointer2. Note that CopyOneEntry()
// DOES NOT copy Next/Prev. (doing so was found to be the cause
// of some REALLY nasty misbehavior in early development stages)
CopyOneEntry(Pointer, Pointer2);
// Now we set up Next/Prev to reflect the entry being added to the
// new list. (In the process, creating a new entry at the end of
// the growing CList and bumping Pointer2 to point at it for the
// next (if any) pass through the for() loop)
Pointer2->Prev = Pointer2;
Pointer2->Next = calloc(1, sizeof(ListEntries));
Pointer2 = Pointer2->Next;
}
// And finally, hand back the list of selected entries.
return CList;
}
This is functional, but I can't help feeling that it's clunky as hell,
and that there's probably a better way to do it. However, I can't come
up with that "better way".
Anybody see any obvious improvements or "gotchas" I might have missed?
I've got a double-linked list of entries - looks similar to this:
typedef struct ListEntry
{
Boolean Used;
// elide approximately two dozen more fields of various types
// for the sake of post brevity
// ...
struct ListEntry *Prev;
struct ListEntry *Next;
} ListEntries;
Elsewhere in the code, I set up a "root" ListEntry, like so:
ListEntries *ListRoot = calloc(1, sizeof(ListEntries));
ListRoot->Next = NULL;
ListRoot->Prev = NULL;
Everything else that happens operates against ListRoot.
I stuff it with (unpredictably variable from run to run, hence the use
of a linked list rather than an array of struct pointers) a number of
entries. That part is all good - everything associated with it works
exactly as intended.
As part of the handling of this list, one of the things I need to do is
select a random sub-group of "PickCount" entries from the list.
Currently, I do so like this:
// Select PickCount entries from List, returning them as a second list.
ListEntries *PickSomeEntries(int PickCount, ListEntries *List)
{
int Limit = CountEntries(List); // Should be self explanatory...
int Index = 0;
int Selected = 0;
ListEntries *Pointer = NULL;
// CList will be a sub-list of List to be returned to caller
ListEntries *CList = calloc(1, sizeof(ListEntries));
ListEntries *Pointer2 = CList;
srandomdev();
for (Index = 0;Index < PickCount; Index++)
{
Selected = random() % Limit; // Pick a number from 0 to Limit
// Yes, I realize mod-ing a random number is relatively poor
// practice. However, since this code doesn't need
// "crypto-strong" randoms - just a reasonably random sub-set
// of a list - I deem it acceptable.
Pointer = List; // Start at the first entry in the list and
// step through the list "Selected" times to reach the
// "Selected"th list entry
while (Selected)
{
Pointer = Pointer->Next;
Selected--;
}
// So Pointer now points at the "Selected"th entry of List.
// Copy it to the CList via Pointer2. Note that CopyOneEntry()
// DOES NOT copy Next/Prev. (doing so was found to be the cause
// of some REALLY nasty misbehavior in early development stages)
CopyOneEntry(Pointer, Pointer2);
// Now we set up Next/Prev to reflect the entry being added to the
// new list. (In the process, creating a new entry at the end of
// the growing CList and bumping Pointer2 to point at it for the
// next (if any) pass through the for() loop)
Pointer2->Prev = Pointer2;
Pointer2->Next = calloc(1, sizeof(ListEntries));
Pointer2 = Pointer2->Next;
}
// And finally, hand back the list of selected entries.
return CList;
}
This is functional, but I can't help feeling that it's clunky as hell,
and that there's probably a better way to do it. However, I can't come
up with that "better way".
Anybody see any obvious improvements or "gotchas" I might have missed?