Начиная цикл заметок о программировании для Nginx, хочется рассказать о списках.

Общие сведения

В nginx (для 0.6.29 вполне актуально) есть связанные списки. Каждый список представляет собой структуру:

typedef struct {
    ngx_list_part_t  *last;
    ngx_list_part_t   part;
    size_t            size;
    ngx_uint_t        nalloc;
    ngx_pool_t       *pool;
} ngx_list_t;

Здесь:

• last — указатель на предыдущий элемент списка
• part — указатель на текущий элемент списка
• size — размер элементов списка. Т.е. если надо хранить строки, то размер будет равен sizeof(ngx_str_t)
• nalloc — количество выделенных элементов памяти для одной части.
• pool — указатель на pool памяти

Список состоит из частей (часть — выделенный блок памяти):

typedef struct ngx_list_part_s  ngx_list_part_t;

struct ngx_list_part_s {
    void             *elts;
    ngx_uint_t        nelts;
    ngx_list_part_t  *next;
};

Здесь:

• elts — указатель на память, где располагаются элементы списка
• nelts — количество использованных элементов в части
• next — указатель на следующую часть

Т.е. список — это несколько частей (минимум 1), в которых располагаются элементы. Каждая часть имеет свою длину и указатель на следующую часть или NULL, если в ней еще есть место. Размер всех частей равен.

Работа со списком

Создание

Всегда можно пересоздать список, используя функцию:

ngx_list_t *ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);

С ее параметрами должно быть все понятно: size — размер одного элемента, n — количество элементов в части, pool — pool с памятью, к которому привязывается выделенная память.

Функция создает новый список и инициализирует его (создает первую часть и определяет размер части). Возвращаемое значение — указатель на список или NULL в случае ошибки.

Инициализация

Список можно не создавать, а просто инициализировать (если у нас он определен на стеке), используя функцию:

static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size)

Параметры ее аналогичны ngx_list_create, за исключением первого — это указатель на список, который будет инициализироваться (или переинициализироваться). Функция возвращает либо NGX_OK в случае успеха, либо NGX_ERROR в случае проблем. Функция небезопасна, т.е. можно переинициализировать любой существующий список и все старые данные потеряются ☺

Добавление элемента

Для добавления элемента в список используется функция:

void *ngx_list_push(ngx_list_t *list);

Она принимает указатель на список и возвращает указатель на место в части, в которое можно записывать значения. Если часть закончилась, создается новая и возвращается указатель на ее первый элемент.

Хождение по элементам списка

Для хождения по списку приходится использовать такой код:

part = &list.part;
data = part->elts;

for (i = 0 ;;i++) {
  if (i >= part->nelts) {
    if (part->next == NULL) {
      break;
    }

    part = part->next;
    data = part->elts;
    i = 0;
  }

  /* use element of list as data[i] */

}

Вместо комментария вставляется ваш код, в котором будет происходить обращение к элементам списка.

Пример работы

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

void ngx_list_sample_using(ngx_http_request_t *r)
{
  ngx_list_t       list;
  ngx_uint_t       i;
  ngx_list_part_t *part;
  ngx_uint_t      *list_element;
  ngx_uint_t      *sum = 0;

  if (ngx_list_init(&list, r->pool, 5, sizeof(ngx_uint_t)) == NGX_ERROR) {
    return;
  }

  for (i = 0; i < 10; i++) {
    list_element = ngx_list_push(&list);
    if (list_element == NULL) {
      return;
    }
    *list_element = i; 
  }

  part = &list.part;
  data = part->elts;

  for (i = 0 ;;i++) {
    if (i >= part->nelts) {
      if (part->next == NULL) {
        break;
      }

      part = part->next;
      data = part->elts;
      i = 0;
    }

  sum += data[i];

  }
/* here sum is 45 */
}