src/shared/tools.h

   1 // generic useful stuff for any C++ program
   2
   3 #ifndef _TOOLS_H
   4 #define _TOOLS_H
   5
   6 #ifdef NULL
   7 #undef NULL
   8 #endif
   9 #define NULL 0
  10
  11 typedef unsigned char uchar;
  12 typedef unsigned short ushort;
  13 typedef unsigned int uint;
  14
  15 #ifdef _DEBUG
  16 #ifdef __GNUC__
  17 #define ASSERT(c) if(!(c)) { asm("int $3"); }
  18 #else
  19 #define ASSERT(c) if(!(c)) { __asm int 3 }
  20 #endif
  21 #else
  22 #define ASSERT(c) if(c) {}
  23 #endif
  24
  25 #ifdef swap
  26 #undef swap
  27 #endif
  28 template<class T>
  29 static inline void swap(T &a, T &b)
  30 {
  31     T t = a;
  32     a = b;
  33     b = t;
  34 }
  35 #ifdef max
  36 #undef max
  37 #endif
  38 #ifdef min
  39 #undef min
  40 #endif
  41 template<class T>
  42 static inline T max(T a, T b)
  43 {
  44     return a > b ? a : b;
  45 }
  46 template<class T>
  47 static inline T min(T a, T b)
  48 {
  49     return a < b ? a : b;
  50 }
  51
  52 #define clamp(a,b,c) (max(b, min(a, c)))
  53 #define rnd(x) ((int)(randomMT()&0xFFFFFF)%(x))
  54 #define detrnd(s, x) ((int)(((((uint)(s))*1103515245+12345)>>16)%(x)))
  55
  56 #define loop(v,m) for(int v = 0; v<int(m); v++)
  57 #define loopi(m) loop(i,m)
  58 #define loopj(m) loop(j,m)
  59 #define loopk(m) loop(k,m)
  60 #define loopl(m) loop(l,m)
  61
  62
  63 #define DELETEP(p) if(p) { delete   p; p = 0; }
  64 #define DELETEA(p) if(p) { delete[] p; p = 0; }
  65
  66 #define PI  (3.1415927f)
  67 #define PI2 (2*PI)
  68 #define SQRT2 (1.4142136f)
  69 #define SQRT3 (1.7320508f)
  70 #define RAD (PI / 180.0f)
  71
  72 #ifdef WIN32
  73 #ifdef M_PI
  74 #undef M_PI
  75 #endif
  76 #define M_PI 3.14159265
  77
  78 #ifndef __GNUC__
  79 #pragma warning (3: 4189)       // local variable is initialized but not referenced
  80 #pragma warning (disable: 4244) // conversion from 'int' to 'float', possible loss of data
  81 #pragma warning (disable: 4267) // conversion from 'size_t' to 'int', possible loss of data
  82 #pragma warning (disable: 4355) // 'this' : used in base member initializer list
  83 #pragma warning (disable: 4996) // 'strncpy' was declared deprecated
  84 #endif
  85
  86 #define strcasecmp _stricmp
  87 #define PATHDIV '\\'
  88 #else
  89 #define __cdecl
  90 #define _vsnprintf vsnprintf
  91 #define PATHDIV '/'
  92 #endif
  93
  94 // easy safe strings
  95
  96 #define MAXSTRLEN 260
  97 typedef char string[MAXSTRLEN];
  98
  99 inline void formatstring(char *d, const char *fmt, va_list v) { _vsnprintf(d, MAXSTRLEN, fmt, v); d[MAXSTRLEN-1] = 0; }
 100 inline char *s_strncpy(char *d, const char *s, size_t m) { strncpy(d,s,m); d[m-1] = 0; return d; }
 101 inline char *s_strcpy(char *d, const char *s) { return s_strncpy(d,s,MAXSTRLEN); }
 102 inline char *s_strcat(char *d, const char *s) { size_t n = strlen(d); return s_strncpy(d+n,s,MAXSTRLEN-n); }
 103
 104
 105 struct s_sprintf_f
 106 {
 107     char *d;
 108     s_sprintf_f(char *str): d(str) {}
 109     void operator()(const char* fmt, ...)
 110     {
 111         va_list v;
 112         va_start(v, fmt);
 113         formatstring(d, fmt, v);
 114         va_end(v);
 115     }
 116 };
 117
 118 #define s_sprintf(d) s_sprintf_f((char *)d)
 119 #define s_sprintfd(d) string d; s_sprintf(d)
 120 #define s_sprintfdlv(d,last,fmt) string d; { va_list ap; va_start(ap, last); formatstring(d, fmt, ap); va_end(ap); }
 121 #define s_sprintfdv(d,fmt) s_sprintfdlv(d,fmt,fmt)
 122
 123 #define loopv(v)    if(false) {} else for(int i = 0; i<(v).length(); i++)
 124 #define loopvj(v)   if(false) {} else for(int j = 0; j<(v).length(); j++)
 125 #define loopvk(v)   if(false) {} else for(int k = 0; k<(v).length(); k++)
 126 #define loopvrev(v) if(false) {} else for(int i = (v).length()-1; i>=0; i--)
 127
 128 template <class T>
 129 struct databuf
 130 {
 131     enum
 132     {
 133         OVERREAD  = 1<<0,
 134         OVERWROTE = 1<<1
 135     };
 136
 137     T *buf;
 138     int len, maxlen;
 139     uchar flags;
 140
 141     template<class U>
 142     databuf(T *buf, U maxlen) : buf(buf), len(0), maxlen((int)maxlen), flags(0) {}
 143
 144     const T &get()
 145     {
 146         static T overreadval;
 147         if(len<maxlen) return buf[len++];
 148         flags |= OVERREAD;
 149         return overreadval;
 150     }
 151
 152     databuf subbuf(int sz)
 153     {
 154         sz = min(sz, maxlen-len);
 155         len += sz;
 156         return databuf(&buf[len-sz], sz);
 157     }
 158
 159     void put(const T &val)
 160     {
 161         if(len<maxlen) buf[len++] = val;
 162         else flags |= OVERWROTE;
 163     }
 164
 165     void put(const T *vals, int numvals)
 166     {
 167         if(maxlen-len<numvals) flags |= OVERWROTE;
 168         memcpy(&buf[len], vals, min(maxlen-len, numvals)*sizeof(T));
 169         len += min(maxlen-len, numvals);
 170     }
 171
 172     int get(T *vals, int numvals)
 173     {
 174         int read = min(maxlen-len, numvals);
 175         if(read<numvals) flags |= OVERREAD;
 176         memcpy(vals, &buf[len], read*sizeof(T));
 177         len += read;
 178         return read;
 179     }
 180
 181     int length() const { return len; }
 182     int remaining() const { return maxlen-len; }
 183     bool overread() const { return flags&OVERREAD; }
 184     bool overwrote() const { return flags&OVERWROTE; }
 185
 186     void forceoverread()
 187     {
 188         len = maxlen;
 189         flags |= OVERREAD;
 190     }
 191 };
 192
 193 typedef databuf<char> charbuf;
 194 typedef databuf<uchar> ucharbuf;
 195
 196 template <class T> struct vector
 197 {
 198     static const int MINSIZE = 8;
 199
 200     T *buf;
 201     int alen, ulen;
 202
 203     vector() : buf(NULL), alen(0), ulen(0)
 204     {
 205     }
 206
 207     vector(const vector &v) : buf(NULL), alen(0), ulen(0)
 208     {
 209         *this = v;
 210     }
 211
 212     ~vector() { setsize(0); if(buf) delete[] (uchar *)buf; }
 213
 214     vector<T> &operator=(const vector<T> &v)
 215     {
 216         setsize(0);
 217         if(v.length() > alen) vrealloc(v.length());
 218         loopv(v) add(v[i]);
 219         return *this;
 220     }
 221
 222     T &add(const T &x)
 223     {
 224         if(ulen==alen) vrealloc(ulen+1);
 225         new (&buf[ulen]) T(x);
 226         return buf[ulen++];
 227     }
 228
 229     T &add()
 230     {
 231         if(ulen==alen) vrealloc(ulen+1);
 232         new (&buf[ulen]) T;
 233         return buf[ulen++];
 234     }
 235
 236     T &dup()
 237     {
 238         if(ulen==alen) vrealloc(ulen+1);
 239         new (&buf[ulen]) T(buf[ulen-1]);
 240         return buf[ulen++];
 241     }
 242
 243     void move(vector<T> &v)
 244     {
 245         if(!ulen)
 246         {
 247             swap(buf, v.buf);
 248             swap(ulen, v.ulen);
 249             swap(alen, v.alen);
 250         }
 251         else
 252         {
 253             vrealloc(ulen+v.ulen);
 254             if(v.ulen) memcpy(&buf[ulen], v.buf, v.ulen*sizeof(T));
 255             ulen += v.ulen;
 256             v.ulen = 0;
 257         }
 258     }
 259
 260     bool inrange(size_t i) const { return i<size_t(ulen); }
 261     bool inrange(int i) const { return i>=0 && i<ulen; }
 262
 263     T &pop() { return buf[--ulen]; }
 264     T &last() { return buf[ulen-1]; }
 265     void drop() { buf[--ulen].~T(); }
 266     bool empty() const { return ulen==0; }
 267
 268     int length() const { return ulen; }
 269     T &operator[](int i) { ASSERT(i>=0 && i<ulen); return buf[i]; }
 270     const T &operator[](int i) const { ASSERT(i >= 0 && i<ulen); return buf[i]; }
 271
 272     void setsize(int i)         { ASSERT(i<=ulen); while(ulen>i) drop(); }
 273     void setsizenodelete(int i) { ASSERT(i<=ulen); ulen = i; }
 274
 275     void deletecontentsp() { while(!empty()) delete   pop(); }
 276     void deletecontentsa() { while(!empty()) delete[] pop(); }
 277
 278     T *getbuf() { return buf; }
 279     const T *getbuf() const { return buf; }
 280
 281     template<class ST>
 282     void sort(int (__cdecl *cf)(ST *, ST *), int i = 0, int n = -1)
 283     {
 284         qsort(&buf[i], n<0 ? ulen : n, sizeof(T), (int (__cdecl *)(const void *,const void *))cf);
 285     }
 286
 287     void vrealloc(int sz)
 288     {
 289         int olen = alen;
 290         if(!alen) alen = max(MINSIZE, sz);
 291         else while(alen < sz) alen *= 2;
 292         if(alen <= olen) return;
 293         uchar *newbuf = new uchar[alen*sizeof(T)];
 294         if(olen > 0)
 295         {
 296             memcpy(newbuf, buf, olen*sizeof(T));
 297             delete[] (uchar *)buf;
 298         }
 299         buf = (T *)newbuf;
 300     }
 301
 302     databuf<T> reserve(int sz)
 303     {
 304         if(ulen+sz > alen) vrealloc(ulen+sz);
 305         return databuf<T>(&buf[ulen], sz);
 306     }
 307
 308     void advance(int sz)
 309     {
 310         ulen += sz;
 311     }
 312
 313     void addbuf(const databuf<T> &p)
 314     {
 315         advance(p.length());
 316     }
 317
 318     void put(const T *v, int n)
 319     {
 320         databuf<T> buf = reserve(n);
 321         buf.put(v, n);
 322         addbuf(buf);
 323     }
 324
 325     void remove(int i, int n)
 326     {
 327         for(int p = i+n; p<ulen; p++) buf[p-n] = buf[p];
 328         ulen -= n;
 329     }
 330
 331     T remove(int i)
 332     {
 333         T e = buf[i];
 334         for(int p = i+1; p<ulen; p++) buf[p-1] = buf[p];
 335         ulen--;
 336         return e;
 337     }
 338
 339     template<class U>
 340     int find(const U &o)
 341     {
 342         loopi(ulen) if(buf[i]==o) return i;
 343         return -1;
 344     }
 345
 346     void removeobj(const T &o)
 347     {
 348         loopi(ulen) if(buf[i]==o) remove(i--);
 349     }
 350
 351     void replacewithlast(const T &o)
 352     {
 353         if(!ulen) return;
 354         loopi(ulen-1) if(buf[i]==o)
 355         {
 356             buf[i] = buf[ulen-1];
 357         }
 358         ulen--;
 359     }
 360
 361     T &insert(int i, const T &e)
 362     {
 363         add(T());
 364         for(int p = ulen-1; p>i; p--) buf[p] = buf[p-1];
 365         buf[i] = e;
 366         return buf[i];
 367     }
 368
 369     T *insert(int i, const T *e, int n)
 370     {
 371         if(ulen+n>alen) vrealloc(ulen+n);
 372         loopj(n) add(T());
 373         for(int p = ulen-1; p>=i+n; p--) buf[p] = buf[p-n];
 374         loopj(n) buf[i+j] = e[j];
 375         return &buf[i];
 376     }
 377
 378     void reverse()
 379     {
 380         loopi(ulen/2) swap(buf[i], buf[ulen-1-i]);
 381     }
 382 };
 383
 384 typedef vector<char *> cvector;
 385 typedef vector<int> ivector;
 386 typedef vector<ushort> usvector;
 387
 388 static inline uint hthash(const char *key)
 389 {
 390     uint h = 5381;
 391     for(int i = 0, k; (k = key[i]); i++) h = ((h<<5)+h)^k;    // bernstein k=33 xor
 392     return h;
 393 }
 394
 395 static inline bool htcmp(const char *x, const char *y)
 396 {
 397     return !strcmp(x, y);
 398 }
 399
 400 static inline uint hthash(int key)
 401 {
 402     return key;
 403 }
 404
 405 static inline bool htcmp(int x, int y)
 406 {
 407     return x==y;
 408 }
 409
 410 template <class K, class T> struct hashtable
 411 {
 412     typedef K key;
 413     typedef const K const_key;
 414     typedef T value;
 415     typedef const T const_value;
 416
 417     enum { CHUNKSIZE = 64 };
 418
 419     struct chain      { T data; K key; chain *next; };
 420     struct chainchunk { chain chains[CHUNKSIZE]; chainchunk *next; };
 421
 422     int size;
 423     int numelems;
 424     chain **table;
 425     chain *enumc;
 426
 427     chainchunk *chunks;
 428     chain *unused;
 429
 430     hashtable(int size = 1<<10)
 431       : size(size)
 432     {
 433         numelems = 0;
 434         chunks = NULL;
 435         unused = NULL;
 436         table = new chain *[size];
 437         loopi(size) table[i] = NULL;
 438     }
 439
 440     ~hashtable()
 441     {
 442         DELETEA(table);
 443     }
 444
 445     chain *insert(const K &key, uint h)
 446     {
 447         if(!unused)
 448         {
 449             chainchunk *chunk = new chainchunk;
 450             chunk->next = chunks;
 451             chunks = chunk;
 452             loopi(CHUNKSIZE-1) chunk->chains[i].next = &chunk->chains[i+1];
 453             chunk->chains[CHUNKSIZE-1].next = unused;
 454             unused = chunk->chains;
 455         }
 456         chain *c = unused;
 457         unused = unused->next;
 458         c->key = key;
 459         c->next = table[h];
 460         table[h] = c;
 461         numelems++;
 462         return c;
 463     }
 464
 465     chain *find(const K &key, bool doinsert)
 466     {
 467         uint h = hthash(key)&(size-1);
 468         for(chain *c = table[h]; c; c = c->next)
 469         {
 470             if(htcmp(key, c->key)) return c;
 471         }
 472         if(doinsert) return insert(key, h);
 473         return NULL;
 474     }
 475
 476     T *access(const K &key, const T *data = NULL)
 477     {
 478         chain *c = find(key, data != NULL);
 479         if(data) c->data = *data;
 480         if(c) return &c->data;
 481         return NULL;
 482     }
 483
 484     T &operator[](const K &key)
 485     {
 486         return find(key, true)->data;
 487     }
 488
 489     bool remove(const K &key)
 490     {
 491         uint h = hthash(key)&(size-1);
 492         for(chain **p = &table[h], *c = table[h]; c; p = &c->next, c = c->next)
 493         {
 494             if(htcmp(key, c->key))
 495             {
 496                 *p = c->next;
 497                 c->data.~T();
 498                 c->key.~K();
 499                 new (&c->data) T;
 500                 new (&c->key) K;
 501                 c->next = unused;
 502                 unused = c->next;
 503                 numelems--;
 504                 return true;
 505             }
 506         }
 507         return false;
 508     }
 509
 510     void clear()
 511     {
 512         if(!numelems) return;
 513         loopi(size) table[i] = NULL;
 514         numelems = 0;
 515         unused = NULL;
 516         for(chainchunk *nextchunk; chunks; chunks = nextchunk)
 517         {
 518             nextchunk = chunks->next;
 519             delete chunks;
 520         }
 521     }
 522 };
 523
 524 #define enumeratekt(ht,k,e,t,f,b) loopi((ht).size)  for(hashtable<k,t>::chain *enumc = (ht).table[i]; enumc; enumc = enumc->next) { hashtable<k,t>::const_key &e = enumc->key; t &f = enumc->data; b; }
 525 #define enumerate(ht,t,e,b)       loopi((ht).size) for((ht).enumc = (ht).table[i]; (ht).enumc; (ht).enumc = (ht).enumc->next) { t &e = (ht).enumc->data; b; }
 526
 527 struct unionfind
 528 {
 529     struct ufval
 530     {
 531         int rank, next;
 532
 533         ufval() : rank(0), next(-1) {}
 534     };
 535
 536     vector<ufval> ufvals;
 537
 538     int find(int k)
 539     {
 540         if(k>=ufvals.length()) return k;
 541         while(ufvals[k].next>=0) k = ufvals[k].next;
 542         return k;
 543     }
 544
 545     int compressfind(int k)
 546     {
 547         if(ufvals[k].next<0) return k;
 548         return ufvals[k].next = compressfind(ufvals[k].next);
 549     }
 550
 551     void unite (int x, int y)
 552     {
 553         while(ufvals.length() <= max(x, y)) ufvals.add();
 554         x = compressfind(x);
 555         y = compressfind(y);
 556         if(x==y) return;
 557         ufval &xval = ufvals[x], &yval = ufvals[y];
 558         if(xval.rank < yval.rank) xval.next = y;
 559         else
 560         {
 561             yval.next = x;
 562             if(xval.rank==yval.rank) yval.rank++;
 563         }
 564     }
 565 };
 566
 567 template <class T, int SIZE> struct ringbuf
 568 {
 569     int index, len;
 570     T data[SIZE];
 571
 572     ringbuf() { clear(); }
 573
 574     void clear()
 575     {
 576         index = len = 0;
 577     }
 578
 579     bool empty() const { return !len; }
 580
 581     const int length() const { return len; }
 582
 583     T &add(const T &e)
 584     {
 585         T &t = data[index];
 586         t = e;
 587         index++;
 588         if(index>=SIZE) index = 0;
 589         if(len<SIZE) len++;
 590         return t;
 591     }
 592
 593     T &add() { return add(T()); }
 594
 595     T &operator[](int i)
 596     {
 597         int start = index - len;
 598         if(start < 0) start += SIZE;
 599         i += start;
 600         if(i >= SIZE) i -= SIZE;
 601         return data[i];
 602     }
 603
 604     const T &operator[](int i) const
 605     {
 606         int start = index - len;
 607         if(start < 0) start += SIZE;
 608         i += start;
 609         if(i >= SIZE) i -= SIZE;
 610         return data[i];
 611     }
 612 };
 613
 614 inline char *newstring(size_t l)                { return new char[l+1]; }
 615 inline char *newstring(const char *s, size_t l) { return s_strncpy(newstring(l), s, l+1); }
 616 inline char *newstring(const char *s)           { return newstring(s, strlen(s));          }
 617 inline char *newstringbuf(const char *s)        { return newstring(s, MAXSTRLEN-1);       }
 618
 619 #if defined(WIN32) && !defined(__GNUC__)
 620 #ifdef _DEBUG
 621 //#define _CRTDBG_MAP_ALLOC
 622 #include <crtdbg.h>
 623 inline void *__cdecl operator new(size_t n, const char *fn, int l) { return ::operator new(n, 1, fn, l); }
 624 inline void __cdecl operator delete(void *p, const char *fn, int l) { ::operator delete(p, 1, fn, l); }
 625 #define new new(__FILE__,__LINE__)
 626 #endif
 627 #endif
 628
 629 extern char *makerelpath(const char *dir, const char *file, const char *prefix = NULL);
 630 extern char *path(char *s);
 631 extern char *path(const char *s, bool copy);
 632 extern const char *parentdir(const char *directory);
 633 extern bool fileexists(const char *path, const char *mode);
 634 extern bool createdir(const char *path);
 635 extern void sethomedir(const char *dir);
 636 extern void addpackagedir(const char *dir);
 637 extern const char *findfile(const char *filename, const char *mode);
 638 extern FILE *openfile(const char *filename, const char *mode);
 639 extern gzFile opengzfile(const char *filename, const char *mode);
 640 extern char *loadfile(const char *fn, int *size);
 641 extern bool listdir(const char *dir, const char *ext, vector<char *> &files);
 642 extern int listfiles(const char *dir, const char *ext, vector<char *> &files);
 643 extern void endianswap(void *, int, int);
 644 extern void seedMT(uint seed);
 645 extern uint randomMT(void);
 646
 647 #endif
 648