DZone Snippets: c code

Disk/flash benchmark

sandos (John Bäckstrand) — Thu, 24 Jul 2008 16:50:04 GMT

Adapted from a LKML posted program. I think I added write support, this for benchmarking random access writes on flash.



/* Simple multi-threaded I/O benchmark program.

 * Copyright (C) Michael Tokarev, mjt@tls.msk.ru

 * Public domain.

 *

 * To compile:

 *   gcc -o iot iot.c -lpthread

 * To run:

 *   Either with disk device or with pre-existing file.

 *    ./iot [options] filename

 *   Filename is the file or device to test on.

 *   By default it uses 8Kb I/O blocks and does sequential read test

 *   until interrupted.

 *   To indicate when to stop:

 *     -t sec - run for this many seconds, say, 30, to eliminate random

 *       noise.

 *     -i num - perform this many I/O operations

 *   To indicate R/W mode:

 *     -wn, -Wn, -rn, -Rn --

 *       perform linear or random write (note: all data will be lost!),

 *       or linear or random read, using given number of threads (n).

 *   I/O modes:

 *    -s - syncronous write (O_SYNC)

 *    -d - direct I/O (O_DIRECT)

 *    -b bs - block size in bytes

 *   And finally:

 *    -h - display usage.

 * Example:

 *   ./iot -t30 -W4 -R4 -d -b8192 /dev/sdb

 * perform random read/write test (4 readers and 4 writers)

 * for 30 seconds using direct I/O and block size of 8Kb.

 *

 * Note: for small blocksize (<64Kb at least) and using direct random I/O,

 * nowadays drives sometimes gives transfer rates below 1Mb/sec - this is

 * expectable, don't be afraid of so low numbers.  The reason is simple:

 * in order to access a given block of data, a disk drive has to seek to the

 * right track (average seek time) and wait for the right sector to be near

 * the head (rotation latency).  Sum up the two, and divide 1 sec to the

 * result -- you'll have max number of requests/sec a drive can perform,

 * not counting the actual data transfer (which reduces this number further).

 * With, say, 5ms seek time + rotation latency, we'll have 200 requests/sec,

 * which, with 4Kb request size, will be about 800Kb/sec - which is below

 * 1Mb/sec, not counting the actual transfer...

 *

 */



#define _GNU_SOURCE

#define _BSD_SOURCE

#define _LARGEFILE_SOURCE

#define _FILE_OFFSET_BITS 64



//#define USE_DEV_URANDOM       /* was not a good idea */



#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 



#ifndef BLKGETSIZE64

#define BLKGETSIZE64 _IOR(0x12,114,size_t)

 /* linux-specific. return device size in bytes (u64 *arg) */

#endif



static void edie(const char *what) {

  fprintf(stderr, "%s: %m \n", what);

  exit(1);

}



#ifdef USE_DEV_URANDOM

static int randfd;

#endif

static int oflags;              // open flags

static char *fn;                // filename

static unsigned bs = 8192;      // block size

static unsigned bc;             // block count (device size in blocks)

static unsigned bm;             // blocks to do



#define MFrnd   1

#define MFwrt   2

#define LinRd   0

#define RndRd   MFrnd

#define LinWr   MFwrt

#define RndWr   (MFrnd|MFwrt)



struct state {

  int fd;

  char *buf;

  unsigned ioc;         // I/O count

  int (*workfn)(struct state *, unsigned blocknr);

  unsigned (*posfn)(struct state *s);

  unsigned opi;         // operation index

  unsigned i;           // curidx

  double stime;         // start time

  unsigned bn;          // current block number for linear i/o

};

static unsigned int alternate;

static unsigned tioc;   // total i/o count

static struct state *states;

static unsigned nt[4];

static unsigned ntt;

static volatile unsigned running;

static const char *const ion[4] = { "LinRd", "RndRd", "LinWr", "RndWr" };



static pthread_mutex_t rnmtx = PTHREAD_MUTEX_INITIALIZER;

static pthread_cond_t rncond = PTHREAD_COND_INITIALIZER;



static double curtime(void) {

  struct timeval tv;

  gettimeofday(&tv, NULL);

  return tv.tv_sec + tv.tv_usec / 1000000.0;

}



static unsigned randpos(struct state *s) {

  unsigned n;

#ifdef USE_DEV_URANDOM

  read(randfd, &n, sizeof(n));

#else

  n = lrand48();

#endif

  s = s;

  if(alternate == 1) {

    if(n > bc/2) {

      return bc-1;

    } else {

      return 0;

    }

  }

  return n % bc;

}



static unsigned linpos(struct state *s) {

  if (s->bn >= bc)

    s->bn = 0;

  return s->bn++;

}



static int wwriter(struct state *s, unsigned b) {

  return pwrite(s->fd, s->buf, bs, (off_t)b * bs);

}

static int wreader(struct state *s, unsigned b) {

  return pread(s->fd, s->buf, bs, (off_t)b * bs);

}



static void pst(FILE *f) {

  double ct = curtime();

  double r[4] = { 0, 0, 0, 0 };

  unsigned c[4] = { 0, 0, 0, 0 };

  unsigned i;

  double d;

  for(i = 0; i < ntt; ++i) {

    d = ct - states[i].stime;

    r[states[i].opi] += states[i].ioc / d;

    c[states[i].opi] += states[i].ioc;

  }

#if 1

  for(i = 0; i < 4; ++i)

    if (c[i])

      fprintf(f, " %s %u %.2f", ion[i], c[i], r[i] * bs / 1024 / 1024);

#endif

}



static void incc() {

  if (!(++tioc % 1000))

    pthread_cond_signal(&rncond);

}

static void decnr() {

  pthread_mutex_lock(&rnmtx);

  --running;

  pthread_mutex_unlock(&rnmtx);

  pthread_cond_broadcast(&rncond);

}



static volatile int term;



void *worker(void *arg) {

  struct state *s = arg;

  s->workfn = s->opi & MFwrt ? wwriter : wreader;

  s->posfn  = s->opi & MFrnd ? randpos : linpos;

  s->fd = open(fn, (s->opi & MFwrt ? O_WRONLY : O_RDONLY) | oflags);

  if (s->fd < 0) {

    int e = errno;

    decnr();

    errno = e;

    edie(fn);

  }

  s->stime = curtime();

  for(;;) {

    if (term) break;

    if (s->workfn(s, s->posfn(s)) < 0) {

      perror(ion[s->opi]);

      break;

    }

    ++s->ioc;

    incc();

    if (bm && s->ioc >= bm) break;

  }

  decnr();

  return 0;

}



static void sig(int s) {

  term = s;

}



int main(int argc, char **argv) {

  int c;

  unsigned i, j;

  unsigned tm = 0;

  struct state *s;

  char *buf;

  struct timeval  first,

                second,

                lapsed;



  while((c = getopt(argc, argv, "r::R::w::W::adsb:n:i:t:h")) != EOF) switch(c) {

  case 'r': nt[LinRd] = optarg ? atoi(optarg) : 1; break;

  case 'R': nt[RndRd] = optarg ? atoi(optarg) : 1; break;

  case 'w': nt[LinWr] = optarg ? atoi(optarg) : 1; break;

  case 'W': nt[RndWr] = optarg ? atoi(optarg) : 1; break;

  case 'd': oflags |= O_DIRECT; break;

  case 's': oflags |= O_SYNC; break;

  case 'b': bs = atoi(optarg); break;

  case 'n': bc = atoi(optarg); break;

  case 'i': bm = atoi(optarg); break;

  case 't': tm = atoi(optarg); break;

  case 'a': alternate = 1; break;

  case 'h':

    puts(

"iotest: perform I/O speed test\n"

"Usage is: iotest [options] device-or-file\n"

"options:\n"

" -r[n] - linear read test (n readers)\n"

" -R[n] - random read test (n readers)\n"

" -w[n] - linear write test (n writers)\n"

" -W[n] - random write test (n writers)\n"

" -d - use direct I/O (O_DIRECT)\n"

" -s - use syncronous I/O (O_SYNC)\n"

" -b bs - blocksize (default is 8192)\n"

" -n bc - block count (default is whole device/file)\n"

" -i nb - number of I/O iterations to perform\n"

" -t sec - time to spend on all I/O\n"

" -h - this help\n"

"It's ok to specify all, one or some of -r,-R,-w and -W\n"

);

    return 0;

  default: fprintf(stderr, "try `iotest -h' for help\n"); exit(1);

  }



  if (optind + 1 != argc) {

    fprintf(stderr, "exactly one device/file argument expected\n");

    return 1;

  }

  fn = argv[optind];



  ntt = nt[0] + nt[1] + nt[2] + nt[3];

  if (!ntt)

    nt[LinRd] = ntt = 1;



  c = open(fn, (nt[LinWr] + nt[RndWr] ? O_RDWR : O_RDONLY) | oflags);

  if (c < 0) edie(fn);

  if (!bc) {

    unsigned long long sz;

    struct stat st;

    fstat(c, &st);

    if (st.st_size) sz = st.st_size;

    else ioctl(c, BLKGETSIZE64, &sz);

    bc = sz / bs;

    fprintf(stderr, "size = %lld (%u blocks)\n", sz, bc);

  }

  close(c);

  if (nt[RndRd] || nt[RndWr]) {

#ifdef USE_DEV_URANDOM

    randfd = open("/dev/urandom", O_RDONLY);

    if (randfd < 0) edie("/dev/urandom");

#else

#if 0

    struct timeval tv;

    gettimeofday(&tv, NULL);

    srand48(tv.tv_usec ^ getpid());

#else

    srand48(0xfeda432); // arbitrary, to get repeated values on repeated runs

#endif

#endif

  }



  gettimeofday(&first, NULL);



  states = calloc(ntt, sizeof(*states));

  s = states;



  buf = valloc(ntt * bs);

  if (tm) {

    signal(SIGALRM, sig);

    alarm(tm);

  }

  running = ntt;

  for(j = 0; j < 4; ++j)

    for(i = 0; i < nt[j]; ++i) {

      pthread_t t;

      s->buf = buf; buf += bs;

      s->opi = j;

      s->i = i;

      pthread_create(&t, NULL, worker, s++);

    }

  while(running) {

    pthread_cond_wait(&rncond, &rnmtx);

    putc('\r', stderr);

    pst(stderr);

  }



  putc('\r', stderr);

  pst(stdout);

  putc('\n', stdout);



  gettimeofday(&second, NULL);



  if (first.tv_usec > second.tv_usec) {

    second.tv_usec += 1000000;

    second.tv_sec--;

  }



  lapsed.tv_usec = second.tv_usec - first.tv_usec;

  lapsed.tv_sec  = second.tv_sec  - first.tv_sec;







  if (nt[RndRd] || nt[RndWr]) {

        printf("I/O latency: %f\n", (lapsed.tv_sec*1000+(lapsed.tv_usec/1000))/(float)tioc);



  }



  return 0;

}

sglib

taiar (André Taiar) — Fri, 18 Jul 2008 00:58:08 GMT



#ifndef _SGLIB__h_

#define _SGLIB__h_



/* the assert is used exclusively to write unexpected error messages */

#include 





/* ---------------------------------------------------------------------------- */

/* ---------------------------------------------------------------------------- */

/* -                            LEVEL - 0  INTERFACE                          - */

/* ---------------------------------------------------------------------------- */

/* ---------------------------------------------------------------------------- */





/* ---------------------------------------------------------------------------- */

/* ------------------------------ STATIC ARRAYS ------------------------------- */

/* ---------------------------------------------------------------------------- */



/* 



  Basic algorithms  for sorting arrays. Multiple  depending arrays can

  be rearranged using user defined 'elem_exchangers'



*/



/*               HEAP - SORT  (level 0)           */



#define SGLIB_ARRAY_SINGLE_HEAP_SORT(type, a, max, comparator) {\

  SGLIB_ARRAY_HEAP_SORT(type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\

}



#define SGLIB_ARRAY_HEAP_SORT(type, a, max, comparator, elem_exchanger) {\

  int   _k_;\

  for(_k_=(max)/2; _k_>=0; _k_--) {\

    SGLIB___ARRAY_HEAP_DOWN(type, a, _k_, max, comparator, elem_exchanger);\

  }\

  for(_k_=(max)-1; _k_>=0; _k_--) {\

    elem_exchanger(type, a, 0, _k_);\

    SGLIB___ARRAY_HEAP_DOWN(type, a, 0, _k_, comparator, elem_exchanger);\

  }\

}



