Accessing complex data from a linked list based data structure..


R

Ram

Hi,

I have a data structure like ..

struct my_node
{
void *data;
struct my_node *next;
struct my_node *prev;
};
typedef struct my_node *my_listptr_t;

struct my_list
{
my_listptr_t first;
my_listptr_t last;
my_cmpfunc_t cmpfunc;
int flags;
unsigned int nents;
};
typedef struct my_list my_list_t;



I have some data in a struct pointer as follows..

typedef struct
{
int object_id;
char *object_name;
}
object_list;

object_list *objects;

Now question is..

I have added my objects in list.. now i want to search object_name at
specific node in list..

I have list search function..
int list_search(my_list_t *x, my_listptr_t *y, char *string)
{

if (*y == NULL)
*y = x->first;
else
*y = (*y)->next;



for (; *y != NULL; *y = (*y)->next)
{

if (strcmp(string, ??) != 0)
return 1;
}

return 0;
}
?? --> How can I access my objects->object_name from each node in the
list?
 
Ad

Advertisements

B

Barry Schwarz

Hi,

I have a data structure like ..

struct my_node
{
void *data;
struct my_node *next;
struct my_node *prev;
};
typedef struct my_node *my_listptr_t;

You should call this type my_nodeptr_t (see next typedef below).
struct my_list
{
my_listptr_t first;
my_listptr_t last;
my_cmpfunc_t cmpfunc;

Should we assume this is a pointer to a compare function?
int flags;
unsigned int nents;
};
typedef struct my_list my_list_t;

You now have two very similar types, my_listptr_t and my_list_t which
relate to completely different structures. This just leads to
confusion.

The two typedefs could (should) be combined with their respective
struct definitions.
I have some data in a struct pointer as follows..

typedef struct
{
int object_id;
char *object_name;
}
object_list;

Just like here
object_list *objects;

Now question is..

I have added my objects in list.. now i want to search object_name at
specific node in list..

If I interpret the function properly, you want to search the list
starting at one node past(?) a specific node but defaulting to the
first node if you don't specify one.
I have list search function..
int list_search(my_list_t *x, my_listptr_t *y, char *string)
{

if (*y == NULL)
*y = x->first;
else
*y = (*y)->next;

Why do you skip the node specified? Is it the case in your calling
program that you are continuing the search after a successful find?
for (; *y != NULL; *y = (*y)->next)
{

if (strcmp(string, ??) != 0)

Why are you using strcmp when your struct my_list contains a compare
function?
return 1;

Assuming your compare function works like strcmp and returns 0 for
equal and non-zero for unequal, you have this backwards. You don't
want to stop at the first miscompare. You want to stop at the first
equality.

if (my_cmpfunc(...) == 0)
return NODE_FOUND
}

return 0;

And here your return NODE_NOT_FOUND.

Note that the return values are potentially redundant because *y will
be NULL if a node is not found and non-NULL if a node is found.
}
?? --> How can I access my objects->object_name from each node in the
list?

What do you mean by object_name? The only member of your node to
search on is the void* called data. You access the member data the
same way you accessed member next. If member data and parameter
string both point to strings, your call to strcmp could be
if (strcmp(string, (*y)->data) == 0)

So then the question becomes, what does data actually point to? And
why do you need a compare function pointer in struct my_list?
 
R

Ram

Are you asking for some kind of reusable iteration function?

If you have a generic linked list, and you would like to deal with specific
types, you could do something like this:

typedef _Bool bool; /* The type doesn't really matter as much as the
concept. */

void list_iterate(struct list_container *list,
                bool (*iter)(struct list_element *,void *),
                void *ptr) {
        struct list_element *elem;

        for(elem = list->head; elem; elem = elem->next) {
                if(!iter(elem, ptr))
                        break;
        }

}

So how might you use that?

struct search_data {
        int value; /* the search value */
        int result; /* the total number of items with value (for example) */

};

bool find_something(struct list_element *elem, void *ptr) {
        struct search_data *search = ptr;
        struct specific_elem_type *spec = elem->data;

        if(spec->value == search->value) {
                search->result += 1;
        }

        /* continue iterating the list */
        return true;

}

...
{
        struct search_data search;

        search.value = 42;
        search.result = 0;
        list_iterate(list, find_something, &search);

        printf("search.result is %d\n", search.result);

}

So that would basically find all instances in the linked list with a value
of 42, and update the result to store the total.

This method also allows you to change the data structure used for an
implementation, without having to change the loops that previously iterated
the data structure.  This is useful if for instance you wanted to switch
from a linked list, to a splay tree, or a hash table at some point, due to
other factors in the program.

-George- Hide quoted text -

- Show quoted text -




my_list_t *
my_list_new(int flags, my_cmpfunc_t cmpfunc)
{
my_list_t *newlist;

#ifdef DS_DEBUG
printf("in my_list_new(%d, 0x%lx)\n", flags, cmpfunc);
#endif

if (flags != LIST_USERFUNC
&& flags != LIST_STACK
&& flags != LIST_QUEUE)
{
errno = EINVAL;
return NULL;
}

newlist = (my_list_t *)calloc(1, sizeof(my_list_t));
if (cmpfunc != NULL)
newlist->cmpfunc = cmpfunc;
else
newlist->cmpfunc = (my_cmpfunc_t)strcmp;
newlist->flags = flags;

return newlist;
}


I have added my objects in list.. now i want to search object_name at
specific node in list..

