diff options
| -rw-r--r-- | src/craftdef.cpp | 338 | ||||
| -rw-r--r-- | src/craftdef.h | 96 | ||||
| -rw-r--r-- | src/server.cpp | 3 |
3 files changed, 349 insertions, 88 deletions
diff --git a/src/craftdef.cpp b/src/craftdef.cpp index bca16a4c6..749490f62 100644 --- a/src/craftdef.cpp +++ b/src/craftdef.cpp @@ -27,10 +27,48 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "gamedef.h" #include "inventory.h" #include "util/serialize.h" +#include "util/string.h" #include "util/numeric.h" #include "strfnd.h" #include "exceptions.h" +inline bool isGroupRecipeStr(const std::string &rec_name) +{ + return str_starts_with(rec_name, std::string("group:")); +} + +inline u64 getHashForString(const std::string &recipe_str) +{ + /*errorstream << "Hashing craft string \"" << recipe_str << "\"";*/ + return murmur_hash_64_ua(recipe_str.data(), recipe_str.length(), 0xdeadbeef); +} + +static u64 getHashForGrid(CraftHashType type, const std::vector<std::string> &grid_names) +{ + switch (type) { + case CRAFT_HASH_TYPE_ITEM_NAMES: { + std::ostringstream os; + bool is_first = true; + for (size_t i = 0; i < grid_names.size(); i++) { + if (grid_names[i] != "") { + os << (is_first ? "" : "\n") << grid_names[i]; + is_first = false; + } + } + return getHashForString(os.str()); + } case CRAFT_HASH_TYPE_COUNT: { + u64 cnt = 0; + for (size_t i = 0; i < grid_names.size(); i++) + if (grid_names[i] != "") + cnt++; + return cnt; + } case CRAFT_HASH_TYPE_UNHASHED: + return 0; + } + // invalid CraftHashType + assert(false); +} + // Check if input matches recipe // Takes recipe groups into account static bool inputItemMatchesRecipe(const std::string &inp_name, @@ -41,7 +79,7 @@ static bool inputItemMatchesRecipe(const std::string &inp_name, return true; // Group - if(rec_name.substr(0,6) == "group:" && idef->isKnown(inp_name)){ + if (isGroupRecipeStr(rec_name) && idef->isKnown(inp_name)) { const struct ItemDefinition &def = idef->get(inp_name); Strfnd f(rec_name.substr(6)); bool all_groups_match = true; @@ -405,8 +443,13 @@ bool CraftDefinitionShaped::check(const CraftInput &input, IGameDef *gamedef) co if(!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x, inp_min_y, inp_max_y)) return false; // it was empty + std::vector<std::string> rec_names; + if (hash_inited) + rec_names = recipe_names; + else + rec_names = craftGetItemNames(recipe, gamedef); + // Get recipe item matrix - std::vector<std::string> rec_names = craftGetItemNames(recipe, gamedef); unsigned int rec_width = width; if(rec_width == 0) return false; @@ -462,6 +505,43 @@ void CraftDefinitionShaped::decrementInput(CraftInput &input, IGameDef *gamedef) craftDecrementOrReplaceInput(input, replacements, gamedef); } +CraftHashType CraftDefinitionShaped::getHashType() const +{ + assert(hash_inited); //pre-condition + bool has_group = false; + for (size_t i = 0; i < recipe_names.size(); i++) { + if (isGroupRecipeStr(recipe_names[i])) { + has_group = true; + break; + } + } + if (has_group) + return CRAFT_HASH_TYPE_COUNT; + else + return CRAFT_HASH_TYPE_ITEM_NAMES; +} + +u64 CraftDefinitionShaped::getHash(CraftHashType type) const +{ + assert(hash_inited); //pre-condition + if ((type == CRAFT_HASH_TYPE_ITEM_NAMES) || (type == CRAFT_HASH_TYPE_COUNT)) { + std::vector<std::string> rec_names = recipe_names; + std::sort(rec_names.begin(), rec_names.end()); + return getHashForGrid(type, rec_names); + } else { + //illegal hash type for this CraftDefinition (pre-condition) + assert(false); + } +} + +void CraftDefinitionShaped::initHash(IGameDef *gamedef) +{ + if (hash_inited) + return; + hash_inited = true; + recipe_names = craftGetItemNames(recipe, gamedef); +} + std::string CraftDefinitionShaped::dump() const { std::ostringstream os(std::ios::binary); @@ -526,12 +606,18 @@ bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) return false; } - // Try with all permutations of the recipe - std::vector<std::string> recipe_copy = craftGetItemNames(recipe, gamedef); - // Start from the lexicographically first permutation (=sorted) - std::sort(recipe_copy.begin(), recipe_copy.end()); - //while(std::prev_permutation(recipe_copy.begin(), recipe_copy.end())){} - do{ + std::vector<std::string> recipe_copy; + if (hash_inited) + recipe_copy = recipe_names; + else { + recipe_copy = craftGetItemNames(recipe, gamedef); + std::sort(recipe_copy.begin(), recipe_copy.end()); + } + + // Try with all permutations of the recipe, + // start from the lexicographically first permutation (=sorted), + // recipe_names is pre-sorted + do { // If all items match, the recipe matches bool all_match = true; //dstream<<"Testing recipe (output="<<output<<"):"; @@ -566,6 +652,42 @@ void CraftDefinitionShapeless::decrementInput(CraftInput &input, IGameDef *gamed craftDecrementOrReplaceInput(input, replacements, gamedef); } +CraftHashType CraftDefinitionShapeless::getHashType() const +{ + assert(hash_inited); //pre-condition + bool has_group = false; + for (size_t i = 0; i < recipe_names.size(); i++) { + if (isGroupRecipeStr(recipe_names[i])) { + has_group = true; + break; + } + } + if (has_group) + return CRAFT_HASH_TYPE_COUNT; + else + return CRAFT_HASH_TYPE_ITEM_NAMES; +} + +u64 CraftDefinitionShapeless::getHash(CraftHashType type) const +{ + assert(hash_inited); //pre-condition + if (type == CRAFT_HASH_TYPE_ITEM_NAMES || type == CRAFT_HASH_TYPE_COUNT) { + return getHashForGrid(type, recipe_names); + } else { + //illegal hash type for this CraftDefinition (pre-condition) + assert(false); + } +} + +void CraftDefinitionShapeless::initHash(IGameDef *gamedef) +{ + if (hash_inited) + return; + hash_inited = true; + recipe_names = craftGetItemNames(recipe, gamedef); + std::sort(recipe_names.begin(), recipe_names.end()); +} + std::string CraftDefinitionShapeless::dump() const { std::ostringstream os(std::ios::binary); @@ -763,6 +885,34 @@ void CraftDefinitionCooking::decrementInput(CraftInput &input, IGameDef *gamedef craftDecrementOrReplaceInput(input, replacements, gamedef); } +CraftHashType CraftDefinitionCooking::getHashType() const +{ + if (isGroupRecipeStr(recipe_name)) + return CRAFT_HASH_TYPE_COUNT; + else + return CRAFT_HASH_TYPE_ITEM_NAMES; +} + +u64 CraftDefinitionCooking::getHash(CraftHashType type) const +{ + if (type == CRAFT_HASH_TYPE_ITEM_NAMES) { + return getHashForString(recipe_name); + } else if (type == CRAFT_HASH_TYPE_COUNT) { + return 1; + } else { + //illegal hash type for this CraftDefinition (pre-condition) + assert(false); + } +} + +void CraftDefinitionCooking::initHash(IGameDef *gamedef) +{ + if (hash_inited) + return; + hash_inited = true; + recipe_name = craftGetItemName(recipe, gamedef); +} + std::string CraftDefinitionCooking::dump() const { std::ostringstream os(std::ios::binary); @@ -844,6 +994,33 @@ void CraftDefinitionFuel::decrementInput(CraftInput &input, IGameDef *gamedef) c craftDecrementOrReplaceInput(input, replacements, gamedef); } +CraftHashType CraftDefinitionFuel::getHashType() const +{ + if (isGroupRecipeStr(recipe_name)) + return CRAFT_HASH_TYPE_COUNT; + else + return CRAFT_HASH_TYPE_ITEM_NAMES; +} + +u64 CraftDefinitionFuel::getHash(CraftHashType type) const +{ + if (type == CRAFT_HASH_TYPE_ITEM_NAMES) { + return getHashForString(recipe_name); + } else if (type == CRAFT_HASH_TYPE_COUNT) { + return 1; + } else { + //illegal hash type for this CraftDefinition (pre-condition) + assert(false); + } +} + +void CraftDefinitionFuel::initHash(IGameDef *gamedef) +{ + if (hash_inited) + return; + hash_inited = true; + recipe_name = craftGetItemName(recipe, gamedef); +} std::string CraftDefinitionFuel::dump() const { std::ostringstream os(std::ios::binary); @@ -876,10 +1053,16 @@ void CraftDefinitionFuel::deSerializeBody(std::istream &is, int version) class CCraftDefManager: public IWritableCraftDefManager { public: + CCraftDefManager() + { + m_craft_defs.resize(craft_hash_type_max + 1); + } + virtual ~CCraftDefManager() { clear(); } + virtual bool getCraftResult(CraftInput &input, CraftOutput &output, bool decrementInput, IGameDef *gamedef) const { @@ -888,47 +1071,55 @@ public: // If all input items are empty, abort. bool all_empty = true; - for(std::vector<ItemStack>::const_iterator + for (std::vector<ItemStack>::const_iterator i = input.items.begin(); - i != input.items.end(); i++) - { - if(!i->empty()) - { + i != input.items.end(); i++) { + if (!i->empty()) { all_empty = false; break; } } - if(all_empty) + if (all_empty) return false; - // Walk crafting definitions from back to front, so that later - // definitions can override earlier ones. - for(std::vector<CraftDefinition*>::const_reverse_iterator - i = m_craft_definitions.rbegin(); - i != m_craft_definitions.rend(); i++) - { - CraftDefinition *def = *i; + std::vector<std::string> input_names; + input_names = craftGetItemNames(input.items, gamedef); + std::sort(input_names.begin(), input_names.end()); - /*infostream<<"Checking "<<input.dump()<<std::endl - <<" against "<<def->dump()<<std::endl;*/ + // Try hash types with increasing collision rate, and return if found. + for (int type = 0; type <= craft_hash_type_max; type++) { + u64 hash = getHashForGrid((CraftHashType) type, input_names); - try { - if(def->check(input, gamedef)) - { + /*errorstream << "Checking type " << type << " with hash " << hash << std::endl;*/ + + // We'd like to do "const [...] hash_collisions = m_craft_defs[type][hash];" + // but that doesn't compile for some reason. This does. + std::map<u64, std::vector<CraftDefinition*> >::const_iterator + col_iter = (m_craft_defs[type]).find(hash); + + if (col_iter == (m_craft_defs[type]).end()) + continue; + + const std::vector<CraftDefinition*> &hash_collisions = col_iter->second; + // Walk crafting definitions from back to front, so that later + // definitions can override earlier ones. + for (std::vector<CraftDefinition*>::const_reverse_iterator + i = hash_collisions.rbegin(); + i != hash_collisions.rend(); i++) { + CraftDefinition *def = *i; + + /*errorstream << "Checking " << input.dump() << std::endl + << " against " << def->dump() << std::endl;*/ + + if (def->check(input, gamedef)) { // Get output, then decrement input (if requested) output = def->getOutput(input, gamedef); - if(decrementInput) + if (decrementInput) def->decrementInput(input, gamedef); + /*errorstream << "Check RETURNS TRUE" << std::endl;*/ return true; } } - catch(SerializationError &e) - { - errorstream<<"getCraftResult: ERROR: " - <<"Serialization error in recipe " - <<def->dump()<<std::endl; - // then go on with the next craft definition - } } return false; } @@ -960,12 +1151,16 @@ public: virtual std::string dump() const { std::ostringstream os(std::ios::binary); - os<<"Crafting definitions:\n"; - for(std::vector<CraftDefinition*>::const_iterator - i = m_craft_definitions.begin(); - i != m_craft_definitions.end(); i++) - { - os<<(*i)->dump()<<"\n"; + os << "Crafting definitions:\n"; + for (int type = 0; type <= craft_hash_type_max; type++) { + for (std::map<u64, std::vector<CraftDefinition*> >::const_iterator + i = (m_craft_defs[type]).begin(); + i != (m_craft_defs[type]).end(); i++) { + for (std::vector<CraftDefinition*>::const_iterator + ii = i->second.begin(); ii != i->second.end(); ii++) { + os << "type " << type << " hash " << i->first << (*ii)->dump() << "\n"; + } + } } return os.str(); } @@ -973,7 +1168,7 @@ public: { verbosestream<<"registerCraft: registering craft definition: " <<def->dump()<<std::endl; - m_craft_definitions.push_back(def); + m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].push_back(def); CraftInput input; std::string output_name = craftGetItemName( @@ -982,48 +1177,41 @@ public: } virtual void clear() { - for(std::vector<CraftDefinition*>::iterator - i = m_craft_definitions.begin(); - i != m_craft_definitions.end(); i++){ - delete *i; + for (int type = 0; type <= craft_hash_type_max; type++) { + for (std::map<u64, std::vector<CraftDefinition*> >::iterator + i = m_craft_defs[type].begin(); + i != m_craft_defs[type].end(); i++) { + for (std::vector<CraftDefinition*>::iterator + ii = i->second.begin(); ii != i->second.end(); ii++) { + delete *ii; + } + i->second.clear(); + } + m_craft_defs[type].clear(); } - m_craft_definitions.clear(); m_output_craft_definitions.clear(); } - virtual void serialize(std::ostream &os) const + virtual void initHashes(IGameDef *gamedef) { - writeU8(os, 0); // version - u16 count = m_craft_definitions.size(); - writeU16(os, count); - for(std::vector<CraftDefinition*>::const_iterator - i = m_craft_definitions.begin(); - i != m_craft_definitions.end(); i++){ + // Move the CraftDefs from the unhashed layer into layers higher up. + for (std::vector<CraftDefinition*>::iterator + i = (m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0]).begin(); + i != (m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0]).end(); i++) { CraftDefinition *def = *i; - // Serialize wrapped in a string - std::ostringstream tmp_os(std::ios::binary); - def->serialize(tmp_os); - os<<serializeString(tmp_os.str()); - } - } - virtual void deSerialize(std::istream &is, IGameDef *gamedef) - { - // Clear everything - clear(); - // Deserialize - int version = readU8(is); - if(version != 0) throw SerializationError( - "unsupported CraftDefManager version"); - u16 count = readU16(is); - for(u16 i=0; i<count; i++){ - // Deserialize a string and grab a CraftDefinition from it - std::istringstream tmp_is(deSerializeString(is), std::ios::binary); - CraftDefinition *def = CraftDefinition::deSerialize(tmp_is); - // Register - registerCraft(def, gamedef); + + // Initialize and get the definition's hash + def->initHash(gamedef); + CraftHashType type = def->getHashType(); + u64 hash = def->getHash(type); + + // Enter the definition + m_craft_defs[type][hash].push_back(def); } + m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].clear(); } private: - std::vector<CraftDefinition*> m_craft_definitions; + //TODO: change both maps to unordered_map when c++11 can be used + std::vector<std::map<u64, std::vector<CraftDefinition*> > > m_craft_defs; std::map<std::string, std::vector<CraftDefinition*> > m_output_craft_definitions; }; diff --git a/src/craftdef.h b/src/craftdef.h index 7902a2e27..cc7a0619c 100644 --- a/src/craftdef.h +++ b/src/craftdef.h @@ -44,6 +44,28 @@ enum CraftMethod }; /* + The type a hash can be. The earlier a type is mentioned in this enum, + the earlier it is tried at crafting, and the less likely is a collision. + Changing order causes changes in behaviour, so know what you do. + */ +enum CraftHashType +{ + // Hashes the normalized names of the recipe's elements. + // Only recipes without group usage can be found here, + // because groups can't be guessed efficiently. + CRAFT_HASH_TYPE_ITEM_NAMES, + + // Counts the non-empty slots. + CRAFT_HASH_TYPE_COUNT, + + // This layer both spares an extra variable, and helps to retain (albeit rarely used) functionality. Maps to 0. + // Before hashes are "initialized", all hashes reside here, after initialisation, none are. + CRAFT_HASH_TYPE_UNHASHED + +}; +const int craft_hash_type_max = (int) CRAFT_HASH_TYPE_UNHASHED; + +/* Input: The contents of the crafting slots, arranged in matrix form */ struct CraftInput @@ -135,8 +157,13 @@ public: // Decreases count of every input item virtual void decrementInput(CraftInput &input, IGameDef *gamedef) const=0; - virtual std::string dump() const=0; + virtual CraftHashType getHashType() const = 0; + virtual u64 getHash(CraftHashType type) const = 0; + + // to be called after all mods are loaded, so that we catch all aliases + virtual void initHash(IGameDef *gamedef) = 0; + virtual std::string dump() const=0; protected: virtual void serializeBody(std::ostream &os) const=0; virtual void deSerializeBody(std::istream &is, int version)=0; @@ -152,14 +179,15 @@ class CraftDefinitionShaped: public CraftDefinition { public: CraftDefinitionShaped(): - output(""), width(1), recipe(), replacements() + output(""), width(1), recipe(), hash_inited(false), replacements() {} CraftDefinitionShaped( const std::string &output_, unsigned int width_, const std::vector<std::string> &recipe_, const CraftReplacements &replacements_): - output(output_), width(width_), recipe(recipe_), replacements(replacements_) + output(output_), width(width_), recipe(recipe_), + hash_inited(false), replacements(replacements_) {} virtual ~CraftDefinitionShaped(){} @@ -169,6 +197,11 @@ public: virtual CraftInput getInput(const CraftOutput &output, IGameDef *gamedef) const; virtual void decrementInput(CraftInput &input, IGameDef *gamedef) const; + virtual CraftHashType getHashType() const; + virtual u64 getHash(CraftHashType type) const; + + virtual void initHash(IGameDef *gamedef); + virtual std::string dump() const; protected: @@ -182,6 +215,10 @@ private: unsigned int width; // Recipe matrix (itemstrings) std::vector<std::string> recipe; + // Recipe matrix (item names) + std::vector<std::string> recipe_names; + // bool indicating if initHash has been called already + bool hash_inited; // Replacement items for decrementInput() CraftReplacements replacements; }; @@ -195,13 +232,14 @@ class CraftDefinitionShapeless: public CraftDefinition { public: CraftDefinitionShapeless(): - output(""), recipe(), replacements() + output(""), recipe(), hash_inited(false), replacements() {} CraftDefinitionShapeless( const std::string &output_, const std::vector<std::string> &recipe_, const CraftReplacements &replacements_): - output(output_), recipe(recipe_), replacements(replacements_) + output(output_), recipe(recipe_), + hash_inited(false), replacements(replacements_) {} virtual ~CraftDefinitionShapeless(){} @@ -211,6 +249,11 @@ public: virtual CraftInput getInput(const CraftOutput &output, IGameDef *gamedef) const; virtual void decrementInput(CraftInput &input, IGameDef *gamedef) const; + virtual CraftHashType getHashType() const; + virtual u64 getHash(CraftHashType type) const; + + virtual void initHash(IGameDef *gamedef); + virtual std::string dump() const; protected: @@ -222,6 +265,10 @@ private: std::string output; // Recipe list (itemstrings) std::vector<std::string> recipe; + // Recipe list (item names) + std::vector<std::string> recipe_names; + // bool indicating if initHash has been called already + bool hash_inited; // Replacement items for decrementInput() CraftReplacements replacements; }; @@ -249,6 +296,11 @@ public: virtual CraftInput getInput(const CraftOutput &output, IGameDef *gamedef) const; virtual void decrementInput(CraftInput &input, IGameDef *gamedef) const; + virtual CraftHashType getHashType() const { return CRAFT_HASH_TYPE_COUNT; } + virtual u64 getHash(CraftHashType type) const { return 2; } + + virtual void initHash(IGameDef *gamedef) {} + virtual std::string dump() const; protected: @@ -272,14 +324,15 @@ class CraftDefinitionCooking: public CraftDefinition { public: CraftDefinitionCooking(): - output(""), recipe(""), cooktime() + output(""), recipe(""), hash_inited(false), cooktime() {} CraftDefinitionCooking( const std::string &output_, const std::string &recipe_, float cooktime_, const CraftReplacements &replacements_): - output(output_), recipe(recipe_), cooktime(cooktime_), replacements(replacements_) + output(output_), recipe(recipe_), hash_inited(false), + cooktime(cooktime_), replacements(replacements_) {} virtual ~CraftDefinitionCooking(){} @@ -289,6 +342,11 @@ public: virtual CraftInput getInput(const CraftOutput &output, IGameDef *gamedef) const; virtual void decrementInput(CraftInput &input, IGameDef *gamedef) const; + virtual CraftHashType getHashType() const; + virtual u64 getHash(CraftHashType type) const; + + virtual void initHash(IGameDef *gamedef); + virtual std::string dump() const; protected: @@ -300,6 +358,10 @@ private: std::string output; // Recipe itemstring std::string recipe; + // Recipe item name + std::string recipe_name; + // bool indicating if initHash has been called already + bool hash_inited; // Time in seconds float cooktime; // Replacement items for decrementInput() @@ -314,12 +376,12 @@ class CraftDefinitionFuel: public CraftDefinition { public: CraftDefinitionFuel(): - recipe(""), burntime() + recipe(""), hash_inited(false), burntime() {} CraftDefinitionFuel(std::string recipe_, float burntime_, const CraftReplacements &replacements_): - recipe(recipe_), burntime(burntime_), replacements(replacements_) + recipe(recipe_), hash_inited(false), burntime(burntime_), replacements(replacements_) {} virtual ~CraftDefinitionFuel(){} @@ -329,6 +391,11 @@ public: virtual CraftInput getInput(const CraftOutput &output, IGameDef *gamedef) const; virtual void decrementInput(CraftInput &input, IGameDef *gamedef) const; + virtual CraftHashType getHashType() const; + virtual u64 getHash(CraftHashType type) const; + + virtual void initHash(IGameDef *gamedef); + virtual std::string dump() const; protected: @@ -338,6 +405,10 @@ protected: private: // Recipe itemstring std::string recipe; + // Recipe item name + std::string recipe_name; + // bool indicating if initHash has been called already + bool hash_inited; // Time in seconds float burntime; // Replacement items for decrementInput() @@ -361,8 +432,6 @@ public: // Print crafting recipes for debugging virtual std::string dump() const=0; - - virtual void serialize(std::ostream &os) const=0; }; class IWritableCraftDefManager : public ICraftDefManager @@ -383,11 +452,12 @@ public: // Add a crafting definition. // After calling this, the pointer belongs to the manager. virtual void registerCraft(CraftDefinition *def, IGameDef *gamedef) = 0; + // Delete all crafting definitions virtual void clear()=0; - virtual void serialize(std::ostream &os) const=0; - virtual void deSerialize(std::istream &is, IGameDef *gamedef) = 0; + // To be called after all mods are loaded, so that we catch all aliases + virtual void initHashes(IGameDef *gamedef) = 0; }; IWritableCraftDefManager* createCraftDefManager(); diff --git a/src/server.cpp b/src/server.cpp index 1969a5946..4971e6f66 100644 --- a/src/server.cpp +++ b/src/server.cpp @@ -334,6 +334,9 @@ Server::Server( // Perform pending node name resolutions m_nodedef->runNodeResolverCallbacks(); + // init the recipe hashes to speed up crafting + m_craftdef->initHashes(this); + // Initialize Environment m_env = new ServerEnvironment(servermap, m_script, this, m_path_world); |