Unhandled exception in doubly linked lists

-5

I'm attempting to implement a limit order book in C++ (a very simple one) by having a std::map where the keys are price points and the values are PricePoint objects.

The Book class has two of these, bid and ask to store the buys and sells (respectively).

#include <iostream>
#include <map>
#include <list>
using namespace std;

#define MAX_NUM_ORDERS 512

class Order
{
  public:
  unsigned int id;
  unsigned int price;
  unsigned int volume;
  bool side;
  time_t added;
  time_t executed;
  time_t cancelled;

  Order *next;
  Order *prev;

  Order(unsigned int price, unsigned int volume, bool side)
  {
    this->id = 0;
    this->price = price;
    this->volume = volume;
    this->side = side;
    this->added = 0;
    this->executed = 0;
    this->cancelled = 0;
    this->next = 0;
    this->prev = 0;
  }
};

class PricePoint
{
  public:
    Order *head;
    Order *tail;

    PricePoint(void)
    {
      this->head = 0;
      this->tail = 0;
    }

    void insertAfter(Order *node, Order new_node)
    {
      new_node.next = node->next;

      if(node->next == 0)
      {
        this->tail = &new_node;
      }
      else
      {
        node->next->prev = &new_node;
      }

      node->next = &new_node;
    }

    void insertHead(Order new_node)
    {
      if(this->head == 0)
      {
        this->head = &new_node;
        this->tail = &new_node;
        new_node.prev = 0;
        new_node.next = 0;
      }
      else
      {
        insertAfter(this->tail, new_node);
      }
    }

    void insertTail(Order new_node)
    {
      if (this->tail == 0)
      {
        insertHead(new_node);
      }
      else
      {
        insertAfter(this->tail, new_node);
      }
    }

    unsigned int count(void)
    {
      unsigned int i;
      Order node(0, 0, false);

      while(node.next == 0)
      {
        for(i=0;i<=MAX_NUM_ORDERS;i++)
        {
          // lol
        }
      }

      return i;
    }

    bool empty(void)
    {
      if(this->head == 0)
      {
        return true;
      }
      else
      {
        return false;
      }
    }

    void print(void)
    {
      if(this->empty() == true)
      {
        cout<<"[None]"<<endl;
        return;
      }
      else
      {
        if(this->head != 0)
        {
          unsigned int i;
          Order *node = this->head; // start at the head

          cout<<"id, volume, added"<<endl; // labels

          while(node->next != 0) // while we're not at the end
          {
            cout<<node->id<<", "<<node->volume<<", "<<node->added<<endl;
            node = node->next;
          }
        }
        else // try and catch it again i guess?
        {
          cout<<"[None]"<<endl;
          return;
        }
      }
    }
};

class Book
{
public:
  map<int, PricePoint> bid; // buy-side
  map<int, PricePoint> ask; // sell-side

  int add(Order order)
  {
    order.id = this->bid.size() + this->ask.size() + 1; // this way, buy-side and sell-side orders have unique identifiers

    if(order.side == false) // buy order
    {
      if(this->bid.count(order.price) == 0) // if the price point isn't already there
      {
        PricePoint pp;
        pair<int, PricePoint> new_pp(order.price, pp);
        bid.insert(new_pp); // add the price point (i.e. add an entry to the map)
      }
      else
      {
        this->bid[order.price].insertTail(order); // insert at tail of the doubly linked list
      }
    }
    else if(order.side == true) // sell order
    {
      if(this->bid.count(order.price) == 0)
      {
        PricePoint pp;
        pair<int, PricePoint> new_pp(order.price, pp);
        ask.insert(new_pp); // add the price point (i.e. add an entry to the map)
      }
      {
        this->ask[order.price].insertTail(order); // insert at the tail of the doubly linked list
      }
    }

    return order.id; // the order's id
  }

  int cancel(unsigned int id)
  {

  }

  void print(void)
  {
    unsigned int i = 0;

    cout<<"-------------------------------------BIDS--------------------------------------"<<endl;
    cout<<this->bid.size()<<endl;

    for(i=0;i<this->bid.size();i++)
    {
      cout<<"Orders for $"<<i<<":"<<endl;
      this->bid[i].print();
    }
    i = 0;
    cout<<endl;

    cout<<"-------------------------------------ASKS--------------------------------------"<<endl;

    for(i=0;i<this->ask.size();i++)
    {
      cout<<"Orders for $"<<i<<":"<<endl;
      this->ask[i].print();
    }
    cout<<endl;
  }
};

int main(void)
{
  unsigned int i;
  Book orderbook; // our limit order book

  // some orders
  Order a(4, 33, false);
  Order b(4, 12, true);
  Order c(5, 33, true);

  //add them
  orderbook.add(a);
  orderbook.add(b);
  orderbook.add(c);

  cout<<"Order book is as follows:"<<endl;

  orderbook.print();

  system("pause");

  return 0;
}

I want to print the order book, but when I attempt to traverse the list I am met with unhandled exceptions, like so:

Unhandled exception at 0x00a418aa in orderbook.exe: 0xC0000005: Access violation reading location 0x00000039.

In the debugger, I'm seeing that the next pointer is eventually becoming junk, indicative I've failed to initialise correctly, yes?

Also, the program outputs junk data (also indicative of uninitialised pointers) before excepting.

