Implemented unique public IDs.

9 files changed, 328 insertions, 112 deletions

diff --git a/ChangeLog b/ChangeLog
index 1865b2cc..875df4bc 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -18,6 +18,11 @@
 	for moving objects; it now matches the one in the client.
 	* src/gameclient.cpp, src/player.h, src/gamehandler.cpp: Added
 	GameClient pointer to Player class for O(1) message sending.
+	* src/mapcomposite.h, src/mapcomposite.cpp, src/Makefile.am: Moved
+	MapComposite class to its own files.
+	* src/gameclient.cpp, src/gamehandler.h, src/state.cpp, src/state.h,
+	src/gamehandler.cpp: Reduced amount of counted pointers. Implemented
+	unique public IDs.
 
 2006-08-28  Eugenio Favalli  <elvenprogrammer@gmail.com>
 
diff --git a/src/Makefile.am b/src/Makefile.am
index b752b0c3..1950aac8 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -41,8 +41,10 @@ tmwserv_SOURCES = main.cpp \
 		  gamehandler.cpp \
 		  items.h \
 		  items.cpp \
-		  map.cpp \
 		  map.h \
+		  map.cpp \
+		  mapcomposite.h \
+		  mapcomposite.cpp \
 		  mapmanager.h \
 		  mapmanager.cpp \
 		  mapreader.cpp \
diff --git a/src/gameclient.cpp b/src/gameclient.cpp
index 26d8aaac..b1e00804 100644
--- a/src/gameclient.cpp
+++ b/src/gameclient.cpp
@@ -46,7 +46,6 @@ void GameClient::setCharacter(PlayerPtr ch)
     assert(mCharacterPtr->mClient == NULL);
     mCharacterPtr->mClient = this;
     gameState->addObject(ObjectPtr(mCharacterPtr));
-    gameState->informPlayer(mCharacterPtr);
 }
 
 void GameClient::unsetCharacter()
diff --git a/src/gamehandler.cpp b/src/gamehandler.cpp
index 5186f92d..26f300ec 100644
--- a/src/gamehandler.cpp
+++ b/src/gamehandler.cpp
@@ -251,8 +251,7 @@ void GameHandler::sayAround(GameClient &computer, std::string const &text)
     }
 }
 
