UtlContainable* UtlHashBag::remove(const UtlContainable* object)
{
   UtlContainable* removed = NULL;

   if (object)
   {
      OsLock take(mContainerLock);

      UtlLink*  link;
      UtlChain* bucket;

      if ( lookup(object, bucket, link) )
      {
         removed = link->data;

         notifyIteratorsOfRemove(link);

         link->detachFromList(bucket);
         removed = link->data;
         link->release();

         mElements--;
      }
   }

   return removed;
}

// Return the list position of the designated object.
ssize_t UtlSList::index(const UtlContainable* containableToMatch) const
{
    ssize_t matchedIndex = UTL_NOT_FOUND;
    ssize_t currentIndex;
    UtlLink* listNode;
    UtlContainable* visitNode = NULL;

    OsLock take(mContainerLock);

    LIST_SANITY_CHECK;
    for(listNode = head(), currentIndex = 0;
        matchedIndex == UTL_NOT_FOUND && listNode;
        listNode = listNode->next()
        )
    {
        visitNode = (UtlContainable*) listNode->data;
        if(visitNode && visitNode->compareTo(containableToMatch) == 0)
        {
           matchedIndex = currentIndex;
        }
        else
        {
           currentIndex++;
        }
    }
    LIST_SANITY_CHECK;

    return matchedIndex;
}

// Find the next like-instance of the designated object .
UtlContainable* UtlSListIterator::findNext(const UtlContainable* containableToMatch) 
{
   UtlContainable* match = NULL;

   UtlContainer::acquireIteratorConnectionLock();
   OsLock takeContainer(mContainerRefLock);
   UtlSList* myList = static_cast<UtlSList*>(mpMyContainer);
   
   OsLock take(myList->mContainerLock);
   UtlContainer::releaseIteratorConnectionLock();

   // advance the iterator
   UtlLink* nextLink = (mpCurrentNode == NULL
                        ? myList->head()
                        : mpCurrentNode->next()
                        );

   // search for the next match forward
   while (nextLink && !match)
   {
      UtlContainable *candidate = (UtlContainable*)nextLink->data;
      if (candidate && candidate->compareTo(containableToMatch) == 0)
      {
         mpCurrentNode = nextLink;
         match = candidate;
      }
      else
      {
         nextLink = nextLink->next();
      }
   }
   
   return match;
}

// Return the first UtlLink node to find.
UtlLink* UtlSortedList::findNode(UtlLink* start, MatchType match, const UtlContainable* obj) const
{
   UtlLink*        listNode;
   UtlLink*        foundNode;
   UtlContainable* listElement;
   int             comparison = 0;
   
   // the caller already holds the mContainerLock

   for (listNode = start, foundNode = NULL;
        !foundNode && listNode;
        listNode = listNode->next()
        )
   {
      listElement = (UtlContainable*)listNode->data;
      if (listElement)
      {
         // we can't use the hash as a shortcut here because we need the order too
         comparison = listElement->compareTo(obj);
         if ( comparison >= 0 )
         {
            foundNode = listNode;
         }
      }
   }

   if (foundNode && match == EXACTLY && comparison != 0) // match not exact
   {
      foundNode = NULL; 
   }
   return foundNode;
}

// Find the first occurrence of the designated object by equality.
UtlContainable* UtlSList::find(const UtlContainable* containableToMatch) const
{
   UtlLink* listNode;
   UtlContainable* matchElement = NULL;
   UtlContainable* visitNode;

   unsigned targetHash = containableToMatch->hash();

   OsLock take(mContainerLock);

   LIST_SANITY_CHECK;
   for(listNode = head()->findNextHash(targetHash);
       listNode &&  matchElement == NULL;
       listNode = listNode->next()->findNextHash(targetHash)
       )
   {
      visitNode = (UtlContainable*) listNode->data;
      if(visitNode && visitNode->compareTo(containableToMatch) == 0)
      {
         matchElement = visitNode;
      }
   }
   LIST_SANITY_CHECK;

   return(matchElement);
}

// Remove the designated object by equality.
UtlContainable* UtlSList::remove(const UtlContainable* object)
{
   UtlLink* listNode;
   UtlLink* found;
   UtlContainable* foundObject = NULL;

   OsLock take(mContainerLock);

   LIST_SANITY_CHECK;
   for (listNode = head(), found = NULL; listNode && !found; listNode = listNode->next())
   {
      UtlContainable* visitNode = (UtlContainable*) listNode->data;
      if(visitNode && visitNode->compareTo(object) == 0)
      {
         found = listNode;
      }
   }

   if (found)
   {
      foundObject = (UtlContainable*)found->data;
      removeLink(found);
   }
   LIST_SANITY_CHECK;

   return foundObject;
}

