class AutoC::HashSet
Public Class Methods
new(*args, **kws)
click to toggle source
Calls superclass method
# File lib/autoc/hash_set.rb, line 28 def initialize(*args, **kws) super dependencies << _bin end
Public Instance Methods
_bin(= @_bin ||= _bin_class.new(identifier(:_vector, abbreviate: true), _slot, _master: self, visibility: :internal))
click to toggle source
# File lib/autoc/hash_set.rb, line 26 def _bin = @_bin ||= _bin_class.new(identifier(:_vector, abbreviate: true), _slot, _master: self, visibility: :internal) def initialize(*args, **kws) super dependencies << _bin end def render_interface(stream) if public? stream << %{ /** #{defgroup} @brief Unordered collection of unique elements of type #{element} For iteration over the set elements refer to @ref #{range}. @see C++ [std::unordered_set<T>](https://en.cppreference.com/w/cpp/container/unordered_set) @since 2.0 */ /** #{ingroup} @brief Opaque structure holding state of the hash set @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ size_t size; /**< @private */ size_t hash_mask; /**< @private */ } #{signature}; } end private def configure super method(:void, :create_capacity, { target: lvalue, capacity: :size_t.rvalue }).configure do code %{ unsigned char bits = 0; assert(target); target->size = 0; /* fix capacity to become the ceiling to the nearest power of two */ if(capacity % 2 == 0) --capacity; while(capacity >>= 1) ++bits; capacity = (size_t)1 << (bits+1); assert(capacity > 0); target->hash_mask = capacity-1; /* fast slot location for value: hash_code(value) & hash_mask */ #{_bin.custom_create.('target->bin', capacity)}; assert(#{_bin.size.('target->bin')} % 2 == 0); } header %{ @brief Create set with specified capacity @param[out] target set to create @param[in] capacity initial capacity of the set This function creates a new set which should be suffice to contain specific number of elements. While the input capacity may be arbitrary the resulting one will be rounded up to the nearest power of two. This function may be useful when the (approximate) number of elements this set is about to contain is known in advance in order to avoid expensive storage reallocation & elements rehashing operations during the set's lifetime. @since 2.0 } end def _find_slot_hash(hash) %{ assert(target); return #{_bin.view.('target->bin', "#{hash} & target->hash_mask")}; } end method(_slot.const_lvalue, :_find_slot, { target: const_rvalue, value: element.const_rvalue }, visibility: :internal).configure do # Find slot based on the value hash code dependencies << _bin.view inline_code _find_slot_hash(element.hash_code.(value)) end method(:void, :_expand, { target: lvalue, force: :int.const_rvalue }, visibility: :internal).configure do code %{ #{type} set; #{_bin.range} r; assert(target); /* capacity threshold == 1.0 */ if(force || target->size >= #{_bin.size.('target->bin')}) { #{create_capacity.(:set, _bin.size.('target->bin') + '*2')}; /* move elements to newly allocated set */ for(r = #{_bin.range.new.('target->bin')}; !#{_bin.range.empty.(:r)}; #{_bin.range.pop_front.(:r)}) { #{_slot.lvalue} src = (#{_slot.lvalue})#{_bin.range.view_front.(:r)}; while(!#{_slot.empty.('*src')}) { /* direct node relocation from original to new list bypassing node reallocation & payload copying */ #{_slot._node_p} node = #{_slot._pull_node.('*src')}; #{_slot.lvalue} dst = (#{_slot.lvalue})#{_find_slot.(target, 'node->element')}; #{_slot._push_node.('*dst', '*node')}; } } set.size = target->size; /* assume all elements have been moved into new set */ #{destroy.(target)}; *target = set; } } end subset.configure do code %{ #{range} r; assert(target); assert(other); if(#{size.(target)} > #{size.(other)}) return 0; /* larger set can't be a subset of a smaller one */ for(r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; if(!#{contains.(other, '*e')}) return 0; } return 1; } end remove.configure do code %{ int c; #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; c = #{_slot.remove_first.('*s', value)}; if(c) --target->size; return c; } end put.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(!#{_slot.find_first.('*s', value)}) { #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 1; } else return 0; } end push.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(#{_slot._replace_first.('*s', value)}) { return 1; } else { /* add brand new value */ #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 0; } } end default_create.configure do dependencies << create_capacity inline_code %{ #{create_capacity.(target, 8)}; } end find_first.configure do code %{ #{_slot.const_lvalue} s = #{_find_slot.(target, value)}; return #{_slot.find_first.('*s', value)}; } end copy.configure do code %{ assert(target); assert(source); #{_bin.copy.('target->bin', 'source->bin')}; target->hash_mask = source->hash_mask; target->size = source->size; } end empty.configure do inline_code %{ assert(target); return target->size == 0; } end size.configure do inline_code %{ assert(target); return target->size; } end contains.configure do code %{ #{_slot.const_lvalue} s; assert(target); s = #{_find_slot.(target, value)}; return #{_slot.contains.('*s', value)}; } end destroy.configure do code %{ assert(target); #{_bin.destroy.('target->bin')}; } end hash_code.configure do code %{ #{range} r; size_t hash; for(hash = AUTOC_HASHER_SEED, r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; hash ^= #{element.hash_code.('*e')}; /* default incremental hasher is applicable to ordered collections only */ } return hash; } end end end
_bin_class(= Vector)
click to toggle source
# File lib/autoc/hash_set.rb, line 20 def _bin_class = Vector def range = @range ||= Range.new(self, visibility: visibility) def _slot = @_slot ||= _slot_class.new(identifier(:_list, abbreviate: true), element, _master: self, maintain_size: false, visibility: :internal) def _bin = @_bin ||= _bin_class.new(identifier(:_vector, abbreviate: true), _slot, _master: self, visibility: :internal) def initialize(*args, **kws) super dependencies << _bin end def render_interface(stream) if public? stream << %{ /** #{defgroup} @brief Unordered collection of unique elements of type #{element} For iteration over the set elements refer to @ref #{range}. @see C++ [std::unordered_set<T>](https://en.cppreference.com/w/cpp/container/unordered_set) @since 2.0 */ /** #{ingroup} @brief Opaque structure holding state of the hash set @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ size_t size; /**< @private */ size_t hash_mask; /**< @private */ } #{signature}; } end private def configure super method(:void, :create_capacity, { target: lvalue, capacity: :size_t.rvalue }).configure do code %{ unsigned char bits = 0; assert(target); target->size = 0; /* fix capacity to become the ceiling to the nearest power of two */ if(capacity % 2 == 0) --capacity; while(capacity >>= 1) ++bits; capacity = (size_t)1 << (bits+1); assert(capacity > 0); target->hash_mask = capacity-1; /* fast slot location for value: hash_code(value) & hash_mask */ #{_bin.custom_create.('target->bin', capacity)}; assert(#{_bin.size.('target->bin')} % 2 == 0); } header %{ @brief Create set with specified capacity @param[out] target set to create @param[in] capacity initial capacity of the set This function creates a new set which should be suffice to contain specific number of elements. While the input capacity may be arbitrary the resulting one will be rounded up to the nearest power of two. This function may be useful when the (approximate) number of elements this set is about to contain is known in advance in order to avoid expensive storage reallocation & elements rehashing operations during the set's lifetime. @since 2.0 } end def _find_slot_hash(hash) %{ assert(target); return #{_bin.view.('target->bin', "#{hash} & target->hash_mask")}; } end method(_slot.const_lvalue, :_find_slot, { target: const_rvalue, value: element.const_rvalue }, visibility: :internal).configure do # Find slot based on the value hash code dependencies << _bin.view inline_code _find_slot_hash(element.hash_code.(value)) end method(:void, :_expand, { target: lvalue, force: :int.const_rvalue }, visibility: :internal).configure do code %{ #{type} set; #{_bin.range} r; assert(target); /* capacity threshold == 1.0 */ if(force || target->size >= #{_bin.size.('target->bin')}) { #{create_capacity.(:set, _bin.size.('target->bin') + '*2')}; /* move elements to newly allocated set */ for(r = #{_bin.range.new.('target->bin')}; !#{_bin.range.empty.(:r)}; #{_bin.range.pop_front.(:r)}) { #{_slot.lvalue} src = (#{_slot.lvalue})#{_bin.range.view_front.(:r)}; while(!#{_slot.empty.('*src')}) { /* direct node relocation from original to new list bypassing node reallocation & payload copying */ #{_slot._node_p} node = #{_slot._pull_node.('*src')}; #{_slot.lvalue} dst = (#{_slot.lvalue})#{_find_slot.(target, 'node->element')}; #{_slot._push_node.('*dst', '*node')}; } } set.size = target->size; /* assume all elements have been moved into new set */ #{destroy.(target)}; *target = set; } } end subset.configure do code %{ #{range} r; assert(target); assert(other); if(#{size.(target)} > #{size.(other)}) return 0; /* larger set can't be a subset of a smaller one */ for(r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; if(!#{contains.(other, '*e')}) return 0; } return 1; } end remove.configure do code %{ int c; #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; c = #{_slot.remove_first.('*s', value)}; if(c) --target->size; return c; } end put.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(!#{_slot.find_first.('*s', value)}) { #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 1; } else return 0; } end push.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(#{_slot._replace_first.('*s', value)}) { return 1; } else { /* add brand new value */ #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 0; } } end default_create.configure do dependencies << create_capacity inline_code %{ #{create_capacity.(target, 8)}; } end find_first.configure do code %{ #{_slot.const_lvalue} s = #{_find_slot.(target, value)}; return #{_slot.find_first.('*s', value)}; } end copy.configure do code %{ assert(target); assert(source); #{_bin.copy.('target->bin', 'source->bin')}; target->hash_mask = source->hash_mask; target->size = source->size; } end empty.configure do inline_code %{ assert(target); return target->size == 0; } end size.configure do inline_code %{ assert(target); return target->size; } end contains.configure do code %{ #{_slot.const_lvalue} s; assert(target); s = #{_find_slot.(target, value)}; return #{_slot.contains.('*s', value)}; } end destroy.configure do code %{ assert(target); #{_bin.destroy.('target->bin')}; } end hash_code.configure do code %{ #{range} r; size_t hash; for(hash = AUTOC_HASHER_SEED, r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; hash ^= #{element.hash_code.('*e')}; /* default incremental hasher is applicable to ordered collections only */ } return hash; } end end end # HashSet class HashSet::Range < ForwardRange def render_interface(stream) if public? render_type_description(stream) stream << %{ /** #{ingroup} @brief Opaque structure holding state of the hash set's range @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ #{_slot} slot; /**< @private */ } #{signature}; } end def _slot = iterable._slot.range def _bin = iterable._bin.range private def configure super method(:void, :_advance, { range: rvalue }, visibility: :internal ).configure do code %{ assert(range); while(1) { if(#{_slot.empty.('range->slot')}) { /* current slot's range is empty - iterate forward to the next one */ #{_bin.pop_front.('range->bin')}; if(#{_bin.empty.('range->bin')}) { /* all bin are iterated through, slot range is also empty - end of set */ break; } else { /* advance to the new (possibly empty) slot */ #{iterable._slot.const_lvalue} b = #{_bin.view_front.('range->bin')}; range->slot = #{_slot.new.('*b')}; } } else { /* current slot's range is not empty - no need to proceed */ break; } } } end custom_create.configure do code %{ #{_iterable._slot.const_lvalue} s; assert(range); assert(iterable); range->bin = #{_bin.new.('iterable->bin')}; /* get the first slot's range regardless of its emptiness status */ s = #{_bin.view_front.('range->bin')}; range->slot = #{_slot.new.('*s')}; /* actually advance to the first non-empty slot */ #{_advance.(range)}; } end empty.configure do code %{ assert(range); return #{_slot.empty.('range->slot')}; } end pop_front.configure do code %{ assert(range); #{_slot.pop_front.('range->slot')}; #{_advance.(range)}; } end view_front.configure do code %{ assert(range); assert(!#{empty.(range)}); return #{_slot.view_front.('range->slot')}; } end end
_find_slot_hash(hash)
click to toggle source
# File lib/autoc/hash_set.rb, line 98 def _find_slot_hash(hash) %{ assert(target); return #{_bin.view.('target->bin', "#{hash} & target->hash_mask")}; } end
_slot(= @_slot ||= _slot_class.new(identifier(:_list, abbreviate: true), element, _master: self, maintain_size: false, visibility: :internal))
click to toggle source
# File lib/autoc/hash_set.rb, line 24 def _slot = @_slot ||= _slot_class.new(identifier(:_list, abbreviate: true), element, _master: self, maintain_size: false, visibility: :internal) def _bin = @_bin ||= _bin_class.new(identifier(:_vector, abbreviate: true), _slot, _master: self, visibility: :internal) def initialize(*args, **kws) super dependencies << _bin end def render_interface(stream) if public? stream << %{ /** #{defgroup} @brief Unordered collection of unique elements of type #{element} For iteration over the set elements refer to @ref #{range}. @see C++ [std::unordered_set<T>](https://en.cppreference.com/w/cpp/container/unordered_set) @since 2.0 */ /** #{ingroup} @brief Opaque structure holding state of the hash set @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ size_t size; /**< @private */ size_t hash_mask; /**< @private */ } #{signature}; } end private def configure super method(:void, :create_capacity, { target: lvalue, capacity: :size_t.rvalue }).configure do code %{ unsigned char bits = 0; assert(target); target->size = 0; /* fix capacity to become the ceiling to the nearest power of two */ if(capacity % 2 == 0) --capacity; while(capacity >>= 1) ++bits; capacity = (size_t)1 << (bits+1); assert(capacity > 0); target->hash_mask = capacity-1; /* fast slot location for value: hash_code(value) & hash_mask */ #{_bin.custom_create.('target->bin', capacity)}; assert(#{_bin.size.('target->bin')} % 2 == 0); } header %{ @brief Create set with specified capacity @param[out] target set to create @param[in] capacity initial capacity of the set This function creates a new set which should be suffice to contain specific number of elements. While the input capacity may be arbitrary the resulting one will be rounded up to the nearest power of two. This function may be useful when the (approximate) number of elements this set is about to contain is known in advance in order to avoid expensive storage reallocation & elements rehashing operations during the set's lifetime. @since 2.0 } end def _find_slot_hash(hash) %{ assert(target); return #{_bin.view.('target->bin', "#{hash} & target->hash_mask")}; } end method(_slot.const_lvalue, :_find_slot, { target: const_rvalue, value: element.const_rvalue }, visibility: :internal).configure do # Find slot based on the value hash code dependencies << _bin.view inline_code _find_slot_hash(element.hash_code.(value)) end method(:void, :_expand, { target: lvalue, force: :int.const_rvalue }, visibility: :internal).configure do code %{ #{type} set; #{_bin.range} r; assert(target); /* capacity threshold == 1.0 */ if(force || target->size >= #{_bin.size.('target->bin')}) { #{create_capacity.(:set, _bin.size.('target->bin') + '*2')}; /* move elements to newly allocated set */ for(r = #{_bin.range.new.('target->bin')}; !#{_bin.range.empty.(:r)}; #{_bin.range.pop_front.(:r)}) { #{_slot.lvalue} src = (#{_slot.lvalue})#{_bin.range.view_front.(:r)}; while(!#{_slot.empty.('*src')}) { /* direct node relocation from original to new list bypassing node reallocation & payload copying */ #{_slot._node_p} node = #{_slot._pull_node.('*src')}; #{_slot.lvalue} dst = (#{_slot.lvalue})#{_find_slot.(target, 'node->element')}; #{_slot._push_node.('*dst', '*node')}; } } set.size = target->size; /* assume all elements have been moved into new set */ #{destroy.(target)}; *target = set; } } end subset.configure do code %{ #{range} r; assert(target); assert(other); if(#{size.(target)} > #{size.(other)}) return 0; /* larger set can't be a subset of a smaller one */ for(r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; if(!#{contains.(other, '*e')}) return 0; } return 1; } end remove.configure do code %{ int c; #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; c = #{_slot.remove_first.('*s', value)}; if(c) --target->size; return c; } end put.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(!#{_slot.find_first.('*s', value)}) { #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 1; } else return 0; } end push.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(#{_slot._replace_first.('*s', value)}) { return 1; } else { /* add brand new value */ #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 0; } } end default_create.configure do dependencies << create_capacity inline_code %{ #{create_capacity.(target, 8)}; } end find_first.configure do code %{ #{_slot.const_lvalue} s = #{_find_slot.(target, value)}; return #{_slot.find_first.('*s', value)}; } end copy.configure do code %{ assert(target); assert(source); #{_bin.copy.('target->bin', 'source->bin')}; target->hash_mask = source->hash_mask; target->size = source->size; } end empty.configure do inline_code %{ assert(target); return target->size == 0; } end size.configure do inline_code %{ assert(target); return target->size; } end contains.configure do code %{ #{_slot.const_lvalue} s; assert(target); s = #{_find_slot.(target, value)}; return #{_slot.contains.('*s', value)}; } end destroy.configure do code %{ assert(target); #{_bin.destroy.('target->bin')}; } end hash_code.configure do code %{ #{range} r; size_t hash; for(hash = AUTOC_HASHER_SEED, r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; hash ^= #{element.hash_code.('*e')}; /* default incremental hasher is applicable to ordered collections only */ } return hash; } end end end # HashSet class HashSet::Range < ForwardRange def render_interface(stream) if public? render_type_description(stream) stream << %{ /** #{ingroup} @brief Opaque structure holding state of the hash set's range @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ #{_slot} slot; /**< @private */ } #{signature}; } end def _slot = iterable._slot.range def _bin = iterable._bin.range private def configure super method(:void, :_advance, { range: rvalue }, visibility: :internal ).configure do code %{ assert(range); while(1) { if(#{_slot.empty.('range->slot')}) { /* current slot's range is empty - iterate forward to the next one */ #{_bin.pop_front.('range->bin')}; if(#{_bin.empty.('range->bin')}) { /* all bin are iterated through, slot range is also empty - end of set */ break; } else { /* advance to the new (possibly empty) slot */ #{iterable._slot.const_lvalue} b = #{_bin.view_front.('range->bin')}; range->slot = #{_slot.new.('*b')}; } } else { /* current slot's range is not empty - no need to proceed */ break; } } } end custom_create.configure do code %{ #{_iterable._slot.const_lvalue} s; assert(range); assert(iterable); range->bin = #{_bin.new.('iterable->bin')}; /* get the first slot's range regardless of its emptiness status */ s = #{_bin.view_front.('range->bin')}; range->slot = #{_slot.new.('*s')}; /* actually advance to the first non-empty slot */ #{_advance.(range)}; } end empty.configure do code %{ assert(range); return #{_slot.empty.('range->slot')}; } end pop_front.configure do code %{ assert(range); #{_slot.pop_front.('range->slot')}; #{_advance.(range)}; } end view_front.configure do code %{ assert(range); assert(!#{empty.(range)}); return #{_slot.view_front.('range->slot')}; } end end end
_slot_class(= List)
click to toggle source
# File lib/autoc/hash_set.rb, line 18 def _slot_class = List def _bin_class = Vector def range = @range ||= Range.new(self, visibility: visibility) def _slot = @_slot ||= _slot_class.new(identifier(:_list, abbreviate: true), element, _master: self, maintain_size: false, visibility: :internal) def _bin = @_bin ||= _bin_class.new(identifier(:_vector, abbreviate: true), _slot, _master: self, visibility: :internal) def initialize(*args, **kws) super dependencies << _bin end def render_interface(stream) if public? stream << %{ /** #{defgroup} @brief Unordered collection of unique elements of type #{element} For iteration over the set elements refer to @ref #{range}. @see C++ [std::unordered_set<T>](https://en.cppreference.com/w/cpp/container/unordered_set) @since 2.0 */ /** #{ingroup} @brief Opaque structure holding state of the hash set @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ size_t size; /**< @private */ size_t hash_mask; /**< @private */ } #{signature}; } end private def configure super method(:void, :create_capacity, { target: lvalue, capacity: :size_t.rvalue }).configure do code %{ unsigned char bits = 0; assert(target); target->size = 0; /* fix capacity to become the ceiling to the nearest power of two */ if(capacity % 2 == 0) --capacity; while(capacity >>= 1) ++bits; capacity = (size_t)1 << (bits+1); assert(capacity > 0); target->hash_mask = capacity-1; /* fast slot location for value: hash_code(value) & hash_mask */ #{_bin.custom_create.('target->bin', capacity)}; assert(#{_bin.size.('target->bin')} % 2 == 0); } header %{ @brief Create set with specified capacity @param[out] target set to create @param[in] capacity initial capacity of the set This function creates a new set which should be suffice to contain specific number of elements. While the input capacity may be arbitrary the resulting one will be rounded up to the nearest power of two. This function may be useful when the (approximate) number of elements this set is about to contain is known in advance in order to avoid expensive storage reallocation & elements rehashing operations during the set's lifetime. @since 2.0 } end def _find_slot_hash(hash) %{ assert(target); return #{_bin.view.('target->bin', "#{hash} & target->hash_mask")}; } end method(_slot.const_lvalue, :_find_slot, { target: const_rvalue, value: element.const_rvalue }, visibility: :internal).configure do # Find slot based on the value hash code dependencies << _bin.view inline_code _find_slot_hash(element.hash_code.(value)) end method(:void, :_expand, { target: lvalue, force: :int.const_rvalue }, visibility: :internal).configure do code %{ #{type} set; #{_bin.range} r; assert(target); /* capacity threshold == 1.0 */ if(force || target->size >= #{_bin.size.('target->bin')}) { #{create_capacity.(:set, _bin.size.('target->bin') + '*2')}; /* move elements to newly allocated set */ for(r = #{_bin.range.new.('target->bin')}; !#{_bin.range.empty.(:r)}; #{_bin.range.pop_front.(:r)}) { #{_slot.lvalue} src = (#{_slot.lvalue})#{_bin.range.view_front.(:r)}; while(!#{_slot.empty.('*src')}) { /* direct node relocation from original to new list bypassing node reallocation & payload copying */ #{_slot._node_p} node = #{_slot._pull_node.('*src')}; #{_slot.lvalue} dst = (#{_slot.lvalue})#{_find_slot.(target, 'node->element')}; #{_slot._push_node.('*dst', '*node')}; } } set.size = target->size; /* assume all elements have been moved into new set */ #{destroy.(target)}; *target = set; } } end subset.configure do code %{ #{range} r; assert(target); assert(other); if(#{size.(target)} > #{size.(other)}) return 0; /* larger set can't be a subset of a smaller one */ for(r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; if(!#{contains.(other, '*e')}) return 0; } return 1; } end remove.configure do code %{ int c; #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; c = #{_slot.remove_first.('*s', value)}; if(c) --target->size; return c; } end put.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(!#{_slot.find_first.('*s', value)}) { #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 1; } else return 0; } end push.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(#{_slot._replace_first.('*s', value)}) { return 1; } else { /* add brand new value */ #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 0; } } end default_create.configure do dependencies << create_capacity inline_code %{ #{create_capacity.(target, 8)}; } end find_first.configure do code %{ #{_slot.const_lvalue} s = #{_find_slot.(target, value)}; return #{_slot.find_first.('*s', value)}; } end copy.configure do code %{ assert(target); assert(source); #{_bin.copy.('target->bin', 'source->bin')}; target->hash_mask = source->hash_mask; target->size = source->size; } end empty.configure do inline_code %{ assert(target); return target->size == 0; } end size.configure do inline_code %{ assert(target); return target->size; } end contains.configure do code %{ #{_slot.const_lvalue} s; assert(target); s = #{_find_slot.(target, value)}; return #{_slot.contains.('*s', value)}; } end destroy.configure do code %{ assert(target); #{_bin.destroy.('target->bin')}; } end hash_code.configure do code %{ #{range} r; size_t hash; for(hash = AUTOC_HASHER_SEED, r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; hash ^= #{element.hash_code.('*e')}; /* default incremental hasher is applicable to ordered collections only */ } return hash; } end end end # HashSet class HashSet::Range < ForwardRange def render_interface(stream) if public? render_type_description(stream) stream << %{ /** #{ingroup} @brief Opaque structure holding state of the hash set's range @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ #{_slot} slot; /**< @private */ } #{signature}; } end def _slot = iterable._slot.range def _bin = iterable._bin.range private def configure super method(:void, :_advance, { range: rvalue }, visibility: :internal ).configure do code %{ assert(range); while(1) { if(#{_slot.empty.('range->slot')}) { /* current slot's range is empty - iterate forward to the next one */ #{_bin.pop_front.('range->bin')}; if(#{_bin.empty.('range->bin')}) { /* all bin are iterated through, slot range is also empty - end of set */ break; } else { /* advance to the new (possibly empty) slot */ #{iterable._slot.const_lvalue} b = #{_bin.view_front.('range->bin')}; range->slot = #{_slot.new.('*b')}; } } else { /* current slot's range is not empty - no need to proceed */ break; } } } end custom_create.configure do code %{ #{_iterable._slot.const_lvalue} s; assert(range); assert(iterable); range->bin = #{_bin.new.('iterable->bin')}; /* get the first slot's range regardless of its emptiness status */ s = #{_bin.view_front.('range->bin')}; range->slot = #{_slot.new.('*s')}; /* actually advance to the first non-empty slot */ #{_advance.(range)}; } end empty.configure do code %{ assert(range); return #{_slot.empty.('range->slot')}; } end pop_front.configure do code %{ assert(range); #{_slot.pop_front.('range->slot')}; #{_advance.(range)}; } end view_front.configure do code %{ assert(range); assert(!#{empty.(range)}); return #{_slot.view_front.('range->slot')}; } end
configure()
click to toggle source
Calls superclass method
# File lib/autoc/hash_set.rb, line 67 def configure super method(:void, :create_capacity, { target: lvalue, capacity: :size_t.rvalue }).configure do code %{ unsigned char bits = 0; assert(target); target->size = 0; /* fix capacity to become the ceiling to the nearest power of two */ if(capacity % 2 == 0) --capacity; while(capacity >>= 1) ++bits; capacity = (size_t)1 << (bits+1); assert(capacity > 0); target->hash_mask = capacity-1; /* fast slot location for value: hash_code(value) & hash_mask */ #{_bin.custom_create.('target->bin', capacity)}; assert(#{_bin.size.('target->bin')} % 2 == 0); } header %{ @brief Create set with specified capacity @param[out] target set to create @param[in] capacity initial capacity of the set This function creates a new set which should be suffice to contain specific number of elements. While the input capacity may be arbitrary the resulting one will be rounded up to the nearest power of two. This function may be useful when the (approximate) number of elements this set is about to contain is known in advance in order to avoid expensive storage reallocation & elements rehashing operations during the set's lifetime. @since 2.0 } end def _find_slot_hash(hash) %{ assert(target); return #{_bin.view.('target->bin', "#{hash} & target->hash_mask")}; } end method(_slot.const_lvalue, :_find_slot, { target: const_rvalue, value: element.const_rvalue }, visibility: :internal).configure do # Find slot based on the value hash code dependencies << _bin.view inline_code _find_slot_hash(element.hash_code.(value)) end method(:void, :_expand, { target: lvalue, force: :int.const_rvalue }, visibility: :internal).configure do code %{ #{type} set; #{_bin.range} r; assert(target); /* capacity threshold == 1.0 */ if(force || target->size >= #{_bin.size.('target->bin')}) { #{create_capacity.(:set, _bin.size.('target->bin') + '*2')}; /* move elements to newly allocated set */ for(r = #{_bin.range.new.('target->bin')}; !#{_bin.range.empty.(:r)}; #{_bin.range.pop_front.(:r)}) { #{_slot.lvalue} src = (#{_slot.lvalue})#{_bin.range.view_front.(:r)}; while(!#{_slot.empty.('*src')}) { /* direct node relocation from original to new list bypassing node reallocation & payload copying */ #{_slot._node_p} node = #{_slot._pull_node.('*src')}; #{_slot.lvalue} dst = (#{_slot.lvalue})#{_find_slot.(target, 'node->element')}; #{_slot._push_node.('*dst', '*node')}; } } set.size = target->size; /* assume all elements have been moved into new set */ #{destroy.(target)}; *target = set; } } end subset.configure do code %{ #{range} r; assert(target); assert(other); if(#{size.(target)} > #{size.(other)}) return 0; /* larger set can't be a subset of a smaller one */ for(r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; if(!#{contains.(other, '*e')}) return 0; } return 1; } end remove.configure do code %{ int c; #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; c = #{_slot.remove_first.('*s', value)}; if(c) --target->size; return c; } end put.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(!#{_slot.find_first.('*s', value)}) { #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 1; } else return 0; } end push.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(#{_slot._replace_first.('*s', value)}) { return 1; } else { /* add brand new value */ #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 0; } } end default_create.configure do dependencies << create_capacity inline_code %{ #{create_capacity.(target, 8)}; } end find_first.configure do code %{ #{_slot.const_lvalue} s = #{_find_slot.(target, value)}; return #{_slot.find_first.('*s', value)}; } end copy.configure do code %{ assert(target); assert(source); #{_bin.copy.('target->bin', 'source->bin')}; target->hash_mask = source->hash_mask; target->size = source->size; } end empty.configure do inline_code %{ assert(target); return target->size == 0; } end size.configure do inline_code %{ assert(target); return target->size; } end contains.configure do code %{ #{_slot.const_lvalue} s; assert(target); s = #{_find_slot.(target, value)}; return #{_slot.contains.('*s', value)}; } end destroy.configure do code %{ assert(target); #{_bin.destroy.('target->bin')}; } end hash_code.configure do code %{ #{range} r; size_t hash; for(hash = AUTOC_HASHER_SEED, r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; hash ^= #{element.hash_code.('*e')}; /* default incremental hasher is applicable to ordered collections only */ } return hash; } end end
range(= @range ||= Range.new(self, visibility: visibility))
click to toggle source
# File lib/autoc/hash_set.rb, line 22 def range = @range ||= Range.new(self, visibility: visibility) def _slot = @_slot ||= _slot_class.new(identifier(:_list, abbreviate: true), element, _master: self, maintain_size: false, visibility: :internal) def _bin = @_bin ||= _bin_class.new(identifier(:_vector, abbreviate: true), _slot, _master: self, visibility: :internal) def initialize(*args, **kws) super dependencies << _bin end def render_interface(stream) if public? stream << %{ /** #{defgroup} @brief Unordered collection of unique elements of type #{element} For iteration over the set elements refer to @ref #{range}. @see C++ [std::unordered_set<T>](https://en.cppreference.com/w/cpp/container/unordered_set) @since 2.0 */ /** #{ingroup} @brief Opaque structure holding state of the hash set @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ size_t size; /**< @private */ size_t hash_mask; /**< @private */ } #{signature}; } end private def configure super method(:void, :create_capacity, { target: lvalue, capacity: :size_t.rvalue }).configure do code %{ unsigned char bits = 0; assert(target); target->size = 0; /* fix capacity to become the ceiling to the nearest power of two */ if(capacity % 2 == 0) --capacity; while(capacity >>= 1) ++bits; capacity = (size_t)1 << (bits+1); assert(capacity > 0); target->hash_mask = capacity-1; /* fast slot location for value: hash_code(value) & hash_mask */ #{_bin.custom_create.('target->bin', capacity)}; assert(#{_bin.size.('target->bin')} % 2 == 0); } header %{ @brief Create set with specified capacity @param[out] target set to create @param[in] capacity initial capacity of the set This function creates a new set which should be suffice to contain specific number of elements. While the input capacity may be arbitrary the resulting one will be rounded up to the nearest power of two. This function may be useful when the (approximate) number of elements this set is about to contain is known in advance in order to avoid expensive storage reallocation & elements rehashing operations during the set's lifetime. @since 2.0 } end def _find_slot_hash(hash) %{ assert(target); return #{_bin.view.('target->bin', "#{hash} & target->hash_mask")}; } end method(_slot.const_lvalue, :_find_slot, { target: const_rvalue, value: element.const_rvalue }, visibility: :internal).configure do # Find slot based on the value hash code dependencies << _bin.view inline_code _find_slot_hash(element.hash_code.(value)) end method(:void, :_expand, { target: lvalue, force: :int.const_rvalue }, visibility: :internal).configure do code %{ #{type} set; #{_bin.range} r; assert(target); /* capacity threshold == 1.0 */ if(force || target->size >= #{_bin.size.('target->bin')}) { #{create_capacity.(:set, _bin.size.('target->bin') + '*2')}; /* move elements to newly allocated set */ for(r = #{_bin.range.new.('target->bin')}; !#{_bin.range.empty.(:r)}; #{_bin.range.pop_front.(:r)}) { #{_slot.lvalue} src = (#{_slot.lvalue})#{_bin.range.view_front.(:r)}; while(!#{_slot.empty.('*src')}) { /* direct node relocation from original to new list bypassing node reallocation & payload copying */ #{_slot._node_p} node = #{_slot._pull_node.('*src')}; #{_slot.lvalue} dst = (#{_slot.lvalue})#{_find_slot.(target, 'node->element')}; #{_slot._push_node.('*dst', '*node')}; } } set.size = target->size; /* assume all elements have been moved into new set */ #{destroy.(target)}; *target = set; } } end subset.configure do code %{ #{range} r; assert(target); assert(other); if(#{size.(target)} > #{size.(other)}) return 0; /* larger set can't be a subset of a smaller one */ for(r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; if(!#{contains.(other, '*e')}) return 0; } return 1; } end remove.configure do code %{ int c; #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; c = #{_slot.remove_first.('*s', value)}; if(c) --target->size; return c; } end put.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(!#{_slot.find_first.('*s', value)}) { #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 1; } else return 0; } end push.configure do code %{ #{_slot.lvalue} s; assert(target); s = (#{_slot.lvalue})#{_find_slot.(target, value)}; if(#{_slot._replace_first.('*s', value)}) { return 1; } else { /* add brand new value */ #{_expand.(target, 0)}; #{_slot.push_front.('*s', value)}; ++target->size; return 0; } } end default_create.configure do dependencies << create_capacity inline_code %{ #{create_capacity.(target, 8)}; } end find_first.configure do code %{ #{_slot.const_lvalue} s = #{_find_slot.(target, value)}; return #{_slot.find_first.('*s', value)}; } end copy.configure do code %{ assert(target); assert(source); #{_bin.copy.('target->bin', 'source->bin')}; target->hash_mask = source->hash_mask; target->size = source->size; } end empty.configure do inline_code %{ assert(target); return target->size == 0; } end size.configure do inline_code %{ assert(target); return target->size; } end contains.configure do code %{ #{_slot.const_lvalue} s; assert(target); s = #{_find_slot.(target, value)}; return #{_slot.contains.('*s', value)}; } end destroy.configure do code %{ assert(target); #{_bin.destroy.('target->bin')}; } end hash_code.configure do code %{ #{range} r; size_t hash; for(hash = AUTOC_HASHER_SEED, r = #{range.new.(target)}; !#{range.empty.(:r)}; #{range.pop_front.(:r)}) { #{element.const_lvalue} e = #{range.view_front.(:r)}; hash ^= #{element.hash_code.('*e')}; /* default incremental hasher is applicable to ordered collections only */ } return hash; } end end end # HashSet class HashSet::Range < ForwardRange def render_interface(stream) if public? render_type_description(stream) stream << %{ /** #{ingroup} @brief Opaque structure holding state of the hash set's range @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ #{_slot} slot; /**< @private */ } #{signature}; } end def _slot = iterable._slot.range def _bin = iterable._bin.range private def configure super method(:void, :_advance, { range: rvalue }, visibility: :internal ).configure do code %{ assert(range); while(1) { if(#{_slot.empty.('range->slot')}) { /* current slot's range is empty - iterate forward to the next one */ #{_bin.pop_front.('range->bin')}; if(#{_bin.empty.('range->bin')}) { /* all bin are iterated through, slot range is also empty - end of set */ break; } else { /* advance to the new (possibly empty) slot */ #{iterable._slot.const_lvalue} b = #{_bin.view_front.('range->bin')}; range->slot = #{_slot.new.('*b')}; } } else { /* current slot's range is not empty - no need to proceed */ break; } } } end custom_create.configure do code %{ #{_iterable._slot.const_lvalue} s; assert(range); assert(iterable); range->bin = #{_bin.new.('iterable->bin')}; /* get the first slot's range regardless of its emptiness status */ s = #{_bin.view_front.('range->bin')}; range->slot = #{_slot.new.('*s')}; /* actually advance to the first non-empty slot */ #{_advance.(range)}; } end empty.configure do code %{ assert(range); return #{_slot.empty.('range->slot')}; } end pop_front.configure do code %{ assert(range); #{_slot.pop_front.('range->slot')}; #{_advance.(range)}; } end view_front.configure do code %{ assert(range); assert(!#{empty.(range)}); return #{_slot.view_front.('range->slot')}; } end end
render_interface(stream)
click to toggle source
# File lib/autoc/hash_set.rb, line 33 def render_interface(stream) if public? stream << %{ /** #{defgroup} @brief Unordered collection of unique elements of type #{element} For iteration over the set elements refer to @ref #{range}. @see C++ [std::unordered_set<T>](https://en.cppreference.com/w/cpp/container/unordered_set) @since 2.0 */ /** #{ingroup} @brief Opaque structure holding state of the hash set @since 2.0 */ } else stream << PRIVATE end stream << %{ typedef struct { #{_bin} bin; /**< @private */ size_t size; /**< @private */ size_t hash_mask; /**< @private */ } #{signature}; } end