PA0：关于剩余练习3

42、44：  1/19

 栈和队列

栈的特点：先入先出，后入后出 。出口也是入口，另一端封闭。  队列：一头入，另一头出（非传统队列也有一端可出入，另一端出的设计）、

这个练习的要求说实话有点奇怪，不准写.c，只写.h头文件来满足单元测试，看具体的要求，它要求基于之前的list来实现栈和队列，但是又不让用.c。不准用.c，那我要怎么实现？最后没办法，直接在.h里把代码实现也写上算了。

题目要求里给出了提示：继续使用list，但是限制list的元素出入，就可以作为stack和queue来用。考虑到这一点，我打算继续用listnode，list结构体也保留，函数就用之前的list封装一下，限制元素读写方向：

#include <ex32.h>

　　#define Stack_count(A) ((A)->count)
　　#define Stack_top(A) ((A)->first != NULL ? (A)->first->value : NULL)

List *Stack_create()
{
    return calloc(1, sizeof(List));    
}

void Stack_destory(List *stack)
{
    LIST_FOREACH(stack, first, next, cur) {
     if(cur->prev) {
            free(cur->prev);
        }
    }
    free(stack->last);
    free(stack);
}

void Stack_push(List *stack,char *val)
{
    List_unshift(stack,val); 
}

void Stack_pop(List *stack)
{
    List_shift(stack);
}

队列：

#define Queue_count(A) ((A)->count)

List *Queue_create()
{
    return calloc(1, sizeof(List));    
}

void Queue_destory(List *queue)
{
    LIST_FOREACH(queue, first, next, cur) {
     if(cur->prev) {
            free(cur->prev);
        }
    }
    free(queue->last);
    free(queue);
}

void Queue_send(List *queue,char *val)
{
    List_push(queue,val); 
}

void Queue_recv(List *queue)
{
    List_shift(queue);
}

附加题里面提到了DArray 动态数组。如果用动态数组的话，声明需要用malloc(count*sizeof(int))  好处是本身支持随机存取，函数里进行一些调整，可以很方便地实现栈和队列的效果。

--------练习44

环形缓冲区

typedef struct {
    char *buffer;
    int length;
    int start;
    int end;
} RingBuffer;

这里用了和之前list不同的定义方式，直接用数字来表示指针，这么做可以更方便地计算缓冲区是否已经被占满。（取余就可以）

#define RingBuffer_available_data(B) (((B)->end + 1) % (B)->length - (B)->start - 1) 这个宏比较值得学习，它的作用是简化直接计算当前缓冲区已用空间，和下一个avaliable_space相对应。首先用end指针+1，余length，得到有效的end位置，再减去start，再-1，就能得到当前有效空间的数量。

在.c中具体实现了5个函数，剩下的都直接在头文件中声明；学习代码，可以看到作者想的各方面还是比较细致的。

以get函数为例：

bstring RingBuffer_gets(RingBuffer *buffer, int amount)
{
    check(amount > 0, "Need more than 0 for gets, you gave: %d ", amount);
    check_debug(amount <= RingBuffer_available_data(buffer),
            "Not enough in the buffer.");

    bstring result = blk2bstr(RingBuffer_starts_at(buffer), amount);
    check(result != NULL, "Failed to create gets result.");
    check(blength(result) == amount, "Wrong result length.");

    RingBuffer_commit_read(buffer, amount);
    assert(RingBuffer_available_data(buffer) >= 0 && "Error in read commit.");

    return result;
error:
    return NULL;
    //首先，要获取的数据要大于0，其次，队列可用数据要充足
    //然后，从当前读位置开始，读出amount个字符，转为string输出
    //如果得到的string长度不对也报错
    //然后读指针后移amount个单位 ，超出长度会根据宏自动重头继续
    //移动后，检查可用数据是否大于0
}

考虑到了各种可能导致失败的情况，包括目标字节数小于0、环形队列内数据不足、字符串转换失败、字符串结果与目标长度不符和读指针移动后已用空间小于0.