void UtlHashBag::notifyIteratorsOfRemove(const UtlLink* link)
{
   UtlLink* listNode;
   UtlHashBagIterator* foundIterator;

   for (listNode = mIteratorList.head(); listNode; listNode = listNode->next())
   {
      foundIterator = (UtlHashBagIterator*)listNode->data;
      foundIterator->removing(link);
   }
}

/*
 * Allocate additional buckets and redistribute existing contents.
 * This should only be called through resizeIfNeededAndSafe.
 */
void UtlHashBag::resize()
{
   // already holding the mContainerLock
   UtlChain* newBucket;
   size_t    newBucketBits;

   // if an iterator had prevented resizing while many elements were added,
   // we might need to double more than once to restore the target ratio.
   for (newBucketBits = mBucketBits+1;
        mElements / NUM_HASHBAG_BUCKETS(newBucketBits) >= 3;
        newBucketBits++
        )
   {
   }

   // allocate the new buckets
   newBucket = new UtlChain[NUM_HASHBAG_BUCKETS(newBucketBits)];

   if (newBucket)
   {
      // save the old buckets until we move the entries out of them
      UtlChain* oldBucket     = mpBucket;
      size_t    numOldBuckets = numberOfBuckets();

      // put in the new buckets
      mBucketBits = newBucketBits;
      mpBucket = newBucket;

      // move all the entries to the new buckets
      size_t old;
      size_t toBeMoved;
      for (old = 0, toBeMoved = mElements;
           old < numOldBuckets && toBeMoved;
           old++
           )
      {
         while(!oldBucket[old].isUnLinked()) // old bucket is not empty yet
         {
            UtlLink* link = static_cast<UtlLink*>(oldBucket[old].head());
            link->detachFromList(&oldBucket[old]);
            insert(link, &mpBucket[bucketNumber(link->hash)]);
            toBeMoved--;
         }
      }

      delete [] oldBucket; // finished with the old empty buckets
   }
   else
   {
      assert(newBucket); // failed to allocate new buckets
   }
}

// Return the number of occurrences of the designated object.
size_t UtlSList::occurrencesOf(const UtlContainable* containableToMatch) const
{
   int count = 0;
   UtlLink* listNode;
   UtlContainable* visitNode = NULL;

   OsLock take(mContainerLock);

   LIST_SANITY_CHECK;
   for(listNode = head(); listNode; listNode = listNode->next())
   {
      visitNode = (UtlContainable*)listNode->data;
      if(visitNode && visitNode->compareTo(containableToMatch) == 0)
      {
         count++;
      }
   }
   LIST_SANITY_CHECK;

   return(count);
}

// Return the number of occurrences of the designated object.
size_t UtlSortedList::occurrencesOf(const UtlContainable* containableToMatch) const 
{
   int count = 0;
   UtlLink* listNode;
   UtlContainable* visitNode = NULL;
   int             comparison;

   OsLock take(const_cast<OsBSem&>(mContainerLock));
   
   for (listNode = head(), comparison = 0;
        comparison <= 0 && listNode;
        listNode = listNode->next()
        )
   {
      visitNode = (UtlContainable*)listNode->data;
      if(visitNode && visitNode->compareTo(containableToMatch) == 0)
      {
         count++;
      }
   }

   return(count);
}

// Return the list position of the designated object.
size_t UtlSortedList::index(const UtlContainable* obj) const 
{
   size_t          index = UTL_NOT_FOUND;
   size_t          thisIndex;
   UtlLink*        listNode;
   unsigned        keyHash = obj->hash();
   
   OsLock take(const_cast<OsBSem&>(mContainerLock));
   
   for (listNode = head(), thisIndex = 0;
        listNode && index == UTL_NOT_FOUND;
        listNode = listNode->next(), thisIndex++)
   {
      if (   listNode->data                      // there is an object (for safety sake)
          && listNode->hash == keyHash           // quick test for possible equality
          && listNode->data->compareTo(obj) == 0 // real (but slower) test for equality
          )
      {
         index = thisIndex;
      }
   }
    
   return index;
}

// Insert at the designated position.
UtlContainable* UtlSList::insertAt(size_t N, UtlContainable* obj)
{
   // :NOTE: this method is deliberately not the same as g_list_insert in that
   //        the glib routine will accept a value of N > the length of the list
   //        but this routine treats that as an error.
   UtlContainable* inserted = NULL;

   OsLock take(mContainerLock);

   LIST_SANITY_CHECK;
   size_t n;
   UtlLink* link;
   for (n = 0, link = head(); link && n < N; link = link->next(), n++)
   {
   }
   if (n == N)
   {
      UtlLink::listBefore(this, link, obj);
      inserted = obj;
   }
   LIST_SANITY_CHECK;

   return inserted;
}