documented updates
[gnutls.git] / lib / gnutls_mbuffers.c
blob333ce59e8ad265e8a68d8579b2ac6ce4b496a2c4
1 /*
2 * Copyright (C) 2009-2012 Free Software Foundation, Inc.
4 * Author: Jonathan Bastien-Filiatrault
6 * This file is part of GNUTLS.
8 * The GNUTLS library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public License
10 * as published by the Free Software Foundation; either version 3 of
11 * the License, or (at your option) any later version.
13 * This library is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this program. If not, see <http://www.gnu.org/licenses/>
23 #include "gnutls_mbuffers.h"
24 #include "gnutls_errors.h"
26 /* Here be mbuffers */
28 /* A note on terminology:
30 * Variables named bufel designate a single buffer segment (mbuffer_st
31 * type). This type is textually referred to as a "segment" or a
32 * "buffer element".
34 * Variables named buf desigate a chain of buffer segments
35 * (mbuffer_head_st type). This type is textually referred to as a
36 * "buffer head" or simply as "buffer".
38 * Design objectives:
40 * - Make existing code easier to understand.
41 * - Make common operations more efficient by avoiding unnecessary
42 * copying.
43 * - Provide a common datatype with a well-known interface to move
44 * data around and through the multiple protocol layers.
45 * - Enable a future implementation of DTLS, which needs the concept
46 * of record boundaries.
50 /* Initialize a buffer head.
52 * Cost: O(1)
54 void
55 _mbuffer_head_init (mbuffer_head_st * buf)
57 buf->head = NULL;
58 buf->tail = NULL;
60 buf->length = 0;
61 buf->byte_length = 0;
64 /* Deallocate all buffer segments and reset the buffer head.
66 * Cost: O(n)
67 * n: Number of segments currently in the buffer.
69 void
70 _mbuffer_head_clear (mbuffer_head_st * buf)
72 mbuffer_st *bufel, *next;
74 for (bufel = buf->head; bufel != NULL; bufel = next)
76 next = bufel->next;
77 gnutls_free (bufel);
80 _mbuffer_head_init (buf);
83 /* Append a segment to the end of this buffer.
85 * Cost: O(1)
87 void
88 _mbuffer_enqueue (mbuffer_head_st * buf, mbuffer_st * bufel)
90 bufel->next = NULL;
91 bufel->prev = buf->tail;
93 buf->length++;
94 buf->byte_length += bufel->msg.size - bufel->mark;
96 if (buf->tail != NULL)
97 buf->tail->next = bufel;
98 else
99 buf->head = bufel;
100 buf->tail = bufel;
103 /* Remove a segment from the buffer.
105 * Cost: O(1)
107 * Returns the buffer following it.
109 mbuffer_st *
110 _mbuffer_dequeue (mbuffer_head_st * buf, mbuffer_st * bufel)
112 mbuffer_st* ret = bufel->next;
114 if (buf->tail == bufel) /* if last */
115 buf->tail = bufel->prev;
117 if (buf->head == bufel) /* if first */
118 buf->head = bufel->next;
120 if (bufel->prev)
121 bufel->prev->next = bufel->next;
123 if (bufel->next)
124 bufel->next->prev = NULL;
126 buf->length--;
127 buf->byte_length -= bufel->msg.size - bufel->mark;
129 bufel->next = bufel->prev = NULL;
131 return ret;
134 /* Get a reference to the first segment of the buffer and
135 * remove it from the list.
137 * Used to start iteration.
139 * Cost: O(1)
141 mbuffer_st *
142 _mbuffer_head_pop_first (mbuffer_head_st * buf)
144 mbuffer_st *bufel = buf->head;
146 if (buf->head == NULL)
147 return NULL;
149 _mbuffer_dequeue(buf, bufel);
151 return bufel;
154 /* Get a reference to the first segment of the buffer and its data.
156 * Used to start iteration or to peek at the data.
158 * Cost: O(1)
160 mbuffer_st *
161 _mbuffer_head_get_first (mbuffer_head_st * buf, gnutls_datum_t * msg)
163 mbuffer_st *bufel = buf->head;
165 if (msg)
167 if (bufel)
169 msg->data = bufel->msg.data + bufel->mark;
170 msg->size = bufel->msg.size - bufel->mark;
172 else
174 msg->data = NULL;
175 msg->size = 0;
178 return bufel;
181 /* Get a reference to the next segment of the buffer and its data.
183 * Used to iterate over the buffer segments.
185 * Cost: O(1)
187 mbuffer_st *
188 _mbuffer_head_get_next (mbuffer_st * cur, gnutls_datum_t * msg)
190 mbuffer_st *bufel = cur->next;
192 if (msg)
194 if (bufel)
196 msg->data = bufel->msg.data + bufel->mark;
197 msg->size = bufel->msg.size - bufel->mark;
199 else
201 msg->data = NULL;
202 msg->size = 0;
205 return bufel;
208 /* Remove the first segment from the buffer.
210 * Used to dequeue data from the buffer. Not yet exposed in the
211 * internal interface since it is not yet needed outside of this unit.
213 * Cost: O(1)
215 static inline void
216 remove_front (mbuffer_head_st * buf)
218 mbuffer_st *bufel = buf->head;
220 if (!bufel)
221 return;
223 _mbuffer_dequeue(buf, bufel);
224 gnutls_free (bufel);
227 /* Remove a specified number of bytes from the start of the buffer.
229 * Useful for uses that treat the buffer as a simple array of bytes.
231 * If more than one mbuffer_st have been removed it
232 * returns 1, 0 otherwise and an error code on error.
234 * Cost: O(n)
235 * n: Number of segments needed to remove the specified amount of data.
238 _mbuffer_head_remove_bytes (mbuffer_head_st * buf, size_t bytes)
240 size_t left = bytes;
241 mbuffer_st *bufel, *next;
242 int ret = 0;
244 if (bytes > buf->byte_length)
246 gnutls_assert ();
247 return GNUTLS_E_INVALID_REQUEST;
250 for (bufel = buf->head; bufel != NULL && left > 0; bufel = next)
252 next = bufel->next;
254 if (left >= (bufel->msg.size - bufel->mark))
256 left -= (bufel->msg.size - bufel->mark);
257 remove_front (buf);
258 ret = 1;
260 else
262 bufel->mark += left;
263 buf->byte_length -= left;
264 left = 0;
267 return ret;
270 /* Allocate a buffer segment. The segment is not initially "owned" by
271 * any buffer.
273 * maximum_size: Amount of data that this segment can contain.
274 * size: Amount of useful data that is contained in this
275 * buffer. Generally 0, but this is a shortcut when a fixed amount of
276 * data will immediately be added to this segment.
278 * Returns the segment or NULL on error.
280 * Cost: O(1)
282 mbuffer_st *
283 _mbuffer_alloc (size_t payload_size, size_t maximum_size)
285 mbuffer_st *st;
287 st = gnutls_calloc (1, maximum_size + sizeof (mbuffer_st));
288 if (st == NULL)
290 gnutls_assert ();
291 return NULL;
294 /* payload points after the mbuffer_st structure */
295 st->msg.data = (uint8_t *) st + sizeof (mbuffer_st);
296 st->msg.size = payload_size;
297 st->maximum_size = maximum_size;
299 return st;
302 /* Copy data into a segment. The segment must not be part of a buffer
303 * head when using this function.
305 * Bounds checking is performed by this function.
307 * Returns 0 on success or an error code otherwise.
309 * Cost: O(n)
310 * n: number of bytes to copy
313 _mbuffer_append_data (mbuffer_st * bufel, void *newdata, size_t newdata_size)
315 if (bufel->msg.size + newdata_size <= bufel->maximum_size)
317 memcpy (&bufel->msg.data[bufel->msg.size], newdata, newdata_size);
318 bufel->msg.size += newdata_size;
320 else
322 gnutls_assert ();
323 return GNUTLS_E_INVALID_REQUEST;
326 return 0;
329 /* Takes a buffer in multiple chunks and puts all the data in a single
330 * contiguous segment.
332 * Returns 0 on success or an error code otherwise.
334 * Cost: O(n)
335 * n: number of segments initially in the buffer
338 _mbuffer_linearize (mbuffer_head_st * buf)
340 mbuffer_st *bufel, *cur;
341 gnutls_datum_t msg;
342 size_t pos = 0;
344 if (buf->length <= 1)
345 /* Nothing to do */
346 return 0;
348 bufel = _mbuffer_alloc (buf->byte_length, buf->byte_length);
349 if (!bufel)
351 gnutls_assert ();
352 return GNUTLS_E_MEMORY_ERROR;
355 for (cur = _mbuffer_head_get_first (buf, &msg);
356 msg.data != NULL; cur = _mbuffer_head_get_next (cur, &msg))
358 memcpy (&bufel->msg.data[pos], msg.data, msg.size);
359 pos += msg.size;
362 _mbuffer_head_clear (buf);
363 _mbuffer_enqueue (buf, bufel);
365 return 0;