FreeBSD/contrib/subversion/subversion/libsvn_subr/cache-membuffer.c
/* Given the GROUP_INDEX that shall contain an entry with the hash key
 * TO_FIND, find that entry in the specified group.
 *
 * If FIND_EMPTY is not set, this function will return the one used entry
 * that actually matches the hash or NULL, if no such entry exists.
 *
 * If FIND_EMPTY has been set, this function will drop the one used entry
 * that actually matches the hash (i.e. make it fit to be replaced with
 * new content), an unused entry or a forcibly removed entry (if all
 * group entries are currently in use). The entries' hash value will be
 * initialized with TO_FIND.
 *
 * Note: This function requires the caller to appropriately lock the CACHE.
 * For FIND_EMPTY==FALSE, a read lock is required, for FIND_EMPTY==TRUE,
 * the write lock must have been acquired.
 */
Given the GROUP_INDEX that shall contain an entry with the hash key
TO_FIND, find that entry in the specified group.

If FIND_EMPTY is not set, this function will return the one used entry
that actually matches the hash or NULL, if no such entry exists.

If FIND_EMPTY has been set, this function will drop the one used entry
that actually matches the hash , an unused entry or a forcibly removed entry (if all
group entries are currently in use). The entries' hash value will be
initialized with TO_FIND.

This function requires the caller to appropriately lock the CACHE.
For FIND_EMPTY==FALSE, a read lock is required, for FIND_EMPTY==TRUE,
the write lock must have been acquired.
Given the GROUP_INDEX that shall contain an entry with the hash key TO_FIND find that entry in the specified group . If FIND_EMPTY is not set this function will return the one used entry that actually matches the hash or NULL if no such entry exists . If FIND_EMPTY has been set this function will drop the one used entry that actually matches the hash an unused entry or a forcibly removed entry ( if all group entries are currently in use ) . The entries ' hash value will be initialized with TO_FIND . This function requires the caller to appropriately lock the CACHE . For FIND_EMPTY == FALSE a read lock is required for FIND_EMPTY == TRUE the write lock must have been acquired .
static entry_t *
find_entry(svn_membuffer_t *cache,
           apr_uint32_t group_index,
           const full_key_t *to_find,
           svn_boolean_t find_empty)
{
  entry_group_t *group;
  entry_t *entry = NULL;
  apr_size_t i;
  group = &cache->directory[group_index];
  if (! is_group_initialized(cache, group_index))
    {
      if (find_empty)
        {
          initialize_group(cache, group_index);
          entry = &group->entries[0];
          entry->key = to_find->entry_key;
        }
      return entry;
    }
  while (1)
    {
      for (i = 0; i < group->header.used; ++i)
        if (entry_keys_match(&group->entries[i].key, &to_find->entry_key))
          {
            entry = &group->entries[i];
            if (!find_empty)
              {
                if (!entry->key.key_len)
                  return entry;
                if (memcmp(to_find->full_key.data,
                           cache->data + entry->offset,
                           entry->key.key_len) == 0)
                  return entry;
                return NULL;
              }
            drop_entry(cache, entry);
            if (group->header.used == GROUP_SIZE)
              group = last_group_in_chain(cache, group);
            else if (group->header.chain_length == 0)
              group = last_group_in_chain(cache,
                                          &cache->directory[group_index]);
            entry = NULL;
            break;
          }
      if (group->header.next == NO_INDEX)
        break;
      assert(group->header.used == GROUP_SIZE);
      group = &cache->directory[group->header.next];
    }
  if (find_empty)
    {
      if (   group->header.used == GROUP_SIZE
          && group->header.chain_length < MAX_GROUP_CHAIN_LENGTH)
        {
          entry_group_t *new_group = allocate_spare_group(cache);
          if (new_group)
            {
              new_group->header.chain_length = group->header.chain_length + 1;
              new_group->header.previous = (apr_uint32_t) (group -
                                                           cache->directory);
              new_group->header.next = NO_INDEX;
              group->header.next = (apr_uint32_t) (new_group -
                                                   cache->directory);
              group = new_group;
            }
        }
      if (group->header.used == GROUP_SIZE)
        {
          cache_level_t *entry_level;
          int to_remove = rand() % (GROUP_SIZE * group->header.chain_length);
          entry_group_t *to_shrink
            = get_group(cache, group_index, to_remove / GROUP_SIZE);
          entry = &to_shrink->entries[to_remove % GROUP_SIZE];
          entry_level = get_cache_level(cache, entry);
          for (i = 0; i < GROUP_SIZE; ++i)
            {
              cache_level_t *level
                = get_cache_level(cache, &to_shrink->entries[i]);
              if (   (level != entry_level && entry_level == &cache->l1)
                  || (entry->hit_count > to_shrink->entries[i].hit_count))
                {
                  entry_level = level;
                  entry = &to_shrink->entries[i];
                }
            }
          for (i = 0; i < GROUP_SIZE; ++i)
            if (entry != &to_shrink->entries[i])
              let_entry_age(cache, entry);
          drop_entry(cache, entry);
        }
      entry = &group->entries[group->header.used];
      entry->key = to_find->entry_key;
    }
  return entry;
}
static entry_t * find_entry ( svn_membuffer_t * cache , apr_uint32_t group_index , const full_key_t * to_find , svn_boolean_t find_empty ) { entry_group_t * group ; entry_t * entry = NULL ; apr_size_t i ; group = & cache -> directory [ group_index ] ; if ( ! is_group_initialized ( cache , group_index ) ) { if ( find_empty ) { initialize_group ( cache , group_index ) ; entry = & group -> entries [ 0 ] ; entry -> key = to_find -> entry_key ; } return entry ; } while ( 1 ) { for ( i = 0 ; i < group -> header . used ; ++ i ) if ( entry_keys_match ( & group -> entries [ i ] . key , & to_find -> entry_key ) ) { entry = & group -> entries [ i ] ; if ( ! find_empty ) { if ( ! entry -> key . key_len ) return entry ; if ( memcmp ( to_find -> full_key . data , cache -> data + entry -> offset , entry -> key . key_len ) == 0 ) return entry ; return NULL ; } drop_entry ( cache , entry ) ; if ( group -> header . used == GROUP_SIZE ) group = last_group_in_chain ( cache , group ) ; else if ( group -> header . chain_length == 0 ) group = last_group_in_chain ( cache , & cache -> directory [ group_index ] ) ; entry = NULL ; break ; } if ( group -> header . next == NO_INDEX ) break ; assert ( group -> header . used == GROUP_SIZE ) ; group = & cache -> directory [ group -> header . next ] ; } if ( find_empty ) { if ( group -> header . used == GROUP_SIZE && group -> header . chain_length < MAX_GROUP_CHAIN_LENGTH ) { entry_group_t * new_group = allocate_spare_group ( cache ) ; if ( new_group ) { new_group -> header . chain_length = group -> header . chain_length + 1 ; new_group -> header . previous = ( apr_uint32_t ) ( group - cache -> directory ) ; new_group -> header . next = NO_INDEX ; group -> header . next = ( apr_uint32_t ) ( new_group - cache -> directory ) ; group = new_group ; } } if ( group -> header . used == GROUP_SIZE ) { cache_level_t * entry_level ; int to_remove = rand ( ) % ( GROUP_SIZE * group -> header . chain_length ) ; entry_group_t * to_shrink = get_group ( cache , group_index , to_remove / GROUP_SIZE ) ; entry = & to_shrink -> entries [ to_remove % GROUP_SIZE ] ; entry_level = get_cache_level ( cache , entry ) ; for ( i = 0 ; i < GROUP_SIZE ; ++ i ) { cache_level_t * level = get_cache_level ( cache , & to_shrink -> entries [ i ] ) ; if ( ( level != entry_level && entry_level == & cache -> l1 ) || ( entry -> hit_count > to_shrink -> entries [ i ] . hit_count ) ) { entry_level = level ; entry = & to_shrink -> entries [ i ] ; } } for ( i = 0 ; i < GROUP_SIZE ; ++ i ) if ( entry != & to_shrink -> entries [ i ] ) let_entry_age ( cache , entry ) ; drop_entry ( cache , entry ) ; } entry = & group -> entries [ group -> header . used ] ; entry -> key = to_find -> entry_key ; } return entry ; }
Given the GROUP_INDEX that shall contain an entry with the hash key
 TO_FIND, find that entry in the specified group.
