diff -Naur srcbak/act.wizard.c src/act.wizard.c --- srcbak/act.wizard.c 2020-05-24 16:10:43.531380763 -0400 +++ src/act.wizard.c 2020-05-24 17:17:48.821852097 -0400 @@ -629,6 +629,8 @@ CCGRN(ch, C_NRM), vnum, CCNRM(ch, C_NRM), GET_OBJ_RNUM(j), obj_script_id(j), buf, GET_OBJ_SPEC(j) ? (get_spec_func_name(GET_OBJ_SPEC(j))) : "None"); + send_to_char(ch, "Generation time: \tg%s\tnUnique ID: \tg%llu\tn\r\n", ctime(&GET_OBJ_GENERATION(j)), GET_OBJ_UID(j)); + send_to_char(ch, "L-Desc: '%s%s%s'\r\n", CCYEL(ch, C_NRM), j->description ? j->description : "", CCNRM(ch, C_NRM)); @@ -2496,8 +2498,9 @@ struct descriptor_data *d; char field[MAX_INPUT_LENGTH], value[MAX_INPUT_LENGTH], arg[MAX_INPUT_LENGTH], buf[MAX_STRING_LENGTH]; - int r, g, b; + int low, high, r, g, b; char colour[16]; + char *strp; struct show_struct { const char *cmd; @@ -2514,9 +2517,10 @@ { "shops", LVL_IMMORT }, { "houses", LVL_IMMORT }, { "snoop", LVL_IMMORT }, /* 10 */ - { "thaco", LVL_IMMORT }, - { "exp", LVL_IMMORT }, - { "colour", LVL_IMMORT }, + { "thaco", LVL_IMMORT }, + { "exp", LVL_IMMORT }, + { "colour", LVL_IMMORT }, + { "uniques", LVL_GRGOD}, { "\n", 0 } }; @@ -2801,7 +2805,26 @@ } page_string(ch->desc, buf, TRUE); break; - + + case 14: + if (value != NULL && *value) { + if (sscanf(value, "%d-%d", &low, &high) != 2) { + if (sscanf(value, "%d", &low) != 1) { + send_to_char(ch, "Usage: show uniques, show uniques [vnum], or show uniques [low-high]\r\n"); + return; + } else { + high = low; + } + } + } else { + low = -1; + high = 99999999; + } + strp = sprintuniques(low, high); + page_string(ch->desc, strp, TRUE); + free(strp); + break; + /* show what? */ default: send_to_char(ch, "Sorry, I don't understand that.\r\n"); diff -Naur srcbak/cedit.c src/cedit.c --- srcbak/cedit.c 2020-05-24 16:10:43.531380763 -0400 +++ src/cedit.c 2020-05-24 17:37:30.849718492 -0400 @@ -101,6 +101,7 @@ OLC_CONFIG(d)->play.map_size = CONFIG_MAP_SIZE; OLC_CONFIG(d)->play.minimap_size = CONFIG_MINIMAP_SIZE; OLC_CONFIG(d)->play.script_players = CONFIG_SCRIPT_PLAYERS; + OLC_CONFIG(d)->play.all_items_unique = CONFIG_ALL_ITEMS_UNIQUE; /* Crash Saves */ OLC_CONFIG(d)->csd.free_rent = CONFIG_FREE_RENT; @@ -205,6 +206,7 @@ CONFIG_MAP_SIZE = OLC_CONFIG(d)->play.map_size; CONFIG_MINIMAP_SIZE = OLC_CONFIG(d)->play.minimap_size; CONFIG_SCRIPT_PLAYERS = OLC_CONFIG(d)->play.script_players; + CONFIG_ALL_ITEMS_UNIQUE = OLC_CONFIG(d)->play.all_items_unique; /* Crash Saves */ CONFIG_FREE_RENT = OLC_CONFIG(d)->csd.free_rent; @@ -382,7 +384,8 @@ "default_minimap_size = %d\n\n", CONFIG_MINIMAP_SIZE); fprintf(fl, "* Do you want scripts to be attachable to players?\n" "script_players = %d\n\n", CONFIG_SCRIPT_PLAYERS); - + fprintf(fl, "* Should all items be treated as unique?\n" + "all_items_unique = %d\n\n", CONFIG_ALL_ITEMS_UNIQUE); strcpy(buf, CONFIG_OK); strip_cr(buf); @@ -634,6 +637,7 @@ "%sP%s) Display Closed Doors : %s%s\r\n" "%sR%s) Diagonal Directions : %s%s\r\n" "%sS%s) Prevent Mortal Level To Immortal : %s%s\r\n" + "%sV%s) Treat all Objects as Unique : %s%s\r\n" "%s1%s) OK Message Text : %s%s" "%s2%s) HUH Message Text : %s%s" "%s3%s) NOPERSON Message Text : %s%s" @@ -663,6 +667,7 @@ grn, nrm, cyn, CHECK_VAR(OLC_CONFIG(d)->play.disp_closed_doors), grn, nrm, cyn, CHECK_VAR(OLC_CONFIG(d)->play.diagonal_dirs), grn, nrm, cyn, CHECK_VAR(OLC_CONFIG(d)->play.no_mort_to_immort), + grn, nrm, cyn, CHECK_VAR(OLC_CONFIG(d)->play.all_items_unique), grn, nrm, cyn, OLC_CONFIG(d)->play.OK, grn, nrm, cyn, OLC_CONFIG(d)->play.HUH, @@ -973,14 +978,19 @@ case 'r': case 'R': - TOGGLE_VAR(OLC_CONFIG(d)->play.diagonal_dirs); - break; + TOGGLE_VAR(OLC_CONFIG(d)->play.diagonal_dirs); + break; - case 's': - case 'S': - TOGGLE_VAR(OLC_CONFIG(d)->play.no_mort_to_immort); + case 's': + case 'S': + TOGGLE_VAR(OLC_CONFIG(d)->play.no_mort_to_immort); + break; + + case 'v': + case 'V': + TOGGLE_VAR(OLC_CONFIG(d)->play.all_items_unique); break; - + case '1': write_to_output(d, "Enter the OK message : "); OLC_MODE(d) = CEDIT_OK; diff -Naur srcbak/config.c src/config.c --- srcbak/config.c 2020-05-24 16:10:43.531380763 -0400 +++ src/config.c 2020-05-24 17:22:09.177340492 -0400 @@ -316,3 +316,10 @@ /* Current Debug Mode */ int debug_mode = OFF; + +/* + * Do you want to treat all objects as unique? Set to YES and + * every object created in the game will be flagged as UNIQUE. This + * will help prevent object duping. + */ +int all_items_unique = YES; diff -Naur srcbak/config.h src/config.h --- srcbak/config.h 2020-05-24 16:10:43.531380763 -0400 +++ src/config.h 2020-05-24 17:43:57.738926180 -0400 @@ -87,5 +87,6 @@ extern int auto_pwipe; extern struct pclean_criteria_data pclean_criteria[]; extern int selfdelete_fastwipe; +extern int all_items_unique; #endif /* _CONFIG_H_*/ diff -Naur srcbak/constants.c src/constants.c --- srcbak/constants.c 2020-05-24 16:10:43.531380763 -0400 +++ src/constants.c 2020-05-24 17:42:23.289654281 -0400 @@ -463,6 +463,7 @@ "ANTI_WARRIOR", "NO_SELL", "QUEST_ITEM", + "UNIQUE", "\n" }; diff -Naur srcbak/db.c src/db.c --- srcbak/db.c 2020-05-24 16:10:43.527380709 -0400 +++ src/db.c 2020-05-24 17:43:26.838510027 -0400 @@ -38,6 +38,7 @@ #include "mud_event.h" #include "msgedit.h" #include "screen.h" +#include "htree.h" #include /* declarations of most of the 'global' variables */ @@ -113,6 +114,14 @@ struct social_messg *soc_mess_list = NULL; /* list of socials */ int top_of_socialt = -1; /* number of socials */ +/* HTREE defines */ +struct htree_node *room_htree = NULL; +struct htree_node *mob_htree = NULL; +struct htree_node *obj_htree = NULL; +void free_obj_unique_hash(); +void init_obj_unique_hash(); + + time_t newsmod; /* Time news file was last modified. */ time_t motdmod; /* Time motd file was last modified. */ @@ -565,6 +574,7 @@ } free(world); top_of_world = 0; + htree_free(room_htree); /* Objects */ for (cnt = 0; cnt <= top_of_objt; cnt++) { @@ -583,6 +593,7 @@ } free(obj_proto); free(obj_index); + htree_free(obj_htree); /* Mobiles */ for (cnt = 0; cnt <= top_of_mobt; cnt++) { @@ -605,6 +616,8 @@ } free(mob_proto); free(mob_index); + htree_free(mob_htree); + /* Shops */ destroy_shops(); @@ -669,11 +682,37 @@ } free(trig_index); + free_obj_unique_hash(); + + /* Htree shutdown */ + htree_shutdown(); + /* Events */ event_free_all(); } +/* You can define this to anything you want; 1 would work but it would + be very inefficient. I would recommend that it actually be close to + your total number of in-game objects if not double or triple it just + to minimize collisions. The only O(n) [n=NUM_OBJ_UNIQUE_POOLS] + operation is initialization of the hash table, all other operations + that have to traverse are O(n) [n=num elements in pool], so more + pools are better. + - Elie Rosenblum Dec. 12 2003 - Cunning updated 2015 */ +#define NUM_OBJ_UNIQUE_POOLS 10000 + +struct obj_unique_hash_elem **obj_unique_hash_pools = NULL; + +void init_obj_unique_hash() +{ + int i; + CREATE(obj_unique_hash_pools, struct obj_unique_hash_elem *, NUM_OBJ_UNIQUE_POOLS); + for (i = 0; i < NUM_OBJ_UNIQUE_POOLS; i++) { + obj_unique_hash_pools[i] = NULL; + } +} + /* body of the booting system */ void boot_db(void) { @@ -711,6 +750,8 @@ mag_assign_spells(); boot_world(); + + htree_test(); log("Loading help entries."); index_boot(DB_BOOT_HLP); @@ -747,6 +788,9 @@ assign_the_quests(); } + log("Init Object Unique Hash"); + init_obj_unique_hash(); + log("Assigning spell and skill levels."); init_spell_levels(); @@ -1282,6 +1326,10 @@ world[room_nr].name = fread_string(fl, buf2); world[room_nr].description = fread_string(fl, buf2); + if (!room_htree) + room_htree = htree_init(); + htree_add(room_htree, virtual_nr, room_nr); + if (!get_line(fl, line)) { log("SYSERR: Expecting roomflags/sector type of room #%d but file ended!", virtual_nr); @@ -1750,6 +1798,10 @@ clear_char(mob_proto + i); + if (! mob_htree) + mob_htree = htree_init(); + htree_add(mob_htree, nr, i); + /* Mobiles should NEVER use anything in the 'player_specials' structure. * The only reason we have every mob in the game share this copy of the * structure is to save newbie coders from themselves. -gg */ @@ -1897,6 +1949,10 @@ obj_index[i].number = 0; obj_index[i].func = NULL; + if (!obj_htree) + obj_htree = htree_init(); + htree_add(obj_htree, nr, i); + clear_object(obj_proto + i); obj_proto[i].item_number = i; @@ -2481,6 +2537,9 @@ obj->script_id = 0; // this is set later by obj_script_id + GET_OBJ_GENERATION(obj) = time(0); + add_unique_id(obj); + return (obj); } @@ -2506,6 +2565,9 @@ obj_index[i].number++; obj->script_id = 0; // this is set later by obj_script_id + + GET_OBJ_GENERATION(obj) = time(0); + add_unique_id(obj); copy_proto_script(&obj_proto[i], obj, OBJ_TRIGGER); assign_triggers(obj, OBJ_TRIGGER); @@ -3206,6 +3268,188 @@ ungetc( c, fp ); } +/* Added by Cunning for Obj Tracking and Obj Uniqueness. 4/8/10 */ + +struct obj_unique_hash_elem { + time_t generation; + long long unique_id; + struct obj_data *obj; + struct obj_unique_hash_elem *next_e; +}; + +void free_obj_unique_hash() +{ + int i; + struct obj_unique_hash_elem *elem; + struct obj_unique_hash_elem *next_elem; + + if (obj_unique_hash_pools) { + for (i = 0; i < NUM_OBJ_UNIQUE_POOLS; i++) { + elem = obj_unique_hash_pools[i]; + while (elem) { + next_elem = elem->next_e; + if (elem->obj) + free(elem->obj); + free(elem); + elem = next_elem; + } + } + free(obj_unique_hash_pools); + } +} + +void add_unique_id(struct obj_data *obj) +{ + struct obj_unique_hash_elem *elem = NULL; + int i; + + if (!obj_unique_hash_pools) + init_obj_unique_hash(); + + if (sizeof(long long) > sizeof(long)) + obj->unique_id = (((long long)circle_random()) << (sizeof(long long) * 4)) + circle_random(); + else + obj->unique_id = circle_random(); + + if (obj->unique_id < 0) + obj->unique_id = 0 - obj->unique_id; + + if (CONFIG_ALL_ITEMS_UNIQUE) { + if (!IS_SET_AR(GET_OBJ_EXTRA(obj), ITEM_UNIQUE_SAVE)) + SET_BIT_AR(GET_OBJ_EXTRA(obj), ITEM_UNIQUE_SAVE); + } + + CREATE(elem, struct obj_unique_hash_elem, 1); + elem->generation = obj->generation; + elem->unique_id = obj->unique_id; + elem->obj = obj; + i = obj->unique_id % NUM_OBJ_UNIQUE_POOLS; + elem->next_e = obj_unique_hash_pools[i]; + obj_unique_hash_pools[i] = elem; +} + +void remove_unique_id(struct obj_data *obj) +{ + struct obj_unique_hash_elem *elem, **ptr, *tmp; + + ptr = obj_unique_hash_pools + (obj->unique_id % NUM_OBJ_UNIQUE_POOLS); + + if (!(ptr && *ptr)) + return; + + elem = *ptr; + + while (elem) { + tmp = elem->next_e; + if (elem->obj == obj) { + free(elem); + *ptr = tmp; + } else { + ptr = &(elem->next_e); + } + elem = tmp; + } +} +void log_dupe_objects(struct obj_data *obj1, struct obj_data *obj2) +{ + if (!obj1 || !obj2) + return; + + mudlog(BRF, LVL_GRGOD, TRUE, "DUPE: Dupe object found: %s [%d] [%ld:%lld]", + obj1->short_description ? obj1->short_description : "", + obj_index[obj1->item_number].vnum, GET_OBJ_GENERATION(obj1), GET_OBJ_UID(obj1)); + + mudlog(BRF, LVL_GRGOD, TRUE, "DUPE: First: In room: %d (%s), " + "In object: %s, Carried by: %s, Worn by: %s", + IN_ROOM(obj1) != NOWHERE ? world[IN_ROOM(obj1)].number : NOWHERE, + IN_ROOM(obj1) == NOWHERE ? "Nowhere" : world[IN_ROOM(obj1)].name, + obj1->in_obj ? obj1->in_obj->short_description : "None", + obj1->carried_by ? GET_NAME(obj1->carried_by) : "Nobody", + obj1->worn_by ? GET_NAME(obj1->worn_by) : "Nobody"); + + + mudlog(BRF, LVL_GRGOD, TRUE, "DUPE: (deleted) Newer: In room: %d (%s), " + "In object: %s, Carried by: %s, Worn by: %s", + IN_ROOM(obj2) != NOWHERE ? world[IN_ROOM(obj2)].number : NOWHERE, + IN_ROOM(obj2) == NOWHERE ? "Nowhere" : world[IN_ROOM(obj2)].name, + obj2->in_obj ? obj2->in_obj->short_description : "None", + obj2->carried_by ? GET_NAME(obj2->carried_by) : "Nobody", + obj2->worn_by ? GET_NAME(obj2->worn_by) : "Nobody"); + + if (obj2->carried_by || obj2->worn_by) + send_to_char(obj2->carried_by ? obj2->carried_by : obj2->worn_by, + "A Duplicate ITEM was found on your character. We have now deleted this item. Please see an Admin if you have any questions."); +} + +int check_unique_id(struct obj_data *obj) +{ + struct obj_unique_hash_elem *elem; + + if (obj == NULL || obj->unique_id <= 0) + return FALSE; + + elem = obj_unique_hash_pools[obj->unique_id % NUM_OBJ_UNIQUE_POOLS]; + while (elem) { + if (elem->obj == obj) { + log("SYSERR: check_unique_id checking for existing object?!"); + } + if (GET_OBJ_VNUM(elem->obj) == GET_OBJ_VNUM(obj)) + if (elem->generation == obj->generation && elem->unique_id == obj->unique_id) { + log_dupe_objects(elem->obj, obj); + return TRUE; + } + elem = elem->next_e; + } + return FALSE; +} + +char *sprintuniques(int low, int high) +{ + int i, count = 0, remain, header; + struct obj_unique_hash_elem *q; + char *str, *ptr; + remain = 40; + for (i = 0; i < NUM_OBJ_UNIQUE_POOLS; i++) { + q = obj_unique_hash_pools[i]; + remain += 40; + while (q) { + count++; + remain += 80 + (q->obj->short_description ? strlen(q->obj->short_description) : 20); + q = q->next_e; + } + } + if (count < 1) { + return strdup("No objects in unique hash.\r\n"); + } + CREATE(str, char, remain + 1); + ptr = str; + count = snprintf(ptr, remain, "Unique object hashes (vnums %d - %d)\r\n", + low, high); + ptr += count; + remain -= count; + for (i = 0; i < NUM_OBJ_UNIQUE_POOLS; i++) { + header = 0; + q = obj_unique_hash_pools[i]; + while (q) { + if (GET_OBJ_VNUM(q->obj) >= low && GET_OBJ_VNUM(q->obj) <= high) { + if (!header) { + header = 1; + count = snprintf(ptr, remain, "|-Hash %d\r\n", i); + ptr += count; + remain -= count; + } + count = snprintf(ptr, remain, "| |- [\tg%6d\tn] - [\ty%10ld:%-19lld\tn] - %s\r\n", + GET_OBJ_VNUM(q->obj), q->generation, q->unique_id, + q->obj->short_description ? q->obj->short_description : ""); + ptr += count; + remain -= count; + } + q = q->next_e; + } + } + return str; +} + /* Called to free all allocated follow_type structs */ static void free_followers(struct follow_type *k) { @@ -3315,7 +3559,8 @@ /* release memory allocated for an obj struct */ void free_obj(struct obj_data *obj) -{ +{ + remove_unique_id(obj); if (GET_OBJ_RNUM(obj) == NOWHERE) { free_object_strings(obj); /* free script proto list */ @@ -3586,78 +3831,123 @@ /* returns the real number of the room with given virtual number */ room_rnum real_room(room_vnum vnum) { - room_rnum bot, top, mid; - - bot = 0; - top = top_of_world; + room_rnum bot, top, mid, i, last_top; + + if (vnum == NOWHERE) + return NOWHERE; + + i = htree_find(room_htree, vnum); + + if (i != NOWHERE && world[i].number == vnum) + return i; + else { + bot = 0; + top = top_of_world; - if (world[bot].number > vnum || world[top].number < vnum) - return (NOWHERE); /* perform binary search on world-table */ - while (bot<= top) { + for (;;) { + last_top = top; mid = (bot + top) / 2; - - if ((world + mid)->number == vnum) + + if ((world + mid)->number == vnum) { + log("room_htree sync fix: %d: %d -> %d", vnum, i, mid); + htree_add(room_htree, vnum, mid); return (mid); + } + if (bot >= top) + return (NOWHERE); + if ((world + mid)->number > vnum) top = mid - 1; else bot = mid + 1; + + if (top > last_top) + return NOWHERE; + } } - return (NOWHERE); } /* returns the real number of the monster with given virtual number */ mob_rnum real_mobile(mob_vnum vnum) { - mob_rnum bot, top, mid; - - bot = 0; - top = top_of_mobt; - - /* quickly reject out-of-range vnums */ - if (mob_index[bot].vnum > vnum || mob_index[top].vnum < vnum) - return (NOBODY); + mob_rnum bot, top, mid, i, last_top; + + if (vnum == NOBODY) + return NOBODY; + + i = htree_find(mob_htree, vnum); + + if (i != NOBODY && mob_index[i].vnum == vnum) + return i; + else { + bot = 0; + top = top_of_mobt; /* perform binary search on mob-table */ - while (bot <= top) { + for (;;) { + last_top = top; mid = (bot + top) / 2; + + if ((mob_index + mid)->vnum == vnum){ + log("mob_htree sync fix: %d: %d -> %d", vnum, i, mid); + htree_add(mob_htree, vnum, mid); + return (mid); + } + + if (bot >= top) + return (NOBODY); - if ((mob_index + mid)->vnum == vnum) - return (mid); if ((mob_index + mid)->vnum > vnum) top = mid - 1; else bot = mid + 1; - } - return (NOBODY); + + if (top > last_top) + return NOWHERE; + } + } } /* returns the real number of the object with given virtual number */ obj_rnum real_object(obj_vnum vnum) { - obj_rnum bot, top, mid; - - bot = 0; - top = top_of_objt; - - /* quickly reject out-of-range vnums */ - if (obj_index[bot].vnum > vnum || obj_index[top].vnum < vnum) - return (NOTHING); + obj_rnum bot, top, mid, i, last_top; + + if (vnum == NOTHING) + return NOTHING; + + i = htree_find(obj_htree, vnum); + + if (i != NOWHERE && obj_index[i].vnum == vnum) + return i; + else { + bot = 0; + top = top_of_objt; /* perform binary search on obj-table */ - while (bot <= top) { + for (;;) { + last_top = top; mid = (bot + top) / 2; - - if ((obj_index + mid)->vnum == vnum) + + if ((obj_index + mid)->vnum == vnum){ + log("obj_htree sync fix: %d: %d -> %d", vnum, i, mid); + htree_add(obj_htree, vnum, mid); return (mid); + } + if (bot >= top) + return (NOTHING); + if ((obj_index + mid)->vnum > vnum) top = mid - 1; else bot = mid + 1; - } - return (NOTHING); + + if (top > last_top) + return NOWHERE; + } + } } /* returns the real number of the zone with given virtual number */ @@ -3861,6 +4151,7 @@ CONFIG_MINIMAP_SIZE = default_minimap_size; CONFIG_SCRIPT_PLAYERS = script_players; CONFIG_DEBUG_MODE = debug_mode; + CONFIG_ALL_ITEMS_UNIQUE = all_items_unique; /* Rent / crashsave options. */ CONFIG_FREE_RENT = free_rent; @@ -3941,6 +4232,8 @@ CONFIG_AUTOSAVE_TIME = num; else if (!str_cmp(tag, "auto_save_olc")) CONFIG_OLC_SAVE = num; + else if (!str_cmp(tag, "all_items_unique")) + CONFIG_ALL_ITEMS_UNIQUE = num; break; case 'c': diff -Naur srcbak/db.h src/db.h --- srcbak/db.h 2020-05-24 16:10:43.531380763 -0400 +++ src/db.h 2020-05-24 17:45:09.427891815 -0400 @@ -257,6 +257,9 @@ void free_player_index(void); void load_help(FILE *fl, char *name); void new_mobile_data(struct char_data *ch); +void add_unique_id(struct obj_data *obj); +int check_unique_id(struct obj_data *obj); +char *sprintuniques(int low, int high); zone_rnum real_zone(zone_vnum vnum); room_rnum real_room(room_vnum vnum); @@ -321,6 +324,11 @@ void renum_world(void); void load_config( void ); +/* Cunnning addition - new sort tree for duping detection - 12/06/10 */ +extern struct htree_node *room_htree; +extern struct htree_node *mob_htree; +extern struct htree_node *obj_htree; + /* Various Files */ extern char *credits; extern char *news; diff -Naur srcbak/dg_variables.c src/dg_variables.c --- srcbak/dg_variables.c 2020-05-24 16:10:43.531380763 -0400 +++ src/dg_variables.c 2020-05-24 16:47:43.441481319 -0400 @@ -1307,7 +1307,19 @@ else if (!str_cmp(field, "timer")) snprintf(str, slen, "%d", GET_OBJ_TIMER(o)); + break; + + case 'u': + if (!str_cmp(field, "uniqueid")) { + if (subfield && *subfield) { + snprintf(str, slen, "%lld", (long long int)(GET_OBJ_UID(o) == atoi(subfield))); + } else { + snprintf(str, slen, "%lld", GET_OBJ_UID(o)); + } + } + break; + case 'v': if (!str_cmp(field, "vnum")) if (subfield && *subfield) { diff -Naur srcbak/genmob.c src/genmob.c --- srcbak/genmob.c 2020-05-24 16:10:43.531380763 -0400 +++ src/genmob.c 2020-05-24 17:11:47.436997190 -0400 @@ -17,6 +17,7 @@ #include "genzon.h" #include "dg_olc.h" #include "spells.h" +#include "htree.h" /* local functions */ static void extract_mobile_all(mob_vnum vnum); @@ -58,6 +59,7 @@ } mob_index[i] = mob_index[i - 1]; mob_proto[i] = mob_proto[i - 1]; + htree_add(mob_htree, mob_index[i].vnum, i); mob_proto[i].nr++; } if (!found) { @@ -67,6 +69,7 @@ mob_index[0].vnum = vnum; mob_index[0].number = 0; mob_index[0].func = 0; + htree_add(mob_htree, mob_index[0].vnum, 0); } log("GenOLC: add_mobile: Added mobile %d at index #%d.", vnum, found); @@ -167,6 +170,9 @@ mob_proto[counter].nr--; } + /* Remove from htree table */ + htree_del(mob_htree, vnum); + top_of_mobt--; RECREATE(mob_index, struct index_data, top_of_mobt + 1); RECREATE(mob_proto, struct char_data, top_of_mobt + 1); diff -Naur srcbak/genobj.c src/genobj.c --- srcbak/genobj.c 2020-05-24 16:10:43.531380763 -0400 +++ src/genobj.c 2020-05-24 17:13:41.578535685 -0400 @@ -19,7 +19,7 @@ #include "handler.h" #include "interpreter.h" #include "boards.h" /* for board_info */ - +#include "htree.h" /* local functions */ static int update_all_objects(struct obj_data *obj); @@ -74,6 +74,8 @@ obj->next_content = swap.next_content; obj->next = swap.next; obj->sitting_here = swap.sitting_here; + obj->unique_id = swap.unique_id; + obj->generation = swap.generation; } return count; @@ -150,6 +152,7 @@ obj_index[i] = obj_index[i - 1]; obj_proto[i] = obj_proto[i - 1]; obj_proto[i].item_number = i; + htree_add(obj_htree, obj_index[i].vnum, i); } /* Not found, place at 0. */ @@ -163,7 +166,7 @@ #else if (obj == NULL || ovnum < 0 || ornum < 0 || ornum > top_of_objt) #endif - return NOWHERE; + return NOTHING; obj->item_number = ornum; obj_index[ornum].vnum = ovnum; @@ -172,6 +175,7 @@ copy_object_preserve(&obj_proto[ornum], obj); obj_proto[ornum].in_room = NOWHERE; + htree_add(obj_htree, obj_index[ornum].vnum, ornum); return ornum; } @@ -434,6 +438,9 @@ GET_OBJ_RNUM(tmp) -= (GET_OBJ_RNUM(tmp) > rnum); } + /* Remove from htree table */ + htree_del(obj_htree, obj_index[rnum].number); + for (i = rnum; i < top_of_objt; i++) { obj_index[i] = obj_index[i + 1]; obj_proto[i] = obj_proto[i + 1]; diff -Naur srcbak/genwld.c src/genwld.c --- srcbak/genwld.c 2020-05-24 16:10:43.531380763 -0400 +++ src/genwld.c 2020-05-24 17:15:07.967698893 -0400 @@ -18,7 +18,7 @@ #include "shop.h" #include "dg_olc.h" #include "mud_event.h" - +#include "htree.h" /* This function will copy the strings so be sure you free your own copies of * the description, title, and such. */ @@ -67,6 +67,7 @@ for (tobj = world[i].contents; tobj; tobj = tobj->next_content) IN_ROOM(tobj) += (IN_ROOM(tobj) != NOWHERE); } + htree_add(room_htree, world[i].number, i); } if (!found) { world[0] = *room; /* Last place, in front. */ @@ -134,6 +135,9 @@ add_to_save_list(zone_table[room->zone].number, SL_WLD); + /* remove from realnum lookup tree */ + htree_del(room_htree, room->number); + /* This is something you might want to read about in the logs. */ log("GenOLC: delete_room: Deleting room #%d (%s).", room->number, room->name); diff -Naur srcbak/htree.c src/htree.c --- srcbak/htree.c 1969-12-31 19:00:00.000000000 -0500 +++ src/htree.c 2020-05-24 17:16:27.860768152 -0400 @@ -0,0 +1,194 @@ +/*************************************************************************** + * File: htree.c * + * Usage: Generalized hash tree code for fast lookups * + * * + * This code is released under the CircleMud License * + * Written by Elie Rosenblum * + * Copyright (c) 7-Oct-2004 * + ***************************************************************************/ + +#include "conf.h" +#include "sysdep.h" + +#include "structs.h" +#include "utils.h" +#include "db.h" +#include "htree.h" + +#undef HTREE_TEST_CYCLES + +struct htree_node *HTREE_NULL = NULL; +int htree_total_nodes = 0; +int htree_depth_used = 0; + +void htree_shutdown() +{ + free(HTREE_NULL); + HTREE_NULL = NULL; +} + +struct htree_node *htree_init() +{ + struct htree_node *newnode; + int i; + + if (! HTREE_NULL) { + htree_total_nodes++; + CREATE(HTREE_NULL, struct htree_node, 1); + for (i = 0; i < HTREE_NODE_SUBS; i++) { + HTREE_NULL->subs[i] = HTREE_NULL; + } + HTREE_NULL->content = NOWHERE; + HTREE_NULL->parent = NULL; + } + + if (! htree_depth_used) + htree_depth_used = 1; + + htree_total_nodes++; + CREATE(newnode, struct htree_node, 1); + memcpy(newnode->subs, HTREE_NULL->subs, HTREE_NODE_SUBS * sizeof(struct htree_node *)); + newnode->content = NOWHERE; + newnode->parent = HTREE_NULL; + + return newnode; +} + +void htree_free(struct htree_node *root) +{ + int i; + + if (! root || root == HTREE_NULL) + return; + + for (i = 0; i < HTREE_NODE_SUBS; i++) + htree_free(root->subs[i]); + + free(root); +} + +void htree_add(struct htree_node *root, IDXTYPE index, IDXTYPE content) +{ + struct htree_node *tmp; + int i, depth; + + if (! root) + return; + + tmp = root; + depth = 0; + while (index) { + depth++; + i = index & HTREE_NODE_MASK; + index >>= HTREE_NODE_BITS; + if (tmp->subs[i] == HTREE_NULL) { + htree_total_nodes++; + CREATE(tmp->subs[i], struct htree_node, 1); + memcpy(tmp->subs[i]->subs, HTREE_NULL->subs, HTREE_NODE_SUBS * sizeof(struct htree_node *)); + tmp->subs[i]->content = NOWHERE; + tmp->subs[i]->parent = HTREE_NULL; + } + tmp = tmp->subs[i]; + } + + if (tmp == HTREE_NULL) /* We fell off somehow! Time to crap our pants */ + return; + + if (depth > htree_depth_used) + htree_depth_used = depth; + + tmp->content = content; +} + +struct htree_node *htree_find_node(struct htree_node *root, IDXTYPE index) +{ + struct htree_node *tmp; + int i; + + tmp = root; + while (index) { + i = index & HTREE_NODE_MASK; + index >>= HTREE_NODE_BITS; + tmp = tmp->subs[i]; + } + + return tmp; +} + +void htree_del(struct htree_node *root, IDXTYPE index) +{ + struct htree_node *tmp; + + tmp = htree_find_node(root, index); + tmp->content = NOWHERE; +} + +IDXTYPE htree_find(struct htree_node *root, IDXTYPE index) +{ + struct htree_node *tmp; + + tmp = htree_find_node(root, index); + return tmp->content; +} + +room_rnum real_room_old(room_vnum vnum) +{ + room_rnum bot, top, mid; + bot = 0; + top = top_of_world; + + /* perform binary search on world-table */ + for (;;) { + mid = (bot + top) / 2; + + if ((world + mid)->number == vnum) + return (mid); + + if (bot >= top) + return (NOWHERE); + if ((world + mid)->number > vnum) + top = mid - 1; + else + bot = mid + 1; + } +} + +void htree_test() +{ +#ifdef HTREE_TEST_CYCLES + int i, n, l; + struct timeval start, finish; + float t1, t2; + + if (gettimeofday(&start, NULL)) { + log("error getting time: gettimeofday(): %s", strerror(errno)); + } + for (i = 0; i < HTREE_TEST_CYCLES; i++) { + n = rand_number(1, top_of_world); + l = real_room_old(world[n].number); + } + if (gettimeofday(&finish, NULL)) { + log("error getting time: gettimeofday(): %s", strerror(errno)); + } + log("old start: %2d.%06d", start.tv_sec, start.tv_usec); + log("old end: %2d.%06d", finish.tv_sec, finish.tv_usec); + t1 = ((float)finish.tv_sec + ((float)finish.tv_usec) / 1000000) - + ((float)start.tv_sec + ((float)start.tv_usec) / 1000000); + if (gettimeofday(&start, NULL)) { + log("error getting time: gettimeofday(): %s", strerror(errno)); + } + for (i = 0; i < HTREE_TEST_CYCLES; i++) { + n = rand_number(1, top_of_world); + l = real_room(world[n].number); + } + if (gettimeofday(&finish, NULL)) { + log("error getting time: gettimeofday(): %s", strerror(errno)); + } + log("new start: %2d.%06d", start.tv_sec, start.tv_usec); + log("new end: %2d.%06d", finish.tv_sec, finish.tv_usec); + t2 = ((float)finish.tv_sec + ((float)finish.tv_usec) / 1000000) - + ((float)start.tv_sec + ((float)start.tv_usec) / 1000000); + log("htree_test: htree speedup factor: %.0f%% (%.2f/%.2f)", t1 * 100 / t2, t1, t2); +#endif /* HTREE_TEST_CYCLES */ + log("htree stats (global): %d nodes, %lu bytes (depth %d/%lu used/possible)", htree_total_nodes, (long unsigned int)(htree_total_nodes * sizeof(struct htree_node)), htree_depth_used, (long unsigned int)HTREE_MAX_DEPTH); +} diff -Naur srcbak/htree.h src/htree.h --- srcbak/htree.h 1969-12-31 19:00:00.000000000 -0500 +++ src/htree.h 2020-05-24 17:02:23.109398621 -0400 @@ -0,0 +1,37 @@ +/*************************************************************************** + * File: htree.h * + * Usage: Generalized hash tree code for fast lookups * + * * + * This code is released under the CircleMud License * + * Written by Elie Rosenblum * + * Copyright (c) 7-Oct-2004 * + ***************************************************************************/ + +/* Magic constants: */ +/* Don't change these unless you know what you're doing, the constants must + * match */ + +#define HTREE_NODE_BITS 5 +#define HTREE_NODE_SUBS (1 << HTREE_NODE_BITS) +#define HTREE_NODE_MASK (HTREE_NODE_SUBS - 1) +#define HTREE_MAX_DEPTH (((sizeof(IDXTYPE) * 8) / HTREE_NODE_BITS) + 1) + +/* End of magic constants */ + +struct htree_node { + IDXTYPE content; + struct htree_node *parent; + struct htree_node *subs[HTREE_NODE_SUBS]; +}; + +extern struct htree_node *HTREE_NULL; +extern int htree_total_nodes; +extern int htree_depth_used; + +void htree_shutdown(); +struct htree_node *htree_init(); +void htree_free(struct htree_node *root); +void htree_add(struct htree_node *root, IDXTYPE index, IDXTYPE content); +void htree_del(struct htree_node *root, IDXTYPE index); +IDXTYPE htree_find(struct htree_node *root, IDXTYPE index); +void htree_test(); diff -Naur srcbak/Makefile src/Makefile --- srcbak/Makefile 2020-05-24 16:10:43.535380816 -0400 +++ src/Makefile 2020-05-24 17:47:41.245937451 -0400 @@ -21,8 +21,8 @@ LIBS = -lcrypt -SRCFILES := act.comm.c act.informative.c act.item.c act.movement.c act.offensive.c act.other.c act.social.c act.wizard.c aedit.c asciimap.c ban.c boards.c bsd-snprintf.c castle.c cedit.c class.c comm.c config.c constants.c db.c dg_comm.c dg_db_scripts.c dg_event.c dg_handler.c dg_misc.c dg_mobcmd.c dg_objcmd.c dg_olc.c dg_scripts.c dg_triggers.c dg_variables.c dg_wldcmd.c fight.c genmob.c genobj.c genolc.c genqst.c genshp.c genwld.c genzon.c graph.c handler.c hedit.c house.c ibt.c improved-edit.c interpreter.c limits.c lists.c magic.c mail.c medit.c mobact.c modify.c msgedit.c mud_event.c oasis.c oasis_copy.c oasis_delete.c oasis_list.c objsave.c oedit.c players.c prefedit.c protocol.c qedit.c quest.c random.c redit.c sedit.c shop.c spec_assign.c spec_procs.c spell_parser.c spells.c tedit.c utils.c weather.c zedit.c zmalloc.c -OBJFILES := act.comm.o act.informative.o act.item.o act.movement.o act.offensive.o act.other.o act.social.o act.wizard.o aedit.o asciimap.o ban.o boards.o bsd-snprintf.o castle.o cedit.o class.o comm.o config.o constants.o db.o dg_comm.o dg_db_scripts.o dg_event.o dg_handler.o dg_misc.o dg_mobcmd.o dg_objcmd.o dg_olc.o dg_scripts.o dg_triggers.o dg_variables.o dg_wldcmd.o fight.o genmob.o genobj.o genolc.o genqst.o genshp.o genwld.o genzon.o graph.o handler.o hedit.o house.o ibt.o improved-edit.o interpreter.o limits.o lists.o magic.o mail.o medit.o mobact.o modify.o msgedit.o mud_event.o oasis.o oasis_copy.o oasis_delete.o oasis_list.o objsave.o oedit.o players.o prefedit.o protocol.o qedit.o quest.o random.o redit.o sedit.o shop.o spec_assign.o spec_procs.o spell_parser.o spells.o tedit.o utils.o weather.o zedit.o zmalloc.o +SRCFILES := act.comm.c act.informative.c act.item.c act.movement.c act.offensive.c act.other.c act.social.c act.wizard.c aedit.c asciimap.c ban.c boards.c bsd-snprintf.c castle.c cedit.c class.c comm.c config.c constants.c db.c dg_comm.c dg_db_scripts.c dg_event.c dg_handler.c dg_misc.c dg_mobcmd.c dg_objcmd.c dg_olc.c dg_scripts.c dg_triggers.c dg_variables.c dg_wldcmd.c fight.c genmob.c genobj.c genolc.c genqst.c genshp.c genwld.c genzon.c graph.c handler.c hedit.c htree.c house.c ibt.c improved-edit.c interpreter.c limits.c lists.c magic.c mail.c medit.c mobact.c modify.c msgedit.c mud_event.c oasis.c oasis_copy.c oasis_delete.c oasis_list.c objsave.c oedit.c players.c prefedit.c protocol.c qedit.c quest.c random.c redit.c sedit.c shop.c spec_assign.c spec_procs.c spell_parser.c spells.c tedit.c utils.c weather.c zedit.c zmalloc.c +OBJFILES := act.comm.o act.informative.o act.item.o act.movement.o act.offensive.o act.other.o act.social.o act.wizard.o aedit.o asciimap.o ban.o boards.o bsd-snprintf.o castle.o cedit.o class.o comm.o config.o constants.o db.o dg_comm.o dg_db_scripts.o dg_event.o dg_handler.o dg_misc.o dg_mobcmd.o dg_objcmd.o dg_olc.o dg_scripts.o dg_triggers.o dg_variables.o dg_wldcmd.o fight.o genmob.o genobj.o genolc.o genqst.o genshp.o genwld.o genzon.o graph.o handler.o hedit.o htree.o house.o ibt.o improved-edit.o interpreter.o limits.o lists.o magic.o mail.o medit.o mobact.o modify.o msgedit.o mud_event.o oasis.o oasis_copy.o oasis_delete.o oasis_list.o objsave.o oedit.o players.o prefedit.o protocol.o qedit.o quest.o random.o redit.o sedit.o shop.o spec_assign.o spec_procs.o spell_parser.o spells.o tedit.o utils.o weather.o zedit.o zmalloc.o default: all diff -Naur srcbak/objsave.c src/objsave.c --- srcbak/objsave.c 2020-05-24 16:10:43.531380763 -0400 +++ src/objsave.c 2020-05-24 17:46:03.632622091 -0400 @@ -120,6 +120,9 @@ if (TEST_OBJN(wear_flags)) fprintf(fp, "Wear: %d %d %d %d\n", GET_OBJ_WEAR(obj)[0], GET_OBJ_WEAR(obj)[1], GET_OBJ_WEAR(obj)[2], GET_OBJ_WEAR(obj)[3]); + fprintf(fp, "UID : %lld\n", GET_OBJ_UID(obj)); + fprintf(fp, "Gen : %ld\n", GET_OBJ_GENERATION(obj)); + /* Do we have affects? */ for (counter2 = 0; counter2 < MAX_OBJ_AFFECT; counter2++) if (obj->affected[counter2].modifier != temp->affected[counter2].modifier) @@ -1120,6 +1123,10 @@ GET_OBJ_EXTRA(temp)[3] = asciiflag_conv(f4); } break; + case 'G': + if (!strcmp(tag, "Gen ")) + sscanf(line, "%ld", &GET_OBJ_GENERATION(temp)); + break; case 'L': if(!strcmp(tag, "Loc ")) current->locate = num; @@ -1149,6 +1156,10 @@ if (!strcmp(tag, "Type")) GET_OBJ_TYPE(temp) = num; break; + case 'U': + if (!strcmp(tag, "UID ")) + sscanf(line, "%lld", &GET_OBJ_UID(temp)); + break; case 'W': if (!strcmp(tag, "Wear")) { sscanf(line, "%s %s %s %s", f1, f2, f3, f4); @@ -1283,6 +1294,10 @@ if (!temp) /* this should never happen, but.... */ return FALSE; + else if (check_unique_id(temp) == 1) { + extract_obj(temp); + return FALSE; + } auto_equip(ch, temp, locate); diff -Naur srcbak/structs.h src/structs.h --- srcbak/structs.h 2020-05-24 16:10:43.531380763 -0400 +++ src/structs.h 2020-05-24 17:41:36.421023257 -0400 @@ -443,8 +443,9 @@ #define ITEM_ANTI_WARRIOR 15 /**< Not usable by warriors */ #define ITEM_NOSELL 16 /**< Shopkeepers won't touch it */ #define ITEM_QUEST 17 /**< Item is a quest item */ +#define ITEM_UNIQUE_SAVE 18 /** Total number of item flags */ -#define NUM_ITEM_FLAGS 18 +#define NUM_ITEM_FLAGS 19 /* Modifier constants used with obj affects ('A' fields) */ #define APPLY_NONE 0 /**< No effect */ @@ -722,6 +723,9 @@ struct obj_flag_data obj_flags; /**< Object information */ struct obj_affected_type affected[MAX_OBJ_AFFECT]; /**< affects */ + + time_t generation; /* creation time for dupe check */ + unsigned long long unique_id; /* random bits for dupe check */ char *name; /**< Keyword reference(s) for object. */ char *description; /**< Shown when the object is lying in a room. */ @@ -1330,6 +1334,7 @@ int map_size; /**< Default size for map command */ int minimap_size; /**< Default size for mini-map (automap) */ int script_players; /**< Is attaching scripts to players allowed? */ + int all_items_unique; /* Treat all items as unique */ char *OK; /**< When player receives 'Okay.' text. */ char *HUH; /**< 'Huh!?!' */ diff -Naur srcbak/utils.h src/utils.h --- srcbak/utils.h 2020-05-24 16:10:43.535380816 -0400 +++ src/utils.h 2020-05-24 17:19:31.371225633 -0400 @@ -716,6 +716,10 @@ #define GET_OBJ_VAL(obj, val) ((obj)->obj_flags.value[(val)]) /** Weight of obj. */ #define GET_OBJ_WEIGHT(obj) ((obj)->obj_flags.weight) +/** Unique ID of obj */ +#define GET_OBJ_UID(obj) ((obj)->unique_id) +/** Creation date of obj */ +#define GET_OBJ_GENERATION(obj) ((obj)->generation) /** Current timer of obj. */ #define GET_OBJ_TIMER(obj) ((obj)->obj_flags.timer) /** Real number of obj instance. */ @@ -981,6 +985,8 @@ #define CONFIG_DISP_CLOSED_DOORS config_info.play.disp_closed_doors /** Get the diagonal directions setting. */ #define CONFIG_DIAGONAL_DIRS config_info.play.diagonal_dirs +/** Make items all unique */ +#define CONFIG_ALL_ITEMS_UNIQUE config_info.play.all_items_unique /* Map/Automap options */ #define CONFIG_MAP config_info.play.map_option