Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.

Due to spam on this forum, all posts now need moderator approval.

 Entire forum ➜ Programming ➜ General ➜ Owned pointers

Owned pointers

It is now over 60 days since the last post. This thread is closed.     Refresh page


Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Tue 05 Aug 2003 11:11 PM (UTC)

Amended on Tue 05 Aug 2003 11:13 PM (UTC) by Nick Gammon

Message
The classes below use an STL map to automatically record pointer "ownership". The intention is that you could have (in a game for instance) pointers to things (like players) where other things might refer to them (eg. a player owns an object, a room contains a player, a player follows another player).

The problem is, though, that if you store the actual pointer then the pointer might be deleted (eg. player A follows player B, however midway through, player B disconnects, and his pointer is deleted. Now the pointer that player A has is invalid, however he doesn't know it).

To work around this, we store an identifier (id) instead of the actual pointer, and then store a mapping between identifiers and their pointers in a map.

The interesting thing about the code below is this is all automatic, provided you derive the class from the appropriate auto-map pointer class. See the example below for how you might do this. Then, doing a "new" automatically adds the newly created pointer to the appropriate map, and doing a "delete" removes it, without any extra lines of code being needed.

Finally, for type-safety, instead of straight integers the identifiers are a small class of their own, so the compiler will restrain you from accidentally using (say) a player ID when you meant to use a room ID.

objectmap.h file



/*

OK, what is all this about?

  I am trying to solve the problem of things in a busy environment
  (eg. a MUD) where you might have lots of pointers which are being
  created and deleted (eg.  players joining, leaving, objects being
  created and destroyed), and you want to have things referring to each
  other. eg. a player might be following another player, or an event might
  refer to a player or object.

  Rather than storing pointers to the thing-to-be-referred-to we will 
  get a unique ID and store that instead. Then, before attempting to use
  the thing, we will look up its ID in the ID map. If found, the object
  still exists and we can use the looked-up pointer. If the object has been
  delete for any reason, then the lookup will fail, and we know the object
  no longer exists.

  The constructor is supplied the owner map (eg. a map of rooms), so we 
  know which map to remove ourselves from eventually, and can add ourselves
  to it initially. 

  Later on, other things would use GetId to find the object's ID so they can
  refer to it (by storing in a uint64 field).

  Then, when they want to get the actual pointer they use FindObject (or similar)
  to find the pointer to it. If NULL is returned, the object has gone away.

  A note of caution - because deleting the object also deletes it from the owner
  map you want to be careful with iterators, deleting an item from a map invalidates
  the iterator. Thus the normal for_each would fail if something for_each calls
  deletes the item it found (ie. the item deletes itself). The function provided below:
  safe_for_each increments the iterator before calling the function so it should
  work, even if the function deletes the object.

  Example:

  //  owner map:

  class tPlayer;

  tPointerOwner<tPlayer> PlayerMap;

  // example owned object - passes map name to constructor:

  class tPlayer : public tObject<tPlayer>
    {

    public:

    // constructor
    tPlayer () : tObject<tPlayer> (PlayerMap) {};

    };  // end of class tPlayer

  // create an instance:

  tPlayer * p1 = new tPlayer;

  // is now in map:

  cout << "Map count: " << PlayerMap.size () << endl;

  // get id from pointer:

  tId<tPlayer> i = p1->GetId ();   // get player's ID

  // get pointer back from id:

  tPlayer * p = PlayerMap [i];

  if (p)  // if not null, it exists in map, thus pointer is valid
    {
    // do something with it
    }

  // delete any of the pointers - removes it from the map

  delete p;

  // not in map now:

  cout << "Map count: " << PlayerMap.size () << endl;

*/

// handy typedef for 64-bit integers
#ifdef WIN32
  typedef __int64 int64;
  typedef unsigned __int64 uint64;
#else
  typedef long long int64;
  typedef unsigned long long uint64;
#endif  

// the base type for our pointer identifiers
typedef uint64 id;

// get unique number (adds 1 every time)
uint64 unique (void);

// identifier for a class - this gives type safety over straight integers
template <class T>
class tId
  {
  protected:

    id ID;    // the identifier

  public:

    // default constructor for when we don't have an ID yet
    tId () : ID (0) { };

    // normal constructor - creates with supplied id
    tId (const id i) : ID (i) { };

    // copy constructor 
    tId (const tId & rhs) : ID (rhs.ID) { };

    // operator=  (assignment)
    const tId & operator= (const tId & rhs)
      {
      ID = rhs.ID;
      return *this;
      };

    // cast to id - return internal ID
    // commented out because with it we lose some type-safety
    //   operator id () const { return ID; };

    // return value (number) corresponding to internal ID
    id Value () const { return ID; };

  };  // end of class tId

template <class T>
class tObject;

// an owner of pointers 
// it uses a map to store them, for fast-lookup purpose
// insertion and deletion is restricted to the friend class (the pointers)

template <class T>
class tPointerOwner
  {
  public:

    typedef map<id, T *, less<id> > container_type;

    typedef typename container_type::value_type     value_type;
    typedef typename container_type::size_type      size_type;
    typedef typename container_type::iterator       iterator;
    typedef typename container_type::const_iterator const_iterator;

  protected:

    // this is where we put them
    container_type c;     // container

  public:

    bool empty () const                        { return c.empty (); }
    size_type size () const                    { return c.size ();  }
                                              
    iterator find (const id& key)              { return c.find (key); }
    const_iterator find (const id& key) const  { return c.find (key); }

    iterator begin()                           { return c.begin (); }
    const_iterator begin() const               { return c.begin (); }

    iterator end()                             { return c.end (); }
    const_iterator end() const                 { return c.end (); }
                                
    // operator [] gives us back the original pointer

    T * operator[] (const tId<T> id) 
      {
      iterator i = c.find (id.Value ());

      if (i == c.end ())
         return NULL;

      return (T *) i->second;
      }

  protected:
  friend class tObject<T>;  // so they can erase from us

  // insertion and deletion is protected so only our friend 
  // (the object who we are storing in the list)
  // can delete or insert

    void insert(const tId<T> item, T * ptr)
      {
      c [item.Value ()] = ptr;
      };

    void erase (const tId<T> item)
      {
      iterator i = c.find (item.Value ());
      if (i != c.end ())
        c.erase (i);
      }

  };  // end of class tPointerOwner


// object for a class
template <class T>
class tObject
  {

  public:

  typedef tPointerOwner<T> tOwnerMap;

  private:
    tOwnerMap & m_owner_map;   // the map that points to us
    const tId<T>   m_id;          // our unique ID

  public:

  // constructor remembers which map points to us, gets unique ID
  tObject (tOwnerMap & owner_map)  // owning map
     : m_owner_map (owner_map), 
       m_id (unique ())
    {
     // put ourselves into the map
    m_owner_map.insert (m_id, reinterpret_cast <T *> (this)); 
    };  // constructor
  
  // destructor deletes us from the map
  virtual ~tObject ()
    {
    m_owner_map.erase (m_id);
    }

  // return details about this object
  tOwnerMap &  GetMap  (void) const { return m_owner_map; };
  tId<T>       GetId   (void) const { return m_id; };

  };  // end of class tObject


// safe_for_each.  Apply a function to every element of a range.
// should handle correctly an element deleting itself 

template <class ITER, class F>
F safe_for_each (ITER first, ITER last, F func) 
  {
  while (first != last)
    func (*first++);
  return func;
  }


- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #1 on Tue 05 Aug 2003 11:15 PM (UTC)
Message
You will need this function somewhere to provide the unique numbers ...


uint64 unique (void)
  {
  static uint64 iNextUnique = 1;
  return iNextUnique++;
  } // end of unique

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #2 on Tue 05 Aug 2003 11:24 PM (UTC)

Amended on Sat 16 Aug 2003 08:13 AM (UTC) by Nick Gammon

Message
This rather messy example program demonstrates using the owned pointers in a reasonably realistic situation.


// disable warnings about long names
#ifdef WIN32
  #pragma warning( disable : 4786)
#endif

#include <iostream>
#include <string>
#include <map>

using namespace std;  

#include "objectmap.h"

class tPlayer;

tPointerOwner<tPlayer> PlayerMap;

class tRoom;

tPointerOwner<tRoom> RoomMap;

class tPlayer : public tObject<tPlayer>
  {

  string m_sName;    // who we are

  public:

  tPlayer (const string sName) : 
     tObject<tPlayer> (PlayerMap), m_sName (sName)
    {
    cout << "tPlayer constructor, ID = " << (int) GetId ().Value () << endl;
    };

  ~tPlayer ()
    {
    cout << "tPlayer destructor for " << m_sName << endl;
    };

  string GetName (void) const { return m_sName; };


  };  // end of class tPlayer

class tRoom : public tObject<tRoom>
  {

  string m_sName;    // where we are

  public:

  tRoom (const string sName) : 
     tObject<tRoom> (RoomMap), m_sName (sName)
    {
    cout << "tRoom constructor, ID = " << (int) GetId ().Value () << endl;
    };

  ~tRoom ()
    {
    cout << "tRoom destructor for " << m_sName << endl;
    };

  string GetName (void) const { return m_sName; };


  };  // end of class tRoom
        
uint64 unique (void)
  {
  static uint64 iNextUnique = 1;
  return iNextUnique++;
  } // end of unique

void listplayers (const pair <tId<tPlayer>, tPlayer *> item)
  {
  cout << " ** name = " << item.second->GetName () << endl;
  } // end of listplayers

void listrooms (const pair <tId<tRoom>, tRoom *> item)
  {
  cout << " ** name = " << item.second->GetName () << endl;
  } // end of listrooms

void delete_north_wing (const pair <tId<tRoom>, tRoom *> item)
  {
  if (item.second->GetName () == "north wing")
    delete item.second;
  } // end of delete_north_wing

int main (void)
  {

  tPlayer * p1 = new tPlayer ("nick");
  tPlayer * p2 = new tPlayer ("john");

  tRoom * r1 = new tRoom ("west wing");
  tRoom * r2 = new tRoom ("north wing");
  
  cout << "Number of items in map is now " << PlayerMap.size () << endl;

  tId<tPlayer> i = p1->GetId ();   // get player 1's ID
  tId<tRoom> j = r1->GetId ();     // get room 1's ID

  tId<tPlayer> m = i;   // assign IDs (with constructor)
  m = i;                // again

  cout << "size of m = " << sizeof (m) << endl;

//  tId<tRoom> k = p1->GetId ();    // syntax error, type mismatch
  
//  k = p1->GetId ();     // syntax error, type mismatch

  cout << "ID of first item is " << (int) i.Value () << endl;

  tPlayer * p = PlayerMap [i];

  cout << "Name of first item is " << p->GetName () << endl;

  safe_for_each (PlayerMap.begin (), PlayerMap.end (), listplayers);
  safe_for_each (RoomMap.begin (), RoomMap.end (), listrooms);

  delete p1;

  safe_for_each (RoomMap.begin (), RoomMap.end (), delete_north_wing);

  cout << "Number of items in player map is now " << PlayerMap.size () << endl;
  cout << "Number of items in room map is now " << RoomMap.size () << endl;

  safe_for_each (RoomMap.begin (), RoomMap.end (), listrooms);

  return 0;
  } // end of main




This should compile and run under Windows or Linux, in conjunction with the objectmap.h file given above.

It creates two simple classes (player and room) based on the object class, and creates a couple of instances of each.

It uses safe_for_each to iterate in a number of ways, including deleting the object during the iteration. You can see from the debugging displays that the map items are indeed added and removed.

You can see the use of the type-safe identifiers, eg.


tId<tPlayer> i;


This is an identifier for a tPlayer class. The commented-out assignment would cause a compile error ...


tId<tRoom> k = p1->GetId ();


Without the type-safe tId class, it would simply assign one integer to another without warning.

If you really want to know the underlying number you can use the Value () function, eg.


cout << "ID of first item is " << (int) i.Value () << endl;


The cast to int here is used because of an error generated by cout - it doesn't seem to handle 64-bit integers.

Example output

tPlayer constructor, ID = 1
tPlayer constructor, ID = 2
tRoom constructor, ID = 3
tRoom constructor, ID = 4
Number of items in map is now 2
size of m = 8
ID of first item is 1
Name of first item is nick
** name = nick
** name = john
** name = west wing
** name = north wing
tPlayer destructor for nick
tRoom destructor for north wing
Number of items in player map is now 1
Number of items in room map is now 1
** name = west wing






- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #3 on Fri 15 Aug 2003 11:01 PM (UTC)

Amended on Fri 15 Aug 2003 11:02 PM (UTC) by David Haley

Message
Hi, long time no see. Just got back recently from the UK. :)


