class AutoC::List

Generator for singly linked collection of elements

Public Class Methods

new(*args, maintain_size: true, **kws) click to toggle source

maintain_size:

true: managed size field (extra memory consumption)
false: computing #size function (slow, O(N))
Calls superclass method AutoC::Collection::new
# File lib/autoc/list.rb, line 30
def initialize(*args, maintain_size: true, **kws)
  super(*args, **kws)
  @_node = identifier(:_node, abbreviate: true)
  @_node_p = _node.lvalue
  @_node_pp = "#{_node}*".lvalue
  @maintain_size = maintain_size
end

Public Instance Methods

_locate_node_equal(eq) click to toggle source

Code template for locating the list node satisfying custom equality condition

# File lib/autoc/list.rb, line 101
def _locate_node_equal(eq)
  %{
    #{_node_p} curr;
    #{_node_p} prev;
    assert(target);
    assert(prev_p);
    assert(curr_p);
    prev = NULL;
    curr = target->front;
    while(curr) {
      if(#{eq}) {
        #ifndef NDEBUG
          if(prev)
            assert(prev->next == curr);
          else
            assert(target->front == curr);
        #endif
        *prev_p = prev;
        *curr_p = curr;
        return 1;
      }
      prev = curr;
      curr = curr->next;
    }
    return 0;
  }
end
_range_class(= Range) click to toggle source
# File lib/autoc/list.rb, line 21
  def _range_class = Range

  def range = @range ||= _range_class.new(self, visibility: visibility)

  attr_reader :_node, :_node_p, :_node_pp

  # maintain_size:
  #  true: managed size field (extra memory consumption)
  #  false: computing #size function (slow, O(N))
  def initialize(*args, maintain_size: true, **kws)
    super(*args, **kws)
    @_node = identifier(:_node, abbreviate: true)
    @_node_p = _node.lvalue
    @_node_pp = "#{_node}*".lvalue
    @maintain_size = maintain_size
  end

  def maintain_size? = @maintain_size

  def render_interface(stream)
    stream << %{
      /** @private */
      typedef struct #{_node} #{_node};
    }
    if public?
      stream << %{
        /**
          #{defgroup}

          @brief Singly linked list of elements of type #{element}

          For iteration over the list elements refer to @ref #{range}.

          @see C++ [std::forward_list<T>](https://en.cppreference.com/w/cpp/container/forward_list)

          @since 2.0
        */
      }
      stream << %{
        /**
          #{ingroup}

          @brief Opaque structure holding state of the list

          @since 2.0
        */
      }
    else
      stream << PRIVATE
    end
    stream << %{
      typedef struct {
        #{_node_p} front; /**< @private */
        #{'size_t size; /**< @private */' if maintain_size?}
      } #{signature};
      /** @private */
      struct #{_node} {
        #{element} element;
        #{_node_p} next;
      };
    }
  end

