text: /**
   * @file
   *
   * @ingroup rtems_rfs
   *
   * @brief RTEMS File Systems Bitmap Routines
   *
   * These functions manage bit maps. A bit map consists of the map of bit
   * allocated in a block and a search map where a bit represents 32 actual
   * bits. The search map allows for a faster search for an available bit as 32
   * search bits can checked in a test.
   */
  
  /*
   *  COPYRIGHT (c) 2010 Chris Johns <chrisj@rtems.org>
   *
   *  The license and distribution terms for this file may be
   *  found in the file LICENSE in this distribution or at
   *  http://www.rtems.org/license/LICENSE.
   */
  
  #ifdef HAVE_CONFIG_H
  #include "config.h"
  #endif
  
  /**
   * Set to 1 to enable warnings when developing.
   */
  #define RTEMS_RFS_BITMAP_WARNINGS 0
  
  #if RTEMS_RFS_BITMAP_WARNINGS
  #include <stdio.h>
  #endif
  #include <stdlib.h>
  #include <rtems/rfs/rtems-rfs-bitmaps.h>
  
  /**
   * Test a bit in an element. If set return true else return false.
   *
   * @param target The target to test the bit in.
   * @param bit The bit to test.
   * @retval true The bit is set.
   * @retval false The bit is clear.
   */
  static bool
  rtems_rfs_bitmap_test (rtems_rfs_bitmap_element target,
                         rtems_rfs_bitmap_bit     bit)
  {
    return RTEMS_RFS_BITMAP_TEST_BIT (target, bit);
  }
  
  /**
   * Set the bits in the element. Bits not set in the bit argument are left
   * unchanged.
   *
   * @param target The target element bits are set.
   * @param bits The bits in the target to set. A 1 in the bits will set the
   *             same bit in the target.
   */
  static rtems_rfs_bitmap_element
  rtems_rfs_bitmap_set (rtems_rfs_bitmap_element target,
                        rtems_rfs_bitmap_element bits)
  {
    return RTEMS_RFS_BITMAP_SET_BITS (target, bits);
  }
  
  /**
   * Clear the bits in the element. Bits not set in the bit argument are left
   * unchanged.
   *
   * @param target The target element to clear the bits in.
   * @param bits The bits in the target to clear. A 1 in the bits will clear the
   *             bit in the target.
   */
  static rtems_rfs_bitmap_element
  rtems_rfs_bitmap_clear (rtems_rfs_bitmap_element target,
                          rtems_rfs_bitmap_element bits)
  {
    return RTEMS_RFS_BITMAP_CLEAR_BITS (target, bits);
  }
  
  /**
   * Merge the bits in 2 variables based on the mask. A set bit in the mask will
   * merge the bits from bits1 and a clear bit will merge the bits from bits2.
   * The mask is always defined as 1 being set and 0 being clear.
   */
  static rtems_rfs_bitmap_element
  rtems_rfs_bitmap_merge (rtems_rfs_bitmap_element bits1,
                          rtems_rfs_bitmap_element bits2,
                          rtems_rfs_bitmap_element mask)
  {
    /*
     * Use the normal bit operators because we do not change the bits just merge
     * the 2 separate parts.
     */
    bits1 &= mask;
    bits2 &= RTEMS_RFS_BITMAP_INVERT_MASK (mask);
    return bits1 | bits2;
  }
  
  /**
   * Match the bits of 2 elements and return true if they match else return
   * false.
   *
   * @param bits1 One set of bits to match.
   * @param bits2 The second set of bits to match.
   * @retval true The bits match.
   * @retval false The bits do not match.
   */
  static bool
  rtems_rfs_bitmap_match (rtems_rfs_bitmap_element bits1,
                          rtems_rfs_bitmap_element bits2)
  {
    return bits1 ^ bits2 ? false : true;
  }
  
  #if RTEMS_NOT_USED_BUT_KEPT
  /**
   * Match the bits of 2 elements within the mask and return true if they match
   * else return false.
   *
   * @param mask The mask over which the match occurs. A 1 is a valid mask bit.
   * @param bits1 One set of bits to match.
   * @param bits2 The second set of bits to match.
   * @retval true The bits match.
   * @retval false The bits do not match.
   */
  static bool
  rtems_rfs_bitmap_match_masked (rtems_rfs_bitmap_element mask,
                                 rtems_rfs_bitmap_element bits1,
                                 rtems_rfs_bitmap_element bits2)
  {
    return (bits1 ^ bits2) & mask ? false : true;
  }
  #endif
  
  /**
   * Return the map after loading from disk if not already loaded.
   *
   * @param control The bitmap control.
   * @param rtems_rfs_bitmap_map* Pointer to the bitmap map data if no error.
   * @return int The error number (errno). No error if 0.
   */
  static int
  rtems_rfs_bitmap_load_map (rtems_rfs_bitmap_control* control,
                             rtems_rfs_bitmap_map*     map)
  {
    int rc;
  
    if (!control->buffer)
      return ENXIO;
  
    *map = NULL;
  
    rc = rtems_rfs_buffer_handle_request (control->fs,
                                          control->buffer,
                                          control->block,
                                          true);
    if (rc)
      return rc;
  
    *map = rtems_rfs_buffer_data (control->buffer);
    return 0;
  }
  
  rtems_rfs_bitmap_element
  rtems_rfs_bitmap_mask (unsigned int size)
  {
    rtems_rfs_bitmap_element mask = RTEMS_RFS_BITMAP_ELEMENT_FULL_MASK;
    mask >>= (rtems_rfs_bitmap_element_bits () - size);
    return mask;
  }
  
  rtems_rfs_bitmap_element
  rtems_rfs_bitmap_mask_section (unsigned int start, unsigned int end)
  {
    rtems_rfs_bitmap_element mask = 0;
    if (end > start)
      mask = rtems_rfs_bitmap_mask (end - start) << start;
    return mask;
  }
  
  int
  rtems_rfs_bitmap_map_set (rtems_rfs_bitmap_control* control,
                            rtems_rfs_bitmap_bit      bit)
  {
    rtems_rfs_bitmap_map     map;
    rtems_rfs_bitmap_map     search_map;
    int                      index;
    int                      offset;
    int                      rc;
    rtems_rfs_bitmap_element element;
  
    rc = rtems_rfs_bitmap_load_map (control, &map);
    if (rc > 0)
      return rc;
  
    if (bit >= control->size)
      return EINVAL;
  
    search_map = control->search_bits;
    index      = rtems_rfs_bitmap_map_index (bit);
    offset     = rtems_rfs_bitmap_map_offset (bit);
    element    = map[index];
    map[index] = rtems_rfs_bitmap_set (element, 1 << offset);
  
    /*
     * If the element does not change, the bit was already set. There will be no
     * further action to take.
     */
    if (rtems_rfs_bitmap_match(element, map[index]))
        return 0;
  
    control->free--;
  
    rtems_rfs_buffer_mark_dirty (control->buffer);
    if (rtems_rfs_bitmap_match(map[index], RTEMS_RFS_BITMAP_ELEMENT_SET))
    {
      bit = index;
      index  = rtems_rfs_bitmap_map_index (bit);
      offset = rtems_rfs_bitmap_map_offset (bit);
      search_map[index] = rtems_rfs_bitmap_set (search_map[index], 1 << offset);
    }
  
    return 0;
  }
  
  int
  rtems_rfs_bitmap_map_clear (rtems_rfs_bitmap_control* control,
                              rtems_rfs_bitmap_bit      bit)
  {
    rtems_rfs_bitmap_map     map;
    rtems_rfs_bitmap_map     search_map;
    int                      index;
    int                      offset;
    int                      rc;
    rtems_rfs_bitmap_element element;
  
    rc = rtems_rfs_bitmap_load_map (control, &map);
    if (rc > 0)
      return rc;
  
    if (bit >= control->size)
      return EINVAL;
  
    search_map = control->search_bits;
    index      = rtems_rfs_bitmap_map_index (bit);
    offset     = rtems_rfs_bitmap_map_offset (bit);
    element    = map[index];
    map[index] = rtems_rfs_bitmap_clear (element, 1 << offset);
  
    /*
     * If the element does not change, the bit was already clear. There will be
     * no further action to take.
     */
    if (rtems_rfs_bitmap_match(element, map[index]))
        return 0;
  
    bit               = index;
    index             = rtems_rfs_bitmap_map_index (bit);
    offset            = rtems_rfs_bitmap_map_offset(bit);
    search_map[index] = rtems_rfs_bitmap_clear (search_map[index], 1 << offset);
    rtems_rfs_buffer_mark_dirty (control->buffer);
    control->free++;
  
    return 0;
  }
  
  int
  rtems_rfs_bitmap_map_test (rtems_rfs_bitmap_control* control,
                             rtems_rfs_bitmap_bit      bit,
                             bool*                     state)
  {
    rtems_rfs_bitmap_map map;
    int                  index;
    int                  rc;
    rc = rtems_rfs_bitmap_load_map (control, &map);
    if (rc > 0)
      return rc;
    if (bit >= control->size)
      return EINVAL;
    index = rtems_rfs_bitmap_map_index (bit);
    *state = rtems_rfs_bitmap_test (map[index], bit);
    return 0;
  }
  
  int
  rtems_rfs_bitmap_map_set_all (rtems_rfs_bitmap_control* control)
  {
    rtems_rfs_bitmap_map map;
    size_t               elements;
    int                  e;
    int                  rc;
  
    rc = rtems_rfs_bitmap_load_map (control, &map);
    if (rc > 0)
      return rc;
  
    elements = rtems_rfs_bitmap_elements (control->size);
  
    control->free = 0;
  
    for (e = 0; e < elements; e++)
      map[e] = RTEMS_RFS_BITMAP_ELEMENT_SET;
  
    elements = rtems_rfs_bitmap_elements (elements);
  
    for (e = 0; e < elements; e++)
      control->search_bits[e] = RTEMS_RFS_BITMAP_ELEMENT_SET;
  
    rtems_rfs_buffer_mark_dirty (control->buffer);
  
    return 0;
  }
  
  int
  rtems_rfs_bitmap_map_clear_all (rtems_rfs_bitmap_control* control)
  {
    rtems_rfs_bitmap_map map;
    rtems_rfs_bitmap_bit last_search_bit;
    size_t               elements;
    int                  e;
    int                  rc;
  
    rc = rtems_rfs_bitmap_load_map (control, &map);
    if (rc > 0)
      return rc;
  
    elements = rtems_rfs_bitmap_elements (control->size);
  
    control->free = control->size;
  
    for (e = 0; e < elements; e++)
      map[e] = RTEMS_RFS_BITMAP_ELEMENT_CLEAR;
  
    /*
     * Set the un-mapped bits in the last search element so the available logic
     * works.
     */
    last_search_bit = rtems_rfs_bitmap_map_offset (elements);
  
    if (last_search_bit == 0)
      last_search_bit = rtems_rfs_bitmap_element_bits ();
  
    elements = rtems_rfs_bitmap_elements (elements);
  
    for (e = 0; e < (elements - 1); e++)
      control->search_bits[e] = RTEMS_RFS_BITMAP_ELEMENT_CLEAR;
  
    control->search_bits[elements - 1] =
      rtems_rfs_bitmap_merge (RTEMS_RFS_BITMAP_ELEMENT_CLEAR,
                              RTEMS_RFS_BITMAP_ELEMENT_SET,
                              rtems_rfs_bitmap_mask (last_search_bit));
  
    rtems_rfs_buffer_mark_dirty (control->buffer);
  
    return 0;
  }
  
  static int
  rtems_rfs_search_map_for_clear_bit (rtems_rfs_bitmap_control* control,
                                      rtems_rfs_bitmap_bit*     bit,
                                      bool*                     found,
                                      size_t                    window,
                                      int                       direction)
  {
    rtems_rfs_bitmap_map      map;
    rtems_rfs_bitmap_bit      test_bit;
    rtems_rfs_bitmap_bit      end_bit;
    rtems_rfs_bitmap_element* search_bits;
    int                       search_index;
    int                       search_offset;
    rtems_rfs_bitmap_element* map_bits;
    int                       map_index;
    int                       map_offset;
    int                       rc;
  
    *found = false;
  
    /*
     * Load the bitmap.
     */
    rc = rtems_rfs_bitmap_load_map (control, &map);
    if (rc > 0)
      return rc;
  
    /*
     * Calculate the bit we are testing plus the end point we search over.
     */
    test_bit = *bit;
    end_bit  = test_bit + (window * direction);
  
    if (end_bit < 0)
      end_bit = 0;
    else if (end_bit >= control->size)
      end_bit = control->size - 1;
  
    map_index     = rtems_rfs_bitmap_map_index (test_bit);
    map_offset    = rtems_rfs_bitmap_map_offset (test_bit);
    search_index  = rtems_rfs_bitmap_map_index (map_index);
    search_offset = rtems_rfs_bitmap_map_offset (map_index);
  
    search_bits = &control->search_bits[search_index];
    map_bits    = &map[map_index];
  
    /*
     * Check each bit from the search map offset for a clear bit.
     */
    do
    {
      /*
       * If any bit is clear find that bit and then search the map element. If
       * all bits are set there are no map bits so move to the next search
       * element.
       */
      if (!rtems_rfs_bitmap_match (*search_bits, RTEMS_RFS_BITMAP_ELEMENT_SET))
      {
        while ((search_offset >= 0)
               && (search_offset < rtems_rfs_bitmap_element_bits ()))
        {
          if (!rtems_rfs_bitmap_test (*search_bits, search_offset))
          {
            /*
             * Find the clear bit in the map. Update the search map and map if
             * found. We may find none are spare if searching up from the seed.
             */
            while ((map_offset >= 0)
                   && (map_offset < rtems_rfs_bitmap_element_bits ()))
            {
              if (!rtems_rfs_bitmap_test (*map_bits, map_offset))
              {
                *map_bits = rtems_rfs_bitmap_set (*map_bits, 1 << map_offset);
                if (rtems_rfs_bitmap_match(*map_bits,
                                           RTEMS_RFS_BITMAP_ELEMENT_SET))
                  *search_bits = rtems_rfs_bitmap_set (*search_bits,
                                                       1 << search_offset);
                control->free--;
                *bit = test_bit;
                *found = true;
                rtems_rfs_buffer_mark_dirty (control->buffer);
                return 0;
              }
  
              if (test_bit == end_bit)
                break;
  
              map_offset += direction;
              test_bit   += direction;
            }
          }
  
          map_bits  += direction;
          map_index += direction;
          map_offset = direction > 0 ? 0 : rtems_rfs_bitmap_element_bits () - 1;
  
          test_bit = (map_index * rtems_rfs_bitmap_element_bits ()) + map_offset;
  
          search_offset += direction;
  
          if (((direction < 0) && (test_bit <= end_bit))
              || ((direction > 0) && (test_bit >= end_bit)))
            break;
        }
      }
      else
      {
        /*
         * Move to the next search element. We need to determine the number of
         * bits in the search offset that are being skipped so the map bits
         * pointer can be updated. If we are moving down and we have a search
         * offset of 0 then the search map adjustment is to the top bit of the
         * pervious search bit's value.
         *
         * Align test_bit either up or down depending on the direction to next 32
         * bit boundary.
         */
        rtems_rfs_bitmap_bit bits_skipped;
        test_bit &= ~((1 << RTEMS_RFS_ELEMENT_BITS_POWER_2) - 1);
        if (direction > 0)
        {
          bits_skipped = rtems_rfs_bitmap_element_bits () - search_offset;
          test_bit += bits_skipped * rtems_rfs_bitmap_element_bits ();
          map_offset = 0;
        }
        else
        {
          bits_skipped = search_offset + 1;
          /*
           * Need to remove 1 for the rounding up. The above rounds down and
           * adds 1. Remember the logic is for subtraction.
           */
          test_bit -= ((bits_skipped - 1) * rtems_rfs_bitmap_element_bits ()) + 1;
          map_offset = rtems_rfs_bitmap_element_bits () - 1;
        }
        map_bits += direction * bits_skipped;
        map_index += direction * bits_skipped;
      }
  
      search_bits  += direction;
      search_offset = direction > 0 ? 0 : rtems_rfs_bitmap_element_bits () - 1;
    }
    while (((direction < 0) && (test_bit >= end_bit))
           || ((direction > 0) && (test_bit <= end_bit)));
  
    return 0;
  }
  
  int
  rtems_rfs_bitmap_map_alloc (rtems_rfs_bitmap_control* control,
                              rtems_rfs_bitmap_bit      seed,
                              bool*                     allocated,
                              rtems_rfs_bitmap_bit*     bit)
  {
    rtems_rfs_bitmap_bit upper_seed;
    rtems_rfs_bitmap_bit lower_seed;
    rtems_rfs_bitmap_bit window;     /* may become a parameter */
    int                  rc = 0;
  
    /*
     * By default we assume the allocation failed.
     */
    *allocated = false;
  
    /*
     * The window is the number of bits we search over in either direction each
     * time.
     */
    window = RTEMS_RFS_BITMAP_SEARCH_WINDOW;
  
    /*
     * Start from the seed and move in either direction. Search in window amounts
     * of bits from the original seed above then below. That is search from the
     * seed up then from the seed down a window number of bits, then repeat the
     * process from the window distance from the seed, again above then
     * below. Keep moving out until all bits have been searched.
     */
    upper_seed = seed;
    lower_seed = seed;
  
    /*
     * If the upper and lower seed values have reached the limits of the bitmap
     * we have searched all of the map. The seed may not be aligned to a window
     * boundary so we may need to search a partial window and this may also not
     * be balanced for the upper or lower seeds. We move to the limits, search
     * then return false if no clear bits are found.
     */
    while (((upper_seed >= 0) && (upper_seed < control->size))
           || ((lower_seed >= 0) && (lower_seed < control->size)))
    {
      /*
       * Search up first so bits allocated in succession are grouped together.
       */
      if (upper_seed < control->size)
      {
        *bit = upper_seed;
        rc = rtems_rfs_search_map_for_clear_bit (control, bit, allocated,
                                                 window, 1);
        if ((rc > 0) || *allocated)
          break;
      }
  
      if (lower_seed >= 0)
      {
        *bit = lower_seed;
        rc = rtems_rfs_search_map_for_clear_bit (control, bit, allocated,
                                                 window, -1);
        if ((rc > 0) || *allocated)
          break;
      }
  
      /*
       * Do not bound the limits at the edges of the map. Do not update if an
       * edge has been passed.
       */
      if (upper_seed < control->size)
        upper_seed += window;
      if (lower_seed >= 0)
        lower_seed -= window;
    }
  
    return 0;
  }
  
  int
  rtems_rfs_bitmap_create_search (rtems_rfs_bitmap_control* control)
  {
    rtems_rfs_bitmap_map search_map;
    rtems_rfs_bitmap_map map;
    size_t               size;
    rtems_rfs_bitmap_bit bit;
    int                  rc;
  
    rc = rtems_rfs_bitmap_load_map (control, &map);
    if (rc > 0)
      return rc;
  
    control->free = 0;
    search_map = control->search_bits;
    size = control->size;
    bit = 0;
  
    *search_map = RTEMS_RFS_BITMAP_ELEMENT_CLEAR;
    while (size)
    {
      rtems_rfs_bitmap_element bits;
      int                      available;
      if (size < rtems_rfs_bitmap_element_bits ())
      {
        bits = rtems_rfs_bitmap_merge (*map,
                                       RTEMS_RFS_BITMAP_ELEMENT_SET,
                                       rtems_rfs_bitmap_mask_section (0, size));
        available = size;
      }
      else
      {
        bits      = *map;
        available = rtems_rfs_bitmap_element_bits ();
      }
  
      if (rtems_rfs_bitmap_match (bits, RTEMS_RFS_BITMAP_ELEMENT_SET))
        rtems_rfs_bitmap_set (*search_map, bit);
      else
      {
        int b;
        for (b = 0; b < available; b++)
          if (!rtems_rfs_bitmap_test (bits, b))
            control->free++;
      }
  
      size -= available;
  
      /* Iterate from 0 to 1 less than the number of bits in an element */
      if (bit == (rtems_rfs_bitmap_element_bits () - 1))
      {
        bit = 0;
        search_map++;
        *search_map = RTEMS_RFS_BITMAP_ELEMENT_CLEAR;
      }
      else
        bit++;
      map++;
    }
  
    return 0;
  }
  
  int
  rtems_rfs_bitmap_open (rtems_rfs_bitmap_control* control,
                         rtems_rfs_file_system*    fs,
                         rtems_rfs_buffer_handle*  buffer,
                         size_t                    size,
                         rtems_rfs_buffer_block    block)
  {
    size_t elements = rtems_rfs_bitmap_elements (size);
  
    control->buffer = buffer;
    control->fs = fs;
    control->block = block;
    control->size = size;
  
    elements = rtems_rfs_bitmap_elements (elements);
    control->search_bits = malloc (elements * sizeof (rtems_rfs_bitmap_element));
  
    if (!control->search_bits)
      return ENOMEM;
  
    return rtems_rfs_bitmap_create_search (control);
  }
  
  int
  rtems_rfs_bitmap_close (rtems_rfs_bitmap_control* control)
  {
    free (control->search_bits);
    return 0;
  }
  