The delimited list builder pattern

If you’re building a delimited list, for your sql injection attack demonstration or just output data dumps, here’s a useful pattern to build it.

I’ll present it as (bad) C++ pseudo code with an explanation to follow. For this example I’ll assume the delimiter is a comma.

string output;
string Delimiter = ",";
list<string> values;
string separator = "";
for ( int i = 0; i < values.size(); i++ )
{
  output += separator + values[i];
  separator = Delimiter;
}
<pre>

You can’t simply add a delimiter after each list element. If you do then the last element will always have an incorrect
delimiter at the end. If you prefix each insertion with the delimiter then you end up with an incorrect delimiter before
the first element in your output.

This algorithm solves the problem by using the prefix method and changing the delimiter. The first insertion is done
using an empty delimiter to avoid the first delimiter problem. All insertions after the first use the correct delimiter.

For optimal performance you should use a reference/pointer to set the delimiter within the loop (if your language of choice
allows it). This avoids a memory copy operation to set the string for each iteration of the loop. An if statement could be used
instead of changing the separator but the cost of setting a pointer will be less than evaluation of a condition and a branch.

This algorithm works correctly if the size of the list is not known in advance and if the output cannot be edited once written to.

++djs

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: