1 /*
2  * Copyright (c) 2015  Machine Zone, Inc.
3  *
4  * Original author: Lev Walkin <lwalkin@machinezone.com>
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14 
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25  * SUCH DAMAGE.
26  */
27 #include <sys/types.h>
28 #include <stdlib.h>
29 #include <stdio.h>
30 #include <string.h>
31 #include <assert.h>
32 
33 #include "tcpkali_ring.h"
34 
35 struct ring_buffer *
ring_buffer_new(size_t unit_size)36 ring_buffer_new(size_t unit_size) {
37     struct ring_buffer *rb = calloc(1, sizeof(*rb));
38     ring_buffer_init(rb, unit_size);
39     return rb;
40 }
41 
42 void
ring_buffer_init(struct ring_buffer * rb,size_t unit_size)43 ring_buffer_init(struct ring_buffer *rb, size_t unit_size) {
44     rb->unit_size = unit_size;
45     rb->size = rb->unit_size * 16;
46     rb->ptr = malloc(rb->size);
47     rb->left = rb->right = rb->ptr;
48     assert(rb->ptr);
49 }
50 
51 void
ring_buffer_grow(struct ring_buffer * rb)52 ring_buffer_grow(struct ring_buffer *rb) {
53     assert(rb->unit_size);
54     assert(rb->size);
55 
56     assert(rb->ptr <= rb->left);
57     assert(rb->ptr <= rb->right);
58     assert(rb->right <= rb->ptr + rb->size);
59     assert(rb->left <= rb->ptr + rb->size);
60 
61     size_t new_size = 2 * rb->size;
62     void *ptr = malloc(new_size);
63     assert(ptr);
64 
65     if(rb->left <= rb->right) {
66         memcpy(ptr, rb->left, rb->right - rb->left);
67         free(rb->ptr);
68         rb->ptr = ptr;
69         rb->right = ptr + (rb->right - rb->left);
70         rb->left = rb->ptr;
71         rb->size = new_size;
72     } else {
73         size_t first_block_size = rb->size - (rb->left - rb->ptr);
74         memcpy(ptr, rb->left, first_block_size);
75         size_t second_block_size = rb->right - rb->ptr;
76         memcpy((char *)ptr + first_block_size, rb->ptr, second_block_size);
77         free(rb->ptr);
78         rb->ptr = ptr;
79         rb->right = ptr + first_block_size + second_block_size;
80         rb->left = rb->ptr;
81         rb->size = new_size;
82     }
83 }
84 
85 #ifdef TCPKALI_RING_UNIT_TEST
86 
87 static void
dump(struct ring_buffer * rb)88 dump(struct ring_buffer *rb) {
89     int i = 0;
90     void *p;
91     assert(rb->unit_size == sizeof(int));
92     printf("Dumping size %d units of size %d\n",
93            (int)(rb->size / rb->unit_size), (int)rb->unit_size);
94     for(p = rb->ptr; (size_t)(p - rb->ptr) < rb->size;
95         p = (char *)p + rb->unit_size) {
96         if(p == rb->left && p == rb->right)
97             printf("[%03d] %d <- left & right\n", i, *(int *)p);
98         else if(p == rb->left)
99             printf("[%03d] %d <- left\n", i, *(int *)p);
100         else if(p == rb->right)
101             printf("[%03d] %d <- right\n", i, *(int *)p);
102         else
103             printf("[%03d] %d\n", i, *(int *)p);
104         i++;
105     }
106 }
107 
108 int
main()109 main() {
110     struct ring_buffer *rb = ring_buffer_new(sizeof(int));
111     int iterations = 1000;
112     int next_add = 1;
113     int next_remove = 1;
114     int added = 0;
115     int removed = 0;
116     int got;
117     int n = -1;
118 
119     got = ring_buffer_get(rb, &n);
120     assert(got == 0);
121     ring_buffer_add(rb, 0);
122     got = ring_buffer_get(rb, &n);
123     assert(got == 1);
124     assert(n == 0);
125 
126     /*
127      * Add a few measurements and remove a few.
128      */
129     while(iterations--) {
130         int to_add = random() % 10;
131         int to_remove = random() % 10;
132         while(to_add--) {
133             ring_buffer_add(rb, next_add);
134             next_add++;
135             added++;
136         }
137         while(to_remove--) {
138             int n;
139             if(!ring_buffer_get(rb, &n)) break;
140             if(n != next_remove) {
141                 dump(rb);
142             }
143             assert(n == next_remove);
144             next_remove++;
145             removed++;
146         }
147     }
148 
149     assert(removed <= added);
150 
151     /*
152      * Remove the rest.
153      */
154     for(; removed < added; removed++) {
155         got = ring_buffer_get(rb, &n);
156         assert(got);
157         assert(n == next_remove);
158         next_remove++;
159     }
160 
161     assert(rb->unit_size == sizeof(int));
162 
163     return 0;
164 }
165 
166 #endif /* TCPKALI_RING_UNIT_TEST */
167