Очереди С Переменным Размером Буфера


Я работаю над созданием очереди переменной размера буферов передачи данных до 256 байт в длину, однако чаще всего буферы будет намного меньше (как правило, около 10-15 байт).

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

Я никогда не делал что-то подобное раньше, поэтому я надеюсь, что кто-то может взглянуть, чтобы увидеть, если то, что я сделал смысл.

Примечание: есть queueTest в нижней части очереди.C, который показывает, как я использую это.

очереди.ч

/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef __SB_QUEUE_H
#define __SB_QUEUE_H

#ifdef __cplusplus
 extern "C" {
#endif

#include "stm32l4xx_hal.h"
#include <stdbool.h>

#define QUEUE_CAPACITY_BYTES 1000

/* Node structure including data length */
typedef struct node {
    uint8_t     *data;
    uint8_t     size;
    struct node *next;
} node_t;


/* Queue structure */
typedef struct myque {
    node_t   *head;
    node_t   *tail;
    uint16_t size;
    uint16_t footprint;
} myque_t; 


void    queueInitialize ( myque_t * q );
int     queuePush       ( myque_t * q, const void * data, uint8_t dataLen );
int     queuePop        ( myque_t * q, uint8_t * data );
void    queuePeek       ( const myque_t * q, uint8_t * data );
bool    queueIsFull     ( myque_t * q );
uint8_t queueGetSize    ( myque_t * q );
void    queueClear      ( myque_t * q );

void queueTest ( void );
void queuePrint ( myque_t * q );

#ifdef __cplusplus
}
#endif
#endif /* __SB_QUEUE_H */

очереди.с

/* Includes ------------------------------------------------------------------*/
#include "sb_queue.h"

#include <stdlib.h>
#include <string.h>

/**@brief Initializes a queue
 * @details Sets the read and write pointers to NULL, and initializes the size as 0
 *
 * @param[in]  q - pointer to queue to initialize
 * @param[in]  capacity - number of elements in the queue
 */
void queueInitialize(myque_t * q)
{
    q->size = 0;
    q->footprint = 0;
    q->head = NULL;
    q->tail = NULL;
}

/**@brief Pushes a data buffer to the queue
 * @details Allocates space for a new node, and a variable length data buffer and pushes
 *          it to the specified queue
 *
 * @param[in]  q - pointer to queue to push to
 * @param[in]  data - pointer to data to be pushed
 * @param[in]  dataLen - number of bytes in data buffer
 */
int queuePush(myque_t *q, const void *data, uint8_t dataLen)
{
    /* Check that data will fit */
    if (q->footprint + (dataLen * sizeof(uint8_t)) > QUEUE_CAPACITY_BYTES)
    {
        return -1;
    }
    else
    {  
        /* Allocate memory for node */
        node_t *newNode = (node_t *)malloc(sizeof(node_t));

        if(newNode == NULL)
        {
            return -1;
        }

        /* Allocate memory for data */
        newNode->data = malloc(dataLen * sizeof(uint8_t));

        if(newNode->data == NULL)
        {
            free(newNode);
            return -1;
        }

        newNode->size = dataLen;
        newNode->next = NULL;

        memcpy(newNode->data, data, newNode->size);

        if(q->size == 0)
        {
            q->head = q->tail = newNode;
        }
        else
        {
            q->tail->next = newNode;
            q->tail = newNode;
        }

        q->size++;
        q->footprint+= dataLen * sizeof(uint8_t);
        //queuePrint(q);
        return 0;
    }
}


/**@brief Remove an item from the queue. Changes the front of queue
 * 
 * @param[in]  queue - pointer to the queue to pop from
 * @param[in]  data - pointer to where to store the item
 */
int queuePop(myque_t * q, uint8_t * data)
{
    if(q->size > 0)
    {
        node_t *tempNode = q->head;

        if (data != NULL)
        {
            memcpy(data, tempNode->data, tempNode->size);
        }

        if(q->size > 1)
        {
            q->head = q->head->next;
        }
        else
        {
            q->head = NULL;
            q->tail = NULL;
        }

        q->size--;
        free(tempNode->data);
        free(tempNode);

        return 0;
    }
    else
    {
        return -1;
    }
}

/**@brief Inspect the item at the head of the queue without altering the queue
 * 
 * @param[in]  queue - pointer to the queue to inspect
 * @param[in]  data - pointer to where to store the item
 */
void queuePeek(const myque_t *q, uint8_t *data)
{
    if(q->size > 0)
    {
       node_t *tempNode = q->head;
       memcpy(data, tempNode->data, tempNode->size);
    }
}

/**@brief Frees all the memory used by the queue
 * 
 * @param[in]  queue - pointer to the queue to free
 */
void queueClear(myque_t *q)
{
  node_t * tempNode;

  while(q->size > 0)
  {
      tempNode = q->head;
      q->head  = tempNode->next;
      free(tempNode->data);
      free(tempNode);
      q->size--;
  }

  q->head = q->tail = NULL;
}

/**@brief Returns true if the queue is empty. The queue is full when it's size is 0
 * 
 * @param[in]  queue - pointer to the queue to check
 *
 * @return Whether or not the queue is empty
 */
uint8_t queueGetSize( myque_t * q )
{  
    return q->size;
}

/**@brief Prints the contents of the queue
 * 
 * @param[in]  queue - pointer to the queue to print
 */