#define SGLIB___ARRAY_HEAP_DOWN(type, a, ind, max, comparator, elem_exchanger) {\

  type  _t_;\

  int   _m_, _l_, _r_, _i_;\

  _i_ = (ind);\

  _m_ = _i_;\

  do {\

    _i_ = _m_;          \

    _l_ = 2*_i_+1;\

    _r_ = _l_+1;\

    if (_l_ < (max)){\

      if (comparator(((a)[_m_]), ((a)[_l_])) < 0) _m_ = _l_;\

      if (_r_ < (max)) {\

        if (comparator(((a)[_m_]), ((a)[_r_])) < 0) _m_ = _r_;\

      }\

    }\

    if (_m_ != _i_) {\

     elem_exchanger(type, a, _i_, _m_);\

    }\

  } while (_m_ != _i_);\

}





/*             QUICK - SORT   (level 0)          */



#define SGLIB_ARRAY_SINGLE_QUICK_SORT(type, a, max, comparator) {\

  SGLIB_ARRAY_QUICK_SORT(type, a, max, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\

}



#define SGLIB_ARRAY_QUICK_SORT(type, a, max, comparator, elem_exchanger) {\

  int   _i_, _j_, _p_, _stacki_, _start_, _end_;\

  /* can sort up to 2^64 elements */\

  int   _startStack_[64]; \

  int   _endStack_[64];\

  type  _tmp_;\

  _startStack_[0] = 0;\

  _endStack_[0] = (max);\

  _stacki_ = 1;\

  while (_stacki_ > 0) {\

    _stacki_ --;\

    _start_ = _startStack_[_stacki_];\

    _end_ = _endStack_[_stacki_];\

    while (_end_ - _start_ > 2) {\

      _p_ = _start_;\

      _i_ = _start_ + 1;\

      _j_ = _end_ - 1;\

      while (_i_<_j_) {\

        for(; _i_<=_j_ && comparator(((a)[_i_]),((a)[_p_]))<=0; _i_++) ;\

        if (_i_ > _j_) {\

          /* all remaining elements lesseq than pivot */\

          elem_exchanger(type, a, _j_, _p_);\

          _i_ = _j_;\

        } else {\

          for(; _i_<=_j_ && comparator(((a)[_j_]),((a)[_p_]))>=0; _j_--) ;\

          if (_i_ > _j_) {\

            /* all remaining elements greater than pivot */\

            elem_exchanger(type, a, _j_, _p_);\

            _i_ = _j_;\

          } else if (_i_ < _j_) {\

            elem_exchanger(type, a, _i_, _j_);\

            if (_i_+2 < _j_) {_i_++; _j_--;}\

            else if (_i_+1 < _j_) _i_++;\

          }\

        }\

      }\

      /* O.K. i==j and pivot is on a[i] == a[j] */\

      /* handle recursive calls without recursion */\

      if (_i_-_start_ > 1 && _end_-_j_ > 1) {\

        /* two recursive calls, use array-stack */\

        if (_i_-_start_ < _end_-_j_-1) {\

          _startStack_[_stacki_] = _j_+1;\

          _endStack_[_stacki_] = _end_;\

          _stacki_ ++;\

          _end_ = _i_;\

        } else {\

          _startStack_[_stacki_] = _start_;\

          _endStack_[_stacki_] = _i_;\

          _stacki_ ++;\

          _start_ = _j_+1;\

        }\

      } else {\

        if (_i_-_start_ > 1) {\

          _end_ = _i_;\

        } else {\

          _start_ = _j_+1;\

        }\

      }\

    }\

    if (_end_ - _start_ == 2) {\

      if (comparator(((a)[_start_]),((a)[_end_-1])) > 0) {\

        elem_exchanger(type, a, _start_, _end_-1);\

      }\

    }\

  }\

}



/*             BINARY SEARCH (level 0)          */



#define SGLIB_ARRAY_BINARY_SEARCH(type, a, start_index, end_index, key, comparator, found, result_index) {\

  int _kk_, _cc_, _ii_, _jj_, _ff_;\

  _ii_ = (start_index); \

  _jj_ = (end_index);\

  _ff_ = 0;\

  while (_ii_ <= _jj_ && _ff_==0) {\

    _kk_ = (_jj_+_ii_)/2;\

    _cc_ = comparator(((a)[_kk_]), (key));\

    if (_cc_ == 0) {\

      (result_index) = _kk_;    \

      _ff_ = 1;\

    } else if (_cc_ < 0) {\

      _ii_ = _kk_+1;\

    } else {\

      _jj_ = _kk_-1;\

    }\

  }\

  if (_ff_ == 0) {\

    /* not found, but set its resulting place in the array */\

    (result_index) = _jj_+1;\

  }\

  (found) = _ff_;\

}



/* -------------------------------- queue (in an array) ------------------ */

/* queue is a quadruple (a,i,j,dim) such that:                             */

/*  a is the array storing values                                          */

/*  i is the index of the first used element in the array                  */

/*  j is the index of the first free element in the array                  */

/*  dim is the size of the array a                                         */

/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */



#define SGLIB_QUEUE_INIT(type, a, i, j) { i = j = 0; }

#define SGLIB_QUEUE_IS_EMPTY(type, a, i, j) ((i)==(j))

#define SGLIB_QUEUE_IS_FULL(type, a, i, j, dim) ((i)==((j)+1)%(dim))

#define SGLIB_QUEUE_FIRST_ELEMENT(type, a, i, j) (a[i])

#define SGLIB_QUEUE_ADD_NEXT(type, a, i, j, dim) {\

  if (SGLIB_QUEUE_IS_FULL(type, a, i, j, dim)) assert(0 && "the queue is full");\

  (j) = ((j)+1) % (dim);\

}

#define SGLIB_QUEUE_ADD(type, a, elem, i, j, dim) {\

  a[j] = (elem);\

  SGLIB_QUEUE_ADD_NEXT(type, a, i, j, dim);\

}

#define SGLIB_QUEUE_DELETE_FIRST(type, a, i, j, dim) {\

  if (SGLIB_QUEUE_IS_EMPTY(type, a, i, j)) assert(0 && "the queue is empty");\

  (i) = ((i)+1) % (dim);\

}

#define SGLIB_QUEUE_DELETE(type, a, i, j, dim) {\

  SGLIB_QUEUE_DELETE_FIRST(type, a, i, j, dim);\

}



/* ----------------- priority queue (heap) (in an array) -------------------- */

/* heap is a triple (a,i,dim) such that:                                      */

/*  a is the array storing values                                             */

/*  i is the index of the first free element in the array                     */

/*  dim is the size of the array a                                            */

/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!!    */



#define SGLIB_HEAP_INIT(type, a, i) { i = 0; }

#define SGLIB_HEAP_IS_EMPTY(type, a, i) ((i)==0)

#define SGLIB_HEAP_IS_FULL(type, a, i, dim) ((i)==(dim))

#define SGLIB_HEAP_FIRST_ELEMENT(type, a, i) (a[0])

#define SGLIB_HEAP_ADD_NEXT(type, a, i, dim, comparator, elem_exchanger) {\

  int _i_;\

  if (SGLIB_HEAP_IS_FULL(type, a, i, dim)) assert(0 && "the heap is full");\

  _i_ = (i)++;\

  while (_i_ > 0 && comparator(a[_i_/2], a[_i_]) < 0) {\

    elem_exchanger(type, a, (_i_/2), _i_);\

    _i_ = _i_/2;\

  }\

}

#define SGLIB_HEAP_ADD(type, a, elem, i, dim, comparator) {\

  if (SGLIB_HEAP_IS_FULL(type, a, i, dim)) assert(0 && "the heap is full");\

  a[i] = (elem);\

  SGLIB_HEAP_ADD_NEXT(type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\

}

#define SGLIB_HEAP_DELETE_FIRST(type, a, i, dim, comparator, elem_exchanger) {\

  if (SGLIB_HEAP_IS_EMPTY(type, a, i)) assert(0 && "the heap is empty");\

  (i)--;\

  a[0] = a[i];\

  SGLIB___ARRAY_HEAP_DOWN(type, a, 0, i, comparator, elem_exchanger);\

}

#define SGLIB_HEAP_DELETE(type, a, i, dim, comparator) {\

  SGLIB_HEAP_DELETE_FIRST(type, a, i, dim, comparator, SGLIB_ARRAY_ELEMENTS_EXCHANGER);\

}





/* ----------------- hashed table of pointers (in an array) -------------------- */



/*



  This hashed table is storing pointers to objects (not containers).

  In this table there is a one-to-one mapping between 'objects' stored

  in the table and indexes where they are placed. Each index is

  pointing to exactly one 'object' and each 'object' stored in the

  table occurs on exactly one index.  Once an object is stored in the

  table, it can be represented via its index.



  In case of collision while adding an object the index shifted 

  by SGLIB_HASH_TAB_SHIFT_CONSTANT (constant can be redefined)



  You can NOT delete an element from such hash table. The only

  justification (I can see) for this data structure is an exchange

  file format, having an index table at the beginning and then

  refering objects via indexes.



  !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! 



*/



#define SGLIB_HASH_TAB_INIT(type, table, dim) {\

  int _i_;\

  for(_i_ = 0; _i_ < (dim); _i_++) (table)[_i_] = NULL;\

}



#define SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER(type, table, dim, elem, hash_function, comparator, member){\

  unsigned _pos_;\

  type     *_elem_;\

  SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, _pos_, _elem_);\

  (member) = (table)[_pos_];\

  if (_elem_ == NULL) {\

    if ((table)[_pos_] != NULL) assert(0 && "the hash table is full");\

    (table)[_pos_] = (elem);\

  }\

}



#define SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, hash_function, comparator, resultIndex, resultMember) {\

  unsigned _i_;\

  int      _count_;\

  type     *_e_;\

  _count = 0;\

  _i_ = hash_function(elem);\

  _i_ %= (dim);\

  while ((_e_=(table)[_i_])!=NULL && comparator(_e_, (elem))!=0 && _count_<(dim)) {\

    _count_ ++;\

    _i_ = (_i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT) % (dim);\

  }\

  (resultIndex) = _i_;\

  if (_count_ < (dim)) (resultMember) = _e_;\

  else (resultMember) = NULL;\

}



#define SGLIB_HASH_TAB_IS_MEMBER(type, table, dim, elem, hash_function, resultIndex) {\

  unsigned _i_;\

  int      _c_;\

  type     *_e_;\

  _count = 0;\

  _i_ = hash_function(elem);\

  _i_ %= (dim);\

  while ((_e_=(table)[_i_])!=NULL && _e_!=(elem) && _c_<(dim)) {\

    _c_ ++;\

    _i_ = (_i_ + SGLIB_HASH_TAB_SHIFT_CONSTANT) % (dim);\

  }\

  if (_e_==(elem)) (resultIndex) = _i_;\

  else (resultIndex) = -1;\

}



#define SGLIB_HASH_TAB_MAP_ON_ELEMENTS(type, table, dim, iteratedIndex, iteratedVariable, command) {\

  unsigned  iteratedIndex;\

  type      *iteratedVariable;\

  for(iteratedIndex=0; iteratedIndex < (dim); iteratedIndex++) {\

    iteratedVariable = (table)[iteratedIndex];\

    if (iteratedVariable != NULL) {command;}\

  }\

}





/* ---------------------------------------------------------------------------- */

/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */

/* ---------------------------------------------------------------------------- */



/* ------------------------------------ lists (level 0) --------------------- */



#define SGLIB_LIST_ADD(type, list, elem, next) {\

  (elem)->next = (list);\

  (list) = (elem);\

}



#define SGLIB_LIST_CONCAT(type, first, second, next) {\

  if ((first)==NULL) {\

    (first) = (second);\

  } else {\

    type *_p_;\

    for(_p_ = (first); _p_->next!=NULL; _p_=_p_->next) ;\

    _p_->next = (second);\

  }\

}



#define SGLIB_LIST_DELETE(type, list, elem, next) {\

  type **_p_;\

  for(_p_ = &(list); *_p_!=NULL && *_p_!=(elem); _p_= &(*_p_)->next) ;\

  assert(*_p_!=NULL && "element is not member of the container, use DELETE_IF_MEMBER instead"!=NULL);\

  *_p_ = (*_p_)->next;\

}



#define SGLIB_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member) {\

  type *_p_;\

  for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) != 0; _p_= _p_->next) ;\

  (member) = _p_;\

  if (_p_ == NULL) {\

    SGLIB_LIST_ADD(type, list, elem, next);\

  }\

}