在作者的环形队列设计里，start表示数据起始位置，它和end指针一样，都可能不在0的位置，也就是说数据有可能不从0开始。

单元测试的代码：

static RingBuffer *ringbuffer=NULL;  //把关键指针声明在外面，这样不用重复 注意用了static，但不用应该也可以？
//一开始准备的指针是NULL，具体的创建留在后面create函数

char *test1="test";
char *res1=NULL;
char *test2="add";
char *res2=NULL;
char *test3="op";
char *res3=NULL;
char *test4="a";
char *res4=NULL;
int t1=0,t2=0,t3=0,t4=0;


char * test_create(int length)
{
    ringbuffer=RingBuffer_create(length);
    mu_assert(ringbuffer != NULL, "Failed to create ringbuffer.");
    return NULL;
}

char *test_destroy()
{
    RingBuffer_destroy(ringbuffer);
    mu_assert(ringbuffer ==NULL,"Failed to destroy.");
    return NULL;
}


char *test_read_and_write()
{
    RingBuffer_write(ringbuffer,test1,5);
    mu_assert(RingBuffer_gets(ringbuffer,5)=="test" , "write data error");
    t1 = RingBuffer_read(ringbuffer,res1,5);
    mu_assert(res1=="test" || t1 != -1, "read data error");

    RingBuffer_write(ringbuffer,test2,4);
    mu_assert(RingBuffer_gets(ringbuffer,4)=="add","write data error");
    t2 = RingBuffer_read(ringbuffer,res2,4);
    mu_assert(res2=="add" || t2 != -1, "read data error");

    RingBuffer_write(ringbuffer,test3,3);
    mu_assert(RingBuffer_gets(ringbuffer,3)=="op","write data error");
    t3 = RingBuffer_read(ringbuffer,res3,3);
    mu_assert(res3=="op" || t3 != -1, "read data error");

    RingBuffer_write(ringbuffer,test4,2);
    mu_assert(RingBuffer_gets(ringbuffer,2)=="a","write data error");
    t4 = RingBuffer_read(ringbuffer,res4,2);
    mu_assert(res4=="a" || t4 != -1, "read data error");

//write 不需要返回值   read会把数据读出存在target里，并返回amount，出问题返回-1
    return NULL;
}

char *all_tests()
{
    test_create();
    test_read_and_write();
    test_destroy();

    printf("all test passed\n");

    return NULL;
}

RUN_TESTS(all_tests);

维基百科里的实现：

#include <stdio.h>

enum { N = 10 };  // N elements of the circular buffer

int buffer [N];   // Note that N-1 is the actual capacity, see put function
int writeIndx = 0;
int readIndx  = 0;

int put (int item) 
{
  if ((writeIndx + 1) % N == readIndx)
  {
     // buffer is full, avoid overflow
     return 0;
  }
  buffer[writeIndx] = item;
  writeIndx = (writeIndx + 1) % N;
  return 1;
}

int get (int * value) 
{
  if (readIndx == writeIndx)
  {
     // buffer is empty
     return 0;
  }

  *value = buffer[readIndx];
  readIndx = (readIndx + 1) % N;
  return 1;
}

int main ()
{
  // test circular buffer
  int value = 1001;
  while (put (value ++));
  while (get (& value))
     printf ("read %d\n", value);
  return 0;
}

代码写的很简洁。效果是直接运行N=10次，将缓冲区填至N-1个空间被占（设计问题，留了一个位置没有用），然后再逐个打印出每一项缓冲区内容。对于这个缓冲区，在缓冲区填满以后不会再试图循环填充数据，而是直接提示已经满额。不过提到的通过POSIX调用实现无限区域的代码似乎没有出现。如果允许用c++的话，那可以利用C++的STL来实现一个自动扩展的无限大的循环队列。

一点遗留的尾巴：练习44：环形缓冲区-笨办法学C(Learn C The Hard Way) (cntofu.com)