On Thu, 27 Apr 2000, Patrick Dughi wrote:
> Actually, if I were to hazzard a guess, I'd say linked lists
> were not used because of the variable access time. See, if I were
> performing a 'tell', first i'd have to lookup the room my first
> character was in;
I would imagine you'd hold a pointer to the room the player was standing
in, since you would need to access that quite frequently. That means your
'tell' example is just locating the character and then doing:
if (ROOM_FLAGGED(ch->in_room, ROOM_SILENT))
...
if (ROOM_FLAGGED(targ->in_room, ROOM_SILENT))
...
For our purposes, there's no difference between the cost of the above and
the cost of 'tell' as it presently stands.
But linear lookups are still a necessary evil when dealing with linked
lists. So for vnum lookups, etc., we will have to scan through the entire
list. A simple extension of using linked lists is the use of a hash table
with linked lists for collisions. Order it by zone real numbers. That
way finding a room becomes:
struct room_data *get_room_by_vnum(room_vnum rv)
{
int zn = rv / 100;
int key = real_zone(zn) + 1;
struct room_data *room = NULL;
/* Is this zone in the hash table? */
if (size_room_hash > key)
for (room = room_hash[key]; room; room = room->next)
if (room->number == rv)
break;
/* No such zone or room in hash table, maybe it's dynamic? */
if (!room)
for (room = dynamic_rooms; room; room = room->next)
if (room->number == rv)
break;
return (room);
}
Ideally, any room created at run-time that has an associated, existing
zone would be inserted into the list of rooms for that particular zone in
the hash table. So the worst case scenario is that our room is at the end
of the dynamic_rooms list. The best case is that we find it right away,
either at the front of room_hash[key]'s list or dynamic_rooms. Either
way, this is fairly cheap -- not nearly as much as the binary search
CircleMUD currently uses with the arrays, but it's not nearly as
unreasonable as scanning through 5000 rooms to find one.
-dak
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://qsilver.queensu.ca/~fletchra/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 04/10/01 PDT