Re: [boost] String algorithm] is_any_of has inefficient implementation

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-02-16 13:25:31

David Abrahams wrote:
>>> Phil Endecott wrote:
>>>> Further investigation with other workloads suggests that this bitset
>>>> really works very well, and I note that it would be possible to
>>>> write a specialisation of std::set<char> using it.  This is probably
>>>> worth pursuing. 

> Assuming you're willing to play fast-and-loose with the big-O of
> iterator increment (I am).

It's still O(1) - its execution time is bounded - so there's nothing to 
worry about even if you did care.  Sketch of iterator-increment code:

// the bit-set:
uint64_t bits[4];

unsigned char inc_iterator(unsigned char c) {
   // Find the next set bit in bits after c.

   // libc defines ffs and fls to find the first and last set bit in a word.
   // At least ffs should be a single instruction on many machines (e.g.
   // the bsfl instruction on x86).
   // gcc has __builtin_ffs that should generate this.  It also has
   // __builtin_ffsll for 64-bit words.  Here I'm using flsll; if that
   // doesn't exist you can reverse the order of the bits - except that
   // you'll still want the other one for decrementing, hmmm.
   // Note that they return the bit number plus 1, or 0 if none is set.

   // The lowest interesting bit:
   int l = c+1;

   // Find any next bit in the same word as l:
   uint64_t w = bits[l>>6]>>(l&63);
   if (w) return flsll(w)-1+l;

   // Look at the remaining words:
   switch (l>>6) {
   case 0: w = bits[1];
           if (w) return flsll(w)+63;
           // fall through
   case 1: w = bits[2];
           if (w) return flsll(w)+127;
           // fall through
   case 2: w = bits[3];
           if (w) return flsll(w)+191;
           // fall through
   }
   return end();
}

Phil.