/* 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 <sys/types.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <sys/ioctl.h>
#include <signal.h>
#include <pthread.h>
#include <string.h>

#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;
}

#ifndef _SGLIB__h_
#define _SGLIB__h_

/* the assert is used exclusively to write unexpected error messages */
#include <assert.h>


/* ---------------------------------------------------------------------------- */
/* ---------------------------------------------------------------------------- */
/* -                            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<t)) {\
      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<t)) {\
      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 = t->left;\
    } 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h>

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<str2_len));i++, j++) {
		result[i]=str2[j];
	}
	result[str1_len+str2_len]='\0';
	return result;
}

#include <sys/statvfs.h>
#include <glib.h>

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;
}

/******************************************************************************
 * 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)