#define SGLIB_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member) {\

  type **_p_;\

  for(_p_ = &(list); *_p_!=NULL && comparator((*_p_), (elem)) != 0; _p_= &(*_p_)->next) ;\

  (member) = *_p_;\

  if (*_p_ != NULL) {\

    *_p_ = (*_p_)->next;\

  }\

}



#define SGLIB_LIST_IS_MEMBER(type, list, elem, next, result) {\

  type *_p_;\

  for(_p_ = (list); _p_!=NULL && _p_ != (elem); _p_= _p_->next) ;\

  (result) = (_p_!=NULL);\

}



#define SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, next, member) {\

  type *_p_;\

  for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) != 0; _p_= _p_->next) ;\

  (member) = _p_;\

}



#define SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command) {\

  type *_ne_;\

  type *iteratedVariable;\

  (iteratedVariable) = (list); \

  while ((iteratedVariable)!=NULL) {\

    _ne_ = (iteratedVariable)->next;\

    {command;};\

    (iteratedVariable) = _ne_;\

  }\

}



#define SGLIB_LIST_LEN(type, list, next, result) {\

  type *_ce_;\

  (result) = 0;\

  SGLIB_LIST_MAP_ON_ELEMENTS(type, list, _ce_, next, (result)++);\

}



#define SGLIB_LIST_REVERSE(type, list, next) {\

  type *_list_,*_tmp_,*_res_;\

  _list_ = (list);\

  _res_ = NULL;\

  while (_list_!=NULL) {\

    _tmp_ = _list_->next; _list_->next = _res_;\

    _res_ = _list_;   _list_ = _tmp_;\

  }\

  (list) = _res_;\

}



#define SGLIB_LIST_SORT(type, list, comparator, next) {\

  /* a non-recursive merge sort on lists */\

  type *_r_;\

  type *_a_, *_b_, *_todo_, *_t_, **_restail_;\

  int _i_, _n_, _contFlag_;\

  _r_ = (list);\

  _contFlag_ = 1;\

  for(_n_ = 1; _contFlag_; _n_ = _n_+_n_) {\

    _todo_ = _r_; _r_ = NULL; _restail_ = &_r_; _contFlag_ =0;\

    while (_todo_!=NULL) {\

      _a_ = _todo_;\

      for(_i_ = 1, _t_ = _a_;  _i_ < _n_ && _t_!=NULL;  _i_++, _t_ = _t_->next) ;\

      if (_t_ ==NULL) {\

        *_restail_ = _a_;\

        break;\

      }\

      _b_ = _t_->next; _t_->next=NULL;\

      for(_i_ =1, _t_ = _b_;  _i_<_n_ && _t_!=NULL;  _i_++, _t_ = _t_->next) ;\

      if (_t_ ==NULL) {\

        _todo_ =NULL;\

      } else {\

        _todo_ = _t_->next; _t_->next=NULL;\

      }\

      /* merge */\

      while (_a_!=NULL && _b_!=NULL) {\

        if (comparator(_a_, _b_) < 0) {\

          *_restail_ = _a_;  _restail_ = &(_a_->next); _a_ = _a_->next;\

        } else {\

          *_restail_ = _b_;  _restail_ = &(_b_->next); _b_ = _b_->next;\

        }\

      }\

      if (_a_!=NULL) *_restail_ = _a_;\

      else *_restail_ = _b_;\

      while (*_restail_!=NULL) _restail_ = &((*_restail_)->next);\

      _contFlag_ =1;\

    }\

  }\

  (list) = _r_;\

}



/* --------------------------------- sorted list (level 0) --------------------- */

/*

  All operations suppose that the list is sorted and they preserve

  this property.

*/





#define SGLIB_SORTED_LIST_ADD(type, list, elem, comparator, next) {\

  type **_e_;\

  int  _cmpres_;\

  SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmpres_, _e_);\

  (elem)->next = *_e_;\

  *_e_ = (elem);\

}



#define SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, next, member) {\

  type **_e_;\

  int _cmp_res_;\

  SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmp_res_, _e_);\

  if (_cmp_res_ != 0) {\

    (elem)->next = *_e_;\

    *_e_ = (elem);\

    (member) = NULL;\

  } else {\

    (member) = *_e_;\

  }\

}



#define SGLIB_SORTED_LIST_DELETE(type, list, elem, next) {\

  SGLIB_LIST_DELETE(type, list, elem, next);\

}



#define SGLIB_SORTED_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, next, member) {\

  type **_e_;\

  int _cmp_res_;\

  SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, _cmp_res_, _e_);\

  if (_cmp_res_ == 0) {\

    (member) = *_e_;\

    *_e_ = (*_e_)->next;\

  } else {\

    (member) = NULL;\

  }\

}



#define SGLIB_SORTED_LIST_FIND_MEMBER(type, list, elem, comparator, next, member) {\

  type *_p_;\

  int _cmpres_ = 1;\

  for(_p_ = (list); _p_!=NULL && (_cmpres_=comparator(_p_, (elem))) < 0; _p_=_p_->next) ;\

  if (_cmpres_ != 0) (member) = NULL;\

  else (member) = _p_;\

}



#define SGLIB_SORTED_LIST_IS_MEMBER(type, list, elem, comparator, next, result) {\

  type *_p_;\

  for(_p_ = (list); _p_!=NULL && comparator(_p_, (elem)) < 0; _p_=_p_->next) ;\

  while (_p_ != NULL && _p_ != (elem) && comparator(_p_, (elem)) == 0) _p_=_p_->next;\

  (result) = (_p_ == (elem));\

}



#define SGLIB_SORTED_LIST_FIND_MEMBER_OR_PLACE(type, list, elem, comparator, next, comparator_result, member_ptr) {\

  (comparator_result) = -1;\

  for((member_ptr) = &(list); \

      *(member_ptr)!=NULL && ((comparator_result)=comparator((*member_ptr), (elem))) < 0; \

      (member_ptr) = &(*(member_ptr))->next) ;\

}



#define SGLIB_SORTED_LIST_LEN(type, list, next, result) {\

  SGLIB_LIST_LEN(type, list, next, result);\

}



#define SGLIB_SORTED_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command) {\

  SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, next, command);\

}





/* ------------------------------- double linked list (level 0) ------------------------- */

/*

  Lists with back pointer to previous element. Those lists implements deletion

  of an element in a constant time.

*/



#define SGLIB___DL_LIST_CREATE_SINGLETON(type, list, elem, previous, next) {\

  (list) = (elem);\

  (list)->next = (list)->previous = NULL;\

}



#define SGLIB_DL_LIST_ADD_AFTER(type, place, elem, previous, next) {\

  if ((place) == NULL) {\

    SGLIB___DL_LIST_CREATE_SINGLETON(type, place, elem, previous, next);\

  } else {\

    (elem)->next = (place)->next;\

    (elem)->previous = (place);\

    (place)->next = (elem);\

    if ((elem)->next != NULL) (elem)->next->previous = (elem);\

  }\

}



#define SGLIB_DL_LIST_ADD_BEFORE(type, place, elem, previous, next) {\

  if ((place) == NULL) {\

    SGLIB___DL_LIST_CREATE_SINGLETON(type, place, elem, previous, next);\

  } else {\

    (elem)->next = (place);\

    (elem)->previous = (place)->previous;\

    (place)->previous = (elem);\

    if ((elem)->previous != NULL) (elem)->previous->next = (elem);\

  }\

}



#define SGLIB_DL_LIST_ADD(type, list, elem, previous, next) {\

  SGLIB_DL_LIST_ADD_BEFORE(type, list, elem, previous, next)\

}



#define SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, the_add_operation) {\

  type *_dlp_;\

  for(_dlp_ = (list); _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->previous) ;\

  if (_dlp_ == NULL && (list) != NULL) {\

    for(_dlp_ = (list)->next; _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->next) ;\

  }\

  (member) = _dlp_;\

  if (_dlp_ == NULL) {\

    the_add_operation(type, list, elem, previous, next);\

  }\

}



#define SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\

  SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD_BEFORE);\

}



#define SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\

  SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD_AFTER);\

}



#define SGLIB_DL_LIST_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member) {\

  SGLIB___DL_LIST_GENERIC_ADD_IF_NOT_MEMBER(type, list, elem, comparator, previous, next, member, SGLIB_DL_LIST_ADD);\

}



#define SGLIB_DL_LIST_CONCAT(type, first, second, previous, next) {\

  if ((first)==NULL) {\

    (first) = (second);\

  } else if ((second)!=NULL) {\

    type *_dlp_;\

    for(_dlp_ = (first); _dlp_->next!=NULL; _dlp_=_dlp_->next) ;\

    SGLIB_DL_LIST_ADD_AFTER(type, _dlp_, second, previous, next);\

  }\

}



#define SGLIB_DL_LIST_DELETE(type, list, elem, previous, next) {\

  type *_l_;\

  _l_ = (list);\

  if (_l_ == (elem)) {\

    if ((elem)->previous != NULL) _l_ = (elem)->previous;\

    else _l_ = (elem)->next;\

  }\

  if ((elem)->next != NULL) (elem)->next->previous = (elem)->previous;\

  if ((elem)->previous != NULL) (elem)->previous->next = (elem)->next;\

  (list) = _l_;\

}



#define SGLIB_DL_LIST_DELETE_IF_MEMBER(type, list, elem, comparator, previous, next, member) {\

  type *_dlp_;\

  for(_dlp_ = (list); _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->previous) ;\

  if (_dlp_ == NULL && (list) != NULL) {\

    for(_dlp_ = (list)->next; _dlp_!=NULL && comparator(_dlp_, (elem)) != 0; _dlp_= _dlp_->next) ;\

  }\

  (member) = _dlp_;\

  if (_dlp_ != NULL) {\

    SGLIB_DL_LIST_DELETE(type, list, _dlp_, previous, next);\

  }\

}



#define SGLIB_DL_LIST_IS_MEMBER(type, list, elem, previous, next, result) {\

  type *_dlp_;\

  SGLIB_LIST_IS_MEMBER(type, list, elem, previous, result);\

  if (result == 0 && (list) != NULL) {\

    _dlp_ = (list)->next;\

    SGLIB_LIST_IS_MEMBER(type, _dlp_, elem, next, result);\

  }\

}



#define SGLIB_DL_LIST_FIND_MEMBER(type, list, elem, comparator, previous, next, member) {\

  type *_dlp_;\

  SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, previous, member);\

  if ((member) == NULL && (list) != NULL) {\

    _dlp_ = (list)->next;\

    SGLIB_LIST_FIND_MEMBER(type, _dlp_, elem, comparator, next, member);\

  }\

}



#define SGLIB_DL_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, previous, next, command) {\

  type *_dl_;\

  type *iteratedVariable;\

  if ((list)!=NULL) {\

    _dl_ = (list)->next;\

    SGLIB_LIST_MAP_ON_ELEMENTS(type, list, iteratedVariable, previous, command);\

    SGLIB_LIST_MAP_ON_ELEMENTS(type, _dl_, iteratedVariable, next, command);\

  }\

}



#define SGLIB_DL_LIST_SORT(type, list, comparator, previous, next) {\

  type *_dll_, *_dlp_, *_dlt_;\

  _dll_ = (list);\

  if (_dll_ != NULL) {\

    for(; _dll_->previous!=NULL; _dll_=_dll_->previous) ;\

    SGLIB_LIST_SORT(type, _dll_, comparator, next);\

    SGLIB___DL_LIST_CREATE_FROM_LIST(type, _dll_, previous, next);\

    (list) = _dll_;\

  }\

}



#define SGLIB_DL_LIST_GET_FIRST(type, list, previous, next, result) {\

  type *_dll_;\

  _dll_ = (list);\

  if (_dll_ != NULL) {\

    for(; _dll_->previous!=NULL; _dll_=_dll_->previous) ;\

  }\

  (result) = _dll_;\

}



#define SGLIB_DL_LIST_GET_LAST(type, list, previous, next, result) {\

  type *_dll_;\

  _dll_ = (list);\

  if (_dll_ != NULL) {\

    for(; _dll_->next!=NULL; _dll_=_dll_->next) ;\

  }\

  (result) = _dll_;\

}



#define SGLIB_DL_LIST_LEN(type, list, previous, next, result) {\

  type *_dl_;\

  int _r1_, _r2_;\

  if ((list)==NULL) {\

    (result) = 0;\

  } else {\

    SGLIB_LIST_LEN(type, list, previous, _r1_);\

    _dl_ = (list)->next;\

    SGLIB_LIST_LEN(type, _dl_, next, _r2_);\

    (result) = _r1_ + _r2_;\

  }\

}