void queuePrint ( myque_t * q )
{
    uint8_t ii = 0;
    uint8_t pp = 0;
    node_t * tempNode = q->head;

    while(ii < q->size)
    {
        printf("Queue %d: ", ii);
        for (pp = 0; pp < tempNode->size; pp++)
        {
            printf("0x%x, ", tempNode->data[pp]);
        }
        printf("\r\n");
        tempNode = tempNode->next;
        ii++;
    }
}


/**@brief Prints the contents of the queue
 * 
 * @param[in]  queue - pointer to the queue to print
 */
void queueTest ( void )
{
    uint8_t ii = 0;
    uint8_t pp = 0;
    myque_t q;
    uint8_t data[10] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09};

    queueInitialize(&q);

    /* Fill queue (should stop pushing at around 100) */
    for (ii = 0; ii < 120; ii++)
    {
        queuePush(&q, data, 10);
        for (pp = 0; pp < 10; pp++)
        {
            data[pp]++;
        }
    }

    queuePrint(&q);
    printf("\r\nCLEAR QUEUE\r\n");
    queueClear(&q);
    queuePrint(&q);
}


718
5
задан 8 февраля 2018 в 09:02 Источник Поделиться
Комментарии
2 ответа

В целом выглядит довольно разумно, мне не хватает queueIsFull() реализации. Я не пытаюсь скомпилировать

Использование bool

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

queuePush()

При расчете след ты игнорируешь размер next ПТР в вашем расчете, если ты на системе, которая заключается в том, что плотно, что вы не ограничивает размер очереди в основном 1Кб, то вы, вероятно, хотите включить это в след расчет.

queuePop()

Есть большое предположение в этом, что ожидает указатель на данные, чтобы иметь возможность быть достаточно большим, чтобы принять количество данных, и, как в СП1 указано, Вы для queuePeek() абонент не знает, сколько данных было скопировано. Я не знаю о среде, в которой вы используете эту, но как вы, освобождая data указатель на узел, вы могли бы сохранить то, что выделение в этом месте и просто вернуть его. Это делает его обязанность вызывающей стороны, чтобы освободить его, но это может сэкономить средства, выделяемые на тот, который передается в поп.

queuePeek()

Как написано, без проверки на выход за границы на записанных данных. Выше нет ответа на какой объем данных был доступен.

Тесты

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

Придирка ...


  • В queue.size и data.size поля, имея одинаковое имя указывают на разные размеры, один граф, другой объем памяти ...

  • myque_tесть опечатка в нее, тоже не идеальная структура наименование, fixed_capacity_queue или что-то еще может быть более полезным и дать вам немного пользы.

  • В node структура, вероятно, должна быть индивидуальная в реализации нет необходимости, чтобы положить его в файл

  • queueClear() могла быть написана без обновления размер, просто проверить head != NULL

  • queueGetSize() на самом деле не очень полезны, у вас есть доступ к структуре или ?

Предложения

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

Вы могли бы ввести буфер просто везти data и size пар, это может сделать peek и pop более понятно, но там, вероятно, всегда будет разница между выделенной суммы от указателя, переданного в фактическое написана сумма. Если объем зарезервированной памяти фиксируется.

Вы могли бы реализовать это как кольцевой буфер на фиксированный объем памяти. Это может иметь некоторые преимущества в зависимости от ваших потребностей. Если у вас мало памяти, вы можете сохранить, а также о распределении.

3
ответ дан 8 февраля 2018 в 11:02 Источник Поделиться

Сокрытие информации

В typedef struct node { .... } node_t и typedef struct node { ... } node_t; не нужны в "queue.h".

typedef struct myque *myque_t; достаточно для "queue.h". Полного определения типов ниже в "queue.c".


Чтобы избежать потери памяти

А .head и .tail член не нужен для круговой очереди. Одного достаточно.

Это может быть расширенный для кого-то, кто "никогда не делал что-то подобное".

Хотя концептуально .head и .tail строительство скважин, код можно использовать только .tail и .tail->next точка в "голове" узел.

С пустой очередью, .tail == NULL. С N > 0 в очередь, последний узел указывает на первый, даже если он сам по себе. Конец списка определяется node->next == q->tail->next а не NULL сравнить.

Такой подход снижает потребность в памяти один указатель/очереди.

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


Другие сокращения памяти тоже возможно.


константный

const не хватает? Я бы вместо того, чтобы ожидать следующую подпись.

// bool    queueIsFull (myque_t * q);
// uint8_t queueGetSize(myque_t * q);
bool queueIsFull (const myque_t * q);
uint8_t queueGetSize(const myque_t * q);


Включить недостающие

Как "queue.h" использует uint8_tдобавить #include <stdint.h>


Типы

Лучше использовать size_t для размеров и void * для пользовательских данных. Чтобы было понятно: дизайн интерфейса (функция подписи) способами, которые имеют смысл для пользователя. Код элементов структуры, как вы считаете нужным. Возможно, размер этой очереди может быть только 255, до сих пор пользуюсь size_t dataLen и проверить, что за допустимый диапазон. int queuePush() есть хороший способ вернуть ошибку показаний.

// int queuePush( myque_t * q, const void * data, uint8_t dataLen );
// int queuePop( myque_t * q, uint8_t * data );
int queuePush( myque_t * q, const void * data, size_t dataLen);
int queuePop( myque_t * q, void * data );


Переполнение

Переполнение возможно. q->size++; может переполниться uint8_t. Попробуйте позвонить int queuePush(q, "", 1) 256 раз.


Другие

Я ожидал queueGetSize вернуться unsigned из size_tдаже если .size член был более узкий тип.

1
ответ дан 9 февраля 2018 в 07:02 Источник Поделиться