Jump to content
  • Advertisement
Sign in to follow this  
_Sigma

Could use a hand with void**

This topic is 4453 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
(*(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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
:( 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!

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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;
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!