Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > `void **' revisited: void *pop(void **root)

Reply
Thread Tools

`void **' revisited: void *pop(void **root)

 
 
Thomas Stegen
Guest
Posts: n/a
 
      10-27-2003
James Antill wrote:

> On Sun, 26 Oct 2003 15:33:26 -0600, James Hu wrote:
>
>
>>On 2003-10-26, Thomas Stegen <(E-Mail Removed)> wrote:

>
>
>>> struct node2 *p = *(struct node2 **)root;
>>>
>>>Since void is a generic pointer it is also a generic pointer
>>>to pointer.

>>
>>Good idea, just needs a minor correction:
>>
>> struct node2 **pp = root;
>> struct node2 *p = *pp;

>
>
> Why does it "need" this? Do you have chapter and verse for why the first
> form is undefined?
>


That is not where the problem is. The problem is the dereferencing of
root a bit further down without an explicit conversion from void*.
This is not the problem, but it solves the problem

--
Thomas.

 
Reply With Quote
 
 
 
 
Stig Brautaset
Guest
Posts: n/a
 
      10-27-2003
James Hu <(E-Mail Removed)> wrote:
> On 2003-10-26, Thomas Stegen <(E-Mail Removed)> wrote:
>> Since void is a generic pointer it is also a generic pointer
>> to pointer.

>
> Good idea, just needs a minor correction:
>
> void *pop(void *root)
> {
> struct node2 **pp = root;
> struct node2 *p = *pp;
> if (!p)
> return NULL;
> *pp = p->next;
> p->next = NULL;
> return p;
> }


