Как я Применяю Анонимную функцию из Списка в Схеме?

1120 Хорошо, у нас есть кусок действительно плохо написанного кода. То, что я сделаю в этом посте, лучше всего описать как программную археологию.

Шаг 1: исправить форматирование.

Отступ и компактный формат никому не помогают. Различные пробелы и пустые строки должны быть вставлены. Комментарии могут быть написаны более читабельными способами. Я начну с исправления.

В то же время я меняю стиль фигурной скобки с стиля K & amp; R - пожалуйста, обратите внимание, что стиль фигурной скобки K & amp; R является приемлемым, это просто мое личное предпочтение. Другое личное предпочтение - написать * для указателей рядом с указанным типом. Я не буду спорить о (субъективных) вопросах стиля здесь.

Кроме того, определение типа Header полностью нечитаемо, оно нуждается в радикальном исправлении.

И я заметил нечто совершенно неясное: кажется, они объявили прототип функции внутри функции. Header* morecore(unsigned);. Это очень старый и очень плохой стиль, и я не уверен, что C даже позволяет это больше. Давайте просто удалим эту строку, что бы ни делала эта функция, она должна быть определена в другом месте.

typedef long Align;                      /* for alignment to long boundary */

typedef union header                     /* block header */
{
  struct
  {
    union header *ptr;                   /* next block if on free list */
    unsigned size;                       /* size of this block */
  } s;

  Align x;                               /* force alignment of blocks */

} Header;


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;
  Header*   prevp;
  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 */
  }
}

Хорошо, теперь мы можем прочитать код.

Шаг 2: отсеять широко признанную плохую практику.

Этот код заполнен вещами, которые в настоящее время считаются плохой практикой. Их необходимо удалить, поскольку они ставят под угрозу безопасность, удобочитаемость и обслуживание кода. Если вам нужна ссылка на авторитет, проповедующий ту же практику, что и я, ознакомьтесь с широко признанным стандартом кодирования MISRA-C .

Я обнаружил и удалил следующие плохие практики:

1) Просто набрать unsigned в коде может привести к путанице: это была опечатка программистом или было намерение написать unsigned int? Мы должны заменить все unsigned на unsigned int. Но когда мы это сделаем, мы обнаружим, что он используется в этом контексте для определения размера различных двоичных данных. Правильным типом, который следует использовать для таких целей, является стандартный тип C size_t. По сути, это также просто unsigned int, но он гарантированно будет «достаточно большим» для конкретной платформы. Оператор sizeof возвращает результат типа size_t, и если мы посмотрим на определение реального malloc в стандарте C, это будет void *malloc(size_t size);. Таким образом, size_t является наиболее правильным типом для использования.

2) Плохая идея использовать то же имя для нашей собственной функции malloc, что и в stdlib.h. Если нам нужно будет включить stdlib.h, все будет грязно. Как правило, никогда не используйте имена идентификаторов функций стандартной библиотеки Си в своем собственном коде. Я поменяю имя на kr_malloc.

3) Код злоупотребляет тем фактом, что все статические переменные гарантированно инициализируются нулями. Это хорошо определено стандартом Си, но довольно тонкое правило. Давайте явным образом инициализируем все статические данные, чтобы показать, что мы не забыли инициировать их случайно.

4) Распределение внутри условий опасно и трудно читаемо. Этого следует избегать, если это возможно, поскольку это также может привести к ошибкам, таким как классическая ошибка = vs ==.

5) Несколько заданий в одном ряду трудно читать, а также, возможно, опасно из-за порядка оценки.

6) Несколько объявлений в одной строке трудно читать и опасно, поскольку это может привести к ошибкам при смешивании данных и объявлений указателей. Всегда объявляйте каждую переменную в отдельной строке.

7) Всегда использует фигурные скобки после каждого утверждения. Невыполнение этого требования приведет к ошибкам. Ошибки.

8) Никогда не вводите приведение из определенного типа указателя в void *. В C это не нужно и может скрывать ошибки, которые иначе компилятор обнаружил бы.

9) Избегайте использования нескольких операторов return внутри функции. Иногда они приводят к более четкому коду, но в большинстве случаев они приводят к спагетти. Поскольку код стоит, мы не можем изменить это без переписывания цикла, поэтому я исправлю это позже.

10) Держите петли простыми. Они должны содержать один оператор init, одно условие цикла и одну итерацию, больше ничего. Цикл for с оператором запятой и всем остальным очень неясен. Опять же, мы замечаем необходимость переписать этот цикл в нечто вменяемое. Я сделаю это дальше, но сейчас у нас есть:

typedef long Align;                      /* for alignment to long boundary */

typedef union header                     /* block header */
{
  struct
  {
    union header *ptr;                   /* next block if on free list */
    size_t size;                         /* size of this block */
  } s;

  Align x;                               /* force alignment of blocks */

} Header;


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


/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
  Header*  p;
  Header*  prevp;
  size_t   nunits;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;

  prevp = freep;
  if (prevp == NULL)                     /* no free list yet */
  {
    base.s.ptr  = &base;
    freeptr     = &base;
    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 p+1;
    }

    if (p == freep)                      /* wrapped around free list */
    {
      p = morecore(nunits);
      if (p == NULL)
      {
        return NULL;                     /* none left */
      }
    }
  } /* for */
}