Given the GROUP_INDEX that shall contain an entry with the hash key TO_FIND find that entry in the specified group .
/* get the group that *must* contain the entry
   */ /* If the entry group has not been initialized, yet, there is no data.
   */ /* initialize entry for the new key */ /* try to find the matching entry
   */ /* This is the only entry that _may_ contain the correct data. */ /* If we want to preserve it, check that it is actual a match. */ /* If there is no full key to compare, we are done. */ /* Compare the full key. */ /* Key conflict. The entry to find cannot be anywhere else.
                 * Therefore, it is not cached. */ /* need to empty that entry */ /* No entry found (actually, none left to find). */ /* end of chain? */ /* only full groups may chain */ /* None found. Are we looking for a free entry?
   */ /* There is no empty entry in the chain, try chaining a spare group.
       */ /* chain groups
               */ /* if GROUP is still filled, we need to remove a random entry */ /* every entry gets the same chance of being removed.
           * Otherwise, we free the first entry, fill it and
           * remove it again on the next occasion without considering
           * the other entries in this group.
           *
           * We hit only one random group instead of processing all
           * groups in the chain.
           */ /* keep L1 entries whenever possible */ /* for the entries that don't have been removed,
           * reduce their hit counts to put them at a relative
           * disadvantage the next time.
           */ /* initialize entry for the new key
       */