Any help is much appreciated, thanking you very much.

c++
exception
asked on Stack Overflow Jul 18, 2014 by pingwing

1 Answer

0

These:

void insertAfter(Order *node, Order new_node)
void insertHead(Order new_node)
void insertTail(Order new_node)

insert a pointer to a local variable. They have to take a pointer:

void insertAfter(Order *node, Order* new_node)
void insertHead(Order* new_node)
void insertTail(Order* new_node)

try this (and correct it, i guess):

#include <iostream>
#include <map>
#include <list>
using namespace std;

#define MAX_NUM_ORDERS 512

class Order
{
  public:
  unsigned int id;
  unsigned int price;
  unsigned int volume;
  bool side;
  time_t added;
  time_t executed;
  time_t cancelled;

  Order *next;
  Order *prev;

  Order(unsigned int price, unsigned int volume, bool side)
  {
    this->id = 0;
    this->price = price;
    this->volume = volume;
    this->side = side;
    this->added = 0;
    this->executed = 0;
    this->cancelled = 0;
    this->next = 0;
    this->prev = 0;
  }
};

class PricePoint
{
  public:
    Order *head;
    Order *tail;

    PricePoint(void)
    {
      this->head = 0;
      this->tail = 0;
    }

    void insertAfter(Order *node, Order* new_node)
    {
      new_node->next = node->next;

      if(node->next == 0)
      {
        this->tail = new_node;
      }
      else
      {
        node->next->prev = new_node;
      }

      node->next = new_node;
    }

    void insertHead(Order* new_node)
    {
      if(this->head == 0)
      {
        this->head = new_node;
        this->tail = new_node;
        new_node->prev = 0;
        new_node->next = 0;
      }
      else
      {
        insertAfter(this->tail, new_node);
      }
    }

    void insertTail(Order* new_node)
    {
      if (this->tail == 0)
      {
        insertHead(new_node);
      }
      else
      {
        insertAfter(this->tail, new_node);
      }
    }

    unsigned int count(void)
    {
      unsigned int i;
      Order node(0, 0, false);

      while(node.next == 0)
      {
        for(i=0;i<=MAX_NUM_ORDERS;i++)
        {
          // lol
        }
      }

      return i;
    }

    bool empty(void)
    {
      if(this->head == 0)
      {
        return true;
      }
      else
      {
        return false;
      }
    }

    void print(void)
    {
      if(this->empty() == true)
      {
        cout<<"[None]"<<endl;
        return;
      }
      else
      {
        if(this->head != 0)
        {
          unsigned int i;
          Order *node = this->head; // start at the head

          cout<<"id, volume, added"<<endl; // labels

          while(node->next != 0) // while we're not at the end
          {
            cout<<node->id<<", "<<node->volume<<", "<<node->added<<endl;
            node = node->next;
          }
        }
        else // try and catch it again i guess?
        {
          cout<<"[None]"<<endl;
          return;
        }
      }
    }
};

class Book
{
public:
  map<int, PricePoint> bid; // buy-side
  map<int, PricePoint> ask; // sell-side

  int add(Order order)
  {
    order.id = this->bid.size() + this->ask.size() + 1; // this way, buy-side and sell-side orders have unique identifiers

    if(order.side == false) // buy order
    {
      if(this->bid.count(order.price) == 0) // if the price point isn't already there
      {
        PricePoint pp;
        pair<int, PricePoint> new_pp(order.price, pp);
        bid.insert(new_pp); // add the price point (i.e. add an entry to the map)
      }
      else
      {
        this->bid[order.price].insertTail(&order); // insert at tail of the doubly linked list
      }
    }
    else if(order.side == true) // sell order
    {
      if(this->bid.count(order.price) == 0)
      {
        PricePoint pp;
        pair<int, PricePoint> new_pp(order.price, pp);
        ask.insert(new_pp); // add the price point (i.e. add an entry to the map)
      }
      {
        this->ask[order.price].insertTail(&order); // insert at the tail of the doubly linked list
      }
    }

    return order.id; // the order's id
  }

  int cancel(unsigned int id)
  {

  }

  void print(void)
  {
    unsigned int i = 0;

    cout<<"-------------------------------------BIDS--------------------------------------"<<endl;
    cout<<this->bid.size()<<endl;

    for(i=0;i<this->bid.size();i++)
    {
      cout<<"Orders for $"<<i<<":"<<endl;
      this->bid[i].print();
    }
    i = 0;
    cout<<endl;

    cout<<"-------------------------------------ASKS--------------------------------------"<< ask.size() <<endl;

    for(i=0;i<this->ask.size();i++)
    {
      cout<<"Orders for $"<<i<<":"<<endl;
      this->ask[i].print();
    }
    cout<<endl;
  }
};

int main(void)
{
  unsigned int i;
  Book orderbook; // our limit order book

  // some orders
  Order a(4, 33, false);
  Order b(4, 12, true);
  Order c(5, 33, true);

  //add them
  orderbook.add(a);
  orderbook.add(b);
  orderbook.add(c);

  cout<<"Order book is as follows:"<<endl;

  orderbook.print();

//  system("pause");

  return 0;
 }
answered on Stack Overflow Jul 18, 2014 by Exceptyon

User contributions licensed under CC BY-SA 3.0