udayv . soundc

Sometimes, I find myself needing a staging memory buffer where I could store data for later retrieval. These kind of buffers essentially need to be FIFOs and should allow unlimited storage with resonably fast data retrieval. These buffers are different from, say, char array buffers since they need to be smart enough to grow based on the requirements.

As one of the scenarios, lets say you have a data processing module in your program that accepts fixed size buffers for processing, however the way you’re accepting data from, lets say, the network is variable sized buffers. The data chunks recieved from over the network may be smaller or larger than the buffer size accepted by the data processing module. In this scenario, you should be able to wait for more data to arrive till your data processor can process it, or in case of access data you should be able to store it somewhere so that it could be retrieved in the next pass.

This is common problem I find myself stuck with whenever I am dealing with data streaming applications. So I wrote a simple class that helps me manage all this. Appending and retrieving operations with this class are O(1) As pointed out by Thomas below, appending and retrieving data is O(n) operation where n is the number of bytes being read in or appended.  Locating the correct block of data which holds the next chunk of data is O(1).

Here’s what the class looks like

class staging_buffer {
private:
	struct __buffer_data { unsigned char *pdata; size_t nlen; size_t offset; };
	std::list<__buffer_data>	__data;
	size_t __held_data_len;
private:
	size_t _internal_min(size_t x, size_t y) {
		return (x < y ? x : y);
	}

public:
	staging_buffer() : __data (), __held_data_len (0) {
	}

	~staging_buffer(void) {
		while (!__data.empty ()) {
			free (__data.front().pdata);
			__data.pop_front ();
		}
		__held_data_len = 0;
	}

	void append (void *pdata, int nlen) {
		__buffer_data bd;
		bd.pdata = (unsigned char *)malloc (nlen); memcpy (bd.pdata, pdata, nlen);
		bd.nlen = nlen;
		bd.offset = 0;

		__held_data_len += bd.nlen;
		__data.push_back (bd);
	}

	size_t  fetch (void *pdata, size_t nlen) {
		size_t nreadbytes = 0;
		while (nreadbytes < nlen && !__data.empty()) {
			__buffer_data& bd = __data.front ();

			size_t bytestocopy = _internal_min (nlen - nreadbytes, bd.nlen - bd.offset);
			std::memcpy ((unsigned char *)pdata + nreadbytes, bd.pdata + bd.offset, bytestocopy);
			if (bytestocopy + bd.offset &gt;= bd.nlen) {
				free (bd.pdata); __data.pop_front  ();
			} else {
				bd.offset += bytestocopy;
			}

			nreadbytes += bytestocopy;
		}
		__held_data_len -= nreadbytes;

		return nreadbytes;
	}

	size_t size () {
		return __held_data_len;
	}
};

Hope you find it useful.