#define SGLIB_DL_LIST_REVERSE(type, list, previous, next) {\

  type *_list_,*_nlist_,*_dlp_,*_dln_;\

  _list_ = (list);\

  if (_list_!=NULL) {\

    _nlist_ = _list_->next;\

    while (_list_!=NULL) {\

      _dln_ = _list_->next; \

      _dlp_ = _list_->previous; \

      _list_->next = _dlp_;\

      _list_->previous = _dln_;\

      _list_ = _dlp_;\

    }\

    while (_nlist_!=NULL) {\

      _dln_ = _nlist_->next; \

      _dlp_ = _nlist_->previous; \

      _nlist_->next = _dlp_;\

      _nlist_->previous = _dln_;\

      _nlist_ = _dln_;\

    }\

  }\

}



#define SGLIB___DL_LIST_CREATE_FROM_LIST(type, list, previous, next) {\

  type *_dlp_, *_dlt_;\

  _dlp_ = NULL;\

  for(_dlt_ = (list); _dlt_!=NULL; _dlt_ = _dlt_->next) {\

    _dlt_->previous = _dlp_;\

    _dlp_ = _dlt_;\

  }\

}





/* ------------------------------- binary tree traversal (level 0) -------------------- */





#define SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, iteratedVariable, order, left, right, command) {\

  /* this is non-recursive implementation of tree traversal */\

  /* it maintains the path to the current node in the array '_path_' */\

  /* the _path_[0] contains the root of the tree; */\

  /* the _path_[_pathi_] contains the _current_element_ */\

  /* the macro does not use the _current_element_ after execution of command */\

  /* command can destroy it, it can free the element for example */\

  type *_path_[SGLIB_MAX_TREE_DEEP];\

  type *_right_[SGLIB_MAX_TREE_DEEP];\

  char _pass_[SGLIB_MAX_TREE_DEEP];\

  type *_cn_;\

  int _pathi_;\

  type *iteratedVariable;\

  _cn_ = (tree);\

  _pathi_ = 0;\

  while (_cn_!=NULL) {\

    /* push down to leftmost innermost element */\

    while(_cn_!=NULL) {\

      _path_[_pathi_] = _cn_;\

      _right_[_pathi_] = _cn_->right;\

      _pass_[_pathi_] = 0;\

      _cn_ = _cn_->left;\

      if (order == 0) {\

        iteratedVariable = _path_[_pathi_];\

        {command;}\

      }\

      _pathi_ ++;\

      if (_pathi_ >= SGLIB_MAX_TREE_DEEP) assert(0 && "the binary_tree is too deep");\

    }\

    do {\

      _pathi_ --;\

      if ((order==1 && _pass_[_pathi_] == 0)\

          || (order == 2 && (_pass_[_pathi_] == 1 || _right_[_pathi_]==NULL))) {\

        iteratedVariable = _path_[_pathi_];\

        {command;}\

      }\

      _pass_[_pathi_] ++;\

    } while (_pathi_>0 && _right_[_pathi_]==NULL) ;\

    _cn_ = _right_[_pathi_];\

    _right_[_pathi_] = NULL;\

    _pathi_ ++;\

  }\

}



#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, left, right, command) {\

  SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 1, left, right, command);\

}



#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_PREORDER(type, tree, _current_element_, left, right, command) {\

  SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 0, left, right, command);\

}



#define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_POSTORDER(type, tree, _current_element_, left, right, command) {\

  SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 2, left, right, command);\

}



#define SGLIB___BIN_TREE_FIND_MEMBER(type, tree, elem, left, right, comparator, res) {\

  type *_s_;\

  int _c_;\

  _s_ = (tree);\

  while (_s_!=NULL) {\

    _c_ = comparator((elem), _s_);\

    if (_c_ < 0) _s_ = _s_->left;\

    else if (_c_ > 0) _s_ = _s_->right;\

    else break;\

  }\

  (res) = _s_;\

}



/* ---------------------------------------------------------------------------- */

/* ---------------------------------------------------------------------------- */

/* -                             LEVEL - 1  INTERFACE                         - */

/* ---------------------------------------------------------------------------- */

/* ---------------------------------------------------------------------------- */







/* ---------------------------------------------------------------------------- */

/* ------------------------------ STATIC ARRAYS ------------------------------- */

/* ---------------------------------------------------------------------------- */



/* ----------------------------- array sorting (level 1) ---------------------- */



#define SGLIB_DEFINE_ARRAY_SORTING_PROTOTYPES(type, comparator) \

 extern void sglib_##type##_array_quick_sort(type *a, int max);\

 extern void sglib_##type##_array_heap_sort(type *a, int max);\





#define SGLIB_DEFINE_ARRAY_SORTING_FUNCTIONS(type, comparator) \

 void sglib_##type##_array_quick_sort(type *a, int max) {\

   SGLIB_ARRAY_SINGLE_QUICK_SORT(type, a, max, comparator);\

 }\

 void sglib_##type##_array_heap_sort(type *a, int max) {\

   SGLIB_ARRAY_SINGLE_HEAP_SORT(type, a, max, comparator);\

 }\





/* ----------------------------- array queue (level 1) ------------------- */

/* sglib's queue is stored in a fixed sized array                          */

/* queue_type MUST be a structure containing fields:                       */

/*  afield is the array storing elem_type                                  */

/*  ifield is the index of the first element in the queue                  */

/*  jfield is the index of the first free element after the queue          */

/*  dim is the size of the array afield                                    */

/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */





#define SGLIB_DEFINE_QUEUE_PROTOTYPES(queue_type, elem_type, afield, ifield, jfield, dim) \

 extern void sglib_##queue_type##_init(queue_type *q); \

 extern int sglib_##queue_type##_is_empty(queue_type *q); \

 extern int sglib_##queue_type##_is_full(queue_type *q); \

 extern elem_type sglib_##queue_type##_first_element(queue_type *q); \

 extern elem_type *sglib_##queue_type##_first_element_ptr(queue_type *q); \

 extern void sglib_##queue_type##_add_next(queue_type *q); \

 extern void sglib_##queue_type##_add(queue_type *q, elem_type elem); \

 extern void sglib_##queue_type##_delete_first(queue_type *q); \

 extern void sglib_##queue_type##_delete(queue_type *q);





#define SGLIB_DEFINE_QUEUE_FUNCTIONS(queue_type, elem_type, afield, ifield, jfield, dim) \

 void sglib_##queue_type##_init(queue_type *q) {\

  SGLIB_QUEUE_INIT(elem_type, q->afield, q->ifield, q->jfield);\

 }\

 int sglib_##queue_type##_is_empty(queue_type *q) {\

  return(SGLIB_QUEUE_IS_EMPTY(elem_type, q->afield, q->ifield, q->jfield));\

 }\

 int sglib_##queue_type##_is_full(queue_type *q) {\

  return(SGLIB_QUEUE_IS_FULL(elem_type, q->afield, q->ifield, q->jfield));\

 }\

 elem_type sglib_##queue_type##_first_element(queue_type *q) {\

  return(SGLIB_QUEUE_FIRST_ELEMENT(elem_type, q->afield, q->ifield, q->jfield));\

 }\

 elem_type *sglib_##queue_type##_first_element_ptr(queue_type *q) {\

  return(& SGLIB_QUEUE_FIRST_ELEMENT(elem_type, q->afield, q->ifield, q->jfield));\

 }\

 void sglib_##queue_type##_add_next(queue_type *q) {\

  SGLIB_QUEUE_ADD_NEXT(elem_type, q->afield, q->ifield, q->jfield, dim);\

 }\

 void sglib_##queue_type##_add(queue_type *q, elem_type elem) {\

  SGLIB_QUEUE_ADD(elem_type, q->afield, elem, q->ifield, q->jfield, dim);\

 }\

 void sglib_##queue_type##_delete_first(queue_type *q) {\

  SGLIB_QUEUE_DELETE_FIRST(elem_type, q->afield, q->ifield, q->jfield, dim);\

 }\

 void sglib_##queue_type##_delete(queue_type *q) {\

  SGLIB_QUEUE_DELETE_FIRST(elem_type, q->afield, q->ifield, q->jfield, dim);\

 }





/* ------------------------ array heap (level 1) ------------------------- */

/* sglib's heap is a priority queue implemented in a fixed sized array     */

/* heap_type MUST be a structure containing fields:                        */

/*  afield is the array of size dim storing elem_type                      */

/*  ifield is the index of the first free element after the queue          */

/* !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! */





#define SGLIB_DEFINE_HEAP_PROTOTYPES(heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger) \

 extern void sglib_##heap_type##_init(heap_type *q); \

 extern int sglib_##heap_type##_is_empty(heap_type *q); \

 extern int sglib_##heap_type##_is_full(heap_type *q); \

 extern elem_type sglib_##heap_type##_first_element(heap_type *q); \

 extern elem_type *sglib_##heap_type##_first_element_ptr(heap_type *q); \

 extern void sglib_##heap_type##_add_next(heap_type *q); \

 extern void sglib_##heap_type##_add(heap_type *q, elem_type elem); \

 extern void sglib_##heap_type##_delete_first(heap_type *q); \

 extern void sglib_##heap_type##_delete(heap_type *q)



#define SGLIB_DEFINE_HEAP_FUNCTIONS(heap_type, elem_type, afield, ifield, dim, comparator, elem_exchanger) \

 void sglib_##heap_type##_init(heap_type *q) {\

  SGLIB_HEAP_INIT(elem_type, q->afield, q->ifield);\

 }\

 int sglib_##heap_type##_is_empty(heap_type *q) {\

  return(SGLIB_HEAP_IS_EMPTY(elem_type, q->afield, q->ifield));\

 }\

 int sglib_##heap_type##_is_full(heap_type *q) {\

  return(SGLIB_HEAP_IS_FULL(elem_type, q->afield, q->ifield));\

 }\

 elem_type sglib_##heap_type##_first_element(heap_type *q) {\

  return(SGLIB_HEAP_FIRST_ELEMENT(elem_type, q->afield, q->ifield));\

 }\

 elem_type *sglib_##heap_type##_first_element_ptr(heap_type *q) {\

  return(& SGLIB_HEAP_FIRST_ELEMENT(elem_type, q->afield, q->ifield));\

 }\

 void sglib_##heap_type##_add_next(heap_type *q) {\

  SGLIB_HEAP_ADD_NEXT(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\

 }\

 void sglib_##heap_type##_add(heap_type *q, elem_type elem) {\

  SGLIB_HEAP_ADD(elem_type, q->afield, elem, q->ifield, dim, comparator, elem_exchanger);\

 }\

 void sglib_##heap_type##_delete_first(heap_type *q) {\

  SGLIB_HEAP_DELETE_FIRST(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\

 }\

 void sglib_##heap_type##_delete(heap_type *q) {\

  SGLIB_HEAP_DELETE_FIRST(elem_type, q->afield, q->ifield, dim, comparator, elem_exchanger);\

 }





/* ------------------------ hashed table  (level 1) ------------------------- */

/*

 

  sglib's hash table is an array storing directly pointers to objects (not containers).

  In this table there is a one-to-one mapping between 'objects' stored

  in the table and indexes where they are placed. Each index is

  pointing to exactly one 'object' and each 'object' stored in the

  table occurs on exactly one index.  Once an object is stored in the

  table, it can be represented via its index.



  type          - is the type of elements

  dim           - is the size of the hash array

  hash_function - is a hashing function mapping type* to unsigned

  comparator    - is a comparator on elements



  !!!!!!! This data structure is NOT documented, do not use it !!!!!!!!!! 

*/



#define SGLIB_DEFINE_HASHED_TABLE_PROTOTYPES(type, dim, hash_function, comparator) \

  struct sglib_hashed_##type##_iterator {\

    int currentIndex;\

    int (*subcomparator)(type *, type *);\

    type *equalto;\

  };\

  extern void sglib_hashed_##type##_init(type *table[dim]);\

  extern int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member);\

  extern int sglib_hashed_##type##_is_member(type *table[dim], type *elem);\

  extern type * sglib_hashed_##type##_find_member(type *table[dim], type *elem);\

  extern type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]); \

  extern type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto); \

  extern type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it); \

  extern type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it);