private

  def configure
    super
    method(:int, :_replace_first, { target: rvalue, value: element.const_rvalue }, visibility: :internal, constraint:-> { element.copyable? }).configure do
      # Replace first found element with specified value in-place
      code %{
        #{element.lvalue} e = (#{element.lvalue})#{find_first.(target, value)};
        if(e) {
          #{element.destroy.('*e') if element.destructible?};
          #{element.copy.('*e', value)};
          return 1;
        } else
          return 0;
      }
    end
    # Code template for locating the list node satisfying custom equality condition
    def _locate_node_equal(eq)
      %{
        #{_node_p} curr;
        #{_node_p} prev;
        assert(target);
        assert(prev_p);
        assert(curr_p);
        prev = NULL;
        curr = target->front;
        while(curr) {
          if(#{eq}) {
            #ifndef NDEBUG
              if(prev)
                assert(prev->next == curr);
              else
                assert(target->front == curr);
            #endif
            *prev_p = prev;
            *curr_p = curr;
            return 1;
          }
          prev = curr;
          curr = curr->next;
        }
        return 0;
      }
    end
    method(:int, :_locate_node, { target: const_rvalue, value: element.const_rvalue, prev_p: _node_pp, curr_p: _node_pp }, visibility: :internal, constraint:-> { element.comparable? }).configure do
      # Locate node satisfying default element equality condition, return this and previous nodes
      code _locate_node_equal(element.equal.('curr->element', value))
    end
    method(:void, :_pop_front, { target: rvalue }, visibility: :internal).configure do
      # Destroy frontal node but keep the element intact
      code %{
        #{_node_p} curr;
        assert(!#{empty.(target)});
        curr = target->front; assert(curr);
        target->front = target->front->next;
        #{'--target->size;' if maintain_size?}
        #{memory.free(:curr)};
      }
    end
    method(_node_p, :_pull_node, { target: rvalue }, visibility: :internal).configure do
      # Cut & return frontal node
      code %{
        #{_node_p} curr;
        assert(!#{empty.(target)});
        curr = target->front; assert(curr);
        target->front = curr->next;
        #{'--target->size;' if maintain_size?}
        return curr;
      }
    end
    method(:void, :_push_node, { target: rvalue, curr: _node_p }, visibility: :internal).configure do
      # Push exising node with intact payload
      code %{
        assert(target);
        curr->next = target->front;
        target->front = curr;
        #{'++target->size;' if maintain_size?}
      }
    end
    method(element.const_lvalue, :view_front, { target: const_rvalue })
    method(element, :take_front, { target: const_rvalue }, constraint:-> { element.copyable? })
    view_front.configure do
      dependencies << empty
      inline_code %{
        assert(!#{empty.(target)});
        return &(target->front->element);
      }
      header %{
        @brief Get a view of the front element

        @param[in] target list to get element from
        @return a view of a front element

        This function is used to get a constant reference (in form of the C pointer) to the front value contained in `target`.
        Refer to @ref #{take_front} to get an independent copy of that element.

        It is generally not safe to bypass the constness and to alter the value in place (although no one prevents to).

        @note List must not be empty (see @ref #{empty}).

        @since 2.0
      }
    end
    take_front.configure do
      code %{
        #{element} result;
        #{element.const_lvalue} e;
        assert(target);
        assert(!#{empty.(target)});
        e = #{view_front.(target)};
        #{element.copy.(:result, '*e')};
        return result;
      }
      header %{
        @brief Get front element

        @param[in] target list to get element from
        @return a *copy* of a front element

        This function is used to get a *copy* of the front value contained in `target`.
        Refer to @ref #{view_front} to get a view of that element without making an independent copy.

        This function requires the element type to be *copyable* (i.e. to have a well-defined copy operation).

        @note List must not be empty (see @ref #{empty}).

        @since 2.0
      }
    end
    method(element, :pull_front, { target: rvalue }).configure do
      code %{
        #{element} result;
        assert(target);
        assert(!#{empty.(target)});
        result = *#{view_front.(target)};
        #{_pop_front.(target)};
        return result;
      }
      header %{
        @brief Extract front element

        @param[in] target list to extract element from
        @return front element

        This function removes front element from the list and returns it.
        Note that contrary to @ref #{take_front} no copy operation is performed - it is the contained value itself that is returned.

        @note List must not be empty (see @ref #{empty}).

        @since 2.0
      }
    end
    method(:void, :drop_front, { target: rvalue }).configure do
      if element.destructible?
        code %{
          #{element.lvalue} e;
          assert(target);
          assert(!#{empty.(target)});
          e = (#{element.lvalue})#{view_front.(target)};
          #{element.destroy.('*e')};
          #{_pop_front.(target)};
        }
      else
        code %{
          assert(target);
          assert(!#{empty.(target)});
          #{_pop_front.(target)};
        }
      end
      header %{
        @brief Drop front element

        @param[in] target list to drop element from

        This function removes front element from the list and destroys it with the respective destructor.

        @note List must not be empty (see @ref #{empty}).

        @since 2.0
      }
    end
    method(:void, :push_front, { target: rvalue, value: element.const_rvalue }, constraint:-> { element.copyable? }).configure do
      code %{
        #{_node_p} curr;
        assert(target);
        curr = #{memory.allocate(_node)};
        curr->next = target->front;
        target->front = curr;
        #{'++target->size;' if maintain_size?}
        #{element.copy.('curr->element', value)};
      }
      header %{
        @brief Put element

        @param[in] target vector to put element into
        @param[in] value value to put

        This function pushes a *copy* of the specified value to the front position of `target`.
        It becomes a new front element.

        This function requires the element type to be *copyable* (i.e. to have a well-defined copy operation).

        @since 2.0
      }
    end
    def _remove_first(locator)
      %{
        #{_node_p} curr;
        #{_node_p} prev;
        assert(target);
        if(#{locator}) {
          assert(curr);
          if(prev) {
            prev->next = curr->next;
          } else {
            target->front = curr->next;
          }
          #{element.destroy.('curr->element') if element.destructible?};
          #{memory.free(:curr)};
          #{'--target->size;' if maintain_size?}
          return 1;
        }
        return 0;
      }
    end
    method(:int, :remove_first, { target: rvalue, value: element.const_rvalue }, constraint:-> { element.comparable? }).configure do
      code _remove_first(_locate_node.(target, value, :prev, :curr))
      header %{
        @brief Remove element

        @param[in] target list to remove element from
        @param[in] value value to search in list
        @return non-zero value on successful removal and zero value otherwise

        This function searches `target` for a first element equal to the specified `value` and removes it from the list.
        The removed element is destroyed with respective destructor.

        The function return value is non-zero if such element was found and removed and zero value otherwise.

        This function requires the element type to be *comparable* (i.e. to have a well-defined equality operation).

        @since 2.0
      }
    end
    default_create.configure do
      inline_code %{
        assert(target);
        target->front = NULL;
        #{'target->size = 0;' if maintain_size?}
      }
    end
    destroy.configure do
      code %{
        assert(target);
        while(!#{empty.(target)}) #{drop_front.(target)};
      }
    end
    copy.configure do
      code %{
        size_t i;
        #{range} r;
        #{element.const_lvalue}* t;
        assert(target);
        assert(source);
        #{default_create.(target)};
        t = #{memory.allocate(element.const_lvalue, size.(source))};
        for(i = 0, r = #{range.new.(source)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) {
          t[i++] = #{range.view_front.(:r)};
        }
        while(i > 0) #{push_front.(target, '*t[(i--)-1]')}; /* put elements in reverse order since the list itself is a LIFO structure */
        #{memory.free(:t)};
      }
    end
    empty.configure do
      inline_code %{
        assert(target);
        return target->front == NULL;
      }
    end
    if maintain_size?
      size.configure do
        inline_code %{
          assert(target);
          return target->size;
        }
      end
    else
      size.configure do
        code %{
          #{range} r;
          size_t size;
          assert(target);
          for(size = 0, r = #{range.new.(target)}; !#{range.empty.(:r)}; ++size, #{range.pop_front.(:r)});
          return size;
        }
      end
    end
  end
end # List


class List::Range < ForwardRange

  def render_interface(stream)
    if public?
      render_type_description(stream)
      stream << %{
        /**
          #{ingroup}
          @brief Opaque structure holding state of the list's range
          @since 2.0
        */
      }
    else
      stream << PRIVATE
    end
    stream << %{
      typedef struct {
        #{iterable._node_p} front; /**< @private */
      } #{signature};
    }
  end

private

  def configure
    super
    custom_create.configure do
      inline_code %{
        assert(range);
        assert(iterable);
        range->front = iterable->front;
      }
    end
    empty.configure do
      inline_code %{
        assert(range);
        return range->front == NULL;
      }
    end
    pop_front.configure do
      dependencies << empty
      inline_code %{
        assert(range);
        assert(!#{empty.(range)});
        range->front = range->front->next;
      }
    end
    view_front.configure do
      dependencies << empty
      inline_code %{
        assert(range);
        assert(!#{empty.(range)});
        return &range->front->element;
      }
    end
  end

end # List

_remove_first(locator) click to toggle source
# File lib/autoc/list.rb, line 289
def _remove_first(locator)
  %{
    #{_node_p} curr;
    #{_node_p} prev;
    assert(target);
    if(#{locator}) {
      assert(curr);
      if(prev) {
        prev->next = curr->next;
      } else {
        target->front = curr->next;
      }
      #{element.destroy.('curr->element') if element.destructible?};
      #{memory.free(:curr)};
      #{'--target->size;' if maintain_size?}
      return 1;
    }
    return 0;
  }
end
configure() click to toggle source
Calls superclass method AutoC::Sequential#configure
# File lib/autoc/list.rb, line 86
def configure
  super
  method(:int, :_replace_first, { target: rvalue, value: element.const_rvalue }, visibility: :internal, constraint:-> { element.copyable? }).configure do
    # Replace first found element with specified value in-place
    code %{
      #{element.lvalue} e = (#{element.lvalue})#{find_first.(target, value)};
      if(e) {
        #{element.destroy.('*e') if element.destructible?};
        #{element.copy.('*e', value)};
        return 1;
      } else
        return 0;
    }
  end
  # Code template for locating the list node satisfying custom equality condition
  def _locate_node_equal(eq)
    %{
      #{_node_p} curr;
      #{_node_p} prev;
      assert(target);
      assert(prev_p);
      assert(curr_p);
      prev = NULL;
      curr = target->front;
      while(curr) {
        if(#{eq}) {
          #ifndef NDEBUG
            if(prev)
              assert(prev->next == curr);
            else
              assert(target->front == curr);
          #endif
          *prev_p = prev;
          *curr_p = curr;
          return 1;
        }
        prev = curr;
        curr = curr->next;
      }
      return 0;
    }
  end
  method(:int, :_locate_node, { target: const_rvalue, value: element.const_rvalue, prev_p: _node_pp, curr_p: _node_pp }, visibility: :internal, constraint:-> { element.comparable? }).configure do
    # Locate node satisfying default element equality condition, return this and previous nodes
    code _locate_node_equal(element.equal.('curr->element', value))
  end
  method(:void, :_pop_front, { target: rvalue }, visibility: :internal).configure do
    # Destroy frontal node but keep the element intact
    code %{
      #{_node_p} curr;
      assert(!#{empty.(target)});
      curr = target->front; assert(curr);
      target->front = target->front->next;
      #{'--target->size;' if maintain_size?}
      #{memory.free(:curr)};
    }
  end
  method(_node_p, :_pull_node, { target: rvalue }, visibility: :internal).configure do
    # Cut & return frontal node
    code %{
      #{_node_p} curr;
      assert(!#{empty.(target)});
      curr = target->front; assert(curr);
      target->front = curr->next;
      #{'--target->size;' if maintain_size?}
      return curr;
    }
  end
  method(:void, :_push_node, { target: rvalue, curr: _node_p }, visibility: :internal).configure do
    # Push exising node with intact payload
    code %{
      assert(target);
      curr->next = target->front;
      target->front = curr;
      #{'++target->size;' if maintain_size?}
    }
  end
  method(element.const_lvalue, :view_front, { target: const_rvalue })
  method(element, :take_front, { target: const_rvalue }, constraint:-> { element.copyable? })
  view_front.configure do
    dependencies << empty
    inline_code %{
      assert(!#{empty.(target)});
      return &(target->front->element);
    }
    header %{
      @brief Get a view of the front element

      @param[in] target list to get element from
      @return a view of a front element

      This function is used to get a constant reference (in form of the C pointer) to the front value contained in `target`.
      Refer to @ref #{take_front} to get an independent copy of that element.

      It is generally not safe to bypass the constness and to alter the value in place (although no one prevents to).

      @note List must not be empty (see @ref #{empty}).

      @since 2.0
    }
  end
  take_front.configure do
    code %{
      #{element} result;
      #{element.const_lvalue} e;
      assert(target);
      assert(!#{empty.(target)});
      e = #{view_front.(target)};
      #{element.copy.(:result, '*e')};
      return result;
    }
    header %{
      @brief Get front element

      @param[in] target list to get element from
      @return a *copy* of a front element

      This function is used to get a *copy* of the front value contained in `target`.
      Refer to @ref #{view_front} to get a view of that element without making an independent copy.

      This function requires the element type to be *copyable* (i.e. to have a well-defined copy operation).

      @note List must not be empty (see @ref #{empty}).

      @since 2.0
    }
  end
  method(element, :pull_front, { target: rvalue }).configure do
    code %{
      #{element} result;
      assert(target);
      assert(!#{empty.(target)});
      result = *#{view_front.(target)};
      #{_pop_front.(target)};
      return result;
    }
    header %{
      @brief Extract front element

      @param[in] target list to extract element from
      @return front element

      This function removes front element from the list and returns it.
      Note that contrary to @ref #{take_front} no copy operation is performed - it is the contained value itself that is returned.

      @note List must not be empty (see @ref #{empty}).

      @since 2.0
    }
  end
  method(:void, :drop_front, { target: rvalue }).configure do
    if element.destructible?
      code %{
        #{element.lvalue} e;
        assert(target);
        assert(!#{empty.(target)});
        e = (#{element.lvalue})#{view_front.(target)};
        #{element.destroy.('*e')};
        #{_pop_front.(target)};
      }
    else
      code %{
        assert(target);
        assert(!#{empty.(target)});
        #{_pop_front.(target)};
      }
    end
    header %{
      @brief Drop front element

      @param[in] target list to drop element from

      This function removes front element from the list and destroys it with the respective destructor.

      @note List must not be empty (see @ref #{empty}).

      @since 2.0
    }
  end
  method(:void, :push_front, { target: rvalue, value: element.const_rvalue }, constraint:-> { element.copyable? }).configure do
    code %{
      #{_node_p} curr;
      assert(target);
      curr = #{memory.allocate(_node)};
      curr->next = target->front;
      target->front = curr;
      #{'++target->size;' if maintain_size?}
      #{element.copy.('curr->element', value)};
    }
    header %{
      @brief Put element

      @param[in] target vector to put element into
      @param[in] value value to put

      This function pushes a *copy* of the specified value to the front position of `target`.
      It becomes a new front element.

      This function requires the element type to be *copyable* (i.e. to have a well-defined copy operation).

      @since 2.0
    }
  end
  def _remove_first(locator)
    %{
      #{_node_p} curr;
      #{_node_p} prev;
      assert(target);
      if(#{locator}) {
        assert(curr);
        if(prev) {
          prev->next = curr->next;
        } else {
          target->front = curr->next;
        }
        #{element.destroy.('curr->element') if element.destructible?};
        #{memory.free(:curr)};
        #{'--target->size;' if maintain_size?}
        return 1;
      }
      return 0;
    }
  end
  method(:int, :remove_first, { target: rvalue, value: element.const_rvalue }, constraint:-> { element.comparable? }).configure do
    code _remove_first(_locate_node.(target, value, :prev, :curr))
    header %{
      @brief Remove element

      @param[in] target list to remove element from
      @param[in] value value to search in list
      @return non-zero value on successful removal and zero value otherwise

      This function searches `target` for a first element equal to the specified `value` and removes it from the list.
      The removed element is destroyed with respective destructor.

      The function return value is non-zero if such element was found and removed and zero value otherwise.

      This function requires the element type to be *comparable* (i.e. to have a well-defined equality operation).

      @since 2.0
    }
  end
  default_create.configure do
    inline_code %{
      assert(target);
      target->front = NULL;
      #{'target->size = 0;' if maintain_size?}
    }
  end
  destroy.configure do
    code %{
      assert(target);
      while(!#{empty.(target)}) #{drop_front.(target)};
    }
  end
  copy.configure do
    code %{
      size_t i;
      #{range} r;
      #{element.const_lvalue}* t;
      assert(target);
      assert(source);
      #{default_create.(target)};
      t = #{memory.allocate(element.const_lvalue, size.(source))};
      for(i = 0, r = #{range.new.(source)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) {
        t[i++] = #{range.view_front.(:r)};
      }
      while(i > 0) #{push_front.(target, '*t[(i--)-1]')}; /* put elements in reverse order since the list itself is a LIFO structure */
      #{memory.free(:t)};
    }
  end
  empty.configure do
    inline_code %{
      assert(target);
      return target->front == NULL;
    }
  end
  if maintain_size?
    size.configure do
      inline_code %{
        assert(target);
        return target->size;
      }
    end
  else
    size.configure do
      code %{
        #{range} r;
        size_t size;
        assert(target);
        for(size = 0, r = #{range.new.(target)}; !#{range.empty.(:r)}; ++size, #{range.pop_front.(:r)});
        return size;
      }
    end
  end
end
maintain_size?(= @maintain_size) click to toggle source
# File lib/autoc/list.rb, line 38
  def maintain_size? = @maintain_size

  def render_interface(stream)
    stream << %{
      /** @private */
      typedef struct #{_node} #{_node};
    }
    if public?
      stream << %{
        /**
          #{defgroup}

          @brief Singly linked list of elements of type #{element}

          For iteration over the list elements refer to @ref #{range}.

          @see C++ [std::forward_list<T>](https://en.cppreference.com/w/cpp/container/forward_list)

          @since 2.0
        */
      }
      stream << %{
        /**
          #{ingroup}

          @brief Opaque structure holding state of the list

          @since 2.0
        */
      }
    else
      stream << PRIVATE
    end
    stream << %{
      typedef struct {
        #{_node_p} front; /**< @private */
        #{'size_t size; /**< @private */' if maintain_size?}
      } #{signature};
      /** @private */
      struct #{_node} {
        #{element} element;
        #{_node_p} next;
      };
    }
  end

private

  def configure
    super
    method(:int, :_replace_first, { target: rvalue, value: element.const_rvalue }, visibility: :internal, constraint:-> { element.copyable? }).configure do
      # Replace first found element with specified value in-place
      code %{
        #{element.lvalue} e = (#{element.lvalue})#{find_first.(target, value)};
        if(e) {
          #{element.destroy.('*e') if element.destructible?};
          #{element.copy.('*e', value)};
          return 1;
        } else
          return 0;
      }
    end
    # Code template for locating the list node satisfying custom equality condition
    def _locate_node_equal(eq)
      %{
        #{_node_p} curr;
        #{_node_p} prev;
        assert(target);
        assert(prev_p);
        assert(curr_p);
        prev = NULL;
        curr = target->front;
        while(curr) {
          if(#{eq}) {
            #ifndef NDEBUG
              if(prev)
                assert(prev->next == curr);
              else
                assert(target->front == curr);
            #endif
            *prev_p = prev;
            *curr_p = curr;
            return 1;
          }
          prev = curr;
          curr = curr->next;
        }
        return 0;
      }
    end
    method(:int, :_locate_node, { target: const_rvalue, value: element.const_rvalue, prev_p: _node_pp, curr_p: _node_pp }, visibility: :internal, constraint:-> { element.comparable? }).configure do
      # Locate node satisfying default element equality condition, return this and previous nodes
      code _locate_node_equal(element.equal.('curr->element', value))
    end
    method(:void, :_pop_front, { target: rvalue }, visibility: :internal).configure do
      # Destroy frontal node but keep the element intact
      code %{
        #{_node_p} curr;
        assert(!#{empty.(target)});
        curr = target->front; assert(curr);
        target->front = target->front->next;
        #{'--target->size;' if maintain_size?}
        #{memory.free(:curr)};
      }
    end
    method(_node_p, :_pull_node, { target: rvalue }, visibility: :internal).configure do
      # Cut & return frontal node
      code %{
        #{_node_p} curr;
        assert(!#{empty.(target)});
        curr = target->front; assert(curr);
        target->front = curr->next;
        #{'--target->size;' if maintain_size?}
        return curr;
      }
    end
    method(:void, :_push_node, { target: rvalue, curr: _node_p }, visibility: :internal).configure do
      # Push exising node with intact payload
      code %{
        assert(target);
        curr->next = target->front;
        target->front = curr;
        #{'++target->size;' if maintain_size?}
      }
    end
    method(element.const_lvalue, :view_front, { target: const_rvalue })
    method(element, :take_front, { target: const_rvalue }, constraint:-> { element.copyable? })
    view_front.configure do
      dependencies << empty
      inline_code %{
        assert(!#{empty.(target)});
        return &(target->front->element);
      }
      header %{
        @brief Get a view of the front element

        @param[in] target list to get element from
        @return a view of a front element

        This function is used to get a constant reference (in form of the C pointer) to the front value contained in `target`.
        Refer to @ref #{take_front} to get an independent copy of that element.

        It is generally not safe to bypass the constness and to alter the value in place (although no one prevents to).

        @note List must not be empty (see @ref #{empty}).

        @since 2.0
      }
    end
    take_front.configure do
      code %{
        #{element} result;
        #{element.const_lvalue} e;
        assert(target);
        assert(!#{empty.(target)});
        e = #{view_front.(target)};
        #{element.copy.(:result, '*e')};
        return result;
      }
      header %{
        @brief Get front element

        @param[in] target list to get element from
        @return a *copy* of a front element

        This function is used to get a *copy* of the front value contained in `target`.
        Refer to @ref #{view_front} to get a view of that element without making an independent copy.

        This function requires the element type to be *copyable* (i.e. to have a well-defined copy operation).

        @note List must not be empty (see @ref #{empty}).

        @since 2.0
      }
    end
    method(element, :pull_front, { target: rvalue }).configure do
      code %{
        #{element} result;
        assert(target);
        assert(!#{empty.(target)});
        result = *#{view_front.(target)};
        #{_pop_front.(target)};
        return result;
      }
      header %{
        @brief Extract front element

        @param[in] target list to extract element from
        @return front element

        This function removes front element from the list and returns it.
        Note that contrary to @ref #{take_front} no copy operation is performed - it is the contained value itself that is returned.

        @note List must not be empty (see @ref #{empty}).

        @since 2.0
      }
    end
    method(:void, :drop_front, { target: rvalue }).configure do
      if element.destructible?
        code %{
          #{element.lvalue} e;
          assert(target);
          assert(!#{empty.(target)});
          e = (#{element.lvalue})#{view_front.(target)};
          #{element.destroy.('*e')};
          #{_pop_front.(target)};
        }
      else
        code %{
          assert(target);
          assert(!#{empty.(target)});
          #{_pop_front.(target)};
        }
      end
      header %{
        @brief Drop front element

        @param[in] target list to drop element from

        This function removes front element from the list and destroys it with the respective destructor.

        @note List must not be empty (see @ref #{empty}).

        @since 2.0
      }
    end
    method(:void, :push_front, { target: rvalue, value: element.const_rvalue }, constraint:-> { element.copyable? }).configure do
      code %{
        #{_node_p} curr;
        assert(target);
        curr = #{memory.allocate(_node)};
        curr->next = target->front;
        target->front = curr;
        #{'++target->size;' if maintain_size?}
        #{element.copy.('curr->element', value)};
      }
      header %{
        @brief Put element

        @param[in] target vector to put element into
        @param[in] value value to put

        This function pushes a *copy* of the specified value to the front position of `target`.
        It becomes a new front element.

        This function requires the element type to be *copyable* (i.e. to have a well-defined copy operation).

        @since 2.0
      }
    end
    def _remove_first(locator)
      %{
        #{_node_p} curr;
        #{_node_p} prev;
        assert(target);
        if(#{locator}) {
          assert(curr);
          if(prev) {
            prev->next = curr->next;
          } else {
            target->front = curr->next;
          }
          #{element.destroy.('curr->element') if element.destructible?};
          #{memory.free(:curr)};
          #{'--target->size;' if maintain_size?}
          return 1;
        }
        return 0;
      }
    end
    method(:int, :remove_first, { target: rvalue, value: element.const_rvalue }, constraint:-> { element.comparable? }).configure do
      code _remove_first(_locate_node.(target, value, :prev, :curr))
      header %{
        @brief Remove element

        @param[in] target list to remove element from
        @param[in] value value to search in list
        @return non-zero value on successful removal and zero value otherwise

        This function searches `target` for a first element equal to the specified `value` and removes it from the list.
        The removed element is destroyed with respective destructor.

        The function return value is non-zero if such element was found and removed and zero value otherwise.

        This function requires the element type to be *comparable* (i.e. to have a well-defined equality operation).

        @since 2.0
      }
    end
    default_create.configure do
      inline_code %{
        assert(target);
        target->front = NULL;
        #{'target->size = 0;' if maintain_size?}
      }
    end
    destroy.configure do
      code %{
        assert(target);
        while(!#{empty.(target)}) #{drop_front.(target)};
      }
    end
    copy.configure do
      code %{
        size_t i;
        #{range} r;
        #{element.const_lvalue}* t;
        assert(target);
        assert(source);
        #{default_create.(target)};
        t = #{memory.allocate(element.const_lvalue, size.(source))};
        for(i = 0, r = #{range.new.(source)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) {
          t[i++] = #{range.view_front.(:r)};
        }
        while(i > 0) #{push_front.(target, '*t[(i--)-1]')}; /* put elements in reverse order since the list itself is a LIFO structure */
        #{memory.free(:t)};
      }
    end
    empty.configure do
      inline_code %{
        assert(target);
        return target->front == NULL;
      }
    end
    if maintain_size?
      size.configure do
        inline_code %{
          assert(target);
          return target->size;
        }
      end
    else
      size.configure do
        code %{
          #{range} r;
          size_t size;
          assert(target);
          for(size = 0, r = #{range.new.(target)}; !#{range.empty.(:r)}; ++size, #{range.pop_front.(:r)});
          return size;
        }
      end
    end
  end
end
range(= @range ||= _range_class.new(self, visibility: visibility)) click to toggle source
# File lib/autoc/list.rb, line 23
    def range = @range ||= _range_class.new(self, visibility: visibility)

    attr_reader :_node, :_node_p, :_node_pp

    # maintain_size:
    #  true: managed size field (extra memory consumption)
    #  false: computing #size function (slow, O(N))
    def initialize(*args, maintain_size: true, **kws)
      super(*args, **kws)
      @_node = identifier(:_node, abbreviate: true)
      @_node_p = _node.lvalue
      @_node_pp = "#{_node}*".lvalue
      @maintain_size = maintain_size
    end

    def maintain_size? = @maintain_size

    def render_interface(stream)
      stream << %{
        /** @private */
        typedef struct #{_node} #{_node};
      }
      if public?
        stream << %{
          /**
            #{defgroup}
  
            @brief Singly linked list of elements of type #{element}
  
            For iteration over the list elements refer to @ref #{range}.
  
            @see C++ [std::forward_list<T>](https://en.cppreference.com/w/cpp/container/forward_list)
  
            @since 2.0
          */
        }
        stream << %{
          /**
            #{ingroup}

            @brief Opaque structure holding state of the list

            @since 2.0
          */
        }
      else
        stream << PRIVATE
      end
      stream << %{
        typedef struct {
          #{_node_p} front; /**< @private */
          #{'size_t size; /**< @private */' if maintain_size?}
        } #{signature};
        /** @private */
        struct #{_node} {
          #{element} element;
          #{_node_p} next;
        };
      }
    end

  private

    def configure
      super
      method(:int, :_replace_first, { target: rvalue, value: element.const_rvalue }, visibility: :internal, constraint:-> { element.copyable? }).configure do
        # Replace first found element with specified value in-place
        code %{
          #{element.lvalue} e = (#{element.lvalue})#{find_first.(target, value)};
          if(e) {
            #{element.destroy.('*e') if element.destructible?};
            #{element.copy.('*e', value)};
            return 1;
          } else
            return 0;
        }
      end
      # Code template for locating the list node satisfying custom equality condition
      def _locate_node_equal(eq)
        %{
          #{_node_p} curr;
          #{_node_p} prev;
          assert(target);
          assert(prev_p);
          assert(curr_p);
          prev = NULL;
          curr = target->front;
          while(curr) {
            if(#{eq}) {
              #ifndef NDEBUG
                if(prev)
                  assert(prev->next == curr);
                else
                  assert(target->front == curr);
              #endif
              *prev_p = prev;
              *curr_p = curr;
              return 1;
            }
            prev = curr;
            curr = curr->next;
          }
          return 0;
        }
      end
      method(:int, :_locate_node, { target: const_rvalue, value: element.const_rvalue, prev_p: _node_pp, curr_p: _node_pp }, visibility: :internal, constraint:-> { element.comparable? }).configure do
        # Locate node satisfying default element equality condition, return this and previous nodes
        code _locate_node_equal(element.equal.('curr->element', value))
      end
      method(:void, :_pop_front, { target: rvalue }, visibility: :internal).configure do
        # Destroy frontal node but keep the element intact
        code %{
          #{_node_p} curr;
          assert(!#{empty.(target)});
          curr = target->front; assert(curr);
          target->front = target->front->next;
          #{'--target->size;' if maintain_size?}
          #{memory.free(:curr)};
        }
      end
      method(_node_p, :_pull_node, { target: rvalue }, visibility: :internal).configure do
        # Cut & return frontal node
        code %{
          #{_node_p} curr;
          assert(!#{empty.(target)});
          curr = target->front; assert(curr);
          target->front = curr->next;
          #{'--target->size;' if maintain_size?}
          return curr;
        }
      end
      method(:void, :_push_node, { target: rvalue, curr: _node_p }, visibility: :internal).configure do
        # Push exising node with intact payload
        code %{
          assert(target);
          curr->next = target->front;
          target->front = curr;
          #{'++target->size;' if maintain_size?}
        }
      end
      method(element.const_lvalue, :view_front, { target: const_rvalue })
      method(element, :take_front, { target: const_rvalue }, constraint:-> { element.copyable? })
      view_front.configure do
        dependencies << empty
        inline_code %{
          assert(!#{empty.(target)});
          return &(target->front->element);
        }
        header %{
          @brief Get a view of the front element

          @param[in] target list to get element from
          @return a view of a front element

          This function is used to get a constant reference (in form of the C pointer) to the front value contained in `target`.
          Refer to @ref #{take_front} to get an independent copy of that element.

          It is generally not safe to bypass the constness and to alter the value in place (although no one prevents to).

          @note List must not be empty (see @ref #{empty}).

          @since 2.0
        }
      end
      take_front.configure do
        code %{
          #{element} result;
          #{element.const_lvalue} e;
          assert(target);
          assert(!#{empty.(target)});
          e = #{view_front.(target)};
          #{element.copy.(:result, '*e')};
          return result;
        }
        header %{
          @brief Get front element

          @param[in] target list to get element from
          @return a *copy* of a front element

          This function is used to get a *copy* of the front value contained in `target`.
          Refer to @ref #{view_front} to get a view of that element without making an independent copy.

          This function requires the element type to be *copyable* (i.e. to have a well-defined copy operation).

          @note List must not be empty (see @ref #{empty}).

          @since 2.0
        }
      end
      method(element, :pull_front, { target: rvalue }).configure do
        code %{
          #{element} result;
          assert(target);
          assert(!#{empty.(target)});
          result = *#{view_front.(target)};
          #{_pop_front.(target)};
          return result;
        }
        header %{
          @brief Extract front element

          @param[in] target list to extract element from
          @return front element

          This function removes front element from the list and returns it.
          Note that contrary to @ref #{take_front} no copy operation is performed - it is the contained value itself that is returned.

          @note List must not be empty (see @ref #{empty}).

          @since 2.0
        }
      end
      method(:void, :drop_front, { target: rvalue }).configure do
        if element.destructible?
          code %{
            #{element.lvalue} e;
            assert(target);
            assert(!#{empty.(target)});
            e = (#{element.lvalue})#{view_front.(target)};
            #{element.destroy.('*e')};
            #{_pop_front.(target)};
          }
        else
          code %{
            assert(target);
            assert(!#{empty.(target)});
            #{_pop_front.(target)};
          }
        end
        header %{
          @brief Drop front element

          @param[in] target list to drop element from

          This function removes front element from the list and destroys it with the respective destructor.

          @note List must not be empty (see @ref #{empty}).

          @since 2.0
        }
      end
      method(:void, :push_front, { target: rvalue, value: element.const_rvalue }, constraint:-> { element.copyable? }).configure do
        code %{
          #{_node_p} curr;
          assert(target);
          curr = #{memory.allocate(_node)};
          curr->next = target->front;
          target->front = curr;
          #{'++target->size;' if maintain_size?}
          #{element.copy.('curr->element', value)};
        }
        header %{
          @brief Put element

          @param[in] target vector to put element into
          @param[in] value value to put

          This function pushes a *copy* of the specified value to the front position of `target`.
          It becomes a new front element.

          This function requires the element type to be *copyable* (i.e. to have a well-defined copy operation).

          @since 2.0
        }
      end
      def _remove_first(locator)
        %{
          #{_node_p} curr;
          #{_node_p} prev;
          assert(target);
          if(#{locator}) {
            assert(curr);
            if(prev) {
              prev->next = curr->next;
            } else {
              target->front = curr->next;
            }
            #{element.destroy.('curr->element') if element.destructible?};
            #{memory.free(:curr)};
            #{'--target->size;' if maintain_size?}
            return 1;
          }
          return 0;
        }
      end
      method(:int, :remove_first, { target: rvalue, value: element.const_rvalue }, constraint:-> { element.comparable? }).configure do
        code _remove_first(_locate_node.(target, value, :prev, :curr))
        header %{
          @brief Remove element

          @param[in] target list to remove element from
          @param[in] value value to search in list
          @return non-zero value on successful removal and zero value otherwise

          This function searches `target` for a first element equal to the specified `value` and removes it from the list.
          The removed element is destroyed with respective destructor.

          The function return value is non-zero if such element was found and removed and zero value otherwise.

          This function requires the element type to be *comparable* (i.e. to have a well-defined equality operation).

          @since 2.0
        }
      end
      default_create.configure do
        inline_code %{
          assert(target);
          target->front = NULL;
          #{'target->size = 0;' if maintain_size?}
        }
      end
      destroy.configure do
        code %{
          assert(target);
          while(!#{empty.(target)}) #{drop_front.(target)};
        }
      end
      copy.configure do
        code %{
          size_t i;
          #{range} r;
          #{element.const_lvalue}* t;
          assert(target);
          assert(source);
          #{default_create.(target)};
          t = #{memory.allocate(element.const_lvalue, size.(source))};
          for(i = 0, r = #{range.new.(source)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) {
            t[i++] = #{range.view_front.(:r)};
          }
          while(i > 0) #{push_front.(target, '*t[(i--)-1]')}; /* put elements in reverse order since the list itself is a LIFO structure */
          #{memory.free(:t)};
        }
      end
      empty.configure do
        inline_code %{
          assert(target);
          return target->front == NULL;
        }
      end
      if maintain_size?
        size.configure do
          inline_code %{
            assert(target);
            return target->size;
          }
        end
      else
        size.configure do
          code %{
            #{range} r;
            size_t size;
            assert(target);
            for(size = 0, r = #{range.new.(target)}; !#{range.empty.(:r)}; ++size, #{range.pop_front.(:r)});
            return size;
          }
        end
      end
    end
  end # List


  class List::Range < ForwardRange

    def render_interface(stream)
      if public?
        render_type_description(stream)
        stream << %{
          /**
            #{ingroup}
            @brief Opaque structure holding state of the list's range
            @since 2.0
          */
        }
      else
        stream << PRIVATE
      end
      stream << %{
        typedef struct {
          #{iterable._node_p} front; /**< @private */
        } #{signature};
      }
    end

  private

    def configure
      super
      custom_create.configure do
        inline_code %{
          assert(range);
          assert(iterable);
          range->front = iterable->front;
        }
      end
      empty.configure do
        inline_code %{
          assert(range);
          return range->front == NULL;
        }
      end
      pop_front.configure do
        dependencies << empty
        inline_code %{
          assert(range);
          assert(!#{empty.(range)});
          range->front = range->front->next;
        }
      end
      view_front.configure do
        dependencies << empty
        inline_code %{
          assert(range);
          assert(!#{empty.(range)});
          return &range->front->element;
        }
      end
    end

  end # List


end
render_interface(stream) click to toggle source
# File lib/autoc/list.rb, line 40
def render_interface(stream)
  stream << %{
    /** @private */
    typedef struct #{_node} #{_node};
  }
  if public?
    stream << %{
      /**
        #{defgroup}
  
        @brief Singly linked list of elements of type #{element}
  
        For iteration over the list elements refer to @ref #{range}.
  
        @see C++ [std::forward_list<T>](https://en.cppreference.com/w/cpp/container/forward_list)
  
        @since 2.0
      */
    }
    stream << %{
      /**
        #{ingroup}

        @brief Opaque structure holding state of the list

        @since 2.0
      */
    }
  else
    stream << PRIVATE
  end
  stream << %{
    typedef struct {
      #{_node_p} front; /**< @private */
      #{'size_t size; /**< @private */' if maintain_size?}
    } #{signature};
    /** @private */
    struct #{_node} {
      #{element} element;
      #{_node_p} next;
    };
  }
end