# # # add_file "cow_trie.hh" # content [2033eefa4bbac0d39cc55b750a38cd39b13dfe79] # # patch "Makefile.am" # from [2a65b561e8fc7ecd02ad248aebeba2cb7e77f84a] # to [a0ed2ec6eda766d2da11b80abf961781e4c486b9] # # patch "cmd_ws_commit.cc" # from [76029d05da2d497248cbf30c84814b7ac96e685b] # to [f671792297e86c7af0251135d759e18df9c3794e] # # patch "database_check.cc" # from [7ab9c29a4afd98142dbb73d85e4dffdc0b449e58] # to [d863d981b77df0e39aba1bd1213cb199d7c209ea] # # patch "rev_types.hh" # from [57f8ea1d809f63101811a9c816f413b3fa912872] # to [c1fdee9901eb139ca5555184ba21b39dd00e09ce] # # patch "roster.cc" # from [b36ee864d37f6ae523bdf51f17ae89ee9d58fab5] # to [bf987c9ad5c5d06dee9c5fcf48e4bbff2798d7ee] # # patch "roster.hh" # from [016b8d7d71074671de87df4f0ec5eed65efd3073] # to [43e645cd02b1aa473fd51628b4965c814caf24b3] # # patch "roster_delta.cc" # from [c2d4643c1dac50ceb8aaefd9297d9f080952b45e] # to [5225677470dde8755581d7ae22081845ac428e60] # # patch "unit-tests/roster.cc" # from [b97daa78753cf898ab900a2ccf53a458d108849a] # to [5c45a937a25de81e4fb0c78c4c1059731bb11ac6] # # patch "work.cc" # from [4624f09640eefc22a17df1a54d3c5b3350a8b83f] # to [2367e4a44ee048b8a341f468fe96156c5f3e1eb5] # ============================================================ --- cow_trie.hh 2033eefa4bbac0d39cc55b750a38cd39b13dfe79 +++ cow_trie.hh 2033eefa4bbac0d39cc55b750a38cd39b13dfe79 @@ -0,0 +1,227 @@ + +#include +#include + +// This is *NOT* a normal STL-compatible container! It pretends well enough to work +// with parallel_iter and such, but it does not have find(), insert(), erase(). +// +// Because this is copy-on-write, and the copying is per-node instead of for the +// whole object, the nodes can not have parent pointers (also, having parent pointers +// would I think make the size 2^n+4 instead of 2^n, which AIUI would waste almost +// equal space with common memory allocators). +// This lack of parent pointers means that iterators are expensive, so they're not +// used except for, well, iteration. + +template +class cow_trie +{ +public: + typedef _Key key_type; + //typedef _Value value_type; + typedef std::pair<_Key, _Value> value_type; +private: + enum { mask = (1<<_Bits)-1 }; + enum { levels = (sizeof(_Key) * 8 + _Bits - 1) / _Bits }; + + struct middle_node_type + { + boost::shared_ptr contents[(1<<_Bits)]; + }; + struct leaf_node_type + { + _Value contents[1<<_Bits]; + }; + + _Value _empty_value; + unsigned _count; + boost::shared_ptr _data; + + bool walk(boost::shared_ptr & d, _Key key, int level, _Value **ret) + { + if (!d) + { + if (level > 0) + d.reset(new middle_node_type()); + else + d.reset(new leaf_node_type()); + } + if (!d.unique()) + { + if (level > 0) + d.reset(new middle_node_type(*boost::static_pointer_cast(d))); + else + d.reset(new leaf_node_type(*boost::static_pointer_cast(d))); + } + unsigned idx = (key >> (_Bits * level)) & mask; + if (level > 0) + return walk(boost::static_pointer_cast(d)->contents[idx], + key, level-1, ret); + else + { + *ret = &boost::static_pointer_cast(d)->contents[idx]; + return true; + } + } + + bool walk(boost::shared_ptr const & d, _Key key, int level, _Value **ret) const + { + if (!d) + { + return false; + } + unsigned idx = (key >> (_Bits * level)) & mask; + if (level > 0) + return walk(boost::static_pointer_cast(d)->contents[idx], + key, level-1, ret); + else + { + *ret = &boost::static_pointer_cast(d)->contents[idx]; + return true; + } + } +public: + cow_trie() : _count(0) { } + unsigned size() const { return _count; } + bool empty() const { return _count == 0; } + void clear() + { + _count = 0; + _data.reset(); + } + void set(_Key key, _Value const & value) { + _Value *p; + walk(_data, key, levels-1, &p); + bool b = (*p != _empty_value); + bool a = (value != _empty_value); + if (b && !a) + --_count; + else if (a && !b) + ++_count; + *p = value; + } + bool set_if_missing(_Key key, _Value const & value) + { + _Value *p; + walk(_data, key, levels-1, &p); + if (*p != _empty_value) + return false; + if (value != _empty_value) + { + ++_count; + *p = value; + } + return true; + } + void unset(_Key key) { + set(key, _empty_value); + } + _Value const &get_if_present(_Key key) const { + _Value *p; + if (walk(_data, key, levels-1, &p)) + return *p; + else + return _empty_value; + } + // This is actually not the same as above. + // It's non-const, so it calls the other walk(). + _Value const &get_unshared_if_present(_Key key) + { + _Value *p; + if (walk(_data, key, levels-1, &p)) + return *p; + else + return _empty_value; + } + + class const_iterator + { + struct stack_item + { + boost::shared_ptr ptr; + unsigned idx; + bool operator==(stack_item const & other) const + { + return ptr == other.ptr && idx == other.idx; + } + }; + std::vector stack; + friend class cow_trie; + explicit const_iterator(cow_trie const & t) + { + if (t._data) + { + stack_item item; + item.ptr = t._data; + item.idx = (unsigned)-1; + stack.push_back(item); + ++(*this); + } + } + _Value _empty_value; + private: + value_type _ret; + public: + bool operator==(const_iterator const & other) + { + return stack == other.stack; + } + bool operator!=(const_iterator const & other) + { + return stack != other.stack; + } + const_iterator() { } + const_iterator const & operator++() + { + while (!stack.empty()) + { + stack_item & item = stack.back(); + boost::shared_ptr middle + = boost::static_pointer_cast(item.ptr); + boost::shared_ptr leaf + = boost::static_pointer_cast(item.ptr); + for (++item.idx; item.idx < (1<<_Bits); ++item.idx) + { + if (stack.size() == levels) + { + if (leaf->contents[item.idx] != _empty_value) + { + _ret.first = (_ret.first & ~mask) | item.idx; + _ret.second = leaf->contents[item.idx]; + return *this; + } + } + else + { + if (middle->contents[item.idx]) + { + int shifts = levels - stack.size(); + int bits = shifts * _Bits; + _ret.first = (_ret.first & ~(mask<contents[item.idx]; + i.idx = (unsigned)-1; + stack.push_back(i); + break; + } + } + } + if (item.idx == (1 << _Bits)) + stack.pop_back(); + } + return *this; + } + value_type const & operator*() const + { + return _ret; + } + value_type const * operator->() const + { + return &_ret; + } + }; + friend class const_iterator; + + const_iterator begin() const { return const_iterator(*this); } + const_iterator end() const { return const_iterator(); } +}; + ============================================================ --- Makefile.am 2a65b561e8fc7ecd02ad248aebeba2cb7e77f84a +++ Makefile.am a0ed2ec6eda766d2da11b80abf961781e4c486b9 @@ -50,6 +50,7 @@ MOST_SOURCES = \ update.cc update.hh \ work.cc migrate_work.cc work.hh \ cert.cc cert.hh \ + cow_trie.hh \ project.cc project.hh \ outdated_indicator.cc outdated_indicator.hh \ database.cc database.hh \ ============================================================ --- cmd_ws_commit.cc 76029d05da2d497248cbf30c84814b7ac96e685b +++ cmd_ws_commit.cc f671792297e86c7af0251135d759e18df9c3794e @@ -789,6 +789,7 @@ drop_attr(app_state & app, args_vector c roster_t new_roster = old_roster; node_t node = new_roster.get_node(path); + new_roster.unshare(node); // Clear all attrs (or a specific attr). if (args.size() == 1) @@ -907,6 +908,7 @@ set_attr(app_state & app, args_vector co roster_t new_roster = old_roster; node_t node = new_roster.get_node(path); + new_roster.unshare(node); attr_key a_key = typecast_vocab(idx(args, 1)); attr_value a_value = typecast_vocab(idx(args, 2)); ============================================================ --- database_check.cc 7ab9c29a4afd98142dbb73d85e4dffdc0b449e58 +++ database_check.cc d863d981b77df0e39aba1bd1213cb199d7c209ea @@ -213,7 +213,7 @@ check_rosters_manifest(database & db, found_manifests.insert(man_id); for (node_map::const_iterator n = ros.all_nodes().begin(); - n != ros.all_nodes().end(); n++) + n != ros.all_nodes().end(); ++n) { if (is_file_t(n->second)) @@ -261,7 +261,7 @@ check_rosters_marking(database & db, db.get_roster(ros_id, ros, mm); for (node_map::const_iterator n = ros.all_nodes().begin(); - n != ros.all_nodes().end(); n++) + n != ros.all_nodes().end(); ++n) { // lots of revisions that must exist marking_t mark = mm[n->first]; ============================================================ --- rev_types.hh 57f8ea1d809f63101811a9c816f413b3fa912872 +++ rev_types.hh c1fdee9901eb139ca5555184ba21b39dd00e09ce @@ -21,6 +21,7 @@ #include "numeric_vocab.hh" #include "hybrid_map.hh" #include "vector.hh" +#include "cow_trie.hh" // full definitions in basic_io.hh namespace basic_io @@ -77,7 +78,8 @@ typedef std::map typedef std::map marking_map; typedef std::map dir_map; -typedef hybrid_map node_map; +//typedef hybrid_map node_map; +typedef cow_trie node_map; // (true, "val") or (false, "") are both valid attr values (for proper // merging, we have to widen the attr_value type to include a first-class ============================================================ --- roster.cc b36ee864d37f6ae523bdf51f17ae89ee9d58fab5 +++ roster.cc bf987c9ad5c5d06dee9c5fcf48e4bbff2798d7ee @@ -156,11 +156,14 @@ dump(marking_map const & markings, strin // existing subdirectory into the root directory. This is an UI constraint, // not a constraint at this level. +u32 last_created_roster = 0; + node::node(node_id i) : self(i), parent(the_null_node), name(), - type(node_type_none) + type(node_type_none), + cow_version(0) { } @@ -169,7 +172,8 @@ node::node() : self(the_null_node), parent(the_null_node), name(), - type(node_type_none) + type(node_type_none), + cow_version(0) { } @@ -206,6 +210,7 @@ dir_node::attach_child(path_component co { I(null_node(child->parent)); I(child->name.empty()); + I(cow_version == child->cow_version); safe_insert(children, make_pair(pc, child)); child->parent = this->self; child->name = pc; @@ -216,6 +221,7 @@ dir_node::detach_child(path_component co dir_node::detach_child(path_component const & pc) { node_t n = get_child(pc); + I(cow_version == n->cow_version); n->parent = the_null_node; n->name = path_component(); safe_erase(children, pc); @@ -294,39 +300,27 @@ dump(node_t const & n, string & out) out = oss.str(); } -// helper -void -roster_t::do_deep_copy_from(roster_t const & other) + +roster_t::roster_t() + : cow_version(++last_created_roster) { - MM(*this); - MM(other); - I(!root_dir); - I(nodes.empty()); - for (node_map::const_iterator i = other.nodes.begin(); i != other.nodes.end(); - ++i) - hinted_safe_insert(nodes, nodes.end(), make_pair(i->first, i->second->clone())); - for (node_map::iterator i = nodes.begin(); i != nodes.end(); ++i) - if (is_dir_t(i->second)) - { - dir_map & children = downcast_to_dir_t(i->second)->children; - for (dir_map::iterator j = children.begin(); j != children.end(); ++j) - j->second = safe_get(nodes, j->second->self); - } - if (other.root_dir) - root_dir = downcast_to_dir_t(safe_get(nodes, other.root_dir->self)); } roster_t::roster_t(roster_t const & other) + : cow_version(++last_created_roster) { - do_deep_copy_from(other); + root_dir = other.root_dir; + nodes = other.nodes; + other.cow_version = ++last_created_roster; } roster_t & roster_t::operator=(roster_t const & other) { - root_dir.reset(); - nodes.clear(); - do_deep_copy_from(other); + root_dir = other.root_dir; + nodes = other.nodes; + cow_version = ++last_created_roster; + other.cow_version = ++last_created_roster; return *this; } @@ -628,7 +622,7 @@ roster_t::has_node(node_id n) const bool roster_t::has_node(node_id n) const { - return nodes.find(n) != nodes.end(); + return nodes.get_if_present(n); } bool @@ -688,7 +682,9 @@ roster_t::get_node(node_id nid) const node_t roster_t::get_node(node_id nid) const { - return safe_get(nodes, nid); + node_t const &n(nodes.get_if_present(nid)); + I(n); + return n; } @@ -731,17 +727,54 @@ roster_t::get_name(node_id nid, file_pat p = file_path(tmp, 0, string::npos); // short circuit constructor } +void +roster_t::unshare(node_t & n, bool is_in_node_map) +{ + if (cow_version == n->cow_version) + return; + // we can't get at the (possibly shared) pointer in the node_map, + // so if we were given the only pointer then we know the node + // isn't in any other rosters + if (n.unique()) + { + n->cow_version = cow_version; + return; + } + // here we could theoretically walk up the tree to see if + // the node or any of its parents have too many references, + // but I'm guessing that the avoided copies won't be worth + // the extra search time + node_t old = n; + n = n->clone(); + n->cow_version = cow_version; + if (is_in_node_map) + nodes.set(n->self, n); + if (!null_node(n->parent)) + { + node_t p = nodes.get_if_present(n->parent); + I(p); + unshare(p); + downcast_to_dir_t(p)->children[n->name] = n; + } + if (root_dir && root_dir->self == n->self) + { + root_dir = downcast_to_dir_t(n); + } +} + void roster_t::replace_node_id(node_id from, node_id to) { I(!null_node(from)); I(!null_node(to)); node_t n = get_node(from); - safe_erase(nodes, from); - safe_insert(nodes, make_pair(to, n)); - n->self = to; + nodes.unset(from); + unshare(n, false); + + I(nodes.set_if_missing(to, n)); + n->self = to; if (is_dir_t(n)) { dir_t d = downcast_to_dir_t(n); @@ -777,7 +810,11 @@ roster_t::detach_node(file_path const & return root_id; } - dir_t parent = downcast_to_dir_t(get_node(dirname)); + node_t pp = get_node(dirname); + unshare(pp); + dir_t parent = downcast_to_dir_t(pp); + node_t c = parent->get_child(basename); + unshare(c); node_id nid = parent->detach_child(basename)->self; safe_insert(old_locations, make_pair(nid, make_pair(parent->self, basename))); @@ -800,8 +837,11 @@ roster_t::detach_node(node_id nid) } else { + unshare(n); path_component name = n->name; - dir_t parent = downcast_to_dir_t(get_node(n->parent)); + node_t p = get_node(n->parent); + unshare(p); + dir_t parent = downcast_to_dir_t(p); I(parent->detach_child(name) == n); safe_insert(old_locations, make_pair(nid, make_pair(n->parent, name))); @@ -819,7 +859,7 @@ roster_t::drop_detached_node(node_id nid if (is_dir_t(n)) I(downcast_to_dir_t(n)->children.empty()); // all right, kill it - safe_erase(nodes, nid); + nodes.unset(nid); // Resolving a duplicate name conflict via drop one side requires dropping // nodes that were never attached. So we erase the key without checking @@ -843,7 +883,8 @@ roster_t::create_dir_node(node_id nid) { dir_t d = dir_t(new dir_node()); d->self = nid; - safe_insert(nodes, make_pair(nid, d)); + d->cow_version = cow_version; + nodes.set(nid, d); } @@ -864,7 +905,8 @@ roster_t::create_file_node(file_id const file_t f = file_t(new file_node()); f->self = nid; f->content = content; - safe_insert(nodes, make_pair(nid, f)); + f->cow_version = cow_version; + nodes.set(nid, f); } void @@ -910,7 +952,10 @@ roster_t::attach_node(node_id nid, node_ } else { - dir_t parent_n = downcast_to_dir_t(get_node(parent)); + unshare(n); + node_t p = get_node(parent); + unshare(p); + dir_t parent_n = downcast_to_dir_t(p); parent_n->attach_child(name, n); I(i == old_locations.end() || i->second != make_pair(n->parent, n->name)); } @@ -924,7 +969,9 @@ roster_t::apply_delta(file_path const & file_id const & old_id, file_id const & new_id) { - file_t f = downcast_to_file_t(get_node(pth)); + node_t n = get_node(pth); + unshare(n); + file_t f = downcast_to_file_t(n); I(f->content == old_id); I(!null_node(f->self)); I(!(f->content == new_id)); @@ -934,7 +981,9 @@ roster_t::set_content(node_id nid, file_ void roster_t::set_content(node_id nid, file_id const & new_id) { - file_t f = downcast_to_file_t(get_node(nid)); + node_t n = get_node(nid); + unshare(n); + file_t f = downcast_to_file_t(n); I(!(f->content == new_id)); f->content = new_id; } @@ -952,6 +1001,7 @@ roster_t::erase_attr(node_id nid, attr_key const & name) { node_t n = get_node(nid); + unshare(n); safe_erase(n->attrs, name); } @@ -970,6 +1020,7 @@ roster_t::set_attr(file_path const & pth pair const & val) { node_t n = get_node(pth); + unshare(n); I(val.first || val.second().empty()); I(!null_node(n->self)); attr_map_t::iterator i = n->attrs.find(name); @@ -987,6 +1038,7 @@ roster_t::set_attr_unknown_to_dead_ok(no pair const & val) { node_t n = get_node(nid); + unshare(n); I(val.first || val.second().empty()); attr_map_t::iterator i = n->attrs.find(name); if (i != n->attrs.end()) @@ -1326,14 +1378,22 @@ namespace break; } } + node_t left_n = left_i->second; for (set::const_iterator j = left_missing.begin(); j != left_missing.end(); ++j) - safe_insert(left_i->second->attrs, - make_pair(*j, make_pair(false, attr_value()))); + { + left.unshare(left_n); + safe_insert(left_n->attrs, + make_pair(*j, make_pair(false, attr_value()))); + } + node_t right_n = right_i->second; for (set::const_iterator j = right_missing.begin(); j != right_missing.end(); ++j) - safe_insert(right_i->second->attrs, - make_pair(*j, make_pair(false, attr_value()))); + { + right.unshare(right_n); + safe_insert(right_n->attrs, + make_pair(*j, make_pair(false, attr_value()))); + } ++left_i; ++right_i; } @@ -1556,6 +1616,7 @@ namespace I(same_type(ln, n) && same_type(rn, n)); I(left_marking.birth_revision == right_marking.birth_revision); new_marking.birth_revision = left_marking.birth_revision; + MM(n->self); // name mark_merged_scalar(left_marking.parent_name, left_uncommon_ancestors, @@ -1582,6 +1643,7 @@ namespace i != n->attrs.end(); ++i) { attr_key const & key = i->first; + MM(key); attr_map_t::const_iterator li = ln->attrs.find(key); attr_map_t::const_iterator ri = rn->attrs.find(key); I(new_marking.attrs.find(key) == new_marking.attrs.end()); @@ -1651,11 +1713,11 @@ mark_merge_roster(roster_t const & left_ i != merge.all_nodes().end(); ++i) { node_t const & n = i->second; - node_map::const_iterator lni = left_roster.all_nodes().find(i->first); - node_map::const_iterator rni = right_roster.all_nodes().find(i->first); + node_t const &left_node = left_roster.all_nodes().get_if_present(i->first); + node_t const &right_node = right_roster.all_nodes().get_if_present(i->first); - bool exists_in_left = (lni != left_roster.all_nodes().end()); - bool exists_in_right = (rni != right_roster.all_nodes().end()); + bool exists_in_left = (left_node); + bool exists_in_right = (right_node); marking_t new_marking; @@ -1664,7 +1726,6 @@ mark_merge_roster(roster_t const & left_ else if (!exists_in_left && exists_in_right) { - node_t const & right_node = rni->second; marking_t const & right_marking = safe_get(right_markings, n->self); // must be unborn on the left (as opposed to dead) I(right_uncommon_ancestors.find(right_marking.birth_revision) @@ -1674,7 +1735,6 @@ mark_merge_roster(roster_t const & left_ } else if (exists_in_left && !exists_in_right) { - node_t const & left_node = lni->second; marking_t const & left_marking = safe_get(left_markings, n->self); // must be unborn on the right (as opposed to dead) I(left_uncommon_ancestors.find(left_marking.birth_revision) @@ -1684,8 +1744,6 @@ mark_merge_roster(roster_t const & left_ } else { - node_t const & left_node = lni->second; - node_t const & right_node = rni->second; mark_merged_node(safe_get(left_markings, n->self), left_uncommon_ancestors, left_node, safe_get(right_markings, n->self), @@ -2753,7 +2811,9 @@ roster_t::parse_from(basic_io::parser & I(static_cast(n)); - safe_insert(nodes, make_pair(n->self, n)); + n->cow_version = cow_version; + I(nodes.set_if_missing(n->self, n)); + if (is_dir_t(n) && pth.empty()) { I(! has_root()); ============================================================ --- roster.hh 016b8d7d71074671de87df4f0ec5eed65efd3073 +++ roster.hh 43e645cd02b1aa473fd51628b4965c814caf24b3 @@ -46,6 +46,7 @@ struct node path_component name; // the_null_component iff this is a root dir attr_map_t attrs; roster_node_type type; + u32 cow_version; // see roster_t::cow_version below // need a virtual function to make dynamic_cast work virtual node_t clone() = 0; @@ -152,7 +153,7 @@ public: class roster_t { public: - roster_t() {} + roster_t(); roster_t(roster_t const & other); roster_t & operator=(roster_t const & other); bool has_root() const; @@ -163,6 +164,7 @@ public: node_t get_node(file_path const & sp) const; node_t get_node(node_id nid) const; void get_name(node_id nid, file_path & sp) const; + void unshare(node_t & n, bool is_in_node_map = true); void replace_node_id(node_id from, node_id to); // editable_tree operations @@ -238,9 +240,17 @@ private: } private: - void do_deep_copy_from(roster_t const & other); + //void do_deep_copy_from(roster_t const & other); dir_t root_dir; node_map nodes; + // This is set to a unique value when a roster is created or + // copied to/from another roster. If a node has the same version + // as the roster it's in, then it is not shared. Nodes with version + // zero are also not shared, since that means they haven't been added + // to a roster yet. + // A simple refcount isn't good enough, because everything that points + // to a node in question could also be shared. + mutable u32 cow_version; // This requires some explanation. There is a particular kind of // nonsensical behavior which we wish to discourage -- when a node is // detached from some location, and then re-attached at that same location ============================================================ --- roster_delta.cc c2d4643c1dac50ceb8aaefd9297d9f080952b45e +++ roster_delta.cc 5225677470dde8755581d7ae22081845ac428e60 @@ -127,6 +127,9 @@ namespace { node_id nid = new_n->self; pair new_loc(new_n->parent, new_n->name); + MM(new_loc.first); + MM(new_loc.second); + MM(nid); if (is_dir_t(new_n)) safe_insert(d.dirs_added, make_pair(new_loc, nid)); ============================================================ --- unit-tests/roster.cc b97daa78753cf898ab900a2ccf53a458d108849a +++ unit-tests/roster.cc 5c45a937a25de81e4fb0c78c4c1059731bb11ac6 @@ -2316,10 +2316,14 @@ UNIT_TEST(unify_rosters_end_to_end_attr_ // put in the attrs on foo { + node_t n = first_roster.get_node(foo_id); + first_roster.unshare(n); safe_insert(first_roster.get_node(foo_id)->attrs, make_pair(attr_key("testfoo1"), make_pair(false, attr_value()))); safe_insert(first_markings.find(foo_id)->second.attrs, make_pair(attr_key("testfoo1"), singleton(first_rid))); + n = second_roster.get_node(foo_id); + second_roster.unshare(n); safe_insert(second_roster.get_node(foo_id)->attrs, make_pair(attr_key("testfoo2"), make_pair(false, attr_value()))); safe_insert(second_markings.find(foo_id)->second.attrs, ============================================================ --- work.cc 4624f09640eefc22a17df1a54d3c5b3350a8b83f +++ work.cc 2367e4a44ee048b8a341f468fe96156c5f3e1eb5 @@ -1604,8 +1604,14 @@ workspace::update_current_roster_from_fi missing_items++; } + file_id fid; + ident_existing_file(fp, fid, status); file_t file = downcast_to_file_t(node); - ident_existing_file(fp, file->content, status); + if (file->content != fid) + { + ros.unshare(node); + downcast_to_file_t(node)->content = fid; + } } }