#define SGLIB_DEFINE_HASHED_TABLE_FUNCTIONS(type, dim, hash_function, comparator) \

  struct sglib_hashed_##type##_iterator {\

    int currentIndex;\

    type **table;\

    int (*subcomparator)(type *, type *);\

    type *equalto;\

  };\

  void sglib_hashed_##type##_init(type *table[dim]) {\

    SGLIB_HASH_TAB_INIT(type, table, dim);\

  }\

  int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member) {\

    SGLIB_HASH_TAB_ADD_IF_NOT_MEMBER(type, table, dim, elem, hash_function, comparator, *member);\

  }\

  int sglib_hashed_##type##_is_member(type *table[dim], type *elem) {\

    int ind;\

    SGLIB_HASH_TAB_IS_MEMBER(type, table, dim, elem, hash_function, ind);\

    return(ind != -1);\

  }\

  type * sglib_hashed_##type##_find_member(type *table[dim], type *elem) {\

    type *mmb;\

    int ind;\

    SGLIB_HASH_TAB_FIND_MEMBER(type, table, dim, elem, hash_function, comparator, ind, mmb);\

    return(mmb);\

  }\

  type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto) {\

    int i;\

    it->table = table;\

    it->subcomparator = subcomparator;\

    it->equalto = equalto;\

    for(i=0; i<(dim) && table[i]==NULL; i++) ;\

    it->currentIndex = i;\

    if (i<(dim)) return(table[i]);\

    return(NULL);\

  }\

  type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]) {\

    sglib_hashed_##type##_it_init_on_equal(it, table, NULL, NULL);\

  }\

  type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it) {\

    return(table[it->currentIndex]);\

  }\

  type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it) {\

    i=it->currentIndex;\

    if (i<(dim)) {\

      for(i++; i<(dim) && table[i]==NULL; i++) ;\

    }\

    it->currentIndex = i;\

    if (i<(dim)) return(table[i]);\

    return(NULL);\

  }





/* ------------------- hashed container (only for level 1)  -------------------- */

/* 

  hashed container is a table of given fixed size containing another

  (dynamic) base container in each cell. Once an object should be

  inserted into the hashed container, a hash function is used to

  determine the cell where the object belongs and the object is

  inserted into the base container stored in this cell. Usually the

  base container is simply a list or a sorted list, but it can be a

  red-black tree as well.



  parameters:

  type - the type of the container stored in each cell.

  dim  - the size of the hashed array

  hash_function - the hashing function hashing 'type *' to unsigned.  



*/



#define SGLIB_DEFINE_HASHED_CONTAINER_PROTOTYPES(type, dim, hash_function) \

  struct sglib_hashed_##type##_iterator {\

    struct sglib_##type##_iterator containerIt;\

    type **table;\

    int currentIndex;\

    int (*subcomparator)(type *, type *);\

    type *equalto;\

  };\

  extern void sglib_hashed_##type##_init(type *table[dim]);\

  extern void sglib_hashed_##type##_add(type *table[dim], type *elem);\

  extern int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member);\

  extern void sglib_hashed_##type##_delete(type *table[dim], type *elem);\

  extern int sglib_hashed_##type##_delete_if_member(type *table[dim], type *elem, type **memb);\

  extern int sglib_hashed_##type##_is_member(type *table[dim], type *elem);\

  extern type * sglib_hashed_##type##_find_member(type *table[dim], type *elem);\

  extern type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]); \

  extern type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto); \

  extern type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it); \

  extern type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it);



#define SGLIB_DEFINE_HASHED_CONTAINER_FUNCTIONS(type, dim, hash_function) \

  /*extern unsigned hash_function(type *elem);*/\

  void sglib_hashed_##type##_init(type *table[dim]) {\

    unsigned i;\

    for(i=0; i<(dim); i++) table[i] = NULL;\

  }\

  void sglib_hashed_##type##_add(type *table[dim], type *elem) {\

    unsigned i;\

    i = ((unsigned)hash_function(elem)) % (dim);\

    sglib_##type##_add(&(table)[i], elem);\

  }\

  int sglib_hashed_##type##_add_if_not_member(type *table[dim], type *elem, type **member) {\

    unsigned i;\

    i = ((unsigned)hash_function(elem)) % (dim);\

    return(sglib_##type##_add_if_not_member(&(table)[i], elem, member));\

  }\

  void sglib_hashed_##type##_delete(type *table[dim], type *elem) {\

    unsigned i;\

    i = ((unsigned)hash_function(elem)) % (dim);\

    sglib_##type##_delete(&(table)[i], elem);\

  }\

  int sglib_hashed_##type##_delete_if_member(type *table[dim], type *elem, type **memb) {\

    unsigned i;\

    i = ((unsigned)hash_function(elem)) % (dim);\

    return(sglib_##type##_delete_if_member(&(table)[i], elem, memb));\

  }\

  int sglib_hashed_##type##_is_member(type *table[dim], type *elem) {\

    unsigned i;\

    i = ((unsigned)hash_function(elem)) % (dim);\

    return(sglib_##type##_is_member((table)[i], elem));\

  }\

  type * sglib_hashed_##type##_find_member(type *table[dim], type *elem) {\

    unsigned i;\

    i = ((unsigned)hash_function(elem)) % (dim);\

    return(sglib_##type##_find_member((table)[i], elem));\

  }\

  type *sglib_hashed_##type##_it_init_on_equal(struct sglib_hashed_##type##_iterator *it, type *table[dim], int (*subcomparator)(type *, type *), type *equalto) {\

    type *e;\

    it->table = table;\

    it->currentIndex = 0;\

    it->subcomparator = subcomparator;\

    it->equalto = equalto;\

    e = sglib_##type##_it_init_on_equal(&it->containerIt, table[it->currentIndex], it->subcomparator, it->equalto);\

    if (e==NULL) e = sglib_hashed_##type##_it_next(it);\

    return(e);\

  }\

  type *sglib_hashed_##type##_it_init(struct sglib_hashed_##type##_iterator *it, type *table[dim]) {\

	return(sglib_hashed_##type##_it_init_on_equal(it, table, NULL, NULL));\

  }\

  type *sglib_hashed_##type##_it_current(struct sglib_hashed_##type##_iterator *it) {\

    return(sglib_##type##_it_current(&it->containerIt));\

  }\

  type *sglib_hashed_##type##_it_next(struct sglib_hashed_##type##_iterator *it) {\

    type *e;\

    e = sglib_##type##_it_next(&it->containerIt);\

    while (e==NULL && (++(it->currentIndex))<(dim)) {\

      e = sglib_##type##_it_init_on_equal(&it->containerIt, it->table[it->currentIndex], it->subcomparator, it->equalto);\

    }\

    return(e);\

  }







/* ---------------------------------------------------------------------------- */

/* ------------------------- DYNAMIC DATA STRUCTURES -------------------------- */

/* ---------------------------------------------------------------------------- */







/* ------------------------------------ list (level 1) -------------------------------- */



#define SGLIB_DEFINE_LIST_PROTOTYPES(type, comparator, next) \

 struct sglib_##type##_iterator {\

   type *currentelem;\

   type *nextelem;\

   int (*subcomparator)(type *, type *);\

   type *equalto;\

 };\

 extern void sglib_##type##_add(type **list, type *elem);\

 extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\

 extern void sglib_##type##_concat(type **first, type *second);\

 extern void sglib_##type##_delete(type **list, type *elem);\

 extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\

 extern int sglib_##type##_is_member(type *list, type *elem);\

 extern type *sglib_##type##_find_member(type *list, type *elem);\

 extern void sglib_##type##_sort(type **list);\

 extern int sglib_##type##_len(type *list);\

 extern void sglib_##type##_reverse(type **list);\

 extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \

 extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \

 extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \

 extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);





#define SGLIB_DEFINE_LIST_FUNCTIONS(type, comparator, next) \

 int sglib_##type##_is_member(type *list, type *elem) {\

   int result;\

   SGLIB_LIST_IS_MEMBER(type, list, elem, next, result);\

   return(result);\

 }\

 type *sglib_##type##_find_member(type *list, type *elem) {\

   type *result;\

   SGLIB_LIST_FIND_MEMBER(type, list, elem, comparator, next, result);\

   return(result);\

 }\

 int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\

   SGLIB_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, next, *member);\

   return(*member==NULL);\

 }\

 void sglib_##type##_add(type **list, type *elem) {\

   SGLIB_LIST_ADD(type, *list, elem, next);\

 }\

 void sglib_##type##_concat(type **first, type *second) {\

   SGLIB_LIST_CONCAT(type, *first, second, next);\

 }\

 void sglib_##type##_delete(type **list, type *elem) {\

   SGLIB_LIST_DELETE(type, *list, elem, next);\

 }\

 int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\

   SGLIB_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, next, *member);\

   return(*member!=NULL);\

 }\

 void sglib_##type##_sort(type **list) { \

   SGLIB_LIST_SORT(type, *list, comparator, next);\

 }\

 int sglib_##type##_len(type *list) {\

   int res;\

   SGLIB_LIST_LEN(type, list, next, res);\

   return(res);\

 }\

 void sglib_##type##_reverse(type **list) {\

   SGLIB_LIST_REVERSE(type, *list, next);\

 }\

 \

 type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\

   it->subcomparator = subcomparator;\

   it->equalto = equalto;\

   it->nextelem = list;\

   return(sglib_##type##_it_next(it));\

 }\

 type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\

   return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\

 }\

 type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\

   return(it->currentelem);\

 }\

 type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\

   type *ce, *eq;\

   int  (*scp)(type *, type *);\

   ce = it->nextelem;\

   it->nextelem = NULL;\

   if (it->subcomparator != NULL) {\

	 eq = it->equalto; \

     scp = it->subcomparator;\

     while (ce!=NULL && scp(ce, eq)!=0) ce = ce->next;\

   }\

   it->currentelem = ce;\

   if (ce != NULL) it->nextelem = ce->next;\

   return(ce);\

 }



/* ----------------------------- sorted list (level 1) ----------------------------------- */





#define SGLIB_DEFINE_SORTED_LIST_PROTOTYPES(type, comparator, next) \

 struct sglib_##type##_iterator {\

   type *currentelem;\

   type *nextelem;\

   int (*subcomparator)(type *, type *);\

   type *equalto;\

 };\

 extern void sglib_##type##_add(type **list, type *elem);\

 extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\

 extern void sglib_##type##_delete(type **list, type *elem);\

 extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\

 extern int sglib_##type##_is_member(type *list, type *elem);\

 extern type *sglib_##type##_find_member(type *list, type *elem);\

 extern int sglib_##type##_len(type *list);\

 extern void sglib_##type##_sort(type **list);\

 extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \

 extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \

 extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \

 extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);





#define SGLIB_DEFINE_SORTED_LIST_FUNCTIONS(type, comparator, next) \

 int sglib_##type##_is_member(type *list, type *elem) {\

   int result;\

   SGLIB_SORTED_LIST_IS_MEMBER(type, list, elem, comparator, next, result);\

   return(result);\

 }\

 type *sglib_##type##_find_member(type *list, type *elem) {\

   type *result;\

   SGLIB_SORTED_LIST_FIND_MEMBER(type, list, elem, comparator, next, result);\

   return(result);\

 }\

 int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\

   SGLIB_SORTED_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, next, *member);\

   return(*member==NULL);\

 }\

 void sglib_##type##_add(type **list, type *elem) {\

   SGLIB_SORTED_LIST_ADD(type, *list, elem, comparator, next);\

 }\

 void sglib_##type##_delete(type **list, type *elem) {\

   SGLIB_SORTED_LIST_DELETE(type, *list, elem, next);\

 }\

 int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\

   SGLIB_SORTED_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, next, *member);\

   return(*member!=NULL);\

 }\

 int sglib_##type##_len(type *list) {\

   int res;\

   SGLIB_SORTED_LIST_LEN(type, list, next, res);\

   return(res);\

 }\

 void sglib_##type##_sort(type **list) { \

   SGLIB_LIST_SORT(type, *list, comparator, next);\

 }\

 \

 type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\

   it->subcomparator = subcomparator;\

   it->equalto = equalto;\

   it->nextelem = list;\

   return(sglib_##type##_it_next(it));\

 }\

 type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\

   return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\

 }\

 type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\

   return(it->currentelem);\

 }\

 type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\

   type *ce, *eq;\

   int  (*scp)(type *, type *);\

   int  c;\

   ce = it->nextelem;\

   it->nextelem = NULL;\

   if (it->subcomparator != NULL) {\

	 eq = it->equalto; \

     scp = it->subcomparator;\

     while (ce!=NULL && (c=scp(ce, eq)) < 0) ce = ce->next;\

     if (ce != NULL && c > 0) ce = NULL;\

   }\

   it->currentelem = ce;\

   if (ce != NULL) it->nextelem = ce->next;\

   return(ce);\

 }





