Could use a hand with void**

Started by
28 comments, last by MaulingMonkey 17 years, 6 months ago
Alright, I have searched, fiddled, asked around, and am at a complete loss as to what I should do here. Pretty much, the assignment is to create a stack based calculator. I am implimenting my stack as a linked list. Input into the calc is like thus: 'push i 56' would specify that an integer of value 56 should be pushed onto the stack. //edit forgot to mention that I am parsing the input (push i 56 for example) in a function call right before the push onto the stack, which works. The part I am having a hard time with is this: The pop function's proto is

//returns 1 on ok, -1 if error occurs
 int Pop(void **item);
I pass it a node of the linked list, which it is supposed to fill, which I can then pass to other functions.

//Temp stacknode to pass to pop
StackNode *dummy;
dummy = (StackNode*)malloc(sizeof(StackNode));
dummy->data = (void*)malloc(sizeof(void));
dummy->next = NULL;
dummy->prev = NULL;
dummy->type = ' ';

ZeroMemory(dummy,sizeof(StackNode));

//pas it in
Pop((void*)&dummy);

//dummy is always a bad pointer by the time I get here
if(dummy->type == 'i')
{
    printf("Contents were %d\n",*(int*)(dummy->data));
}


Pop function


 // - retrieve the item from the stack
 int Pop(void **item)
 {
      /*since this is a linked list, and we are removing the head node, headnode->next becomes the new head. If headnode->next is null, then the head node is set to null, so when push is called, this is checked so a new headnode can be created. Old head points to the old headnode*/

	StackNode *oldHead = (StackNode*)malloc(sizeof(StackNode));


	if(oldHead == NULL)
		return -1;

	ZeroMemory(oldHead,sizeof(StackNode));

     /*Runtime stack is just the uper level of the linked list*/
	oldHead = runTimeStack.head;
	runTimeStack.head = runTimeStack.head->next;

	if(oldHead->type == 'i')
	{
              /* So this portion works, it is being assigned the right values from what I can see tracing it with VS 2k5*/
		(*(StackNode*)(item)).data = *(int*)(oldHead->data);
		(*(StackNode*)(item)).type = (oldHead->type);
               /*This printf does infact print what is in the head node*/
		printf("What really came off was %d\n",(*(StackNode*)(item)).data);
	}
	
	return 1;
 }


Node struct in case this helps at all

typedef struct _node 
{
	void* data;
	char type;
	struct _node* next;
	struct _node* prev;
	
} StackNode;


typedef struct _stack
{
	StackNode *head;
	unsigned int size;
} Stack;



static Stack runTimeStack;

 int Push( void *item);

 int Pop(void **item);


So the comments show what is happening and where my errors are. pretty much, after the pop call, even though item in the pop call is getting assigned the right value, it seems this is a problem of byval instead of byref. But thats the thing, as I can't sort out what i'm doing wrong to have dummy (item in the function) modified by the function. Any help I get would be very very very much appreciated. O btw, this is C not C++. Cheers
Advertisement
You should really explicitly define types of objects and such. The use of void pointers of any kind can be problematic and extremely hard to debug.
There was a saying we had in college: Those who walk into the engineering building are never quite the same when they walk out.
has to be void* and void** I have no choice in this matter.
(*(StackNode*)(item)).data = *(int*)(oldHead->data);(*(StackNode*)(item)).type = (oldHead->type);

item is as follows (for example):
+----+----+----+----+----+----+----+----+----+----+----+----+|item| ?? | ?? | ?? |dumy| ?? | ?? | ?? | ?? | ?? |data|type|+----+----+----+----+----+----+----+----+----+----+----+----+    |                ^  |                          top of stack    +----------------+  +--------------->?      points to dummy       points to some                          unknown place

Then you cast it to a StackNode *, which means you interpret it as:
+----+----+----+----+----+----+----+----+----+----+----+----+|item| ?? | ?? | ?? |StackNode| ?? | ?? | ?? | ?? |data|type|+----+----+----+----+----+----+----+----+----+----+----+----+    |                ^                             top of stack    +----------------+      points to dummy

