// VERS 2.1 ///* new.bit.c -- infinite bitmask system */// // This is Runter's system for infinite bits. It was made for use // in Feltain. I, Runter, require no credit, no // help file documentation of your use, and no email confirmation. // The only thing I do ask is if you find a bug or have a major change // that makes the system more efficient or more intelligent than // let me know about it. Just remember what goes around comes around. // We all benifit when we work together. // // To successfully use this you will use the variable BITMASK // "BITMASK act;" // instead of int in your struct declarations for your bitmasks. // On this new variable type just pass the variables address to // the new functions-- set_bit, remove_bit, is_set. // example: if(is_set(&ch->act, ACT_NPC)) // // This system passes normal numbers as the bits so you'll need // to redeclare stuff as you are passing it. // // if(is_set(&ch->act, 400)) // is the 400th bit set? // // A good way to change your entire system over would be to redo // your definitions of A B C D E... aa bb cc and such from defines // to one enum struct. // // Another important note is that you need to use the new loading // and saving functions provided when saving your bitmasks. It // saves them to a single line and loads them from a single line. // // Technical note: This system will only use memory required for the // size of your bitmask. It allocates memory as needed only. This does // use malloc() and free(). Some servers have memory management systems // in with their own functions. Feel free to change it how you see fit. // If you need any more help installing the system you can find me at // feltain.org 7777 or aim me at jeffreybasurto. // VERS 2 // In version 2 it still maintains the above functionality with fixes // but also lets you serialize your bitmask to an array of values // as well as free and initilize it easily. // // I use this system as a high level solution to linked lists and have // used it for my char_list, obj_list, and other places. It is // efficient enough to do this and actually saves you managing linked // lists and next pointers of ANY kind. It can be adapted for room lists // for objects and players or global lists. This is an abstract data // type and you can NOT use this as a queue. Ie, the order you set it // in will not be the order it comes out serialized. It will sort the // serialization in no particular way like a linked list does. // // This system also allows you to use qsort out of the box after calling // serialize_bitmask(). // // After getting your array after calling serialize_bitmask() you will have // to loop through it to get what is in the list and it will be NUL // terminated like a string. It can be of any size so don't assume, please. // // Report any bugs or additions you have made please!! Any praise is // appreciated as well. ^_- I spent a lot of intellectual time trying // to think of a good implementation of this. #include #include #include #include #include #include "merc.h" /* This struct stuff goes in your global.h -- usually * merc.h or mud.h ************************************************* typedef struct bmlist BMlist; struct bmlist { BMlist *next; long set; long tar_mask; }; typedef struct bitmask { long bits; // number of bits set in total. long masks; // number of masks in all. BMlist *int_list; } BITMASK; *************************************************/ // returns false if no removal. True if so. int remove_bit(BITMASK *mask, int bit) { BMlist *pBlist, *last = 0; if (!is_set(mask, bit)) // nothing doing. It isn't set. return FALSE; --bit; // loop through each bitmask we have allocated for(pBlist = mask->int_list;pBlist;pBlist = pBlist->next) { if (pBlist->set == bit / 32) {// Is this the correct set? pBlist->tar_mask &= ~(1 << (bit % 32)); // remove it. --mask->bits; if (pBlist->tar_mask == 0) { if (last) last->next = pBlist->next; else mask->int_list = pBlist->next; free(pBlist); --mask->masks; } return TRUE; } last = pBlist; } return FALSE; // a bug happened. Wee. Somehow. } // returns true if a bit was set. Returns 2 if had to allocate. // False if already set. int set_bit(BITMASK *mask, int bit) { BMlist *pBlist; --bit; // loop through each bitmask we have already allocated. for(pBlist = mask->int_list;pBlist;pBlist = pBlist->next) { if (pBlist->set == bit / 32) { // Is this the correct set? if (pBlist->tar_mask & (1 << (bit % 32))) return FALSE; // Already set. pBlist->tar_mask |= 1 << (bit % 32); // Set our bit inside the mask. ++mask->bits; return 1; // return true with no allocation } } // Not found but not set. We have to allocate and add to the list. pBlist = malloc(sizeof(BMlist)); ++mask->masks; pBlist->next = mask->int_list; mask->int_list = pBlist; pBlist->tar_mask = 0; pBlist->set = bit / 32; pBlist->tar_mask |= 1 << (bit % 32); // set our bit on new mask ++mask->bits; return 2; // return true with allocation } int is_set(BITMASK *mask, int bit) { BMlist *pBlist; --bit; for(pBlist = mask->int_list;pBlist;pBlist = pBlist->next) if (pBlist->set == bit / 32) { if (pBlist->tar_mask & 1 << (bit % 32)) return TRUE; else return FALSE; } return FALSE; } // Let's serialize this and return all bits that are set in a dynamic list. // This is useful when you just want to know what to traverse in a bitmask. // Good for high level solutions to lists of pointers! This is a high level // solution that *does not* maintain an ordered queue for specific BFS or // DFS algorithms. This is for algorithms that do not matter. int *serialize_bitmask(BITMASK *mask) { BMlist *pBlist; int *ilist = malloc(sizeof(int) * mask->bits + 1), i = 0, z; ilist[mask->bits] = 0; // zero terminates it. 0th bit CAN NOT BE SET. for(pBlist = mask->int_list;pBlist;pBlist = pBlist->next) { for(z = 0;z < 32;++z) { if (i > mask->bits) { // more found than we have allocated. Maybe residual. // May add a check before setting ilist to make sure it // doesn't over run but this should be fine. Just don't // bug it here for sure. It may not be an error at this // point. If you do decide to error check this better // this break should be replaced to let it go through. break; } if (pBlist->tar_mask & 1 << z) ilist[i++] = pBlist->set * 32 + z + 1; } } if (i < mask->bits + 1) { // error. We have less recorded bits than we allocated. } // This must be freed somewhere with free(ilist) or it will leak. // Using a static buffer here would be a poor idea. Using temporary // memory allocation would be a good one. Too bad there isn't an // ANSI thing for that in C. return ilist; } // Frees your bitmask. Safe to call dry. Returns 2 if // it frees anything. 1 if it doesn't. int free_bitmask(BITMASK *pBmask) { BMlist *pBMlist, *next; int found = 1; for(pBMlist = pBmask->int_list;pBMlist;pBMlist = next) { next = pBMlist->next; free_mem(pBMlist); found = 2; } return found; } // initialze a bitmask. // bm = init_bitmask(NULL); // init_bitmask(&bm); // Both of above work. BITMASK init_bitmask(BITMASK *bm) { static BITMASK bmzero; if (bm == 0) return bmzero; *bm = bmzero; return bmzero; } // #masks #bits #mask #vector #mask #vector ... void load_bitmask(BITMASK *pBmask, FILE *fp) { int i; BMlist *pBMlist; pBmask->masks = fread_number(fp); pBmask->bits = fread_number(fp); for(i = 0;i < pBmask->masks;++i) { pBMlist = malloc(sizeof(BMlist)); pBMlist->set = fread_number(fp); pBMlist->next = pBmask->int_list; pBmask->int_list = pBMlist; pBMlist->tar_mask = fread_number(fp); } } void save_bitmask(BITMASK *pBmask, FILE *fp) { BMlist *pBMlist; fprintf(fp, "%d %d", pBmask->masks, pBmask->bits); for(pBMlist = pBmask->int_list;pBMlist;pBMlist = pBMlist->next) fprintf(fp, " %d %ld", pBMlist->set, pBMlist->tar_mask); fprintf(fp, "\n"); } // Pop a single element from the list. It's abstract so remember // that it will probably be a random item. You can not assume it won't // be. We could fix this but it'd take more memory. Don't use this // unless pop order doesn't matter. Use std::stack or something...or // a raw linked list in C if it does matter. void *pop_bitmask(BITMASK *pBmask) { void **vlist = 0; void *vp = 0; vlist = serialize_bitmask(pBmask); if (vlist[0]) vp = vlist[0]; if (vp) remove_bit(pBmask, (int)vp); return vp; } // All this goes in the your new.bit.c file with the rest of the functions for bitmasks. // converts an int to exflags. // The format is // (A)(B)(C)(D) ... (Z) // Then for number greater than 32 // (AA)(BB) ... (ZZ) // then it starts over for greater numbers // (AAA)(BBB) ... (ZZZ) // This lets have a string value for *any* amount of flags. char *int_to_flag(int value) { static char buffer[256]; char face_value = 'A' + ((value-1) % 26); // Convert any number into 'A' - 'Z' int multiple = (value-1) / 26 + 1; // how many of the face value buffer[0] = 0; if (value == 0) { // 0 is no bit. return buffer; } strcpy(buffer, "("); while(multiple--) { // Now we put them char buf[32]; sprintf(buf, "%c", face_value); strcat(buffer, buf); } strcat(buffer, ")"); return buffer; } //returns a flag back to the int format. int flag_to_int(char *flag) { char *ptr = flag; int value; int count = 0; while(*ptr && *ptr == '(') ptr++; value = *ptr - 'A' + 1; ++ptr; while(*ptr && *ptr != ')') ptr++, count++; return value + (26 * count); } // Saves a bitmask using Extended Flags Format. void save_bitmask_flags(BITMASK *pBmask, FILE *fp) { int *ilist = (int *)serialize_bitmask(pBmask); BMlist *pBMlist; char buf[1000]; int i; buf[0] = 0; for(i = 0;ilist[i];++i) { strcat(buf, int_to_flag(ilist[i])); } fprintf(fp, "%d Masks %d flags %s~\r\n", pBmask->masks, pBmask->bits, buf); } // get one exflag from an argument and return pointer char *one_exflag(char *p, char *flag) { int count = 0; while(*p&& *p != '(') { p++; } if (!*p) return 0; p++; flag[count] = '('; count++; while(*p && *p != ')') { flag[count] = *p; count++, p++; } p++; flag[count] = ')'; count++; flag[count] = 0; return p; } // Loads a bitmask from an extended flags format. void load_bitmask_flags(BITMASK *bm, FILE *fp) { init_bitmask(bm); char temp[1000]; char buf[126]; char *p; bm->masks = fread_number(fp); /* = */ fread_word(fp); // winds us forward to the next number bm->bits = fread_number(fp); /* = */ fread_word(fp); // winds us again. //Now we're to our flags. p = fread_string(fp); strcpy(temp, p); free_string(p); p = temp; while(*p && *p == ' ') ++p; while ((p = one_exflag(p, buf)) != 0) { set_bit(bm, flag_to_int(buf)); } } // This could be useful. It dumps the contents of a bitmask into a string and returns the string. char *dump_bitmask(BITMASK *bm) { int *ilist= (int *) serialize_bitmask(bm); static char dump[500]; // int i; dump[0] = 0; for(i = 0; ilist[i];++i) { char buf[256]; sprintf(buf, "%d ", ilist[i]); strcat(dump, buf); } free (ilist); return dump; } // Command function I used to test the new stuff with. void do_bitmasktest(CHAR_DATA*ch, char *arg) { BITMASK bm = init_bitmask(NULL); int i = number_range(15, 25); while(i--) set_bit(&bm, number_range(5, 100)); set_bit(&bm, 1); printf_to_char(ch, "%s\r\n", dump_bitmask(&bm)); { FILE *fp = fopen("../data/bitmasktest.txt", "w"); save_bitmask_flags(&bm, fp); fclose(fp); } printf_to_char(ch, "%s\r\n", dump_bitmask(&bm)); { FILE *fp = fopen("../data/bitmasktest.txt", "r"); load_bitmask_flags(&bm, fp); fclose(fp); } printf_to_char(ch, "%s\r\n", dump_bitmask(&bm)); { int r = number_range(1, 200); printf_to_char(ch, "%d %d",r, flag_to_int(int_to_flag(r))); } }