Well Nick, that's certainly a really neat piece of code. If I were to make a new MUD code base from nearly scratch, I'd certainly use something like that, but for now it's too hard to implement. It'd mean going through everything and changing how it works.

There are a few problems I see though. When you store a player with its unique ID, and then get a pointer to it, and delete the original object, as far as I can tell you have no way of checking if your pointer is still valid. Furthermore, if you try to access your pointer, it will crash, because the memory has already been deleted.

Take the following code. I took it from your example, and took out the parts I don't need.

  tPlayer * p1 = new tPlayer ("nick");

  tId<tPlayer> i = p1->GetId ();   // get player 1's ID

  tPlayer * p = PlayerMap [i];

  delete p1;

  p->doSomething();


If I'm not mistaken, when you delete p1, you're deleting the same memory that p points to. Now, when you say p->doSomething, the program will probably die (or at best do something odd) because the memory is no longer there.

That's why I used reference counts instead, and the memory only actually goes away when nothing references it anymore. Unfortunately the reference increases and decreases are not automatic - that is the very important advantage to your system - but you are guaranteed that memory only goes poof when nobody refers to it anymore, so there is no risk of overwriting memory or crashing if you access something that isn't there. Of course, you shouldn't be doing that in the first place, but better safe than sorry. :)


However, your code gave me an idea which, if I do say so myself, is kind of neat. :) Your code automatically handles adding and removing from a map; well, I wrote code that automatically adds and removes strings from a hash table.