Шаг 3: переписать скрытый цикл.

По причинам, упомянутым ранее. Мы можем видеть, что этот цикл продолжается вечно, он завершается возвратом из функции, либо когда выделение завершено, либо когда не осталось памяти. Итак, давайте создадим это как условие цикла и перенесем возврат в конец функции, где она должна быть. И давайте избавимся от этого уродливого оператора запятой.

Я введу две новые переменные: одну переменную результата, чтобы хранить результирующий указатель, и другую, чтобы отслеживать, должен ли цикл продолжаться или нет. Я взорву умы K & amp; R, используя тип bool, который является частью языка C с 1999 года.

(Я надеюсь, что я не изменил алгоритм с этим изменением, я думаю, что не сделал)

#include 

typedef long Align;                      /* for alignment to long boundary */

typedef union header                     /* block header */
{
  struct
  {
    union header *ptr;                   /* next block if on free list */
    size_t size;                         /* size of this block */
  } s;

  Align x;                               /* force alignment of blocks */

} Header;


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


/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
  Header*  p;
  Header*  prevp;
  size_t   nunits;
  void*    result;
  bool     is_allocating;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;

  prevp = freep;
  if (prevp == NULL)                     /* no free list yet */
  {
    base.s.ptr  = &base;
    freeptr     = &base;
    prevptr     = &base;
    base.s.size = 0;
  }

  is_allocating = true;
  for (p = prevp->s.ptr; is_allocating; 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;
      result = p+1;
      is_allocating = false;             /* we are done */
    }

    if (p == freep)                      /* wrapped around free list */
    {
      p = morecore(nunits);
      if (p == NULL)
      {
        result = NULL;                   /* none left */
        is_allocating = false;
      }
    }
    prevp = p;
  } /* for */

  return result;
}

Шаг 4: сделайте это дерьмо скомпилированным.

1145] Так как это из K & amp; R, оно заполнено опечатками. sizeof(header) должно быть sizeof(Header). Есть пропущенные точки с запятой. Они используют разные имена freep, prevp и freeptr, prevptr, но явно обозначают одну и ту же переменную. Я считаю, что последние на самом деле были лучшими именами, поэтому давайте воспользуемся ими.

#include 

typedef long Align;                      /* for alignment to long boundary */

typedef union header                     /* block header */
{
  struct
  {
    union header *ptr;                   /* next block if on free list */
    size_t size;                         /* size of this block */
  } s;

  Align x;                               /* force alignment of blocks */

} Header;


static Header base = {0};                /* empty list to get started */
static Header* freeptr = NULL;           /* start of free list */


/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
  Header*  p;
  Header*  prevptr;
  size_t   nunits;
  void*    result;
  bool     is_allocating;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

  prevptr = freeptr;
  if (prevptr == NULL)                   /* no free list yet */
  {
    base.s.ptr  = &base;
    freeptr     = &base;
    prevptr     = &base;
    base.s.size = 0;
  }

  is_allocating = true;
  for (p = prevptr->s.ptr; is_allocating; p = p->s.ptr)
  {
    if (p->s.size >= nunits)             /* big enough */
    {
      if (p->s.size == nunits)           /* exactly */
      {
        prevptr->s.ptr = p->s.ptr;
      }
      else                               /* allocate tail end */
      {
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits;
      }

      freeptr = prevptr;
      result = p+1;
      is_allocating = false;             /* we are done */
    }

    if (p == freeptr)                    /* wrapped around free list */
    {
      p = morecore(nunits);
      if (p == NULL)
      {
        result = NULL;                   /* none left */
        is_allocating = false;
      }
    }
    prevptr = p;
  } /* for */

  return result;
}

И теперь у нас есть несколько читаемый, поддерживаемый код, без многочисленных опасных практик, который даже скомпилируется! Так что теперь мы можем начать размышлять о том, что на самом деле делает код.

Структура «Заголовок» - это, как вы уже догадались, объявление узла в связанном списке. Каждый такой узел содержит указатель на следующий. Я не совсем понимаю ни функцию morecore, ни «обход», я никогда не использовал ни эту функцию, ни sbrk. Но я предполагаю, что он выделяет заголовок, как указано в этой структуре, а также некоторый кусок необработанных данных, следующих за этим заголовком. Если это так, это объясняет, почему нет фактического указателя данных: предполагается, что данные следуют за заголовком, смежно в памяти. Таким образом, для каждого узла мы получаем заголовок и получаем фрагмент необработанных данных после заголовка.

Сама итерация довольно проста: они проходят через односвязный список, по одному узлу за раз.

В конце цикла они устанавливают указатель так, чтобы он указывал на один конец конца «чанка», затем сохраняют его в статической переменной, чтобы программа запомнила, где она ранее выделяла память, в следующий раз, когда функция называется.

Они используют уловку, чтобы заголовок заканчивался на выровненном адресе памяти: они хранят всю служебную информацию в объединении вместе с переменной, достаточно большой, чтобы соответствовать требованию выравнивания платформы. Таким образом, если размер «ptr» плюс размер «size» слишком мал для точного выравнивания, объединение гарантирует, что будет выделено как минимум sizeof (Align) байтов. Я полагаю, что весь этот трюк сегодня устарел, поскольку стандарт C требует автоматического заполнения struct / union.