#c #prog

Пост специально для Вафеля.

Преамбула:
У нас в кодах есть очередь. Она предназначена для работы из двух потоков: один поток пишет в очередь, другой из неё читает.
При этом в ней не используются никакие примитивы синхронизации. И вот не все верят в то, что это может работать гарантированно и безопасно.
Сейчас я покажу, что это за очередь и объясню как она работает, и почему это безопасно. Единственное, чтобы соблюсти все правовые аспекты, я рассмотрю не конкретно ту очередь, что используется у нас, а напишу вольную интерпретацию идеи на чистом Си.
К слову, идея очень просто и элегантна и очень мне нравится. Вполне вероятно, что этот код изначально был взят из книг (Александреску, или что-то подобное), но уверенности у меня в этом нет, только подозрение.

Так как переписываем на Си, и шаблонов тут нема, то в качестве данных будем использовать обычный int.
Итак, нам нужна очередь. Простейший способ оформить очередь - односвязный список. Так и сделаем:

struct Item {
   int data;
   struct Item* next;
};

Так же добавим для удобства методы для создания и удаления Item'а:

struct Item* new_item(int data) {
   struct Item* item = (struct Item*)calloc(1, sizeof(struct Item));
   item->data = data;
   return item;
}
void free_item(struct Item* item) {
   free(item);
}

Обращаю внимание, что мы не следим за корректностью выделения памяти и проверкой входных данных на NULL, ибо это всего лишь пример.

Что же, вроде бы очередь фактически готова, но пока не понятно, как оно может предоставлять гарантии безопасности и отсутствия гонок данных при конкурентном доступе. А всё потому, что чтобы магия заработала, нам потребуется ещё одна небольшая структурка:

struct Queue {
   struct Item* head;
   struct Item* tail;
}
struct Queue* queue_init() {
   struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
   struct Item* item = new_item(0);
   queue->head = item;
   queue->tail = item;
   return queue;
}

В примере выше нет функции-деструктора, потому что в нём будет некоторая хитрость, и рассмотрим мы его позже.