#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
/* #define DEBUG */
#if defined(DEBUG)
#include "xmalloc.h"
#else
#define xmalloc(x, y) malloc(x)
#define xfree(x, y) free(x)
#define xrealloc(x, y, z) realloc(x, y)
#define xmallocdump()
#endif
#define ID_DATANODE 1001
 
struct node {
  int value;
  struct node *next;
};
 
void push(struct node **root, int value) {
  struct node *p;
  if ((p = xmalloc(sizeof(struct node), ID_DATANODE)) != 0) {
    p->value = value;
    p->next = *root;
    *root = p;
  }
}
 
int pop(struct node **root, int *value) {
  int r;
  struct node *p;
  r = 0;
  if (*root != 0) {
    p = *root;
    *root = p->next;
    *value = p->value;
    xfree(p, ID_DATANODE);
    r = 1;
  }
  return r;
}
 
void sub_swap(struct node **p, struct node **q) {
  struct node *t, *s;
  if (&((*p)->next) == q) {
    assert((*p)->next == *q);
    t = *p;
    s = (*q)->next;
    *p = (*p)->next;
    (*q)->next = t;
    *q = s;
  } else {
    t = *p;
    *p = *q;
    *q = t;
    s = (*p)->next; /* in fact *p<=>*q but neet to do (*p)->next <=> (*q)->next */
    (*p)->next = (*q)->next;
    (*q)->next = s;
  }
}
 
void combsort(struct node **root, int n, int (*comp)(int, int)) {
  struct node **p, **q;
  int i, h, flag, c;
  c = 0;
  h = n;
  do {
    h = (int)(h / 1.247330950103979);
    if (h == 10)
      h = 11;
    if (h < 1)
      h = 1;
    fprintf(stderr, "%d:%d\n", ++c, h);
    flag = 0;
    for (q = root, i = 0; i < h; q = &((*q)->next), i++)
      ;
    p = root;
    for (;;) {
      if (comp((*p)->value, (*q)->value) > 0) {
        flag = 1;
        sub_swap(p, q);
      }
      if (*p == 0 || *q == 0 || (*p)->next == 0 || (*q)->next == 0)
        break;
      p = &((*p)->next);
      q = &((*q)->next);
    }
  } while (flag);
}
 
int cmp_ascent(int a, int b) {
  return a - b;
}
 
int isSortOK(struct node *root) {
  if (root->next) {
    if (root->value <= root->next->value) {
      return isSortOK(root->next);
    } else {
      return 0;
    }
  } else {
    return 1;
  }
}
 