-void
-GameHandler::sendTo(PlayerPtr beingPtr, MessageOut &msg)
+void GameHandler::sendTo(Player *beingPtr, MessageOut &msg)
 {
     GameClient *client = beingPtr->getClient();
     assert(client != NULL);
diff --git a/src/gamehandler.h b/src/gamehandler.h
index 520f290c..e0f39e65 100644
--- a/src/gamehandler.h
+++ b/src/gamehandler.h
@@ -25,8 +25,8 @@
 #define _TMW_SERVER_GAMEHANDLER_
 
 #include "account.h"
-#include "being.h"
 #include "connectionhandler.h"
+#include "player.h"
 
 class GameClient;
 
@@ -41,7 +41,7 @@ class GameHandler: public ConnectionHandler
         /**
          * Send message to the given player.
          */
-        void sendTo(PlayerPtr playerPtr, MessageOut &msg);
+        void sendTo(Player *, MessageOut &msg);
 
     protected:
         NetComputer *computerConnected(ENetPeer *);
diff --git a/src/mapcomposite.cpp b/src/mapcomposite.cpp
new file mode 100644
index 00000000..dfbbc052
--- /dev/null
+++ b/src/mapcomposite.cpp
@@ -0,0 +1,138 @@
+/*
+ *  The Mana World Server
+ *  Copyright 2006 The Mana World Development Team
+ *
+ *  This file is part of The Mana World.
+ *
+ *  The Mana World is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  any later version.
+ *
+ *  The Mana World is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with The Mana World; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ *  $Id: $
+ */
+
+#include "mapcomposite.h"
+
+ObjectBucket::ObjectBucket()
+  : free(256), next_object(0)
+{
+    for (unsigned i = 0; i < 256 / sizeof(unsigned); ++i)
+    {
+        bitmap[i] = ~0;
+    }
+}
+
+int ObjectBucket::allocate()
+{
+    if (!free)
+    {
+        return -1;
+    }
+
+    if (bitmap[next_object / sizeof(unsigned)] & (1 << (next_object % sizeof(unsigned))))
+    {
+        bitmap[next_object / sizeof(unsigned)] &= ~(1 << (next_object % sizeof(unsigned)));
+        int i = next_object;
+        next_object = (i + 1) & 255;
+        --free;
+        return i;
+    }
+
+    for (unsigned i = 0; i < 256 / sizeof(unsigned); ++i)
+    {
+        unsigned &current = bitmap[(i + next_object / sizeof(unsigned)) & 255];
+        unsigned b = current;
+        if (b)
+        {
+            int j = 0;
+            while (!(b & 1))
+            {
+                b >>= 1;
+                ++j;
+            }
+            current &= ~(1 << j);
+            next_object = (j + 1) & 255;
+            --free;
+            return j;
+        }
+    }
+    return -1;
+}
+
+void ObjectBucket::deallocate(int i)
+{
+    bitmap[i / sizeof(unsigned)] |= 1 << (i % sizeof(unsigned));
+    ++free;
+}
+
+MapComposite::MapComposite()
+  : map(NULL), last_bucket(0)
+{
+    buckets[0] = new ObjectBucket;
+    for (int i = 1; i < 256; ++i)
+    {
+        buckets[i] = NULL;
+    }
+}
+
+MapComposite::~MapComposite()
+{
+    for (int i = 0; i < 256; ++i)
+    {
+        delete buckets[i];
+    }
+}
+
+void MapComposite::allocate(MovingObject *obj)
+{
+    ObjectBucket *b = buckets[last_bucket];
+    int i = b->allocate();
+    if (i >= 0)
+    {
+        b->objects[i] = obj;
+        int id = last_bucket * 256 + i;
+        obj->setPublicID(id);
+        return;
+    }
+
+    for (i = 0; i < 256; ++i)
+    {
+        b = buckets[i];
+        if (!b)
+        {
+            b = new ObjectBucket;
+            buckets[i] = b;
+        }
+        int j = b->allocate();
+        if (j >= 0)
+        {
+            last_bucket = i;
+            b->objects[j] = obj;
+            int id = i * 256 + j;
+            obj->setPublicID(id);
+            return;
+        }
+    }
+}
+
+void MapComposite::deallocate(MovingObject *obj)
+{
+    int id = obj->getPublicID();
+    if (id == 65535)
+    {
+        return;
+    }
+
+    obj->setPublicID(65535);
+    buckets[id / 256]->deallocate(id % 256);
+}
diff --git a/src/mapcomposite.h b/src/mapcomposite.h
new file mode 100644
index 00000000..a6b8b40b
--- /dev/null
+++ b/src/mapcomposite.h
@@ -0,0 +1,97 @@
+/*
+ *  The Mana World Server
+ *  Copyright 2006 The Mana World Development Team
+ *
+ *  This file is part of The Mana World.
+ *
+ *  The Mana World is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  any later version.
+ *
+ *  The Mana World is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with The Mana World; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ *  $Id: $
+ */
+
+#ifndef _TMW_SERVER_MAPCOMPOSITE_
+#define _TMW_SERVER_MAPCOMPOSITE_
+
+#include "object.h"
+
+class Player;
+class Map;
+
+/**
+ * Pool of MovingObject.
+ */
+struct ObjectBucket
+{
+    unsigned bitmap[256 / sizeof(unsigned)]; /**< Bitmap of free locations. */
+    short free; /**< Number of empty places. */
+    short next_object; /**< Next object to look at. */
+    MovingObject *objects[256];
+
+    ObjectBucket();
+    int allocate();
+    void deallocate(int);
+};
+
+/**
+ * Combined map/entity structure.
+ */
+class MapComposite {
+
+    public:
+        MapComposite();
+        ~MapComposite();
+
+        /**
+         * Actual map.
+         */
+        Map *map;
+
+        /**
+         * Objects (items, players, monsters, etc) located on the map.
+         */
+        Objects objects;
+
+        /**
+         * Players located on the map. Already owned by the objects field.
+         */
+        std::vector< Player * > players;
+
+        /**
+         * Allocates a unique ID for a moving object on this map.
+         */
+        void allocate(MovingObject *);
+
+        /**
+         * Deallocates an ID.
+         */
+        void deallocate(MovingObject *);
+
+        /**
+         * Gets an object given its ID.
+         */
+        MovingObject *getObjectByID(int) const;
+
+    private:
+        MapComposite(MapComposite const &);
+
+        /**
+         * Buckets of MovingObject located on the map, referenced by ID.
+         */
+        ObjectBucket *buckets[256];
+
+        int last_bucket; /**< Last bucket acted upon. */
+};
+
+#endif
diff --git a/src/state.cpp b/src/state.cpp
index 5471e121..e992fbf6 100644
--- a/src/state.cpp
+++ b/src/state.cpp
@@ -28,6 +28,7 @@
 #include "controller.h"
 #include "gamehandler.h"
 #include "map.h"
+#include "mapcomposite.h"
 #include "mapmanager.h"
 #include "messageout.h"
 #include "point.h"
@@ -40,8 +41,7 @@ State::State()
     // Create 10 maggots for testing purposes
     for (int i = 0; i < 10; i++)
     {
-        // TODO: Unique object numbering
-        BeingPtr being = BeingPtr(new Being(OBJECT_MONSTER, 1000 + i));
+        BeingPtr being = BeingPtr(new Being(OBJECT_MONSTER, 65535));
         being->setSpeed(150);
         being->setMapId(1);
         Point pos = { 720, 900 };
@@ -54,11 +54,11 @@ State::State()
 
 State::~State()
 {
-    for (std::map<unsigned int, MapComposite>::iterator i = maps.begin();
-         i != maps.end();
-         i++)
+    for (std::map< unsigned, MapComposite * >::iterator i = maps.begin(),
+         i_end = maps.end(); i != i_end; ++i)
     {
-        delete i->second.map;
+        delete i->second->map;
+        delete i->second;
     }
 }
 
@@ -66,27 +66,28 @@ void
 State::update()
 {
     // update game state (update AI, etc.)
-    for (std::map<unsigned int, MapComposite>::iterator m = maps.begin(),
+    for (std::map< unsigned, MapComposite * >::iterator m = maps.begin(),
          m_end = maps.end(); m != m_end; ++m)
     {
-        typedef std::vector<MovingObjectPtr> Movings;
+        MapComposite *map = m->second;
+
+        typedef std::vector< MovingObject * > Movings;
         Movings movings;
 
-        for (Objects::iterator o = m->second.objects.begin(),
-             o_end = m->second.objects.end(); o != o_end; ++o)
+        for (Objects::iterator o = map->objects.begin(),
+             o_end = map->objects.end(); o != o_end; ++o)
         {
             (*o)->update();
             int t = (*o)->getType();
             if (t == OBJECT_NPC || t == OBJECT_PLAYER || t == OBJECT_MONSTER) {
-                MovingObjectPtr ptr(*o);
+                MovingObject *ptr = static_cast< MovingObject * >(o->get());
                 ptr->move();
                 movings.push_back(ptr);
             }
         }
 
-        Players &players = m->second.players;
-        for (Players::iterator p = players.begin(),
-             p_end = players.end(); p != p_end; ++p)
+        for (std::vector< Player * >::iterator p = map->players.begin(),
+             p_end = map->players.end(); p != p_end; ++p)
         {
             MessageOut msg(GPMSG_BEINGS_MOVE);
 
@@ -122,7 +123,7 @@ State::update()
                     switch (type) {
                     case OBJECT_PLAYER:
                     {
-                        PlayerPtr q(*o);
+                        Player *q = static_cast< Player * >(*o);
                         msg2.writeString(q->getName());
                         msg2.writeByte(q->getHairStyle());
                         msg2.writeByte(q->getHairColor());
@@ -203,85 +204,90 @@ void
 State::addObject(ObjectPtr objectPtr)
 {
     unsigned mapId = objectPtr->getMapId();
-    if (!loadMap(mapId)) return;
-    maps[mapId].objects.push_back(objectPtr);
+    MapComposite *map = loadMap(mapId);
+    if (!map) return;
+    map->objects.push_back(objectPtr);
     objectPtr->setNew(true);
-    if (objectPtr->getType() != OBJECT_PLAYER) return;
-    PlayerPtr ptr(objectPtr);
-    // TODO: Unique object numbering
-    ptr->setPublicID(ptr->getDatabaseID());
-    maps[mapId].players.push_back(ptr);
+    int type = objectPtr->getType();
+    if (type != OBJECT_MONSTER && type != OBJECT_PLAYER && type != OBJECT_NPC) return;
+    map->allocate(static_cast< MovingObject * >(objectPtr.get()));
+    if (type != OBJECT_PLAYER) return;
+    Player *playerPtr = static_cast< Player * >(objectPtr.get());
+    map->players.push_back(playerPtr);
+
+    /* Since the player doesn't know yet where on the world he is after
+     * connecting to the map server, we send him an initial change map message.
+     */
+    Storage &store = Storage::instance("tmw");
+    MessageOut mapChangeMessage(GPMSG_PLAYER_MAP_CHANGE);
+    mapChangeMessage.writeString(store.getMapNameFromId(mapId));
+    Point pos = playerPtr->getPosition();
+    mapChangeMessage.writeShort(pos.x);
+    mapChangeMessage.writeShort(pos.y);
+    mapChangeMessage.writeByte(0);
+    gameHandler->sendTo(playerPtr, mapChangeMessage);
 }
 
 void
 State::removeObject(ObjectPtr objectPtr)
 {
     unsigned mapId = objectPtr->getMapId();
-    std::map<unsigned, MapComposite>::iterator m = maps.find(mapId);
+    std::map< unsigned, MapComposite * >::iterator m = maps.find(mapId);
     if (m == maps.end()) return;
-    Objects &objects = m->second.objects;
-    for (Objects::iterator o = objects.begin(),
-         o_end = objects.end(); o != o_end; ++o) {
-        if (o->get() == objectPtr.get()) {
-            objects.erase(o);
-            break;
-        }
-    }
-    if (objectPtr->getType() != OBJECT_PLAYER) return;
-
-    MessageOut msg(GPMSG_BEING_LEAVE);
-    msg.writeShort(PlayerPtr(objectPtr)->getPublicID());
+    MapComposite *map = m->second;
 
-    Point objectPosition = objectPtr->getPosition();
-    Players &players = maps[mapId].players;
-    Players::iterator p_end = players.end(), j = p_end;
-    for (Players::iterator p = players.begin(); p != p_end; ++p)
+    int type = objectPtr->getType();
+    if (type == OBJECT_MONSTER || type == OBJECT_PLAYER || type == OBJECT_NPC)
     {
-        if (p->get() == objectPtr.get())
+        MovingObject *obj = static_cast< MovingObject * >(objectPtr.get());
+        MessageOut msg(GPMSG_BEING_LEAVE);
+        msg.writeShort(obj->getPublicID());
+
+        Point objectPos = obj->getPosition();
+        typedef std::vector< Player * > Players;
+        Players &players = map->players;
+        Players::iterator p_end = players.end(), j = p_end;
+        for (Players::iterator p = players.begin(); p != p_end; ++p)
         {
-            j = p;
+            if (*p == obj)
+            {
+                j = p;
+            }
+            else if (objectPos.inRangeOf((*p)->getPosition()))
+            {
+                gameHandler->sendTo(*p, msg);
+            }
         }
-        else if (objectPosition.inRangeOf((*p)->getPosition()))
+
+        if (j != p_end)
         {
-            gameHandler->sendTo(*p, msg);
+            players.erase(j);
         }
+
+        map->deallocate(obj);
     }
 
-    if (j != p_end)
+    for (Objects::iterator o = map->objects.begin(),
+         o_end = map->objects.end(); o != o_end; ++o)
     {
-        players.erase(j);
+        if (o->get() == objectPtr.get()) {
+            map->objects.erase(o);
+            break;
+        }
     }
 }
 
-void
-State::informPlayer(PlayerPtr playerPtr)
-{
-    unsigned mapId = playerPtr->getMapId();
-    std::map<unsigned, MapComposite>::iterator m = maps.find(mapId);
-    if (m == maps.end()) return;
-
-    /* Since the player doesn't know yet where on the world he is after
-     * connecting to the map server, we send him an initial change map message.
-     */
-    Storage &store = Storage::instance("tmw");
-    MessageOut mapChangeMessage(GPMSG_PLAYER_MAP_CHANGE);
-    mapChangeMessage.writeString(store.getMapNameFromId(mapId));
-    Point pos = playerPtr->getPosition();
-    mapChangeMessage.writeShort(pos.x);
-    mapChangeMessage.writeShort(pos.y);
-    mapChangeMessage.writeByte(0);
-    gameHandler->sendTo(playerPtr, mapChangeMessage);
-}
-
-bool
-State::loadMap(const unsigned int mapId)
+MapComposite *State::loadMap(unsigned mapId)
 {
-    if (maps.find(mapId) != maps.end()) return true;
-    Map *tmp = MapManager::instance().loadMap(mapId);
-    if (!tmp) return false;
-    maps[mapId].map = tmp;
+    std::map< unsigned, MapComposite * >::iterator m = maps.find(mapId);
+    if (m != maps.end()) return m->second;
+    Map *map = MapManager::instance().loadMap(mapId);
+    if (!map) return NULL;
+    MapComposite *tmp = new MapComposite;
+    tmp->map = map;
+    maps[mapId] = tmp;
 
     // will need to load extra map related resources here also
 
-    return true; // We let true for testing on beings
+    return tmp;
 }
diff --git a/src/state.h b/src/state.h
index 955b37da..07d466a1 100644
--- a/src/state.h
+++ b/src/state.h
@@ -26,34 +26,9 @@
 
 #include <map>
 
-#include "player.h"
+#include "object.h"
 
-class Map;
-
-/**
- * Combined map/entity structure.
- */
-struct MapComposite {
-    /**
-     * Default constructor.
-     */
-    MapComposite() : map(NULL) { }
-
-    /**
-     * Actual map.
-     */
-    Map *map;
-
-    /**
-     * Objects (items, players, monsters, etc) located on the map.
-     */
-    Objects objects;
-
-    /**
-     * Players located on the map.
-     */
-    Players players;
-};
+class MapComposite;
 
 /**
  * State class contains all information/procedures associated with the game
@@ -64,7 +39,7 @@ class State
     /**
      * List of maps.
      */
-    std::map<unsigned int, MapComposite> maps;
+    std::map<unsigned int, MapComposite *> maps;
 
  public:
     State();
@@ -76,14 +51,9 @@ class State
     void update();
 
     /**
-     * Send game state to given player.
-     */
-    void informPlayer(PlayerPtr playerPtr);
-
-    /**
      * Load map into game world.
      */
-    bool loadMap(unsigned mapId);
+    MapComposite *loadMap(unsigned mapId);
 
     /**
      * Add object to the map.