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