Fifo реализация на Си с минимальными затратами по времени

Перезатирай удаляемые элементы списка новыми, вместо того, чтоб удалять и снова распределять для них память.

Зачем тебе маллок и фри? Зачем сдвигать массив? Отцепляешь голову, затираешь данные, переносишь в хвост. В случае с массивом хранишь указатель (или индекс на голову и хвост

man кольцевой буфер

Почему бы тебе не использовать массив в качестве циклического списка:

  i = ( i + 1 ) % 5

Придется все элементы перетасовывать, важно, что-бы последовательность поступающих элементов сохранялась.

Не подойдет, поскольку он будет менять последовательность элементов, если мы полностью заполним его, то новый элемент запишется на место первого, если буфер из 5-ти элементов, то получится, что 6-й встанет на место первого, а следующий будет 2-м в последовательности

Та же самая проблема, что и с кольцевым буфером, 6-й элемент запишется на место первого, за ним в очереди будет 2-й, а надо, чтобы второй стал первым (с нулевым смещением в массиве) а 6-й, 5-м (со смещением 4 в массиве)

странно, конечно.

список можно, а кольцевой буфер нет. почему-то. почему?

списком можно и без malloc\free. создаешь список из 5-и элементов, при записи меняешь указатель на следующий свободный элемент списка. те же яйца (что и кольцевой буфер) только в профиль. только доступ по индексу всяко быстрее и проще.

Придется все элементы перетасовывать, важно, что-бы последовательность поступающих элементов сохранялась.

Храни рядом массив референсов и тасуй его. А массив с данными делай, как ребята предлагают.

Придется все элементы перетасовывать

Зачем перетасовывать все элементы списка? Вставляешь на место последнего новый элемент, который теперь указывает на 2-й, а предпоследний, указывавший на последний, теперь указывает на NULL, т. е. становится последним. Т. о. заменяются только 2 указателя, плюс first и last указатели, которые показывают, куда вставлять и на что указывать вставляемому в следующий раз.

5 -> 4 -> 3 -> 2 -> 1

(6) -> 5 -> 4 -> 3 -> 2

Адрес (6) == адресу 1.

Ну допустим у нас есть кольцевой буфер из 5-ти элементов, при инициализации и голова и хвост указывают на 0-й элемент, поступили данные, 1,2,3,4,5,6. 6 встал на 0-й элемент и буфер стал представлять такую последовательность: 6,2,3,4,5. А мне нужно, чтобы он представлял вот какую: 2,3,4,5,6. Этого можно достичь только сдвигом всего массива на 1 элемент, или я чего-то не догоняю. Списком можно, но придется делать фри для нулевого элемента и маллок для последнего пришедшего

До этого не додумался, спасибо

Получается, что нужно всего 5 маллоков при инициализации?

буфер стал представлять такую последовательность: 6,2,3,4,5. А мне нужно, чтобы он представлял вот какую: 2,3,4,5,6

ты не можешь считать начиная со второго элемента? интересно почему.

Списком можно, но придется делать фри для нулевого элемента и маллок для последнего пришедшего

не придется. достаточно поменять указатель на следующий элемент УЖЕ аллоцированного списка.

Со списком понял, уже объяснили

А если так?

Было:

   Head
   |
   V
34512
  ^
  |
  tail

Т.е. 12345

Стало

    Head
    |
    V
34562
   ^
   |
   tail

Т.е. 23456

с кольцевым буфером те же яйца. индекс следующего элемента считается так, как написано вот в этом сообщении Fifo реализация на Си с минимальными затратами по времени (комментарий)

Должно сработать, завтра попробую

Спасибо, завтра попробую

Получается, что нужно всего 5 маллоков при инициализации?

Если реальная задача такова, как описана в верхнем посте, то маллоки вообще не нужны. Достаточно статического или локального (на стеке) массива на 5 элементов + 2 отдельных указателя на 1-й и последний элементы. Или при желании динамического выделения такого массива за 1 раз. Если истинная задача сложнее и предполагает возможность расширения очереди, то по мере такого расширения может потребоваться несколько маллоков, но, опять же, совсем необязательно выделять память для каждого элемента отдельным маллоком, если сразу добавляется несколько элементов. Но можно и по отдельности. Это уже дело вкуса. Оба подхода имеют свои достоинства и недостатки.

Вопрос скорее в том: тебе нужны 5 первых или 5 последних?

Ну, а так: queue(3) → sys/queue. h (в линукс тоже завезли в кастрированном виде пару десятков лет назад).

Не надо никаких списков и malloc’ов

#define LEN 5    /* размер fifo */
#define TYPE int /* тип данных в fifo */

typedef struct {
  TYPE d[LEN]; /* буфер для данных */
  int ii;      /* индекс "входа" */
  int io;      /* индекс "выхода" */
  int cnt;     /* количество значений */
  int err;     /* ошибка: переполнение, пустой буфер или неверный индекс */
} cbuf

/* запихать v на "вход" буфера a */
static inline void cbuf_put( cbuf * a, TYPE v )
{
  if( a->cnt >= LEN )
  { /* буфер переполнен */
    a->err = 1;
    return;
  }

  a->d[a->ii] = v;
  a->ii = ( a->ii + 1 ) % LEN;
  a->cnt++;
  a->err = 0;
}

/* прочитать значение с "выхода" буфера а */
static inline TYPE cbuf_get( cbuf * a )
{
  if( a->cnt <= 0 )
  { /* буфер пуст */
    a->err = 1;
    return 0;
  }
  TYPE ret = a->d[a->io];
  a->io = ( a->io + 1 ) % LEN;
  a->cnt--
  a->err = 0;
  return ret;
}

/* прочитать i-тое значение от "входа" */
static inline TYPE cbuf_idx( cbuf * a, int i )
{
  if( i < 0 || i >= a->cnt )
  {
    a->err = 1;
    return 0;
  }
  a->err = 0;
  i = a->ii - i + LEN;
  return a->d[i % LEN];
}

/* инициализировать буфер */
static inline void cbuf_init( cbuf * a )
{
  memset( a, 0, sizeof( cbuf) );
}

Немного странная реализация. Циклический буфер ведь нельзя переполнить, так как он циклический. :) Мой вариант

#define LEN 5    /* размер fifo */
#define TYPE int /* тип данных в fifo */

typedef struct {
  TYPE dat[LEN];
  int ind;      
  int cnt;     
} cfifo;

void init( cfifo *p )
{
  p->ind=p->cnt=0;
}

void push( cfifo *p, TYPE val )
{
  p->dat[p->ind]= val;
  p->ind= (p->ind + 1)%LEN;
  if( p->cnt < LEN )
     p->cnt++;
}

int pop( cfifo * p, TYPE* val )
{
  int ret= p->cnt > 0;
  if( ret ) {
    *val= p->dat[ (LEN + p->ind - p->cnt)%LEN ];
    p->cnt= p->cnt-1;
    if( p->cnt == 0 )
       p->ind= 0;
  }
  return ret; /* 1- что-то вернули 0-ничего нет*/
}

int copy( cfifo * p, TYPE* val, int pos )
{
  int ret= p->cnt > 0 && pos >=0;
  if( ret ) {
    *val= p->dat[ (LEN + p->ind - p->cnt + pos)%LEN ];
  }
  return ret; /* 1- что-то вернули 0-ничего нет*/
}

Да.

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

Немного странная реализация. Циклический буфер ведь нельзя переполнить, так как он циклический. :)

Всё зависит от того, хочется ли терять старые данные при переполнении и что из него читать если буфер пуст.