objects[] array removal (bugreport:2559)

- Removed the 2 MB wide static array in favor of a general-purpose DBMap (id_db for now).
- Inlined functions map_addobject, map_delobject and map_delobjectnofree into their callers' code.
- Replaced the free id lookup algorithm from ancient jathena with something more efficient.
- Moved the algorithm to map_get_new_object_id() (similar idea as r13481).

git-svn-id: https://rathena.svn.sourceforge.net/svnroot/rathena/trunk@13503 54d463be-8e91-2dee-dedb-b68131a5f0ec

4 files changed, 48 insertions, 133 deletions

diff --git a/src/map/chat.c b/src/map/chat.c
index 8446596e6..a761d528a 100644
--- a/src/map/chat.c
+++ b/src/map/chat.c
@@ -40,12 +40,12 @@ static struct chat_data* chat_createchat(struct block_list* bl, const char* titl
 	cd->owner = bl;
 	safestrncpy(cd->npc_event, ev, sizeof(cd->npc_event));
 
+	cd->bl.id   = map_get_new_object_id();
 	cd->bl.m    = bl->m;
 	cd->bl.x    = bl->x;
 	cd->bl.y    = bl->y;
 	cd->bl.type = BL_CHAT;
 	cd->bl.next = cd->bl.prev = NULL;
-	cd->bl.id   = map_addobject(&cd->bl);
 
 	if( cd->bl.id == 0 )
 	{
@@ -53,6 +53,8 @@ static struct chat_data* chat_createchat(struct block_list* bl, const char* titl
 		cd = NULL;
 	}
 
+	map_addiddb(&cd->bl);
+
 	return cd;
 }
 
@@ -172,7 +174,8 @@ int chat_leavechat(struct map_session_data* sd, bool kicked)
 	if( cd->users == 0 && cd->owner->type == BL_PC )
 	{	// Delete empty chatroom
 		clif_clearchat(cd, 0);
-		map_delobject(cd->bl.id);
+		map_delblock(&cd->bl);
+		map_freeblock(&cd->bl);
 		return 1;
 	}
 
@@ -323,7 +326,8 @@ int chat_deletenpcchat(struct npc_data* nd)
 	
 	chat_npckickall(cd);
 	clif_clearchat(cd, 0);
-	map_delobject(cd->bl.id);	// freeまでしてくれる
+	map_delblock(&cd->bl);
+	map_freeblock(&cd->bl);
 	nd->chat_id = 0;
 	
 	return 0;
diff --git a/src/map/map.c b/src/map/map.c
index c732e2d55..372647088 100644
--- a/src/map/map.c
+++ b/src/map/map.c
@@ -102,8 +102,6 @@ static DBMap* charid_db=NULL; // int char_id -> struct map_session_data*
 static DBMap* regen_db=NULL; // int id -> struct block_list* (status_natural_heal processing)
 
 static int map_users=0;
-static struct block_list *objects[MAX_FLOORITEM];
-static int first_free_object_id=0,last_object_id=0;
 
 #define block_free_max 1048576
 struct block_list *block_free[block_free_max];
@@ -1129,124 +1127,38 @@ int map_foreachinmap(int (*func)(struct block_list*,va_list), int m, int type,..
 	return returnCount;
 }
 
-/*==========================================
- * 床アイテムやエフェクト用の一三bj割り?て
- * object[]への保存とid_db登?まで
- *
- * bl->idもこの中で設定して問題無い?
- *------------------------------------------*/
-int map_addobject(struct block_list *bl)
+
+/// Generates a new flooritem object id from the interval [MIN_FLOORITEM, MAX_FLOORITEM).
+/// Used for floor items, skill units and chatroom objects.
+/// @return The new object id
+int map_get_new_object_id(void)
 {
+	static int last_object_id = MIN_FLOORITEM - 1;
 	int i;
-	if( bl == NULL ){
-		ShowWarning("map_addobject nullpo?\n");
-		return 0;
-	}
-	if(first_free_object_id<2 || first_free_object_id>=MAX_FLOORITEM)
-		first_free_object_id=2;
-	for(i=first_free_object_id;i<MAX_FLOORITEM && objects[i];i++);
-	if(i>=MAX_FLOORITEM){
-		ShowWarning("no free object id\n");
-		return 0;
-	}
-	first_free_object_id=i;
-	if(last_object_id<i)
-		last_object_id=i;
-	objects[i]=bl;
-	idb_put(id_db,i,bl);
-	return i;
-}
 
-/*==========================================
- * 一三bjectの解放
- *	map_delobjectのfreeしないバ?ジョン
- *------------------------------------------*/
-int map_delobjectnofree(int id)
-{
-	if( id < 0 || id >= MAX_FLOORITEM )
+	// find a free id
+	i = last_object_id + 1;
+	while( i != last_object_id )
 	{
-		ShowError("map_delobjectnofree: invalid object id '%d'!\n", id);
-		return 0;
-	}
-
-	if(objects[id]==NULL)
-		return 0;
-
-	map_delblock(objects[id]);
-	idb_remove(id_db,id);
-	objects[id]=NULL;
-
-	if(first_free_object_id>id)
-		first_free_object_id=id;
-
-	while(last_object_id>2 && objects[last_object_id]==NULL)
-		last_object_id--;
+		if( i == MAX_FLOORITEM )
+			i = MIN_FLOORITEM;
 
-	return 0;
-}
-
-/*==========================================
- * 一三bjectの解放
- * block_listからの削除、id_dbからの削除
- * object dataのfree、object[]へのNULL代入
- *
- * addとの??性が無いのが?になる
- *------------------------------------------*/
-int map_delobject(int id)
-{
-	struct block_list* bl;
+		if( idb_get(id_db, i) == NULL )
+			break;
 
-	if( id < 0 || id >= MAX_FLOORITEM )
-	{
-		ShowError("map_delobject: invalid object id '%d'!\n", id);
-		return 0;
+		++i;
 	}
 
-	if(objects[id]==NULL)
+	if( i == last_object_id )
+	{
+		ShowError("map_addobject: no free object id!\n");
 		return 0;
-
-	bl = objects[id];
-	map_delobjectnofree(id);
-	map_freeblock(bl);
-
-	return 0;
-}
-
-/*==========================================
- * 全一三bj相手にfuncを呼ぶ
- *
- *------------------------------------------*/
-void map_foreachobject(int (*func)(struct block_list*,va_list),int type,...)
-{
-	int i;
-	int blockcount=bl_list_count;
-
-	for(i=2;i<=last_object_id;i++){
-		if(objects[i]){
-			if(!(objects[i]->type==type)) // Fixed [Lance]
-				continue;
-			if(bl_list_count>=BL_LIST_MAX) {
-				ShowWarning("map_foreachobject: too many blocks !\n");
-				break;
-			}
-			bl_list[bl_list_count++]=objects[i];
-		}
 	}
 
-	map_freeblock_lock();
-
-	for(i=blockcount;i<bl_list_count;i++)
-		if( bl_list[i]->prev || bl_list[i]->next )
-		{
-			va_list ap;
-			va_start(ap, type);
-			func(bl_list[i], ap);
-			va_end(ap);
-		}
-
-	map_freeblock_unlock();
+	// update cursor
+	last_object_id = i;
 
-	bl_list_count = blockcount;
+	return i;
 }
 
 /*==========================================
@@ -1259,9 +1171,7 @@ void map_foreachobject(int (*func)(struct block_list*,va_list),int type,...)
  *------------------------------------------*/
 int map_clearflooritem_timer(int tid, unsigned int tick, int id, intptr data)
 {
-	struct flooritem_data *fitem=NULL;
-
-	fitem = (struct flooritem_data *)objects[id];
+	struct flooritem_data* fitem = idb_get(id_db, id);
 	if(fitem==NULL || fitem->bl.type!=BL_ITEM || (!data && fitem->cleartimer != tid)){
 		ShowError("map_clearflooritem_timer : error\n");
 		return 1;
@@ -1271,7 +1181,8 @@ int map_clearflooritem_timer(int tid, unsigned int tick, int id, intptr data)
 	else if(fitem->item_data.card[0] == CARD0_PET)
 		intif_delete_petdata( MakeDWord(fitem->item_data.card[1],fitem->item_data.card[2]) );
 	clif_clearflooritem(fitem,0);
-	map_delobject(fitem->bl.id);
+	map_delblock(&fitem->bl);
+	map_freeblock(&fitem->bl);
 
 	return 0;
 }
@@ -1414,7 +1325,7 @@ int map_addflooritem(struct item *item_data,int amount,int m,int x,int y,int fir
 	fitem->bl.m=m;
 	fitem->bl.x=x;
 	fitem->bl.y=y;
-	fitem->bl.id = map_addobject(&fitem->bl);
+	fitem->bl.id = map_get_new_object_id();
 	if(fitem->bl.id==0){
 		aFree(fitem);
 		return 0;
@@ -1433,6 +1344,7 @@ int map_addflooritem(struct item *item_data,int amount,int m,int x,int y,int fir
 	fitem->suby=((r>>2)&3)*3+3;
 	fitem->cleartimer=add_timer(gettick()+battle_config.flooritem_lifetime,map_clearflooritem_timer,fitem->bl.id,0);
 
+	map_addiddb(&fitem->bl);
 	map_addblock(&fitem->bl);
 	clif_dropflooritem(fitem);
 
@@ -1765,13 +1677,7 @@ struct map_session_data * map_nick2sd(const char *nick)
  *------------------------------------------*/
 struct block_list * map_id2bl(int id)
 {
-	struct block_list *bl;
-	if(id >= 0 && id < ARRAYLENGTH(objects))
-		bl = objects[id];
-	else
-		bl = (struct block_list*)idb_get(id_db,id);
-
-	return bl;
+	return (struct block_list*)idb_get(id_db,id);
 }
 
 /*==========================================
diff --git a/src/map/map.h b/src/map/map.h
index a401214c8..02314318e 100644
--- a/src/map/map.h
+++ b/src/map/map.h
@@ -38,7 +38,8 @@ struct item_data;
 #define MAX_EVENTQUEUE 2
 #define MAX_EVENTTIMER 32
 #define NATURAL_HEAL_INTERVAL 500
-#define MAX_FLOORITEM 500000
+#define MIN_FLOORITEM 2
+#define MAX_FLOORITEM START_ACCOUNT_NUM
 #define MAX_LEVEL 99
 #define MAX_DROP_PER_MAP 48
 #define MAX_IGNORE_LIST 20 // official is 14
@@ -535,10 +536,7 @@ int map_foreachinmap(int (*func)(struct block_list*,va_list), int m, int type, .
 int map_count_oncell(int m,int x,int y,int type);
 struct skill_unit *map_find_skill_unit_oncell(struct block_list *,int x,int y,int skill_id,struct skill_unit *);
 // 一時的object関連
-int map_addobject(struct block_list *);
-int map_delobject(int);
-int map_delobjectnofree(int id);
-void map_foreachobject(int (*)(struct block_list*,va_list),int,...);
+int map_get_new_object_id(void);
 int map_search_freecell(struct block_list *src, int m, short *x, short *y, int rx, int ry, int flag);
 //
 int map_quit(struct map_session_data *);
diff --git a/src/map/skill.c b/src/map/skill.c
index 54968bf3d..7187cc37b 100644
--- a/src/map/skill.c
+++ b/src/map/skill.c
@@ -9504,7 +9504,7 @@ struct skill_unit *skill_initunit (struct skill_unit_group *group, int idx, int
 	if(!unit->alive)
 		group->alive_count++;
 
-	unit->bl.id=map_addobject(&unit->bl);
+	unit->bl.id=map_get_new_object_id();
 	unit->bl.type=BL_SKILL;
 	unit->bl.m=group->map;
 	unit->bl.x=x;
@@ -9514,6 +9514,7 @@ struct skill_unit *skill_initunit (struct skill_unit_group *group, int idx, int
 	unit->val1=val1;
 	unit->val2=val2;
 
+	map_addiddb(&unit->bl);
 	map_addblock(&unit->bl);
 
 	// perform oninit actions
@@ -9583,7 +9584,7 @@ int skill_delunit (struct skill_unit* unit)
 
 	unit->group=NULL;
 	unit->alive=0;
-	map_delobjectnofree(unit->bl.id);
+	map_delblock(&unit->bl); // don't free yet
 	if(--group->alive_count==0)
 		skill_delunitgroup(NULL, group);
 
@@ -9851,11 +9852,17 @@ int skill_unit_timer_sub_onplace (struct block_list* bl, va_list ap)
  *------------------------------------------*/
 int skill_unit_timer_sub (struct block_list* bl, va_list ap)
 {
-	struct skill_unit* unit = (struct skill_unit *)bl;
-	struct skill_unit_group* group = unit->group;
 	unsigned int tick = va_arg(ap,unsigned int);
+	struct skill_unit* unit;
+	struct skill_unit_group* group;
   	bool dissonance;
 
+	if( bl->type != BL_SKILL )
+		return 0;
+
+	unit = (struct skill_unit *)bl;
+	group = unit->group;
+
 	if( !unit->alive )
 		return 0;
 
@@ -10011,7 +10018,7 @@ int skill_unit_timer(int tid, unsigned int tick, int id, intptr data)
 {
 	map_freeblock_lock();
 
-	map_foreachobject( skill_unit_timer_sub, BL_SKILL, tick );
+	map_foreachiddb( skill_unit_timer_sub, tick );
 
 	map_freeblock_unlock();