int
my_list_add(my_list_t *l, void *data)
{
my_listptr_t n, m;

n = (my_listptr_t)malloc(sizeof(struct my_node));
if (n == NULL)
return -1;
n->data = data;
l->nents++;


/* if the list is empty */
if (l->first == NULL)
{
l->last = l->first = n;
n->next = n->prev = NULL;
return 0;
}


if (l->flags == LIST_STACK)
{
n->prev = NULL;
n->next = l->first;
if (l->first != NULL)
l->first->prev = n;
l->first = n;

return 0;
}

if (l->flags == LIST_QUEUE)
{
n->prev = l->last;
n->next = NULL;
if (l->last != NULL)
l->last->next = n;
l->last = n;

return 0;
}

return 0;
}

I have search function like this..
int
my_list_search(my_list_t *l,
my_listptr_t *n, void *data,
my_matchfunc_t matchfunc)
{


if (matchfunc == NULL)
matchfunc = (my_matchfunc_t)my_str_match;

if (*n == NULL)
*n = l->first;
else
*n = (*n)->next;



for (; *n != NULL; *n = (*n)->next)
{
if ((*(matchfunc))(data, (*n)->data) != 0)
return 1;
}

return 0;
}


I have list search function..


int
my_list_search(my_list_t *l,
my_listptr_t *n, void *data,
my_matchfunc_t matchfunc)
{


if (matchfunc == NULL)
matchfunc = (my_matchfunc_t)my_str_match;

if (*n == NULL)
*n = l->first;
else
*n = (*n)->next;



for (; *n != NULL; *n = (*n)->next)
{

if ((*(matchfunc))(data, (*n)->data) != 0)
return 1;
}

return 0;
}

if you see the matchfunc(), its argument is a string from void *data ,
string from object_list struct(..->object_name)
So i cant re-write all the list functions for this..

please just help me.. during search, i have to get object_list data (-
object_name) from each node & just return the node if
match occurs.. if ((*(matchfunc))(data, (*n)->data) != 0)

my main() is looks like..

main()
{
my_list_t *dir_list = NULL;
my_listptr_t *obj;
object_list *objects;

dir_list = my_list_new(LIST_STACK, NULL);

while(do some operation)
{
//do something
objects->object_id = some_id;
temp_objects->object_name = some_name;
my_list_add(dir_list, (object_list *)objects);
......
......
if(my_list_search(dir_list, NULL, some_name, NULL))
do_something;

}

} //main ends



Thanks for your help!
-Ram
 
Ad

Advertisements

B

Barry Schwarz

snip





my_list_t *
my_list_new(int flags, my_cmpfunc_t cmpfunc)
{
my_list_t *newlist;

#ifdef DS_DEBUG
printf("in my_list_new(%d, 0x%lx)\n", flags, cmpfunc);
#endif

if (flags != LIST_USERFUNC
&& flags != LIST_STACK
&& flags != LIST_QUEUE)
{
errno = EINVAL;
return NULL;
}

newlist = (my_list_t *)calloc(1, sizeof(my_list_t));

There is no benefit and a possible detriment when you cast the return
value of c/m/realloc.

You leave a couple of pointers in the allocated structure set to
all-bits-0. This need not be the representation of a NULL pointer; it
need not be a valid pointer value at all. If you want the pointers to
be NULL, set them so.
if (cmpfunc != NULL)
newlist->cmpfunc = cmpfunc;
else
newlist->cmpfunc = (my_cmpfunc_t)strcmp;
newlist->flags = flags;

return newlist;
}


I have added my objects in list.. now i want to search object_name at
specific node in list..

int
my_list_add(my_list_t *l, void *data)
{
my_listptr_t n, m;

n = (my_listptr_t)malloc(sizeof(struct my_node));
if (n == NULL)
return -1;
n->data = data;
l->nents++;


/* if the list is empty */
if (l->first == NULL)
{
l->last = l->first = n;
n->next = n->prev = NULL;
return 0;
}


if (l->flags == LIST_STACK)
{
n->prev = NULL;
n->next = l->first;
if (l->first != NULL)
l->first->prev = n;
l->first = n;

return 0;
}

if (l->flags == LIST_QUEUE)
{
n->prev = l->last;
n->next = NULL;
if (l->last != NULL)
l->last->next = n;
l->last = n;

return 0;
}

return 0;
}

I have search function like this..
int
my_list_search(my_list_t *l,
my_listptr_t *n, void *data,
my_matchfunc_t matchfunc)

What type is my_matchfunc_t? Yes, it can make a difference.
{


if (matchfunc == NULL)
matchfunc = (my_matchfunc_t)my_str_match;

if (*n == NULL)
*n = l->first;
else
*n = (*n)->next;



for (; *n != NULL; *n = (*n)->next)
{
if ((*(matchfunc))(data, (*n)->data) != 0)
return 1;
}

return 0;
}


I have list search function..

Is this deja vu?
int
my_list_search(my_list_t *l,
my_listptr_t *n, void *data,
my_matchfunc_t matchfunc)
{


if (matchfunc == NULL)
matchfunc = (my_matchfunc_t)my_str_match;

if (*n == NULL)
*n = l->first;
else
*n = (*n)->next;



for (; *n != NULL; *n = (*n)->next)
{

if ((*(matchfunc))(data, (*n)->data) != 0)
return 1;
}

return 0;
}

if you see the matchfunc(), its argument is a string from void *data ,
string from object_list struct(..->object_name)
So i cant re-write all the list functions for this..

please just help me.. during search, i have to get object_list data (-
match occurs.. if ((*(matchfunc))(data, (*n)->data) != 0)

Are you trying to say that member data in struct my_node actually
points to an object_list structure? If so, then you can access the
string pointed to by member object_name with the expression
((object_list*)((*n)->data))->object_name

If not, you are going to express the issue more clearly. It would
also help if you trimmed the quotes.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top