My problem with SMAUG hashed strings is and always has been that you have no way of knowing if any one particular char * points to a hashed string, or to a "normal" string. Many times I seriously messed up the code because I did my own mallocs and frees instead of STRALLOC and STRFREE, or I unwittingly mixed them... yeah, so it's my fault for not looking up where the string is allocated, to know if it's hashed or not. But, I thought the whole process was a bother.

So to solve this, I adopted a solution somewhat like yours. I created a new class, cHashedString, that upon creation, assignment and all that will automatically add itself to the hash table (a global variable.) To access the string, you use the () operator on the class. You can do nifty things like compare and whatnot. I will post the code shortly (tomorrow morning most likely), but I have to admit that it's kind of ugly. I took the same hashing algorithm that SMAUG uses (which... sucks, but anyways) and created a hash table class and a hashed string class around that.

I like your safe_for_each. Why didn't they do it that way in the first place? Is there a reason for that? Is your way slower, but safe?

That's all from me for now... still kind of tired. I'll get that code tidied up a bit and posted tomorrow. :)


P.S. I ordered Josuttis's book. It should arrive shortly... Woohoo. :)

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #4 on Sat 16 Aug 2003 05:51 AM (UTC)
Message
Quote:

Take the following code. I took it from your example, and took out the parts I don't need.


  tPlayer * p1 = new tPlayer ("nick");

  tId<tPlayer> i = p1->GetId ();   // get player 1's ID

  tPlayer * p = PlayerMap [i];

  delete p1;

  p->doSomething();




