#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <sys/times.h>

static int case_cnt, i, *cases, *one_case, *cases_end;
static long long int j, attempts_cnt;
static clock_t tm_beg, tm_now= 0 ;
static time_t tm_all_beg, tm_all_now;

#define ice_system_bsearch(key, base, cnt, f_cmp) \
  ({ \
    register int _cmp_res, i_res, i_beg, i_end; \
    register typeof(base) p_res; \
    \
    i_beg= 0 ; \
    i_end=(cnt- 1 ); \
    while (i_end>=i_beg) \
    { \
      i_res=(i_end+i_beg)>> 1 ; \
      if ((_cmp_res=f_cmp((key), (base+i_res)))> 0 ) \
        i_beg=i_res+ 1 ; \
      else if (_cmp_res< 0 ) \
        i_end=i_res- 1 ; \
      else \
        break; \
    } \
    if (i_end>=i_beg) \
      p_res=base+i_res; \
    else \
      p_res=NULL; \
    p_res; \
  })


static inline int cmp(const void *p1, const void *p2)
{
  return (*((int *)p1)-*((int *)p2));
}

static void binary()
{
  for(j= 0 ;j<attempts_cnt;j++)
  {
    i=rand() % case_cnt;
    if (bsearch(&i, cases, case_cnt, sizeof(int), cmp)==NULL)
    {
      fprintf(stderr, "binary: error in searching\n");
      return;
    }
  }
}

static void binary_via_macros()
{
  for(j= 0 ;j<attempts_cnt;j++)
  {
    i=rand() % case_cnt;
    if (ice_system_bsearch(&i, cases, case_cnt, cmp)==NULL)
    {
      fprintf(stderr, "binary: error in searching\n");
      return;
    }
  }
}

static void linear()
{
  for(j= 0 ;j<attempts_cnt;j++)
  {
    i=rand() % case_cnt;
    for(one_case=cases;one_case<cases_end;one_case++)
      if (*one_case==i)
        goto cont;
    fprintf(stderr, "linear: error in searching\n");
    return;
  cont:;
  }
}

static inline int GetTimeNow()
{
  static struct tms buffer;
  //
  if (times(&buffer)==((clock_t) - 1 ))
  {
    perror("GetTimeNow");
    return  1 ;
  }
  else
  {
    tm_now=buffer.tms_utime;
    if ((tm_all_now=time(NULL))==((time_t)- 1 ))
    {
      perror("GetTimeNow");
      return  1 ;
    }
    return  0 ;
  }
}

static inline int GetTimeStat()
{
  if (GetTimeNow())
    return  1 ;
  fprintf(stderr, "Job proceeded %lf seconds\n", (tm_now-tm_beg)/(double) sysconf(_SC_CLK_TCK));
  fprintf(stderr, "%d seconds spended in system environment at all\n", (int)(tm_all_now-tm_all_beg));
  return  0 ;
}

int main(int argc, char **argv)
{
  case_cnt=atoi(argv[ 1 ]);
  attempts_cnt=strtoll(argv[ 2 ], NULL,  10 );
  if ((cases=malloc(case_cnt*sizeof(int)))==NULL)
  {
    fprintf(stderr, "No memory\n");
    return  1 ;
  }
  for (i= 0 ;i<case_cnt;i++)
    cases[i]=i;
  cases_end=cases+case_cnt;
  //
  tm_all_beg=time(NULL);
  {
    struct tms buffer;
    //
    if (times(&buffer)==((clock_t) - 1 ))
    {
      perror("main: cannot find time: ");
      return  1 ;
    }
    else
      tm_beg=buffer.tms_utime;
  }
  //
  fprintf(stderr, "Binary search is about to start...\n");
  binary();
  GetTimeStat();
  fprintf(stderr, "Binary (via macros) search is about to start...\n");
  binary_via_macros();
  GetTimeStat();
  fprintf(stderr, "Linear search is about to start...\n");
  linear();
  GetTimeStat();
  return  0 ;
}