Sign in to follow this  

Could use a hand with void**

This topic is 4087 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
(*(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
Quote:
Original post by Enigma
[code]
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
Guest Anonymous Poster
To OP
your pop( void** ) has a memory leak !!
its not done that way.
Do not malloc oldHead !!
It just needs to act as a pointer , which points to the head pointer or whatever .
Saw it so pointed it out :D

Share this post


Link to post
Share on other sites
A question -- I'm assuming you are writing every part of the code posted? Is any of it provided by your prof, and you aren't allowed to change it?

I'm assuming all of the code listed is your code (possibly foolishly). Then...

First, screw the assignment interface requirements.

You can have a good, sane interface -- then expose the stupid assignment interface as well.

Here is an interface to write to:


int StackPop( Stack* stack, StackNode** node );
int StackPush( Stack* stack, StackNode* node );
StackNode* MakeNode();
Stack* MakeStack();


Stack* GetGlobalStack();
void DestroyGlobalStack();


First rule: never ever call malloc for a StackNode outside of MakeNode(). MakeNode's job is to allocate a StackNode and set it up.

The same with Stacks -- the only function that allocates a stack is MakeStack().

GetGlobalStack() should return a pointer to the global stack -- ideally it should allocate the GlobalStack if it doesn't exist yet. Nobody else should even look at the global stack pointer. StackPush and StackPop should not call GetGlobalStack -- they should use the stack passed in to them.

The only time you should ever deal with void pointers is when playing with the StackNode->data member.

Get the above working.

Now, it is really easy to expose the interface your prof asks. Writing the professors "Pop" function is really easy, and you can check that the data makes sense along the way.

Share this post


Link to post
Share on other sites
Thanks for all the help guys. I hope I can get this sorted out. Yes, the mem leak, I just stopped caring, and just wanted something to work =)

The code is all mine EXCEPT for the function protos. It HAS TO BE, NO QUESTION ASKED void**, etc.

Yes the prof is stuck in the 80s, but what can I say? =)

Quote:

In particular, if you can't figure out these kinds of things for yourself, you have no business trying to do them in C.

I'll choose to read this in the best way possible. yes I normally code in c++, but I'll be honest, I've never really had a need to use void* or even double pointers for that matter. So even though I am comfortable with pointers, I am just getting caught up with ** b/c of my inexperiance with it. So i'm trying to learn. BTW, I spent a good 5hrs trying to sort this al out on my own before I came here, so I think that qualifies as a good try imho. But not to turn this into a flame war...

Cheers

//edit
HELL YES! I got. Cheers all

Share this post


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


It is my considered opinion that very few people in the world have any business doing anything in plain C these days, at all. In a great majority of cases, the extra work done and mental burden taken on (versus using C++ and taking advantage of the full standard library) are ridiculous for no performance benefit whatsoever; in a great majority of the remaining cases, the performance benefit is barely measurable and the extra work is still ridiculous; in almost every remaining case after that, the performance benefit is not enough to matter while the burden would still be eased significantly by things like built-in-to-the-language RAII. C++ can be treated, to a large extent, like a preprocessor for C which is orders of magnitude more powerful than the built-in one, and that's still not harnessing the full power of the language. And if you're one of those oddballs using C99 explicitly for the few minor changes that actually let you do very specific optimizations that C++ won't trust you to do... then you'd probably have more luck writing it in FORTRAN.

Seriously, the only real excuses for using C that I can consider are "a C++ compiler does not exist for the target platform" or (which usually goes hand-in-hand) "the target platform requires the final executable to be smaller than what is realizable if I include <iostream>".