If I'm not mistaken, when you delete p1, you're deleting the same memory that p points to. Now, when you say p->doSomething, the program will probably die (or at best do something odd) because the memory is no longer there.



Well, you may as well do this ...


  tPlayer * p1 = new tPlayer ("nick");

  tPlayer * p = p1;

  delete p1;

  p->doSomething();


Nothing can guard you against egregious errors. ;)

However the intent of my code was that you could have something like, say, an event handler, that is given a player ID, and by dereferencing it see if the pointer is still valid. Of course, if in a short piece of code you delete the pointer, one way or another, other pointers will become invalid.

My idea was that - if some code might delete a pointer - you re-get the pointer. So, code might look like this:



  tPlayer * p1 = new tPlayer ("nick");

  tId<tPlayer> i = p1->GetId ();   // get player 1's ID


// later ...

  tPlayer * p = PlayerMap [i];

  DoFight (p);  // player gets into a fight, might be deleted

// re-get the pointer

  p = PlayerMap [i];

  if (p)
    p->doSomething();




- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #5 on Sat 16 Aug 2003 08:10 AM (UTC)
Message
Quote:

I like your safe_for_each. Why didn't they do it that way in the first place? Is there a reason for that? Is your way slower, but safe?


The other (VC++, sti, Linux) for_each implementations seem to be done like this:


// for_each.  Apply a function to every element of a range.
template <class _InputIter, class _Function>
_Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
  for ( ; __first != __last; ++__first)
    __f(*__first);
  return __f;
}


I can't see a huge amount of difference between theirs and mine, except that they recommend pre-incrementing rather than post-incrementing (ie. ++__first rather than __first++) which gives a slight speed improvement. I think in many cases if the function itself takes more than a few clock cycles the difference would be marginal.

Probably I should call it "safer" because some containers may invalidate all iterators if you delete something, so the idea that it is safer to increment first may be an illusion.

I got the idea from Josuttis p 205 where he describes the correct way of deleting items from a map (not deleting pointers, but the items themselves), but in my case where deleting the pointer would have the side-effect of deleting the item from the map, I thought that would be a safer way to go.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


16,764 views.

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum


[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.