/* ----------------------------- double linked list (level 1) ------------------------------ */





#define SGLIB_DEFINE_DL_LIST_PROTOTYPES(type, comparator, previous, next) \

 struct sglib_##type##_iterator {\

   type *currentelem;\

   type *prevelem;\

   type *nextelem;\

   int (*subcomparator)(type *, type *);\

   type *equalto;\

 };\

 extern void sglib_##type##_add(type **list, type *elem);\

 extern void sglib_##type##_add_before(type **list, type *elem);\

 extern void sglib_##type##_add_after(type **list, type *elem);\

 extern int sglib_##type##_add_if_not_member(type **list, type *elem, type **member);\

 extern int sglib_##type##_add_before_if_not_member(type **list, type *elem, type **member);\

 extern int sglib_##type##_add_after_if_not_member(type **list, type *elem, type **member);\

 extern void sglib_##type##_concat(type **first, type *second);\

 extern void sglib_##type##_delete(type **list, type *elem);\

 extern int sglib_##type##_delete_if_member(type **list, type *elem, type **member);\

 extern int sglib_##type##_is_member(type *list, type *elem);\

 extern type *sglib_##type##_find_member(type *list, type *elem);\

 extern type *sglib_##type##_get_first(type *list);\

 extern type *sglib_##type##_get_last(type *list);\

 extern void sglib_##type##_sort(type **list);\

 extern int sglib_##type##_len(type *list);\

 extern void sglib_##type##_reverse(type **list);\

 extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list); \

 extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto); \

 extern type *sglib_##type##_it_current(struct sglib_##type##_iterator *it); \

 extern type *sglib_##type##_it_next(struct sglib_##type##_iterator *it);





#define SGLIB_DEFINE_DL_LIST_FUNCTIONS(type, comparator, previous, next) \

 void sglib_##type##_add(type **list, type *elem) {\

  SGLIB_DL_LIST_ADD(type, *list, elem, previous, next);\

 }\

 void sglib_##type##_add_after(type **list, type *elem) {\

  SGLIB_DL_LIST_ADD_AFTER(type, *list, elem, previous, next);\

 }\

 void sglib_##type##_add_before(type **list, type *elem) {\

  SGLIB_DL_LIST_ADD_BEFORE(type, *list, elem, previous, next);\

 }\

 int sglib_##type##_add_if_not_member(type **list, type *elem, type **member) {\

  SGLIB_DL_LIST_ADD_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\

  return(*member==NULL);\

 }\

 int sglib_##type##_add_after_if_not_member(type **list, type *elem, type **member) {\

  SGLIB_DL_LIST_ADD_AFTER_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\

  return(*member==NULL);\

 }\

 int sglib_##type##_add_before_if_not_member(type **list, type *elem, type **member) {\

  SGLIB_DL_LIST_ADD_BEFORE_IF_NOT_MEMBER(type, *list, elem, comparator, previous, next, *member);\

  return(*member==NULL);\

 }\

 void sglib_##type##_concat(type **first, type *second) {\

   SGLIB_DL_LIST_CONCAT(type, *first, second, previous, next);\

 }\

 void sglib_##type##_delete(type **list, type *elem) {\

  SGLIB_DL_LIST_DELETE(type, *list, elem, previous, next);\

 }\

 int sglib_##type##_delete_if_member(type **list, type *elem, type **member) {\

  SGLIB_DL_LIST_DELETE_IF_MEMBER(type, *list, elem, comparator, previous, next, *member);\

  return(*member!=NULL);\

 }\

 int sglib_##type##_is_member(type *list, type *elem) {\

   int result;\

   SGLIB_DL_LIST_IS_MEMBER(type, list, elem, previous, next, result);\

   return(result);\

 }\

 type *sglib_##type##_find_member(type *list, type *elem) {\

   type *result;\

   SGLIB_DL_LIST_FIND_MEMBER(type, list, elem, comparator, previous, next, result);\

   return(result);\

 }\

 type *sglib_##type##_get_first(type *list) {\

   type *result;\

   SGLIB_DL_LIST_GET_FIRST(type, list, previous, next, result);\

   return(result);\

 }\

 type *sglib_##type##_get_last(type *list) {\

   type *result;\

   SGLIB_DL_LIST_GET_LAST(type, list, previous, next, result);\

   return(result);\

 }\

 void sglib_##type##_sort(type **list) {\

   SGLIB_DL_LIST_SORT(type, *list, comparator, previous, next);\

 }\

 int sglib_##type##_len(type *list) {\

   int res;\

   SGLIB_DL_LIST_LEN(type, list, previous, next, res);\

   return(res);\

 }\

 void sglib_##type##_reverse(type **list) {\

   SGLIB_DL_LIST_REVERSE(type, *list, previous, next);\

 }\

 \

 type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *list, int (*subcomparator)(type *, type *), type *equalto) {\

   it->subcomparator = subcomparator;\

   it->equalto = equalto;\

   it->prevelem = list;\

   it->nextelem = list;\

   if (list != NULL) it->nextelem = list->next;\

   return(sglib_##type##_it_next(it));\

 }\

 type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *list) {\

   return(sglib_##type##_it_init_on_equal(it, list, NULL, NULL));\

 }\

 type *sglib_##type##_it_current(struct sglib_##type##_iterator *it) {\

   return(it->currentelem);\

 }\

 type *sglib_##type##_it_next(struct sglib_##type##_iterator *it) {\

   type *ce, *eq;\

   int  (*scp)(type *, type *);\

   ce = it->prevelem;\

   it->prevelem = NULL;\

   if (it->subcomparator != NULL) {\

	 eq = it->equalto; \

     scp = it->subcomparator;\

     while (ce!=NULL && scp(eq, ce)!=0) ce = ce->previous;\

   }\

   if (ce != NULL) {\

     it->prevelem = ce->previous;\

   } else {\

     ce = it->nextelem;\

     it->nextelem = NULL;\

     if (it->subcomparator != NULL) {\

	   eq = it->equalto; \

       scp = it->subcomparator;\

       while (ce!=NULL && scp(ce, eq)!=0) ce = ce->next;\

     }\

     if (ce != NULL) it->nextelem = ce->next;\

   }\

   it->currentelem = ce;\

   return(ce);\

 }





/* --------------------------------- red-black trees (level 1) -------------------------------- */



/*



This  implementation requires  pointers  to left  and  right sons  (no

parent  pointer  is needed)  and  one  bit  of additional  information

storing the color of  the node. The implementation follows discrepancy

fixing rules from:

http://www.cis.ohio-state.edu/~gurari/course/cis680/cis680Ch11.html



*/



#define SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK) {\

  type *t, *tl, *a, *b, *c, *ar, *bl, *br, *cl, *cr;\

  t = *tree;\

  tl = t->leftt;\

  if (t->rightt!=NULL && SGLIB___GET_VALUE(t->rightt->bits)==RED) {\

    if (SGLIB___GET_VALUE(tl->bits)==RED) {\

      if ((tl->leftt!=NULL && SGLIB___GET_VALUE(tl->leftt->bits)==RED) \

          || (tl->rightt!=NULL && SGLIB___GET_VALUE(tl->rightt->bits)==RED)) {\

        SGLIB___SET_VALUE(t->leftt->bits,BLACK);\

        SGLIB___SET_VALUE(t->rightt->bits,BLACK);\

        SGLIB___SET_VALUE(t->bits,RED);\

      }\

    }\

  } else {\

    if (SGLIB___GET_VALUE(tl->bits)==RED) {\

      if (tl->leftt!=NULL && SGLIB___GET_VALUE(tl->leftt->bits)==RED) {\

        a = t; b = tl; c = tl->leftt;\

        br = b->rightt;\

        a->leftt = br;\

        b->leftt = c; b->rightt = a;\

        SGLIB___SET_VALUE(a->bits,RED);\

        SGLIB___SET_VALUE(b->bits,BLACK);\

        *tree = b;\

      } else if (tl->rightt!=NULL && SGLIB___GET_VALUE(tl->rightt->bits)==RED) {\

        a = t; b = tl; ar=a->rightt;\

        bl=b->leftt; c=b->rightt;\

        cl=c->leftt; cr=c->rightt;\

        b->rightt = cl;\

        a->leftt = cr;\

        c->leftt = b;\

        c->rightt = a;\

        SGLIB___SET_VALUE(c->bits,BLACK);\

        SGLIB___SET_VALUE(a->bits,RED);\

        *tree = c;\

      }\

    }\

  }\

}



#define SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK, res) {\

  type  *t, *a, *b, *c, *d, *ar, *bl, *br, *cl, *cr, *dl, *dr;\

  t = a = *tree;\

  assert(t!=NULL);\

  ar = a->rightt;\

  b = t->leftt;\

  if (b==NULL) {\

    assert(SGLIB___GET_VALUE(t->bits)==RED);\

    SGLIB___SET_VALUE(t->bits,BLACK);\

    res = 0;\

  } else {\

    bl = b->leftt;\

    br = b->rightt;\

    if (SGLIB___GET_VALUE(b->bits)==RED) {\

      if (br==NULL) {\

        *tree = b;\

        SGLIB___SET_VALUE(b->bits,BLACK);\

        b->rightt = a;\

        a->leftt = br;\

        res = 0;\

      } else {\

        c = br;\

        assert(c!=NULL && SGLIB___GET_VALUE(c->bits)==BLACK);\

        cl = c->leftt;\

        cr = c->rightt;\

        if ((cl==NULL||SGLIB___GET_VALUE(cl->bits)==BLACK) && (cr==NULL||SGLIB___GET_VALUE(cr->bits)==BLACK)) {\

          *tree = b;\

          b->rightt = a;\

          SGLIB___SET_VALUE(b->bits,BLACK);\

          a->leftt = c;\

          SGLIB___SET_VALUE(c->bits,RED);\

          res = 0;\

        } else if (cl!=NULL && SGLIB___GET_VALUE(cl->bits)==RED) {\

          if (cr!=NULL && SGLIB___GET_VALUE(cr->bits)==RED) {\

            d = cr;\

            dl = d->leftt;\

            dr = d->rightt;\

            *tree = d;\

            SGLIB___SET_VALUE(d->bits,BLACK);\

            d->leftt = b;\

            c->rightt = dl;\

            d->rightt = a;\

            a->leftt = dr;\

            res = 0;\

          } else {\

            *tree = c;\

            c->leftt = b;\

            c->rightt = a;\

            b->leftt = bl;\

            b->rightt = cl;\

            a->leftt = cr;\

            SGLIB___SET_VALUE(cl->bits,BLACK);\

            res = 0;\

          }\

        } else if (cr!=NULL && SGLIB___GET_VALUE(cr->bits)==RED) {\

          assert(cl==NULL || SGLIB___GET_VALUE(cl->bits)==BLACK);\

          d = cr;\

          dl = d->leftt;\

          dr = d->rightt;\

          *tree = d;\

          SGLIB___SET_VALUE(d->bits,BLACK);\

          d->leftt = b;\

          c->rightt = dl;\

          d->rightt = a;\

          a->leftt = dr;\

          res = 0;\

        } else {\

          assert(0);\

          res = 0;\

        }\

      }\

    } else {\

      if ((bl==NULL || SGLIB___GET_VALUE(bl->bits)==BLACK) && (br==NULL || SGLIB___GET_VALUE(br->bits)==BLACK)) {\

        res = (SGLIB___GET_VALUE(a->bits)==BLACK);\

        SGLIB___SET_VALUE(a->bits,BLACK);\

        SGLIB___SET_VALUE(b->bits,RED);\

      } else if (bl!=NULL && SGLIB___GET_VALUE(bl->bits)==RED) {\

        if (br==NULL || SGLIB___GET_VALUE(br->bits)==BLACK) {\

          *tree = b;\

          SGLIB___SET_VALUE(b->bits,SGLIB___GET_VALUE(a->bits));\

          SGLIB___SET_VALUE(a->bits,BLACK);\

          b->rightt = a;\

          a->leftt = br;\

          SGLIB___SET_VALUE(bl->bits,BLACK);\

          res = 0;\

        } else {\

          assert(bl!=NULL);\

          assert(br!=NULL);\

          assert(SGLIB___GET_VALUE(bl->bits)==RED);\

          assert(SGLIB___GET_VALUE(br->bits)==RED);\

          c = br;\

          cl = c->leftt;\

          cr = c->rightt;\

          *tree = c;\

          SGLIB___SET_VALUE(c->bits,SGLIB___GET_VALUE(a->bits));\

          SGLIB___SET_VALUE(a->bits,BLACK);\

          c->leftt = b;\

          c->rightt = a;\

          b->rightt = cl;\

          a->leftt = cr;\

          res = 0;\

        }\

      } else {\

        assert(br!=NULL && SGLIB___GET_VALUE(br->bits)==RED);\

        c = br;\

        cl = c->leftt;\

        cr = c->rightt;\

        *tree = c;\

        SGLIB___SET_VALUE(c->bits,SGLIB___GET_VALUE(a->bits));\

        SGLIB___SET_VALUE(a->bits,BLACK);\

        c->leftt = b;\

        c->rightt = a;\

        b->rightt = cl;\

        a->leftt = cr;\

        res = 0;\

      }\

    }\

  }\

}