#define SEED 31415926
#define N 100
int main(int argc, char *argv[]) {
  struct node *root;
  int i, v, flag;
 
  root = 0;
  srand(SEED);
  for (i = 0; i < N; i++)
    push(&root, (rand() / (RAND_MAX + 1.0) * 1000.0));
 
  combsort(&root, i, cmp_ascent);
  flag = isSortOK(root);
 
  i = 0;
  while (pop(&root, &v) != 0)
    printf("%3d : %4d\n", ++i, v);
 
  if (flag)
    fprintf(stderr, "Good.\n");
  else
    fprintf(stderr, "NG, there are some bugs in this program.\n");
  xmallocdump();
  return 0;
}
/* end */
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8YXNzZXJ0Lmg+CiAKLyogI2RlZmluZSBERUJVRyAqLwojaWYgZGVmaW5lZChERUJVRykKI2luY2x1ZGUgInhtYWxsb2MuaCIKI2Vsc2UKI2RlZmluZSB4bWFsbG9jKHgsIHkpIG1hbGxvYyh4KQojZGVmaW5lIHhmcmVlKHgsIHkpIGZyZWUoeCkKI2RlZmluZSB4cmVhbGxvYyh4LCB5LCB6KSByZWFsbG9jKHgsIHkpCiNkZWZpbmUgeG1hbGxvY2R1bXAoKQojZW5kaWYKI2RlZmluZSBJRF9EQVRBTk9ERSAxMDAxCgpzdHJ1Y3Qgbm9kZSB7CiAgaW50IHZhbHVlOwogIHN0cnVjdCBub2RlICpuZXh0Owp9OwoKdm9pZCBwdXNoKHN0cnVjdCBub2RlICoqcm9vdCwgaW50IHZhbHVlKSB7CiAgc3RydWN0IG5vZGUgKnA7CiAgaWYgKChwID0geG1hbGxvYyhzaXplb2Yoc3RydWN0IG5vZGUpLCBJRF9EQVRBTk9ERSkpICE9IDApIHsKICAgIHAtPnZhbHVlID0gdmFsdWU7CiAgICBwLT5uZXh0ID0gKnJvb3Q7CiAgICAqcm9vdCA9IHA7CiAgfQp9CgppbnQgcG9wKHN0cnVjdCBub2RlICoqcm9vdCwgaW50ICp2YWx1ZSkgewogIGludCByOwogIHN0cnVjdCBub2RlICpwOwogIHIgPSAwOwogIGlmICgqcm9vdCAhPSAwKSB7CiAgICBwID0gKnJvb3Q7CiAgICAqcm9vdCA9IHAtPm5leHQ7CiAgICAqdmFsdWUgPSBwLT52YWx1ZTsKICAgIHhmcmVlKHAsIElEX0RBVEFOT0RFKTsKICAgIHIgPSAxOwogIH0KICByZXR1cm4gcjsKfQoKdm9pZCBzdWJfc3dhcChzdHJ1Y3Qgbm9kZSAqKnAsIHN0cnVjdCBub2RlICoqcSkgewogIHN0cnVjdCBub2RlICp0LCAqczsKICBpZiAoJigoKnApLT5uZXh0KSA9PSBxKSB7CiAgICBhc3NlcnQoKCpwKS0+bmV4dCA9PSAqcSk7CiAgICB0ID0gKnA7CiAgICBzID0gKCpxKS0+bmV4dDsKICAgICpwID0gKCpwKS0+bmV4dDsKICAgICgqcSktPm5leHQgPSB0OwogICAgKnEgPSBzOwogIH0gZWxzZSB7CiAgICB0ID0gKnA7CiAgICAqcCA9ICpxOwogICAgKnEgPSB0OwogICAgcyA9ICgqcCktPm5leHQ7IC8qIGluIGZhY3QgKnA8PT4qcSBidXQgbmVldCB0byBkbyAoKnApLT5uZXh0IDw9PiAoKnEpLT5uZXh0ICovCiAgICAoKnApLT5uZXh0ID0gKCpxKS0+bmV4dDsKICAgICgqcSktPm5leHQgPSBzOwogIH0KfQoKdm9pZCBjb21ic29ydChzdHJ1Y3Qgbm9kZSAqKnJvb3QsIGludCBuLCBpbnQgKCpjb21wKShpbnQsIGludCkpIHsKICBzdHJ1Y3Qgbm9kZSAqKnAsICoqcTsKICBpbnQgaSwgaCwgZmxhZywgYzsKICBjID0gMDsKICBoID0gbjsKICBkbyB7CiAgICBoID0gKGludCkoaCAvIDEuMjQ3MzMwOTUwMTAzOTc5KTsKICAgIGlmIChoID09IDEwKQogICAgICBoID0gMTE7CiAgICBpZiAoaCA8IDEpCiAgICAgIGggPSAxOwogICAgZnByaW50ZihzdGRlcnIsICIlZDolZFxuIiwgKytjLCBoKTsKICAgIGZsYWcgPSAwOwogICAgZm9yIChxID0gcm9vdCwgaSA9IDA7IGkgPCBoOyBxID0gJigoKnEpLT5uZXh0KSwgaSsrKQogICAgICA7CiAgICBwID0gcm9vdDsKICAgIGZvciAoOzspIHsKICAgICAgaWYgKGNvbXAoKCpwKS0+dmFsdWUsICgqcSktPnZhbHVlKSA+IDApIHsKICAgICAgICBmbGFnID0gMTsKICAgICAgICBzdWJfc3dhcChwLCBxKTsKICAgICAgfQogICAgICBpZiAoKnAgPT0gMCB8fCAqcSA9PSAwIHx8ICgqcCktPm5leHQgPT0gMCB8fCAoKnEpLT5uZXh0ID09IDApCiAgICAgICAgYnJlYWs7CiAgICAgIHAgPSAmKCgqcCktPm5leHQpOwogICAgICBxID0gJigoKnEpLT5uZXh0KTsKICAgIH0KICB9IHdoaWxlIChmbGFnKTsKfQoKaW50IGNtcF9hc2NlbnQoaW50IGEsIGludCBiKSB7CiAgcmV0dXJuIGEgLSBiOwp9CgppbnQgaXNTb3J0T0soc3RydWN0IG5vZGUgKnJvb3QpIHsKICBpZiAocm9vdC0+bmV4dCkgewogICAgaWYgKHJvb3QtPnZhbHVlIDw9IHJvb3QtPm5leHQtPnZhbHVlKSB7CiAgICAgIHJldHVybiBpc1NvcnRPSyhyb290LT5uZXh0KTsKICAgIH0gZWxzZSB7CiAgICAgIHJldHVybiAwOwogICAgfQogIH0gZWxzZSB7CiAgICByZXR1cm4gMTsKICB9Cn0KCiNkZWZpbmUgU0VFRCAzMTQxNTkyNgojZGVmaW5lIE4gMTAwCmludCBtYWluKGludCBhcmdjLCBjaGFyICphcmd2W10pIHsKICBzdHJ1Y3Qgbm9kZSAqcm9vdDsKICBpbnQgaSwgdiwgZmxhZzsKCiAgcm9vdCA9IDA7CiAgc3JhbmQoU0VFRCk7CiAgZm9yIChpID0gMDsgaSA8IE47IGkrKykKICAgIHB1c2goJnJvb3QsIChyYW5kKCkgLyAoUkFORF9NQVggKyAxLjApICogMTAwMC4wKSk7CgogIGNvbWJzb3J0KCZyb290LCBpLCBjbXBfYXNjZW50KTsKICBmbGFnID0gaXNTb3J0T0socm9vdCk7CgogIGkgPSAwOwogIHdoaWxlIChwb3AoJnJvb3QsICZ2KSAhPSAwKQogICAgcHJpbnRmKCIlM2QgOiAlNGRcbiIsICsraSwgdik7CgogIGlmIChmbGFnKQogICAgZnByaW50ZihzdGRlcnIsICJHb29kLlxuIik7CiAgZWxzZQogICAgZnByaW50ZihzdGRlcnIsICJORywgdGhlcmUgYXJlIHNvbWUgYnVncyBpbiB0aGlzIHByb2dyYW0uXG4iKTsKICB4bWFsbG9jZHVtcCgpOwogIHJldHVybiAwOwp9Ci8qIGVuZCAqLwo=