Goh, Yong Kwang wrote:
I'm currently doing a project that has a array that supposed to be
determined only at runtime.
Originally, the prototype I did as a proof of theory (or a quick hack)
So one method is to create a linked list and use malloc to create
LinkedListNode as needed and use free() to destroy a node.
But another easier way would be to use the realloc() function call to
resize a memory block in the heap so that all the "nodes" are now
consecutive and I can use the qsort() function. With LinkedList, I
can't use qsort() in stdlib.
I believe that by using realloc. Although it seems that this is a
"clumsy" approach, I believe that it's actually more efficient and
faster over using LinkedList due to 2 reasons:
(1) Using the qsort() that comes with stdlib is faster than some
bubble sort code I write myself. At least it is optimized and bugfree
and tested.
(2) Reallocating (resizing) has overheads but the overhead for doing
multiple malloc for each node for LinkedList is about the same. Also,
realloc() will provide a block of consecutive memory bytes, thus more
locality and speeds up searching and sorting, instead of LinkedList
nodes that are scattered all over in the heap.
Are my above 2 assumptions true? Anyone tried this out before? And how
is the performance like?
I'm not sure that it would be of better performance, but it seems to
me, that if the nodes are large objects, you can store the nodes in
a singly-linked (or doubly if you going to be removing nodes) list
and at the same time create an array of pointers
to each of the nodes in the linked list. This way instead of moving
around the nodes, you will sort the array of pointers, search the
array of pointers with the Standard C functions qsort and bsearch,
leaving the list structure unchanged.
For example you could cread a data type similiar to this:
typedef struct LIST
{
struct bio *listhead;
struct bio **sortedlist;
size_t count;
} LIST;
where listhead is a pointer to the head of the list, sortedlist
is an array of the node pointers that you dynamically reallocate and
count is a counter of the number of nodes created.
You then can write functions to manage the datatype.
Here is a simple example that can be modified to give you
even better performance.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_NAME 64
typedef enum{NO,YES} bool;
struct bio
{
char name[MAX_NAME];
unsigned age;
struct bio *next;
};
typedef struct LIST
{
struct bio *listhead;
struct bio **sortedlist;
size_t count;
} LIST;
/* Prototypes */
bool AddToLIST(LIST *p, const char *name, unsigned age,
int (*cmp)(const void *v1, const void *v2));
void FreeLIST(LIST *p);
int cmp(const void *v1, const void *v2);
int main(void)
{
LIST presidents = {NULL};
size_t i;
AddToLIST(&presidents,"Washington, George",34,cmp);
AddToLIST(&presidents,"Clinton, Bill",35,cmp);
AddToLIST(&presidents,"Nixon, Richard", 36,cmp);
puts("Sorted list of Presidents");
for(i = 0;i < presidents.count;i++)
printf("\tname: %s\n\tage: %u\n\n",
presidents.sortedlist[i]->name,
presidents.sortedlist[i]->age);
FreeLIST(&presidents);
return 0;
}
bool AddToLIST(LIST *p, const char *name, unsigned age,
int (*cmp)(const void *v1, const void *v2))
{
struct bio *new, **tmp;
if((new = malloc(sizeof *new)) == NULL) return NO;
if((tmp = realloc(p->sortedlist,
(p->count+1)*sizeof *tmp)) == NULL)
{
free(new);
return NO;
}
p->sortedlist = tmp;
new->next = p->listhead;
strncpy(new->name,name,MAX_NAME);
new->name[MAX_NAME-1] = '\0';
new->age = age;
p->listhead = p->sortedlist[p->count++] = new;
if(p->count >1)
qsort(p->sortedlist,p->count,sizeof *p->sortedlist,cmp);
return YES;
}
void FreeLIST(LIST *p)
{
size_t i;
for(i = 0;i < p->count;i++) free(p->sortedlist[i]);
free(p->sortedlist);
p->count = 0;
p->listhead = NULL;
p->sortedlist = NULL;
return;
}
int cmp(const void *v1, const void *v2)
{
const struct bio *s1 = *(void **)v1;
const struct bio *s2 = *(void **)v2;
return strcmp(s1->name,s2->name);
}
--
Al Bowers
Tampa, Fl USA
mailto:
xa******@myrapidsys.com (remove the x to send email)
http://www.geocities.com/abowers822/ 
