Код K&R malloc не имеет смысла?

Этот код взят из книги K&R — Глава 8 Раздел 7: Пример — Распределитель памяти. Этот код, по крайней мере для меня, не имеет смысла. «Заголовок» — это объединение структуры и «наиболее ограничительного типа выравнивания», который является длинным типом. Затем Malloc найдет достаточно большое свободное пространство размером, кратным размеру заголовка.

static Header base;            /* empty list to get started */
static Header *freep = NULL;   /* start of free list */

/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
  Header *p, *prevp;
  Header *morecore(unsigned);
  unsigned nunits;
  nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
  if ((prevp = freep) == NULL) {     /* no free list yet */
    base.s.ptr = freeptr = prevptr = &base;
    base.s.size = 0;
  }
  for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
    if (p->s.size >= nunits) { /* big enough */
      if (p->s.size == nunits) /* exactly */
        prevp->s.ptr = p->s.ptr;
      else {     /* allocate tail end */
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits;
      }
      freep = prevp;
      return (void *)(p+1);
    }
    if (p == freep) /* wrapped around free list */
      if ((p = morecore(nunits)) == NULL)
        return NULL; /* none left */

  }
}

Нечетной частью этого кода является оператор nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;, который затем используется в сравнении if (p->s.size >= nunits), чтобы найти достаточно большое пространство с единицами измерения с точки зрения размера заголовка. Разве первое не должно быть только nunits = (nbytes+sizeof(Header)) / sizeof(Header)? Исходный код будет оценивать значение меньше, чем должно быть. Что с +-1s? Зачем выделять места меньше, чем нужно.


person 1der    schedule 26.05.2012    source источник
comment
Помните о приоритете оператора и снова проанализируйте его...   -  person K-ballo    schedule 27.05.2012
comment
@duffymo: Вместо того, чтобы рассказывать мне это, не могли бы вы просто рассказать мне, как работает код? Кстати, вы читали эту книгу? Заметили множество опечаток? Но про них никто ничего не говорил.   -  person 1der    schedule 27.05.2012
comment
Предположим, что это первый вызов malloc, и вы запросили 1 байт, т. е. malloc(1), и посмотрите, что возвращает nunits как с предложенным вами исправлением, так и с кодом из книги.   -  person dirkgently    schedule 27.05.2012
comment
@K-ballo: Конечно, какой же я глупый. Но есть еще одна путаница. Этот код будет оценивать больший размер для больших распределений. Почему бы просто не сделать арифметику без единиц?   -  person 1der    schedule 27.05.2012
comment
Да, я читал книгу. Ты читаешь это в первый раз, а не я. Потратьте некоторое время на обдумывание идиомы.   -  person duffymo    schedule 27.05.2012
comment
@dirkgently: теперь это имеет смысл   -  person 1der    schedule 27.05.2012
comment
K&R — это не учебник по программированию. Его целевой аудиторией являются программисты, поэтому авторы могут обращаться с вами как со взрослыми. Они не говорят вам, как это работает, потому что предполагают, что, зная детали, из которых оно состоит, вы можете во всем разобраться сами. Если вы обнаружите, что вас что-то смущает, вы, вероятно, недостаточно тщательно об этом подумали. Вернитесь назад, прочтите эту часть еще раз и обдумайте точно то, что было сказано.   -  person dmckee --- ex-moderator kitten    schedule 27.05.2012
comment
@dmckee: хорошо сказано. Я запомню это.   -  person 1der    schedule 27.05.2012


Ответы (2)


-1 и +1 должны учитывать значения, которые не умножаются на размер блока.

Например, предположим, что размер блока равен 10. Если вы попытаетесь использовать формулу n / 10, чтобы получить количество требуемых блоков, то вы получите 1 блок для n = 15. Это неверно, вам нужно 2.

Если вы измените формулу на n / 10 + 1, она также будет неправильной. Когда n = 20, вам нужно всего 2 блока, но эта формула вернет 3.

Правильная формула (n - 1) / 10 + 1. Вот как вы округляете с помощью целочисленного деления. Единственная разница между этим и формулой, о которой вы спрашивали, - это дополнительное sizeof(Header), которое является дополнительным пространством, необходимым для самого заголовка.

person Peter Alexander    schedule 26.05.2012
comment
Спасибо, это действительно помогает. На самом деле путаница возникла из-за того, что я рассматривал выражение после знака деления '/' как единое целое. - person 1der; 27.05.2012
comment
Не проще ли использовать (n + 9) / 10? - person Joshua Green; 27.05.2012
comment
@JoshuaGreen: Да, это то, что я обычно использую. - person Peter Alexander; 27.05.2012
comment
Скорее всего портировали с ассемблера :-) - person Prof. Falken; 28.12.2012

(nbytes+sizeof(Header)-1)/sizeof(Header) + 1 — довольно стандартная идиома в коде для получения количества единиц чего-либо с правильным округлением. Если вы попробуете это с некоторыми значениями, вы увидите, что это работает правильно.

Фактическая идиома лучше выражается как (nbytes - 1)/unitSizeInBytes + 1.

Чтобы уточнить, исходя из последнего абзаца принятого ответа, использование sizeof(Header) различно с обеих сторон разделения. Его использование в дивиденде связано с тем, что ему необходимо выделить байты для заголовка и nbytes. Он используется в делителе, потому что это размер выделяемых блоков. В этом случае бывает, что они имеют одно и то же значение, sizeof(Header).

person Francis Upton IV    schedule 26.05.2012
comment
Да, и, как говорит К-балло, учитывайте приоритет операторов. - person Francis Upton IV; 27.05.2012
comment
Означает ли это, что я должен много читать чужие коды, чтобы ознакомиться с этими стандартными идиомами? - person 1der; 27.05.2012
comment
Да, это так, и задавать подобные вопросы тоже хорошая идея, но перед этим внимательно изучите. Читайте хороший открытый исходный код. Тогда работайте над этим. Сделать мир лучше. :) - person Francis Upton IV; 27.05.2012
comment
@1der: Вы также столкнетесь с подобными вещами, просто написав много кода. В какой-то момент вам нужно будет решить ту же проблему, и вы, вероятно, найдете такое же решение и научитесь его распознавать. - person Peter Alexander; 27.05.2012
comment
Я так понимаю выражение в делении, что просто получается потолок nbytes/sizeof(Header). Для чего + 1? - person Joshua Green; 27.05.2012
comment
Чтобы учесть, что бы остаток округлить до следующего значения. Если бы у вас его не было и деления не было ровным то вы бы и единицы на остаток не выделили. - person Francis Upton IV; 27.05.2012
comment
Разве (nbytes + sizeof(Header) - 1)/sizeof(Header) не учитывает остаток автоматически? Я думаю, что это выражение всегда дает потолок деления и, следовательно, + 1 не нужен и приводит к тому, что приведенный выше код выделяет на одну единицу больше, чем необходимо. - person Joshua Green; 27.05.2012
comment
Посмотрите на пересмотр моих комментариев и принятый ответ. - person Francis Upton IV; 27.05.2012
comment
Ах, нам нужно достаточно места для nbytes (в единицах sizeof(Header)), а также достаточно места для хранения Header. Спасибо за разъяснения. - person Joshua Green; 27.05.2012