Problems concatenating strings

[stroker_ace]

Hi,

I am working on a problem where I need to implement a string buffer
that I can remove an arbitary length char* from one end and add them to
the other.

So far the only way I have thought of to accomplish this task involves
creating using

new char[length];

and the strcopy,strcat functions to repopulate the char array with the
required amount of data each time I add/remove bytes from the head/tail
of the string.

Is there a more efficient method of implementing my required behaviour?

Many thanks

Lawrie

 

[BigBrian]

If you're always going to be removing from one end and adding from the
other, then use std::queue<char>. If you need arbitrary access, use
std::vector<char>.

-Brian

 

[Manvel Avetisian]

Try ring buffer.

#define BUFFER_SIZE 4096
#define INDEX_MASK (BUFFER_SIZE-1)
char buffer[BUFFER_SIZE];
int head_index,tail_index;

void push_front(char ch) {
buffer[head_index]=ch;
head_index=(head_index+1)&INDEX_MASK;
}

char pop_back() {
char ch=buffer[tail_index];
tail_index=(tail_index+1)&INDEX_MASK;
}

void copy_from_front_to_back(int n) {
while(n-->0) {
push_front(pop_back());
}
}

 

[BigBrian]

#define BUFFER_SIZE 4096

The original post said nothing about how big the buffer needed to be,
thus it's best to assume an arbitrary size, which your code does not.
Since you're using the bitwize & to do the wrap around of your indices,
your code will break if you change BUFFER_SIZE to anything other than a
power of 2. It's also going to break if you push_front() more
characters than BUFFER_SIZE ( which you're code doesn't check for. )
This is exactly why its better to use the containers in the standard
library.

-Brian

 

[Manvel Avetisian]

But my solution will be much faster and efficent than yours

#define BUFFER_SIZE 100000
char buffer[BUFFER_SIZE];
int head_index,tail_index;

void push_front(char ch) {
buffer[head_index]=ch;
head_index=(head_index+1)%BUFFER_SIZE;



}


char pop_back() {
char ch=buffer[tail_index];
tail_index=(tail_index+1)%BUFFER_SIZE;


}


void copy_from_front_to_back(int n) {
while(n-->0) {
push_front(pop_back());
}
}

 

[Karl Heinz Buchegger]

But my solution will be much faster and efficent than yours

Wow. I'm impressed.
A programm that produces garbage more efficiently then
any other program.

Increasing a constant in some source code isn't going
to help if the program is already running at the customers
site.

 

[Manvel Avetisian]

Now compare speed of my ring_buffer with speed of std::queue<char>...

struct ring_buffer {
char *buffer;
int length,head_offset,tail_offset;

ring_buffer() {
buffer=(char *) malloc(length=4096);
if(!buffer) throw "out of memory";
head_offset=tail_offset=0;
}

void resize() {
int new_length=length*2;
char *new_buffer=(char *) malloc(new_length);
if(!new_buffer) throw "out of memory";
memcpy(new_buffer,buffer,head_offset);
memcpy(new_buffer+length+tail_offset,buffer+tail_offset,length-tail_offset);
free(buffer);
tail_offset+=length;
}

void push_front(char ch) {
buffer[head_offset]=ch;
head_offset=(head_offset+1)%length;
if(head_offset==tail_offset) resize();
}

char pop_back() {
char ch=buffer[tail_offset];
tail_offset=(tail_offset+1)%length;
if(tail_offset==head_offset) resize();
return ch;
}

void copy_from_front_to_back(int n) {
while(n--) push_front(pop_back());
}
};

void main() {
ring_buffer rb;

rb.push_front('a');
rb.push_front('b');
rb.push_front('c');
rb.push_front('d');

std::cout<<rb.pop_back()<<rb.pop_back()<<rb.pop_back()<<rb.pop_back();
}

 

[Karl Heinz Buchegger]

Now compare speed of my ring_buffer with speed of std::queue<char>...