#define SGLIB_DEFINE_RBTREE_FUNCTIONS_GENERAL(type, left, right, bits, comparator, RED, BLACK) \

static void sglib___##type##_fix_left_insertion_discrepancy(type **tree) {\

  SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK);\

}\

\

static void sglib___##type##_fix_right_insertion_discrepancy(type **tree) {\

  SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK);\

}\

\

static int sglib___##type##_fix_left_deletion_discrepancy(type **tree) {\

  int       res;\

  SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK, res);\

  return(res);\

}\

\

static int sglib___##type##_fix_right_deletion_discrepancy(type **tree) {\

  int       res;\

  SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK, res);\

  return(res);\

}\

\

static void sglib___##type##_add_recursive(type **tree, type *elem) {\

  int cmp;\

  type *t;\

  t = *tree;\

  if (t == NULL) {\

    SGLIB___SET_VALUE(elem->bits,RED);\

    *tree =elem;\

  } else {\

    cmp = comparator(elem, t);\

    if (cmp < 0 || (cmp==0 && elem      sglib___##type##_add_recursive(&t->left, elem);\

      if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_left_insertion_discrepancy(tree);\

    } else {\

      sglib___##type##_add_recursive(&t->right, elem);\

      if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_right_insertion_discrepancy(tree);\

    }\

  }\

}\

\

static int sglib___##type##_delete_rightmost_leaf(type **tree, type **theLeaf) {\

  type  *t;\

  int       res, deepDecreased;\

  t = *tree;\

  res = 0;\

  assert(t!=NULL);\

  if (t->right == NULL) {\

    *theLeaf = t;\

    if (t->left!=NULL) {\

      if (SGLIB___GET_VALUE(t->bits)==BLACK && SGLIB___GET_VALUE(t->left->bits)==BLACK) res = 1;\

      SGLIB___SET_VALUE(t->left->bits,BLACK);\

      *tree = t->left;\

    } else {\

      *tree = NULL;\

      res = (SGLIB___GET_VALUE(t->bits)==BLACK);\

    }\

  } else {\

    deepDecreased = sglib___##type##_delete_rightmost_leaf(&t->right, theLeaf);\

    if (deepDecreased) res = sglib___##type##_fix_right_deletion_discrepancy(tree);\

  }\

  return(res);\

}\

\

int sglib___##type##_delete_recursive(type **tree, type *elem) {\

  type  *t, *theLeaf;\

  int       cmp, res, deepDecreased;\

  t = *tree;\

  res = 0;\

  if (t==NULL) {\

    assert(0 && "The element to delete not found in the tree,  use 'delete_if_member'"!=NULL);\

  } else {\

    cmp = comparator(elem, t);\

    if (cmp < 0 || (cmp==0 && elem      deepDecreased = sglib___##type##_delete_recursive(&t->left, elem);\

      if (deepDecreased) {\

        res = sglib___##type##_fix_left_deletion_discrepancy(tree);\

      }\

    } else if (cmp > 0  || (cmp==0 && elem>t)) {\

      deepDecreased = sglib___##type##_delete_recursive(&t->right, elem);\

      if (deepDecreased) {\

        res = sglib___##type##_fix_right_deletion_discrepancy(tree);\

      }\

    } else {\

      assert(elem==t && "Deleting an element which is non member of the tree, use 'delete_if_member'"!=NULL);\

      if (t->left == NULL) {\

        if (t->right == NULL) {\

          /* a leaf, delete, it; */\

          *tree = NULL;\

          res = (SGLIB___GET_VALUE(t->bits)==BLACK);\

        } else {\

          if (SGLIB___GET_VALUE(t->bits)==0 && SGLIB___GET_VALUE(t->right->bits)==0) res = 1;\

          SGLIB___SET_VALUE(t->right->bits,BLACK);\

          *tree = t->right;\

        }\

      } else {\

        /* propagate deletion until righmost leaf of left subtree */\

        deepDecreased = sglib___##type##_delete_rightmost_leaf(&t->left, &theLeaf);\

        theLeaf->left = t->left;\

        theLeaf->right = t->right;\

        SGLIB___SET_VALUE(theLeaf->bits,SGLIB___GET_VALUE(t->bits));\

        *tree = theLeaf;\

        if (deepDecreased) res = sglib___##type##_fix_left_deletion_discrepancy(tree);\

      }\

    }\

  }\

  return(res);\

}\

\

void sglib_##type##_add(type **tree, type *elem) {\

  elem->left = elem->right = NULL;\

  sglib___##type##_add_recursive(tree, elem);\

  SGLIB___SET_VALUE((*tree)->bits,BLACK);\

}\

\

void sglib_##type##_delete(type **tree, type *elem) {\

  sglib___##type##_delete_recursive(tree, elem);\

  if (*tree!=NULL) SGLIB___SET_VALUE((*tree)->bits,BLACK);\

}\

\

type *sglib_##type##_find_member(type *t, type *elem) {\

  type *res;\

  SGLIB___BIN_TREE_FIND_MEMBER(type, t, elem, left, right, comparator, res);\

  return(res);\

}\

\

