Actually, you're absolutely right. If your areas are distributed like normal
ROM areas and don't have a lot of fragmentation, you could save quite a bit
of memory and keep the search time low.
Figure out a good vnum block size
#define ROOM_BLOCK_SIZE 50
Then create some structure.
typedef struct some_structure {
char max_vnum;
pRoomIndex **rooms;
} some_structure;
some_structure pWhateverStructures[MAX_VNUM / ROOM_BLOCK_SIZE];
Then to look up the room,
some_structure *block = pWhateverStructures[index / ROOM_BLOCK_SIZE];
if ((index % ROOM_BLOCK_SIZE) > block->max_vnum)
return NULL
else
return block->rooms[index % ROOM_BLOCK_SIZE];
Inserting a new room is fairly easy as well.. just have to realloc the rooms
pointer if it's not big enough.
some_structure *block = pWhateverStructures[index / ROOM_BLOCK_SIZE];
if ((index%50) > block->max_vnum)
{
block->rooms = realloc(block->rooms, index%ROOM_BLOCK_SIZE);
for (i = block->max_vnum % 50; i < index % ROOM_BLOCK_SIZE; i++)
block->rooms[i] = NULL;
block->max_vnum = index % ROOM_BLOCK_SIZE;
}
block->rooms[index%50] = pRoomIndex;
He's using almost 6 MB on his room list right now.
Using blocks of 50, that list of structures takes up about 150 kb. 300k room
pointers is just over 1 MB.
So, depending on distribution and fragmentation, you can cut the memory use by
up to 80%, and the search time is basically O(1).
--Palrich, feeling stupid now.
On Thursday 14 August 2003 01:56 pm, Jed Yang wrote:
> I am not sure how your vnum's are distributed, but if, just IF look like
> this:
>
> 100-159 200-287 300-365 400-412 (wow small area) ... 1532400-1532462
>
> Than MAYBE you could make an array of length 15324 having the value of
> address of dynamic arrays. Then you have 15324 dynamic arrays with
> length 60, 88, 66, 13, ..., 63 respectively.
> That will save memory, and you could call vnum x by
> pRoomArray[x/100-1][x%100] or something of the like.
> I am not sure of the possibility of this, though, since I just started
> programming a few month ago.
>
> Htam
>
> Jason Gauthier wrote:
> > Hey Gang-
> >
> > Sometime back I removed all my get_room_index (and others) with an array.
> > (pRoomArray).
> >
> > However, I have *very* high vnums. So, I've defined a MAX_ROOM at
> > 1500000. His makes for a large array!
> >
> > I use pRoomArray[vnum] to quickly and efficiently access room data.
> >
> > I would like to use this convention while allocating the memory in the
> > array dynamically (so I only allocate 300k rooms worth, not 1.5m)
> >
> > Is there someway I can keep my method but gain a better allocation
> > concept?
> >
> > I don't want to loop through pointers, or vnums, or anything to find a
> > room. I want to call it out quickly and easily.
> >
> > All ideas welcome, and I hope I've explained what I'm doing here.
> >
> > Thanks!
> >
> > Jason
> >
> > --
> > ROM mailing list
> > [email protected]
> > http://www.rom.org/cgi-bin/mailman/listinfo/rom
