0

The purpose of the queue is to store pointers to objects of type T. The queue is used to push and pop objects on and off the queue as I traverse various data structures.

The queue works fine except the line :

out = t->payload;

(four lines from the bottom)

out never changes value to what is in t->payload. Looking at it in the debugger, I can see that t->payload is set correctly, but out is not assigned the value that is in t->payload. Can someone tell me what is going on?

template<typename T>
class Queue
{
private:
    struct node
    {
        T           *payload;
        struct node *next;
    };
    node *head;
    node *tail;
public:
    Queue()
    {
            head = new node;
        tail = new node;
        head->next = tail;
        tail->next = tail;
    }
        ...
    void push(T *payload)
    {
        node *newNode;
                node *temp;
        newNode = new node;
        temp = head->next;
        head->next = newNode;
        newNode->next = temp;
        newNode->payload = payload;
    }
    bool pop(T *out)
    {
        node *t;
        node *x;
        t = head;
        x = head;
        if(t == tail)
        {
            return false;  //already empty
        }
        while(t->next != tail)
        {
            x = t;
            t = t->next;
        }
        x->next = tail;
        out = t->payload;
        delete t;
        return true;
    }
}
Maroun
  • 94,125
  • 30
  • 188
  • 241
user758362
  • 291
  • 1
  • 6
  • 18
  • How do I make the code pretty. This is terrible. – user758362 Jan 26 '14 at 07:21
  • See http://stackoverflow.com/help/formatting – Maroun Jan 26 '14 at 07:22
  • use `
    ` and `
    ` tags     – user3159253 Jan 26 '14 at 07:22
  • I think the problem here is the delete t; in pop(), because it will call the default destructor, which will call the destructor on the members.. meaning that out is pointing to invalid memory.. my advise: either make payload a reference instead of a pointer since is shouldn't change anyway.. or implement a destructor for your struct which doesn't delete the payload, but sets it to nullptr, which means someone else (who?) is responsible for the delete. – cageman Jan 26 '14 at 07:49
  • The [minimal complete example](http://sscce.org) for this problem comes to a dozen lines. – Beta Jan 26 '14 at 07:54

5 Answers5

1
bool pop(T *out)
T *payload;
out = t->payload;

You are copying a T* to a T*, but the destination is a function parameter, which is invariably "in". Use a function result, or a T**out or a T * & out.

laune
  • 31,114
  • 3
  • 29
  • 42
1

Strictly speaking, I cannot reproduce your error: out is being set to the value of t->payload... within the function.

bool pop(T *out)
{
  ...
  out = t->payload;
  ...
}

You pass in the pointer out by value. The function modifies the pointer out which is a local variable, not the thing it pointed to when you called the function, and not the pointer that may exist as a variable in the calling code.

Beta
  • 96,650
  • 16
  • 149
  • 150
0

out = t->payload;

This is the source of your problem. You are severing the link between the parameter passed to the function. Your parameter out is pointer. If you want to use this paradigm (note: not the best idea), you should never change out. You should instead change the contents of out via 

*out = *(t->payload);

There are a two key issues with the above. This will croak if either out or t->payload is a null pointer. You can fix the former problem by passing a reference rather than a pointer. If you do that then you should use out = *(t->payload). This doesn't solve the problem of a null payload. You can fix that by ensuring that the payload is always non-null on adding a node.

A problem still remains, however. For example, what if that payload pointer is deleted, making dereferencing invalid? Using pointers is always a bit problematic.

David Hammen
  • 32,454
  • 9
  • 60
  • 108
  • Pointers aren't a problem if handled correctly ;-) But accepting a pointer in the push and expecting the pointed-to value in the pop isn't a good strategy. If a pointer goes in, a pointer must come out, and a null pointer won't be a problem. Moral of the story: never dereference a pointer that's been passed to you unless the contract says that it's not null (and here we agree). – laune Jan 29 '14 at 07:35
0

Note that a container is better off if it does not force pointer types on the client. The very simple example given below avoids the explicit asterisk (*) in the signatures. Thus, it is open to the user whether she'll trust a Keeper with a plain type or a pointer type. Either way data is simply copied to and from the "keep" instance variable. If she decides to use pointers, fine, but the responsibilty for allocating and freeing dynamic memory rests with her.

template<typename T>
class Keeper {
public:
  Keeper() : keeping(false){}
  virtual ~Keeper(){}
  void push( T & payload ){
    if( keeping ) throw "I'm busy";
    keeping = true;
    keep = payload;
  }
  bool pop( T & payload ){
    if( ! keeping ) return false;
    keeping = false;
    payload = keep;
    return true;
  }
private:
  bool keeping;
  T keep;
};
laune
  • 31,114
  • 3
  • 29
  • 42
-1

Try adding some brackets when you create a new object.

Like this:

head = new node();
tail = new node();
...

For further explanation as to why this is important, see these links:

Do the parentheses after the type name make a difference with new?

Not using parentheses in constructor call with new (c++)

EDIT: Added a few print statements to your code. The problem seems to be twofold.

  1. in push, instead of setting newNode->payload to payload, try setting it to new int(*payload). That way the value will be copied.
  2. At the end of pop, you set the address of out to t->payload, but t is deleted right after, so out is pointing to nothing. Instead, copy the value as described above.

If you correct these two things, it seems to work!

Edit 2: Implementing it as a reference

bool pop(T &out)
{
    node *t;
    node *x;
    t = head;
    x = head;
    if(t == tail)
    {
        return false;  //already empty
    }
    while(t->next != tail)
    {   
        x = t;
        t = t->next;
    }
    x->next = tail;
    out = *(t->payload);
    delete t;
    return true;
}
Community
  • 1
  • 1
anubhavashok
  • 532
  • 3
  • 15
  • Thanks for the suggestion. I will do that in the future. I added the brackets but out is still not being set to the t->payload value. – user758362 Jan 26 '14 at 07:38
  • Check the above two suggestions, they should solve your problem ;) – anubhavashok Jan 26 '14 at 07:50
  • Note that advise 1. is a design decision. Either you want to take ownership of the object pushed on the queue or you don't. Important thing is though that if you don't take ownership (which makes sense) i would advise to implement payload as a reference instead. This also means that you need to call delete for your payload somewhere else or you have a memory leak. – cageman Jan 26 '14 at 07:56
  • The advice given in 1 works, but it isn't what I want to do. I do not want to take ownership. Do you have an example of how to implement it as a reference? – user758362 Jan 26 '14 at 08:05
  • cageman: Yep, agreed. user758362: I have included an example of how to implement it as a reference above. Remember to change the first part too and it should work! – anubhavashok Jan 26 '14 at 08:12
  • Ok. I understand what is going on now. I am ok. – user758362 Jan 26 '14 at 08:12
  • your member should be T payload; void push(const T& payload) and T* pop(); return nullptr in the false cases and &payload in case something can be popped – cageman Jan 26 '14 at 08:15
  • @anubhavashok,@user758362: I've downvoted this answer because copying the payload from \*(t->payload) to a variable passed by reference and then deleting t, a node \*, where the last copy of that T\* may have been stored, is a 1st class memory leak. – laune Jan 26 '14 at 09:24
  • @laune It does not cause a memory leak. When you use indirection, you access the value of the variable which has nothing to do with the address of the containing variable. Once t is deleted, only the value still remains. Pls remove your downvote – anubhavashok Jan 27 '14 at 08:00
  • @anubhavashok,@user758362: You can do queue.push(new Data(...)), passing a pointer to a payload T=Data. That's stored in a node, allocated with new node, and this node is correctly deleted. But pop receives the *contents* of that Data object, stored in a plain and simple variable. The original heap address of that "new Data" is gone unless the module doing the push has kept it, is informed that it may not be needed etc etc. The -1 remains. If a pointer is passed into a container, the container must return a pointer. – laune Jan 27 '14 at 12:06
  • @laune Note that payload is a pointer to T. If T is a pointer itself, when the push is done, payload is a Data**. Its indirection will be a Data* (which contains the address its has to rightly point to NOT the value of the contents in the address). When pop is called, the contents of the address are not deleted, just the pointer to the pointer. As long as the module does not delete the contents of the pointer it just stored, there should be no error. Does this make sense? And is there anything I might have missed out? – anubhavashok Jan 28 '14 at 02:40
  • @anubhavashok Basically correct, but "if T is a pointer" requires you to instantiate the template as, for example, Queue. If that's an requirement for avoiding problems, the code must enforce it. - Never write code that invites the user to run into trouble. If you want to push(T*ptr) you may use pop(T**ptrptr) to get the pointer back. – laune Jan 29 '14 at 06:30
  • @laune The scope of this question was not to give advice on good practices in coding. The queue implementation by itself has NO memory leaks. I agree that messing with the pointers outside the queue may result in memory leaks. But that is the nature of using pointers and one must take measures to ensure that proper practices are used outside the module. Also, since the implementation inherently has no memory leaks, I dont see the point of a -1 where a simple comment warning the user to watch out for memory leaks outside the module would suffice. edit: Q and Q work without leaks! – anubhavashok Jan 29 '14 at 09:57
  • @anubhavashok Sigh. So please tell me how the code at the "push" end of the queue that does Msg* p = new Msg(); q.push( p ); can be notified that a pop of this payload has occurred and that it may be advisable to delete p. This wouldn't be an issue if you'd have proposed a pop that returns a T\*, not a T. (And I'll grant you that the original idea to force queuing pointers isn't very good.) – laune Jan 29 '14 at 12:04