int sglib_##type##_is_member(type *t, type *elem) {\

  int       cmp;\

  while (t!=NULL) {\

    cmp = comparator(elem, t);\

    if (cmp < 0 || (cmp==0 && elem      t = t->left;\

    }



Listing the files and subdirectories in C - Linux
Tvrtko (Tvrtko) — Tue, 08 Jul 2008 01:13:50 GMT
// program lists the files and subdirectories within a given directory in full path





#include 

#include 

#include 

#include 



char *path_cat (const char *str1, char *str2);



int main () {

	struct dirent *dp;



        // enter existing path to directory below

	const char *dir_path="/path/to/directory/to/list";

	DIR *dir = opendir(dir_path);

	while ((dp=readdir(dir)) != NULL) {

		char *tmp;

		tmp = path_cat(dir_path, dp->d_name);

		printf("%s\n", tmp);

		free(tmp);

		tmp=NULL;

	}

	closedir(dir);

	return 0;

}



char *path_cat (const char *str1, char *str2) {

	size_t str1_len = strlen(str1);

	size_t str2_len = strlen(str2);

	char *result;

	result = malloc((str1_len+str2_len+1)*sizeof *result);

	strcpy (result,str1);

	int i,j;

	for(i=str1_len, j=0; ((i<(str1_len+str2_len)) && (j		result[i]=str2[j];

	}

	result[str1_len+str2_len]='\0';

	return result;

}




C functions for getting disk space information in Linux OS
Tvrtko (Tvrtko) — Fri, 06 Jun 2008 16:41:22 GMT
These are 2 C functions for getting disk capacity and disk free space in megabytes into char array





#include 

#include 



gchar *

g_get_capacity ( gchar * dev_path)

{

	unsigned long long result = 0;

	int n;

	gchar s_cap[50];

	gchar * ss_cap = "N/A";

	struct statvfs sfs;

	if ( statvfs ( dev_path, &sfs) != -1 )

	{

		result = (unsigned long long)sfs.f_bsize * sfs.f_blocks;

	}

	if (result > 0)

	{

		double f_cap = (double)result/(1024*1024);

		n = sprintf(s_cap, "%.2f Mb", f_cap);

		ss_cap = g_strdup(s_cap);

	}

	return ss_cap;

}



gchar * 

g_get_free_space ( gchar * dev_path)

{

	unsigned long long result = 0;

	int n;

	gchar s_cap[50];

	gchar * ss_cap = "N/A";

	struct statvfs sfs;

	if ( statvfs ( dev_path, &sfs) != -1 )

	{

		result = (unsigned long long)sfs.f_bsize * sfs.f_bfree;

	}

	if (result > 0)

	{

		double f_cap = (double)result/(1024*1024);

		n = sprintf(s_cap, "%.2f Mb", f_cap);

		ss_cap = g_strdup(s_cap);

	}

	return ss_cap;

}




Fast anagram determination
phaana (Irfan Hamid) — Wed, 14 May 2008 23:40:31 GMT
// This function will determine whether the two C strings provided are anagrams or not. Only alphabetical strings are considered.





/******************************************************************************

 * This function is a code snippet. It can be freely used and distributed.

 * Author: irfan[dot]hamid[at]gmail[at]com

 *

 * This function takes two ASCII strings in C syntax (null-terminated

 * character arrays) and determines whether they are anagrams or not.

 *

 * Implementation notes:

 * The function contains a histogram that stores the frequency of each 

 * character it encounters in the first string. For each character of the 

 * second string, it decrements the corresponding entry in the histogram. If 

 * before every decrement, the value of the histogram bucket reaches zero, 

 * then the two strings are not anagrams, as there is some character that has

 * more occurrences in the second string than in the first string.

 *

 * If either of the two strings contains a non-alphabetic character, the

 * anagram property is considered to be violated.

 *

 * Remarks:

 * It is an efficient implementation because:

 *   o It is in-place, the original strings are not copied, no alloc or copy

 *   o Does not clobber the original strings

 *   o It is a linear time implementation

 *

 * Returns:

 * True if the strings are anagrams, false otherwise.

******************************************************************************/



bool is_anagram (char w1[], char w2[])

{

	unsigned int i, sz;



	/* The histogram */

	int freqtbl[26];



	/* Sanity check */

	if ((sz = strlen(w1)) != strlen(w2))

		return false;



	/* Initialize the histogram */

	bzero(freqtbl, 26*sizeof(int));



	/* Read the first string, incrementing the corresponding histogram entry */

	for (i = 0; i < sz; i++) {

		if (w1[i] >= 'A' && w1[i] <= 'Z')

			freqtbl[w1[i]-'A']++;

		else if (w1[i] >= 'a' && w1[i] <= 'z')

			freqtbl[w1[i]-'a']++;

		else

			return false;

	}



	/* Read the second string, decrementing the corresponding histogram entry */

	for (i = 0; i < sz; i++) {

		if (w2[i] >= 'A' && w2[i] <= 'Z') {

			if (freqtbl[w2[i]-'A'] == 0)

				return false;

			freqtbl[w2[i]-'A']--;

		} else if (w2[i] >= 'a' && w2[i] <= 'z') {

			if (freqtbl[w2[i]-'a'] == 0)

				return false;

			freqtbl[w2[i]-'a']--;

		} else {

			return false;

		}

	}



	return true;

}




Pointer swap function
rasmus (Rasmus Frederiksen) — Wed, 23 Apr 2008 10:39:53 GMT
// A generic pointer swap function that works with all structs by calling swap(&A, &B), where A and B are struct pointers





void swap(void **x, void **y) {

	void *t = *x;

	*x = *y;

	*y = t;

}




A solution for the "Interpreter" problem
jmftrindade (Joana M. F. da Trindade) — Tue, 18 Mar 2008 09:26:35 GMT
A solution for the "Interpreter" problem.

 

Problem description:

http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10033.html



Author: Joana Matos Fonseca da Trindade

Date: 2008.03.16





/* 

 * Solution for the "Interpreter" problem.

 * UVa ID: 10033

 */

#include 



#define MAX_REG 10

#define MAX_RAM 1000



int pointer;

int regArray[MAX_REG];

int ram[MAX_RAM];



/* initialize registers and ram */

int init() {

	int i;

	for (i = 0; i < MAX_REG; i++) {

		regArray[i] = 0;

	}

	for (i = 0; i < MAX_RAM; i++) {

		ram[i] = 0;

	}

	

}



/* decode instruction */

int decode() {

	int command, a1, a2;

	command = ram[pointer] / 100;

	a1 = (ram[pointer] % 100) / 10;

	a2 = ram[pointer] % 10;

	

	switch (command) {

		/* halt */

		case 1 :		

			return 0;

			break;

			

		/* set register a1 to a2 */

		case 2 :

			regArray[a1] = a2;

			pointer++;

			break;

			

		/* add a2 to register a1 */

		case 3 :

			regArray[a1] = (regArray[a1] + a2) % 1000;

			pointer++;

			break;

			

		/* multiply register a1 by a2 */

		case 4 :

			regArray[a1] = (regArray[a1] * a2) % 1000;

			pointer++;

			break;

			

		/* set register a1 to the value of register a2 */

		case 5 : 

			regArray[a1] = regArray[a2];

			pointer++;

			break;

			

		/* add the value of register a2 to register a1 */

		case 6 : 

			regArray[a1] = (regArray[a1] + regArray[a2]) % 1000;

			pointer++;

			break;

			

		/* multiply register a1 by the value of register a2 */

		case 7 :

			regArray[a1] = (regArray[a1] * regArray[a2]) % 1000;

			pointer++;

			break;

			

		/* set register a1 to the value in RAM whose address is in register a2 */

		case 8 :

			regArray[a1] = ram[regArray[a2]];

			pointer++;

			break;			

			

		/* set the value in RAM whose address in in register a2 to that of register a1 */

		case 9 :

			ram[regArray[a2]] = regArray[a1];

			pointer++;

			break;			

			

		/* goto */		

		case 0 :

			if (regArray[a2] != 0) {

				pointer = regArray[a1];

			} else {

				pointer++;

			}

			break;			

			

		default: 

			break;

	}

	return 1;	

}



/* main */

int main (int argc, const char * argv[]) {

	int i, j, cases, num_instr;

	char instr[5];



	scanf("%d", &cases);

	fgets(instr, sizeof(instr), stdin);

	fgets(instr, sizeof(instr), stdin);

	num_instr = 0;

	

	/* for the number of test cases specified */

	for (i = 0; i < cases; i++) {

		init();

		

		pointer = 0;

		

		if (i != 0) {

			printf("\n");

		}

		

		/* read input ram */

		while(fgets(instr, sizeof(instr), stdin) != NULL) {

			if (instr[0] == '\n') {

				break;

			}

			ram[pointer] = (instr[0] - '0') * 100 + (instr[1] - '0') * 10 + (instr[2] - '0');

			pointer++;

		}

		

		/* decode and interpret instructions until halt */

		num_instr = 1;

		pointer = 0;

		while (decode()) {

			num_instr++;

		}	

		

		printf("%d\n",num_instr);	

	}

	

	return 0;

}




A solution for the "Graphical Editor" problem
jmftrindade (Joana M. F. da Trindade) — Tue, 18 Mar 2008 09:23:41 GMT
A solution for the "Graphical Editor" problem.

 

Problem description:

http://icpcres.ecs.baylor.edu/onlinejudge/external/102/10267.html



Author: Joana Matos Fonseca da Trindade

Date: 2008.03.12





/* 

 * Solution for the "Graphical Editor" problem.

 * UVa ID: 10267

 */

#include 



#define MAX 250

#define OFFSET 1

#define DOS_NAME 12



/* global image bounds */

int n, m;



/* fills a rectangle with the specified color */

int fillRectangle(int m_ini, int n_ini, int m_end, int n_end, char color, char pTable[][MAX+OFFSET]) {

	int i, j;

	for (i = n_ini; i <= n_end; i++) {

		for (j = m_ini; j <= m_end; j++) {

			pTable[i][j] = color;

		}

	}

	return 0;

}



/* fills a region R with the specified color */

int fillRegion(int x, int y, char oldColor, char newColor, char pTable[][MAX+OFFSET]) {	

	/* (x,y) is in region R */

	pTable[y][x] = newColor;

	

	/* recursively check all 4 directions for neighbours of (x,y) with same color */

	if ((pTable[y][x-1] == oldColor) && (x > OFFSET)) {         

		fillRegion(x-1, y, oldColor, newColor, pTable);

	}

	if ((pTable[y][x+1] == oldColor) && (x < m)) {       

		fillRegion(x+1, y, oldColor, newColor, pTable);

	}

	if ((pTable[y-1][x] == oldColor) && (y > OFFSET)) {        

		fillRegion(x, y-1, oldColor, newColor, pTable);

	}

	if ((pTable[y+1][x] == oldColor) && (y < n)) {        

		fillRegion(x, y+1, oldColor, newColor, pTable);

	}

	return 0;

}



/* outputs the image */

int printImage(int m, int n, char pTable[][MAX+OFFSET]) {

	int i, j;	

	for (i = OFFSET; i < n+OFFSET; i++) {

		for (j = OFFSET; j < m+OFFSET; j++ ) {

			printf("%c", pTable[i][j]);

		}

		printf("\n");

	}

	return 0;

}



/* main */

int main (int argc, const char * argv[]) {

	/* the image */

	char image[MAX+OFFSET][MAX+OFFSET];



	/* editor command */

	char command;

	

	/* coords */

	int x1, x2, y1, y2, tmp;

	

	/* colors */

	char color, oldColor;

	

	/* filename */

	char filename[DOS_NAME+1];

			

	while(scanf("%c", &command) != EOF) {		

		/* X, terminates the session */

		if (command == 'X') {

			return 0;

		}		

		switch (command) {

			/* create image */

			case 'I' :

				scanf("%d %d", &m, &n);

				fillRectangle(1, 1, m, n, 'O', image);

				break;

			

			/* clear image */

			case 'C' :

				fillRectangle(1, 1, m, n, 'O', image);

				break;

			

			/* colors a pixel */

			case 'L' :

				scanf("%d %d %c", &x1, &y1, &color);

				image[y1][x1] = color;

				break;

			

			/* draw vertical segment */

			case 'V' :

				scanf("%d %d %d %c", &x1, &y1, &y2, &color);

				if (y2 >= y1)

					fillRectangle(x1, y1, x1, y2, color, image);

				else

					fillRectangle(x1, y2, x1, y1, color, image);

				break;

			

			/* draw horizontal segment */

			case 'H' : 

				scanf("%d %d %d %c", &x1, &x2, &y1, &color);

				if (x2 >= x1)

					fillRectangle(x1, y1, x2, y1, color, image);

				else

					fillRectangle(x2, y1, x1, y1, color, image);

				break;

			

			/* draw rectangle */

			case 'K' : 

				scanf("%d %d %d %d %c", &x1, &y1, &x2, &y2, &color);

				if (x1 >= x2) {

					tmp = x1;

					x1 = x2;

					x2 = tmp;

				}

				if (y1 >= y2) {

					tmp = y1;

					y1 = y2;

					y2 = tmp;

				}

				fillRectangle(x1, y1, x2, y2, color, image);

				break;

			

			/* fill */

			case 'F' :

				scanf("%d %d %c", &x1, &y1, &color);

				oldColor = image[y1][x1];

				if (oldColor != color) {

					fillRegion(x1, y1, oldColor, color, image);

				}

				break;



			/* fill */

			case 'S' :

				scanf("%s", &filename);

				printf("%s\n", filename);

				printImage(m, n, image);

				break;			

		

			default: 

				break;

		}		

	}

	

	return 0;

}




A solution for the "LCD Display" problem
jmftrindade (Joana M. F. da Trindade) — Tue, 18 Mar 2008 09:16:55 GMT
A solution for the "LCD Display" problem.

 

Problem description:

http://acm.uva.es/p/v7/706.html



Author: Joana Matos Fonseca da Trindade

Date: 2008.03.09





/* 

 * Solution for the "LCD Display" problem.

 * UVa ID: 706

 */

#include 

#include 

#include 



#define MAX_SIZE 9



int main (int argc, const char * argv[]) {

	/* number of vertical or horizontal segments in each digit */

	int s;

	

	/* the number to print */

	char digitString[MAX_SIZE];

	

	/* 

	 * LED representation for each number, according to 

	 * the following convention:

	 *

	 *  -0-

	 * |   |

	 * 2   1

	 * |   |

	 *  -3-

	 * |   |

	 * 5   4

	 * |   |

	 *  -6-

	 *

	 */

	

	const char conversionTable[10][7] = {

		      /* 0   1   2   3   4   5   6 */

		/* 0 */ '-','|','|',' ','|','|','-',	  

		/* 1 */ ' ','|',' ',' ','|',' ',' ',

		/* 2 */ '-','|',' ','-',' ','|','-',

		/* 3 */ '-','|',' ','-','|',' ','-',

		/* 4 */ ' ','|','|','-','|',' ',' ',

		/* 5 */ '-',' ','|','-','|',' ','-',

		/* 6 */ '-',' ','|','-','|','|','-',

		/* 7 */ '-','|',' ',' ','|',' ',' ',

		/* 8 */ '-','|','|','-','|','|','-',

		/* 9 */ '-','|','|','-','|',' ','-',



	};

	

	/* iterators */

	int i, j, k;

	

	while(scanf("%d %s", &s, &digitString) != EOF) {

		

		/* 0, ends the program */

		if (!s) {

			return 0;

		}

		

		int n = strlen(digitString);

		int digit;

		

		for (i = 0; i < 2*s+3; i++) {					

			for (j = 0; j < n; j ++) { 

						

				digit = digitString[j] - '0';



				/* upper, middle and lower parts */

				if ((i % (s + 1)) == 0) {

					printf(" ");

					for (k = 0; k < s; k++) {

						printf("%c", conversionTable[digit][(i / (s + 1)) * 3]);

					}

					printf(" ");

				}

				

				/* between upper and middle parts */

				if (i > 0 && i < (s + 1)) {

					printf("%c", conversionTable[digit][2]);

					for (k = 0; k < s; k++) {

						printf(" ");

					}

					printf("%c", conversionTable[digit][1]);

				}



				

				/* between middle and lower parts */

				if (i > (s + 1) && i < (2*s + 2)) {

					printf("%c", conversionTable[digit][5]);

					for (k = 0; k < s; k++) {

						printf(" ");

					}

					printf("%c", conversionTable[digit][4]);

				}

				

				/* if not the last number */

				if (j != n-1)

					printf(" ");

	

			}			

			printf("\n");

			

		}

		printf("\n");

		

	}

	

	return 0;

}




A solution for "The Trip" problem
jmftrindade (Joana M. F. da Trindade) — Sun, 09 Mar 2008 21:09:41 GMT
A solution for the Minesweeper problem.

 

Problem description:

http://icpcres.ecs.baylor.edu/onlinejudge/external/101/10137.html



Author: Joana Matos Fonseca da Trindade

Date: 2008.03.08





/* 

 * A solution for "The Trip" problem.

 * UVa ID: 10137

 */

#include 



int main (int argc, const char * argv[]) {

	/* number of students in the trip */

	long numOfStudents;

	

	/* the total sum of money spent */

	double total;

	

	/* the total amount of money to exchange in order to equalize */

	double exchange;

	

	/* the equalized trip amount to be payed by each student */

	double equalizedAmount;

	

	/* difference between the equalized amount and the amount spent */

	double diff;

	

	/* sum of all negative differences */

	double negativeSum;

	

	/* sum of all positive differences */

	double positiveSum;

	

	/* iterator */

	int i;

	

	while(scanf("%ld", &numOfStudents) != EOF) {

				

		/* 0, ends the program */

		if (!numOfStudents) {

			return 0;

		}

		

		/* keeps the amount of money spent by each student */

		double amountSpent[numOfStudents];		

		

		/* clean */

		total = 0;

		negativeSum = 0;

		positiveSum = 0;

				

		for (i = 0; i < numOfStudents; i++) {

			scanf("%lf\n", &amountSpent[i]);

			total += amountSpent[i];

		}

				

		equalizedAmount = total / numOfStudents;

		

		for (i = 0; i < numOfStudents; i++) {

			/* to ensure 0.01 precision */

			diff = (double) (long) ((amountSpent[i] - equalizedAmount) * 100.0) / 100.0;

			

			if (diff < 0) {

				negativeSum += diff;

			} else { 

				positiveSum += diff;

			}

		}



		/* when the total amount is even, these sums do not differ. otherwise, they differ in one cent */

		exchange = (-negativeSum > positiveSum) ? -negativeSum : positiveSum;

						

		/* output result */

		printf("$%.2lf\n", exchange);

	}



    return 0;

}