Then you dereference and write data and type:
+----+----+----+----+----+----+----+----+----+----+----+----+|item| ?? | ?? | ?? |data|type| ?? | ?? | ?? | ?? |data|type|+----+----+----+----+----+----+----+----+----+----+----+----+    |                ^                             top of stack    +----------------+      points to dummy

Then you return from the function and item is once again a void * * (item here actually equates to &dummy):
+----+----+----+----+----+----+----+----+----+----+----+----+|item| ?? | ?? | ?? |data|type| ?? | ?? | ?? | ?? |data|type|+----+----+----+----+----+----+----+----+----+----+----+----+    |                ^  |                          top of stack    +----------------+  +--------------->elsewhere      points to dummy       points to the address                          that happens to equal                          the value of data

What you want is:
+----+----+----+----+----+----+----+----+----+----+----+----+|item| ?? | ?? | ?? |dumy| ?? | ?? | ?? | ?? | ?? |data|type|+----+----+----+----+----+----+----+----+----+----+----+----+    |                ^  |                          ^    +----------------+  +--------------------------+      points to dummy       points to existing node

Σnigma
Thanks for the reply Enigma. Very sexy pics ;)

So that makes a good deal of sense. So, probably a silly question given what you wrote, but what do I need to do to get that result? I'm getting caught up when to cast, dereference etc. Are you suggesting I shouldn't cast to StackNode?
So I suppose if you can give me the two lines of code to do that correctly, it with your images should make a great deal of sense!

Cheers
:( I am in desperate need of help! If anyone can elaborate on Enigma's diagrams (code is good :P haha) I'd be very grateful!
Quote:Original post by Enigma

What you want is:
+----+----+----+----+----+----+----+----+----+----+----+----+|item| ?? | ?? | ?? |dumy| ?? | ?? | ?? | ?? | ?? |data|type|+----+----+----+----+----+----+----+----+----+----+----+----+    |                ^  |                          ^    +----------------+  +--------------------------+      points to dummy       points to existing node

Σnigma


((StackNode**)item) - pointer to dummy
(*((StackNode**)item)) - pointer to an existing node (you overwrote this value)
(*(*((StackNode**)item))) - the node(actual node memory)
0xa0000000
Since this is C there's actually no casting required.

I don't want to just give you the answer, since you say this is an assignment, but consider this analogy:
int i = 7;int j;set(&j, i);void set(int * j, int i){	*j = i;}
By the way, I'm unconvinced of the need to malloc in Pop. Presumably you're passing in pointers to StackNodes when you push. You should probably be getting those exact same pointers back when you Pop, rather than a copy.

Σnigma
0) For something like this, there is very little justification I could accept for "I have to use C" - except possibly "I'm doing this for school and my prof is stuck in the 80s". Although a prof stuck in the 80s wouldn't speak of ZeroMemory() but instead memset().

1) In particular, if you can't figure out these kinds of things for yourself, you have no business trying to do them in C. It's not as if there's any significant amount of fat *available* to trim out of a standard C++ (using the standard library) implementation, and there are much better ways to learn how low-level algorithmic ideas.

2) Notwithstanding that, and assuming we're stuck with C, there is much better code organization - and interface - available.

- In C, don't cast the result of malloc(). This hides the error of failing to include stdlib.h. Oh, make sure you include stdlib.h. :)

- "sizeof(void)" looks rather suspicious to me, especially as a malloc() argument. Just default to a NULL pointer.

- The ZeroMemory() call in the first source box is silly and redundant; you just finished initializing all the values, and then you scrub them all over anyway. BTW, ' ' does NOT have an ascii value of 0. It has an ascii value of 32.

- There's absolutely no reason to use a void** for the function prototype. While it's true that the StackNode.data member is of some unknown hidden-behind-void-* type, we're always going to pass in a StackNode to be initialized, and the list is always going to pop a StackNode out and assign from one StackNode to another.

- We could at least learn the lessons of C++ and set up free functions to do construction/destruction/assignment-like tasks, even if the language won't call them for us automatically. It's just good factoring.