Ah, this would do me nicely as long as it is conforming C. Using a `void
*' as argument did cross my mind at one point, but I discarded it
because I didn't think it would work since I wanted to pass data _back_
through it too.

It is weird-looking, but with proper documentation...

Thanks guys


--
brautaset.org
 
Reply With Quote
 
 
 
 
goose
Guest
Posts: n/a
 
      10-27-2003
Stig Brautaset <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>...
> Hi group,
>
> I'm playing with a little generic linked list/stack library, and have a
> little problem with the interface of the pop() function.


<rest of post snipped>

I've also played around with a generic list library, haven't
as yet /used/ it anywhere, but feel free to use and distribute.
this was done purely in response to an earlier thread on clc
(search google groups (clc) for goose ll_new to find the thread).

<beware>
there may be bugs, not fully tested as this is
just a toy for playing, not production.
</beware>


/*
credit all the macro-safety fixes to Bernd Jendrissek
(berndj at prism.co.za) and the initial rather dodgy
code to l. k. manickum (leem at acs.altech.co.za).

consider this code to be in the public domain, with
no warranties, etc ad nauseum ...

-lee
*/

#include <stdio.h>
#include <stdlib.h>


/* TODO: some sort of iterator */

/***************************/
/* some misc. declarations */
/***************************/
typedef int (*f_compare_ptr) (void *, void *);


/******************************/
/* all the node related stuff */
/******************************/
struct node_t {
void *data;
struct node_t *next;
struct node_t *prev;
};

struct node_t *fll_new (size_t size) {
struct node_t *node = malloc (sizeof *node);
if (!node) {
return NULL;
}
node->data = malloc (size);
if (!node->data) {
free (node);
return NULL;
} else {
node->next = NULL;
node->prev = NULL;
return node;
}
}


#define ll_node_new(the_type) fll_new (sizeof (the_type))
#define ll_node_del(node) \
do { free(node->data); free (node); } while (0)
#define ll_node_set(node,type,val) *(type *)node->data = val
#define ll_node_get(node,type) *(type *)node->data

#define ll_node_insert(list,node) do {\
struct node_t *t = list->next;\
list->next = node;\
node->prev = list;\
node->next = t;\
} while (0)

#define ll_node_remove(node) do {\
node->prev->next = node->next;\
node->next->prev = node->prev;\
ll_node_del (node);\
} while (0)


/******************************/
/* all the list related stuff */
/******************************/
struct list_t {
struct node_t *head;
struct node_t *tail;
};

struct list_t *fll_list_new (void) {
struct list_t *retvalue = malloc (sizeof *retvalue);
if (!retvalue) {
return NULL;
}
retvalue->head = fll_new (0);
if (!retvalue->head) {
free (retvalue);
return NULL;
}
retvalue->tail = fll_new (0);
if (!retvalue->tail) {
free (retvalue->head);
free (retvalue);
return NULL;
}
ll_node_insert (retvalue->head, retvalue->tail);
return retvalue;
}

void *fll_list_find (struct list_t *list, void *value, f_compare_ptr compare) {
struct node_t *t = list->head;
while (t!=list->tail) {
if ((*compare)(t->data, value)==0) {
return t;
}
t = t->next;
}
return NULL;
}

#define ll_list_insert(list,node) ll_node_insert (list->head, node)
#define ll_list_remove(list,node) ll_node_remove (node) /* for later */

#define ll_list_new fll_list_new /* also for future use*/

#define ll_list_del(list) do {\
while (list->head->next!=list->tail) {\
struct node_t *t = list->head->next;\
ll_node_remove (t);\
}\
ll_node_del (list->head);\
ll_node_del (list->tail);\
} while (0)

#define ll_list_find(list,value,functino) \
fll_list_find (list, value, functino)


/* the comparison function for ints */
int compare_ints (void *int1, void *int2) {
if (*(int *)int1 < *(int *)int2) {
return -1;
}
if (*(int *)int1 > *(int *)int2) {
return 1;
}
return 0;
}

int main (void) {
int i;
struct list_t *list;
struct node_t *t;

/* create a linked list */
list = ll_list_new ();
if (!list) {
printf ("no mem ?\n");
return EXIT_FAILURE;
}

/* add stuff into the list */
for (i = 0; i<10; i++) {
struct node_t *node = ll_node_new (int);
ll_node_set (node, int, i+42);
ll_list_insert (list, node);
printf ("set %i\n", i+42);
}

/* find an item in the list */
i = 45;
t = ll_list_find (list, &i, compare_ints);
printf ("item is %p\n value is %i\n", (void *)t, ll_node_get (t, int));

/* print the list out */
t = list->head->next;
while (t!=list->tail) {
int value = ll_node_get (t, int);
printf ("%i\n", value);
t = t->next;
}

/* delete the list */
ll_list_del (list);

return EXIT_SUCCESS;
}
 
Reply With Quote
 
Stig Brautaset
Guest
Posts: n/a
 
      10-27-2003
goose <(E-Mail Removed)> wrote:
> Stig Brautaset <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>...
>> Hi group,
>>
>> I'm playing with a little generic linked list/stack library, and have a
>> little problem with the interface of the pop() function.

>
><rest of post snipped>
>
> I've also played around with a generic list library, haven't
> as yet /used/ it anywhere, but feel free to use and distribute.
> this was done purely in response to an earlier thread on clc
> (search google groups (clc) for goose ll_new to find the thread).


I have written such a small library already (which I've used in a few
programs), but it (as yours) uses two allocations per node. I wanted to
get that down to one. Mostly out of curiosity, to be honest.

http://www.brautaset.org/projects/#yalla

><beware>
> there may be bugs, not fully tested as this is
> just a toy for playing, not production.
></beware>


Likewise

Stig

--
brautaset.org
 
Reply With Quote
 
James Hu
Guest
Posts: n/a
 
      10-27-2003
On 2003-10-27, Stig Brautaset <(E-Mail Removed)> wrote:
> goose <(E-Mail Removed)> wrote:
>>
>> I've also played around with a generic list library, haven't
>> as yet /used/ it anywhere, but feel free to use and distribute.
>> this was done purely in response to an earlier thread on clc
>> (search google groups (clc) for goose ll_new to find the thread).

>
> I have written such a small library already (which I've used in a few
> programs), but it (as yours) uses two allocations per node. I wanted to
> get that down to one. Mostly out of curiosity, to be honest.
>
> http://www.brautaset.org/projects/#yalla
>
>><beware>
>> there may be bugs, not fully tested as this is
>> just a toy for playing, not production.
>></beware>

>
> Likewise


One way to reduce the number of allocations is to provide an inheritance
interface to your list. This way is closest in spirit to the interface
you posted recently.

---
#define IS_A(type) type is_a

struct listnode {
struct listnode *next;
};

struct list {
struct listnode *top;
}

extern int push(struct list *l, struct listnode *n);
extern struct listnode * pop(struct list *l);

#define PUSH(root,node) push(&root->is_a, &node->is_a)
#define POP(root) pop(&root->is_a)
---
struct my_listnode1 {
IS_A(struct listnode);
int data;
};

struct my_list1 {
IS_A(struct list);
};

struct my_listnode2 {
IS_A(struct listnode);
double data;
};

struct my_list2 {
IS_A(struct list);
};
---

Another way to reduce the number of allocations is to provide a factory
mechanism for creating nodes.

---
struct listnode; /* opaque */

/* allocates a listnode */
extern struct listnode * make_listnode(size_t data_size);

/* returns pointer to data portion of listnode */
extern void * listnode_data(struct listnode *node);

... rest of listnode interface ...
---

-- James
 
Reply With Quote
 
The Real OS/2 Guy
Guest
Posts: n/a
 
      10-28-2003
On Mon, 27 Oct 2003 16:17:04 UTC, Stig Brautaset <(E-Mail Removed)>
wrote:

> I have written such a small library already (which I've used in a few
> programs), but it (as yours) uses two allocations per node. I wanted to
> get that down to one. Mostly out of curiosity, to be honest.


Legitime because avoiding pointers is avoiding memory overload.


------------list.h-------------

typedef void *(*pfnlist)(void *elem);

void *new_list(void *root, size_t size);
void *insert_list(void *root, void *elem);
void *remove_list(void *elem, pfnlist);
.......

typedef struct list *PLIST; /* incomplete type - but enough to use */
/* it as self document placeholder */
/* instead of plain void* in the caller*/
--------------------------------

------------list.c--------------
struct list {
struct list *pNext;
} list;

/* create new node, insert at end of list */
void* new_list(void *root, size_t size) {
struct list *pel = malloc(sizeof(*p) + size);
struct list *pprev = root;
struct list *pcur;
if (p) {
/* insert at end of list */
for (pcur = root; pprev->pNext; pprev = pcur, pcur = pcur->
pNext)
;

pcur->pNext = pel; /* same as *pcur = pel; */
pel->pNext = NULL;
}
return pel;
}

...........

-------------data.c---------

#include "list.h" /* anything we need to know about a list */

struct data {
PLIST pNEXT; /* must be 1. member of struct! */
/* data definitions */
} data;

struct data *root = NULL;


struct data *p = new_list(&root, sizeof(*p);
.......

-----------------------------


The same is for tree:

struct tree {
struct tree *pNelt;
struct tree *pPre;
} tree;

We use the warranty the standard gives about the member alignment of
the first element of a struct. So even if we address

struct data data;
struct data p = NULL;

struct list *pl = &p;
struct list *pn = pl->pNext;
struct list *pn2 = *p1;

pl->pNext = ....;

the target is always the same pointer.




--
Tschau/Bye
Herbert

eComStation 1.1 Deutsch wird jetzt ausgeliefert!
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is the difference between void proba(); and void proba(void); ??? PencoOdStip@gmail.com C++ 1 05-23-2007 07:12 PM
what is the difference, void func(void) and void fucn() noblesantosh@yahoo.com C Programming 5 07-22-2005 04:38 PM
"void Method()" vs "void Method(void)" Ollej Reemt C++ 7 04-22-2005 03:47 AM
returning a void (*)(void) Sergio C++ 6 01-05-2005 08:30 PM
[Slightly OT] Casting non-void function results to void in modern compilers. David M. Wilson C Programming 8 01-07-2004 07:32 AM



Advertisments