Lots of profs - colleges - programming curricula in general - have some *very* strange ideas about how to teach "a deep understanding of the machine". (At least, I hope that's what they're after. I shudder to think that they expect to teach people *how to program* like this! Absolutely disgusting.) It's better done via instruction in what they call "computer organization", which might (but needn't) get as high-level as an introduction to some form of assembly language (the one chosen doesn't matter).

Quote:

The code is all mine EXCEPT for the function protos. It HAS TO BE, NO QUESTION ASKED void**


See? Pure idiocy. Nothing is gained by throwing away the idea of *data types*. In fact, this idea is *fundamental* to programming. And there's no reason the function can't accept a StackNode** instead, because that's the only kind of pointer it will *ever* receive. Nothing else is valid. Notice that the dereferenced parameter is cast to StackNode* *unconditionally*.

Please, PM me contact information for your prof (and/or the department of computer science, if appropriate). I am volunteering - with discretion assured, and at no cost and assuming full legal responsibility - to tell him/her/them off.

Share this post


Link to post
Share on other sites
Apparently Zohlman you forget. It matters not the language, it is the concept that counts. A good programmer does not care what language, he uses what language his boss (or Prof) says to use.

_Sigma, your prof (who I know) is not stuck in the 80's, C is widely used especially by low level hardware engineer's. Its OO brother C++ being widely used in game design. I teach a class on C++ myself, preferring OO over procedural programming.


Halsafar

Share this post


Link to post
Share on other sites
GBD is a good console debugger.
If you understand the low level layer of something then you can very easily master the higher level. You've been babied on GUI Debuggers. Learn the console debugger and not only can you take this knowledge the most basic UNIX machines you will see how for example VS Debugger works with a better picture. Or for example 'ddd' the gui version of gdb.

Would you have been more pleased if he gave us a entire library to debug as our FIRST debugging lesson?

Good thing I knew all this last year.


Halsafar

Share this post


Link to post
Share on other sites
Quote:
Original post by Halsafar
Apparently Zohlman you forget. It matters not the language, it is the concept that counts. A good programmer does not care what language, he uses what language his boss (or Prof) says to use.


Complete and utter bullshit. Any half-competent programmer will be aware that each language brings it's own advantages and disadvantages to the table and will attempt to use the right tool for the right job. He will not code his MMO entirely in assembly. He will not hack togehter a cgi script in C and make a webpage hammer the server with HTTP requests to simply embed a real time clock into his site. He will use javascript and let the client side take care of that, because it's the far superior solution. If horrible choices are made routinely and forced upon him, he may even consider updating his resume, fearing that he is on a sinking ship of incompetence among the project managers.

Certainly he should probably be able to hack together many monstrosities as bad technology choices are forced upon him, as a good programmer should be able to make do with what he's got. Being able to handle C programming should probably be on the list I'll even agree, as the concepts do carry over. But unless he's a two bit code monkey which has never left the mindless drone of endless reams of repetitive boilerplate, he will yearn for the greener pastures of actually being something half resembling productive.

Share this post


Link to post
Share on other sites
I agree with the idea of "Right tool for right job.". In fact this is the theme of the class. If you where a half-knowledgable programmer you would understand that programming concepts (searching and sorting) and data structures (stack, queue, lists, tree's, hashmaps) are things you MUST learn, regardless of language. If you have a mind full of concepts and a toolbox full of languages you can program anything for anyone.




Halsafar

Share this post


Link to post
Share on other sites
hey, i am in your class also
I completely understand why he is using Unix/C, and I don't think its about using the right tool for the job, he is just trying to teach very low level. If your not interested in the very low level workings of a computer go into engineering and more application based study.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Zahlman
Quote:
Original post by 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...


It is my considered opinion that very few people in the world have any business doing anything in plain C these days, at all. In a great majority of cases, the extra work done and mental burden taken on (versus using C++ and taking advantage of the full standard library) are ridiculous for no performance benefit whatsoever; in a great majority of the remaining cases, the performance benefit is barely measurable and the extra work is still ridiculous; in almost every remaining case after that, the performance benefit is not enough to matter while the burden would still be eased significantly by things like built-in-to-the-language RAII. C++ can be treated, to a large extent, like a preprocessor for C which is orders of magnitude more powerful than the built-in one, and that's still not harnessing the full power of the language. And if you're one of those oddballs using C99 explicitly for the few minor changes that actually let you do very specific optimizations that C++ won't trust you to do... then you'd probably have more luck writing it in FORTRAN.

Seriously, the only real excuses for using C that I can consider are "a C++ compiler does not exist for the target platform" or (which usually goes hand-in-hand) "the target platform requires the final executable to be smaller than what is realizable if I include <iostream>".

Lots of profs - colleges - programming curricula in general - have some *very* strange ideas about how to teach "a deep understanding of the machine". (At least, I hope that's what they're after. I shudder to think that they expect to teach people *how to program* like this! Absolutely disgusting.) It's better done via instruction in what they call "computer organization", which might (but needn't) get as high-level as an introduction to some form of assembly language (the one chosen doesn't matter).

Quote:

The code is all mine EXCEPT for the function protos. It HAS TO BE, NO QUESTION ASKED void**


See? Pure idiocy. Nothing is gained by throwing away the idea of *data types*. In fact, this idea is *fundamental* to programming. And there's no reason the function can't accept a StackNode** instead, because that's the only kind of pointer it will *ever* receive. Nothing else is valid. Notice that the dereferenced parameter is cast to StackNode* *unconditionally*.

Please, PM me contact information for your prof (and/or the department of computer science, if appropriate). I am volunteering - with discretion assured, and at no cost and assuming full legal responsibility - to tell him/her/them off.


For someone who only recently learned what actually happens if you use the & to take an address of an array you sure sound high and mighty up there.

Share this post


Link to post
Share on other sites
So uhmm...I have to ask:

What low level thing does this actually show? It's nice & fun to tout that you're learning low-level concepts, but all I see is a large number of poorly designed type casts and some crummy memory management.

I mean, I'm for-sure not a high & mighty expert on the topic, but it seems that if you want to demonstrate some of the concepts here there are a lot of better ways to do so other than horrid code.

But like I said, I could just be "missing the big picture" but somehow I doubt it. The whole thing about being coddled by a GUI Debugger made me LOL.

Quote:
If you understand the low level layer of something then you can very easily master the higher level.


By your logic, Assembly is a better 1st language than VB/Pascal/Python.

Share this post


Link to post
Share on other sites
Quote:
Original post by _Sigma

The code is all mine EXCEPT for the function protos. It HAS TO BE, NO QUESTION ASKED void**, etc.



How is this?


#define void Node
int Pop( void** node );
int Push( void* node );



Beautiful :-)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by ShadowWolf
So uhmm...I have to ask:

What low level thing does this actually show? It's nice & fun to tout that you're learning low-level concepts, but all I see is a large number of poorly designed type casts and some crummy memory management.

I mean, I'm for-sure not a high & mighty expert on the topic, but it seems that if you want to demonstrate some of the concepts here there are a lot of better ways to do so other than horrid code.


Horrid code is a great lesson. There will be plenty of it in the real world. Better learn how to deal with it as soon as possible. Those who have not seen horrid code do not know good code.

Some people here get a hissy fit as soon as they see something that isn't theoretically perfect C++ with the standard libraries and boost. Don't become one of them - learn bad code, because it is a fact of life that will not end any time soon.

Share this post


Link to post
Share on other sites

This topic is 4087 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this