To see, if the enlargement really works, you should start out
with a ringbuffer size of eg. 2 in your test program.

Hint: It doesn't work. It crashes.

The point is not that it cannot be done your way.
The point is that with deque you already would have
a reliable, working solution.

 

[Manvel Avetisian]

Now compare speed of my ring_buffer with speed of std::queue<char>...

struct ring_buffer {
char *buffer;
int length,head_offset,tail_offset;

ring_buffer() {
buffer=(char *) malloc(length=4096);
if(!buffer) throw "out of memory";
head_offset=tail_offset=0;
}

void resize() {
int new_length=length*2;
char *new_buffer=(char *) malloc(new_length);
if(!new_buffer) throw "out of memory";

if(head_offset > tail_offset) {
memcpy(new_buffer,buffer+tail_offset,head_offset-tail_offset);
} else {
memcpy(new_buffer,buffer,head_offset);
memcpy(new_buffer+new_length-(length-tail_offset),buffer+tail_offset,tail_offset-head_offset);
tail_offset=new_length-(length-tail_offset);
}

free(buffer);
buffer=new_buffer;
length=new_length;
}

void push_front(char ch) {
int new_head_offset=(head_offset+1)%length;
if(new_head_offset==tail_offset ||
abs(new_head_offset-tail_offset)==length) resize();

buffer[head_offset]=ch;
head_offset=(head_offset+1)%length;
}

char pop_back() {
char ch=buffer[tail_offset];
tail_offset=(tail_offset+1)%length;
if(tail_offset==head_offset) throw "no data in buffer";
return ch;
}

void copy_from_front_to_back(int n) {
while(n--) push_front(pop_back());
}
};

void main() {
try {
ring_buffer rb;

for(int i=0; i<100000; i++) rb.push_front('a'+i%10);
for(int j=0; j<100000; j++) std::cout<<j<<rb.pop_back()<<std::endl;
} catch(const char *str) {
std::cerr<<str;
}
}

 

[Karl Heinz Buchegger]

Now compare speed of my ring_buffer with speed of std::queue<char>...

To see, if the enlargement really works, you should start out
with a ringbuffer size of eg. 2 in your test program.

Hint: It doesn't work. It crashes.

The point is not that it cannot be done your way.
The point is that with deque you already would have
a reliable, working solution.

 

[Manvel Avetisian]

And the final (stable?) version of resize() specially for you:

void resize() {
int new_length=length*2;
char *new_buffer=(char *) malloc(new_length);
if(!new_buffer) throw "out of memory";

if(head_offset > tail_offset) {
memcpy(new_buffer,buffer+tail_offset,head_offset-tail_offset);
tail_offset=0;
head_offset-=tail_offset;
} else {
int n;
memcpy(new_buffer,buffer+tail_offset,n=length-tail_offset);
memcpy(new_buffer+n,buffer,head_offset);
head_offset+=n;
tail_offset=0;
}

free(buffer);
buffer=new_buffer;
length=new_length;
}

 

[Karl Heinz Buchegger]

And the final (stable?) version of resize() specially for you:

void resize() {
int new_length=length*2;
char *new_buffer=(char *) malloc(new_length);
if(!new_buffer) throw "out of memory";

if(head_offset > tail_offset) {
memcpy(new_buffer,buffer+tail_offset,head_offset-tail_offset);
tail_offset=0;
head_offset-=tail_offset;
} else {
int n;
memcpy(new_buffer,buffer+tail_offset,n=length-tail_offset);
memcpy(new_buffer+n,buffer,head_offset);
head_offset+=n;
tail_offset=0;
}

free(buffer);
buffer=new_buffer;
length=new_length;
}

If I replace that in your class, the class still has the same problem:
I put 5 characters in, I get 4 characters back

So it still (after 2 hours?) is an efficient(*) but buggy solution.

* nobody knows how efficient it really is. Up to now there is no
working solution that can be timed against deque
And I definitly will not time it.