- The interface is needlessly complex, and introduces a needless copy. Just have pop() *return* a StackNode*; return NULL if nothing is found, and otherwise return a pointer to the old top node *itself*, which has merely been disconnected. There's no reason to copy the data because *we're removing it from the list anyway*. Note that pop() as written leaks memory *twice*: once because OldHead is pointed at a new allocation and then re-pointed at the head of the list without anything being done with/to the new allocation, and again because the old head node is removed from the list and we lose the pointer to it at the end of the function, but never deallocate it. The proposed interface sidesteps that difficulty (except that the caller will have to deallocate).

- This assignment doesn't work for two reasons:

(*(StackNode*)(item)).data = *(int*)(oldHead->data);


First, the data from the old head is being dereferenced, to yield an int, but then the int is being directly assigned to the void* data member of 'item'. That doesn't match in terms of levels of indirection. Second, that 'data' member never actually got pointed towards any memory allocation, so there's nowhere to copy the int into. Note: void* is not "an untyped piece of memory", it is a pointer to such.

/* Our wrapper functions */StackNode* newStackNode() {  StackNode* result = malloc(sizeof(StackNode));  if (!result) return NULL;  result->data = NULL;  result->next = NULL;  result->prev = NULL;  result->type = ' ';  return result;}void destroyStackNode(StackNode* toDestroy) {  switch(toDestroy->type) {    case 'i':    assert(toDestroy->data);    free((int*)(toDestroy->data));    break;    case ' ':    break;    default:    assert(false);  }  free(toDestroy);}StackNode* intStackNode(int i) {  StackNode* result = newStackNode();  if (!result) return NULL;  result->data = malloc(sizeof(int));  if (!result->data) {    destroyStackNode(result);    return NULL;  }  result->type = 'i';  return result;}StackNode* copyStackNode(StackNode* other) {  switch(other->type) {    case 'i':    /* The prev and next pointers are not "intrinsic"       properties that we want to copy. */    return intStackNode(*(int*)(other->data));    case ' ':    return newStackNode();    default:    assert(false);  }}void assignStackNode(StackNode* lhs, StackNode* rhs) {  /* Behold, you can do copy-and-swap in C, although maybe you don't need to */  StackNode* other;   void* tmp;  other = copyStackNode(rhs);  tmp = lhs.data;  lhs.data = other.data;  other.data = tmp;  lhs.type = other.type;  destroyStackNode(other);}/* We can access data like this: */int* getDataIfInt(StackNode* node) {  return (node->type == 'i') ? (int*)(node->data) : NULL;}/* We'll call pop() like this: */StackNode *top;int* data;top = Pop();data = getDataIfInt();if (data) {    printf("Contents were %d\n", *data);}destroyStackNode(top);/* You could wrap that kind of logic up into a function, too, if you don't want   to burden clients with the destroyStackNode() responsibility. *//* We'll implement pop() like this: */StackNode* Pop() {  StackNode* oldHead;  oldHead = runTimeStack.head;  if (!oldHead) { return NULL; }  runTimeStack.head = runTimeStack.head->next;  /* Disconnect stuff */  runTimeStack.head->prev = NULL;  oldHead->next = NULL;  /* Do upkeep on the stack */  runTimeStack.size--;  return oldHead;}
Quote:Original post by Zahlman
0) For something like this, there is very little justification I could accept for "I have to use C" - except possibly "I'm doing this for school and my prof is stuck in the 80s". Although a prof stuck in the 80s wouldn't speak of ZeroMemory() but instead memset().

1) In particular, if you can't figure out these kinds of things for yourself, you have no business trying to do them in C. It's not as if there's any significant amount of fat *available* to trim out of a standard C++ (using the standard library) implementation, and there are much better ways to learn how low-level algorithmic ideas.


</holierthanthou>

"If you can't figure out these things for yourself, you have no business blah blah...."

If you can't figure out these things for yourself you have no business learning them? Hello? He's obviously taking some kind of course here...

This topic is closed to new replies.

Advertisement