>>>>> "D3" == donalson  <donalson@lifesci.ucsb.edu> writes:

D3> In fact if I remember Glen and I had a discussion on the O(n) vs. O(1)
D3> matter.  I was complaining that swarm was not O(1) on delete. 

Here's an example of how to get O(1) on delete.  (Code at end of message.)

Compare the USE_MEMBERLOC configuration:

  mgd@pojoaque[~] $ time ./memberloc2
  68918: List_mlinks, display name: List_mlinks
  > number of members: 5000
  > internal links at offset: 12

  real    0m1.830s
  user    0m0.350s
  sys     0m0.100s

..with the plain list member deletion:

  mgd@pojoaque[~] $ time ./memberloc2
  68800: List_linked, display name: List_linked
  > number of members: 5000

  real    0m19.608s
  user    0m15.420s
  sys     0m0.170s

D3> BTW: I tried to make a "generic" list object in C++ using a templete
D3> (which is similar to dynamic binding, I think)

A C++ template is a way to get some generic code structure optimized
to some particular types you specify.  With Swarm phases
(conceptually) those types could be specified using the -setWhatever:
methods between +createBegin: and -createEnd.  In practice, the
comparision is silly because Swarm is not a compiler -- the best it
can do is use these types to choose between different precompiled
alternatives.  If someday Swarm had a runtime code generator,
+createBegin:/-createEnd would be a nice interface to get something
like templates.

Anyway, dynamic binding (the ability to bind an interface to different
code behind the scenes) can be applied to get something like C++
templates, but the two aren't directly comparable otherwise.


#import <simtools.h>
#import <collections.h>
#import <defobj/Create.h>

@interface Integer: CreateDrop
{
  int value;
  member_t link;
}
- setValue: (int)value;
- (int)getValue;
@end

@implementation Integer
- setValue: (int)theValue
{
  value = theValue;
  return self;
}

- (int)getValue
{
  return value;
}

- (void)describe: outputCharStream
{
  char buf[DSIZE (int) + 1 + 1];

  sprintf (buf, "%d\n", value);
  [outputCharStream catC: buf];
}
@end

#define MAKEINTEGER(aZone,value) \
  [[[Integer createBegin: aZone] setValue: value] createEnd]
  
int 
main (int argc, const char **argv)
{
  initSwarmBatch (argc, argv);
  
  {
    id <Zone> aZone = [Zone create: globalZone];
    id l, rl;
    unsigned i;

    l = [List createBegin: aZone];
#ifdef USE_MEMBERLOC
    [l setIndexFromMemberLoc: offsetof (Integer, link)];
#endif
    l = [l createEnd];
    rl = [List create: aZone];
    
    for (i = 0; i < 5000; i++)
      [l addLast: MAKEINTEGER (aZone, i)];
    for (i = 5000; i < 10000; i++)
      {
        id rmember = MAKEINTEGER (aZone, i);

        [l addLast: rmember];
        [rl addLast: rmember];
      }
    {
      id <Index> rli = [rl begin: scratchZone];
      id member;
      
      for (member = [rli next]; [rli getLoc] == Member; member = [rli next])
        {
#ifdef USE_MEMBERLOC     
          id <Index> index = [l createIndex: aZone fromMember: member];
          
          [index remove];
          [index drop];
#else
          [l remove: member];
#endif
        }
      [rli drop];
    }
    xprint (l);
  }
}

/*
Local Variables:
compile-command: "$SWARMHOME/bin/libtool-swarm --mode=link gcc -DUSE_MEMBERLOC -o memberloc2 -g -Wno-import -I$SWARMHOME/include -L$SWARMHOME/lib memberloc2.m -lswarm -lobjc"
End:
*/