// 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 <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#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)));
}
}