Re: [CODE CONCEPTS] Linked lists / reenterant list iterators

From: George (greerga@CIRCLEMUD.ORG)
Date: 03/25/98

On Wed, 25 Mar 1998, Chris Jacobson wrote:

>The SAFEST system, to my knowledge, is using vectors - as implemented in
>Eric Green's FL codebase.  Any removal-from-list simply NULLs the current
>vector and sets the "dirty" flag on the master vector structure.  During
>iteration, if the current vector is NULL, simply skip it.  The vector

Quickest thing I can think of is to add a bit to the major structures for
deleted and have another global bit for 'we deleted something.'


unsigned character_list_dirty : 1 = 0;  /* One bit, you get the idea. */

void foo()
  struct char_data *tch;

  for (tch = character_list; tch; tch = tch->next) { stuff...


void free_char(tch)
  tch->deleted = TRUE;
  character_list_dirty = TRUE;

void heartbeat(void)
  if (character_list_dirty) {
    REMOVE_DELETED(character_list);     /* Macro just like
                                        REMOVE_FROM_LIST. */
    character_list_dirty = FALSE;

Where REMOVE_DELETED(...) simply iterates over the list looking for deleted
items.  When it finds one it removes it and really frees it.

Thus you avoid scanning lists when nothing deleted and you have a minor
overhead of (1 + 1*N items) bits (w/o alignment).


You could also save time by having free_char() simply move the deleted node
to a different list, keeping it in memory.  That would make your scanning
function in heartbeat simply check for a head item to a deleted item linked
list and erase everything in that list. (This might cause odd stuff to
happen though if you think about it, a scanning loop may end up onto the
deleted list instead, in theory.)

But then again, I have no idea what his vectors do.

George Greer  -   | Genius may have its limitations, but stupidity | is not thus handicapped. -- Elbert Hubbard

     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | |

This archive was generated by hypermail 2b30 : 12/15/00 PST