Lecture Material

Class string

simple

with reference counting

Exceptions

The volatile specifier

Semaphores

The string Class

Text processing is a common domain in computer applications

In C and C++ there is no real string type, char* is hard to use and error prone

class mystring

{

char *data;

public:

mystring ();

~mystring ();

mystring (const char *s);

unsigned int length () const;

mystring (const mystring & src);

mystring & operator= (const mystring & src);

mystring & operator+= (const mystring & src);

char operator[] (unsigned int i) const;

char &operator[] (unsigned int i);

friend ostream & operator<< (ostream & o, const mystring & s);

};

inline mystring operator+ (const mystring & s1, const mystring & s2);

Reference

No reference

string - Constructor and Member Initializer List

Without member initializer list

With member initializer list

There is no difference in this case

The diference appears, when the members have constructors

Without initializer list: default constructor called, then the assignment operator

With initializer list: constructor with a parameter called

Using member initializer list makes program shorter and faster

mystring ()

{

data = NULL;

}

mystring ():data (NULL) {};

The string Class - operator +

The friend specifier is not needed, function uses exclusively the public members of the string class

When returning result from the function, the copy constructor will be used

inline mystring operator+ (const mystring & s1, const mystring & s2)

{

mystring s (s1);

return s += s2;

}

The string Class - operator char*

In class you can define the conversion operators to different types

Frequently useful in case you are using function accepted built-in types (e.g. char*)

In the string class possibility of clash with an indexing operator

mystring::operator char*()

{

if(!data)

{

data=new char[1];

data[0]='\0';

}

return data;

};

mystring s;

s[0]='a'; //s.operator[](0) or (s.operator char*())[0] ?

Exceptions

Correct program checks for error codes

Checking for error conditions every time is boring and it is easy to forget about it

In some cases it is difficult to return an error code, e.g. atoi() can return any integer and there is no value to signal an error

Signalling errors in constructors is a hard problem

int fun()

{

//...

fd=open("file",O_RDWR);

if(fd==-1)

return -1;

if(read(fd,buffer,15)!=15)

return -1;

if(write(fd,buffer,4)!=4)

return -1;

//...

return 0;

}

Exceptions

C++ provides a new mechanism to signal errors: exceptions

class myexception{};

void f1()

{

if(...)

throw myexception();

};

void f2()

{

f1();

};

int main()

{

try {

f2();

} catch(myexception&)

{

cout << "myexception caught"<<endl;

}

return 0;

};

The exception class, allows to distinguish errors

Signalling an error

Detection of error

Exceptions

The errors can be distinguished based on the type of exception thrown

Operator new throws bad_alloc when there is not enough memory

class bad_index{};

class no_memory {};

void f1()

{

if(...)

throw bad_index();

if(...)

throw no_memory();

};

//...

try {

f2();

} catch(bad_index&)

{

//...

} catch (no_memory&)

{

//...

}

Exceptions

When the exception is thrown, all destructors of local objects on the way from callee to caller are invoked

#include <iostream>

using namespace std;

class myexception{};

class tester

{

string name;

public:

tester(const string& n): name(n)

{

cout<<name<<"()"<<endl;

};

~tester()

{

cout<<"~"<<name<<"()"<<endl;

};

};

void f1()

{

tester f1("f1");

throw myexception();

cout << "Exiting f1"<<endl;

};

void f2()

{

tester f2("f2");

f1();

cout << "Exiting f2"<<endl;

};

int main()

{

tester main("main");

f2();

return 0;

};

Exceptions

When the appropriate catch clause is not present, the execution of program is aborted

We can modify the string class to use exceptions

class mystring

{

char *data;

public:

class index_out_of_range{};

//...

char operator[] (unsigned int i) const

{

if (!data)

throw index_out_of_range();

if (i >= strlen (data))

throw index_out_of_range();

return data[i];

}

};

Problems with Exceptions

Careless usage of exceptions can lead to resource leaks or data inconsistency

void fun()

{

char* a = new char[1024];

char* b = new char[1024];

//...

delete [] a;

delete [] b;

}

If new throws an exception, the memory allocated for a will not be freed

void fun()

{

char* a = NULL, *b=NULL;

try{

a = new char[1024];

b = new char[1024];

//...

} catch (...)

{

delete [] a;

delete [] b;

throw;

}

delete [] a;

delete [] b;

}

A way to fix the error, correct but not the best

Problems with Exceptions

Careless usage of exceptions can lead to resource leaks or data inconsistency

mystring & operator=
(const mystring & src)

{

if (this != &src)

{

delete[]data;

if (src.data)

{

data = new char
[strlen(src.data) + 1];

strcpy (data, src.data);

}

else

data = 0;

};

return *this;

}

mystring & operator=
(const mystring & src)

{

if (this != &src)

{

char* newdata;

if (src.data)

{

newdata = new char [strlen (src.data) + 1];

strcpy (newdata, src.data);

}

else

newdata = 0;

delete [] data;

data=newdata;

};

return *this;

}

If new throws an exception, the contents of the string will be lost, and data will have incorrect value, what will cause problems in destructor

Fixed version does not destroy the string in case of lack of memory

The string Class with Reference Counting

Copying of a string is a costly operation

Strings are frequently passed by value

We are looking for an efficient implementation, which will decrease the number of allocations and copying

The solution is the reference counting

The string Class with Reference Counting

The class is only a handle - it contains the pointer to the real string implementation

s

size=3

n=1

class string{

struct rctext;

rctext* data;

public:

string(char* s);

string& operator=
(const string&);

~string();

...

};

struct string::rctext

{

char* s;

unsigned int size;

unsigned int n;

...

};

string s1("ala");

s1

data

ala\0

The string Class with Reference Counting

The copying of string copies the pointer to the internal reprezentation and increments the reference counter

s1

data

ala\0

s2

data

class string{

struct rctext;

rctext* data;

public:

string(char* s);

string& operator=
(const string&);

~string();

...

};

struct string::rctext

{

char* s;

unsigned int size;

unsigned int n;

...

};

string s1("ala");

string s2=s1;

s

size=3

n=2

The string Class with Reference Counting

Modification of one of the copies caues separation of s1 and s2 (copy-on-write)

s1

data

ala\0

s2

data

class string{

public:

char read
(unsigned int i) const;

void write
(unsigned int i, char c);

...

};

string s1("ala");

string s2=s1;

s2.write(0,'o');

s

size=3

n=1

ola\0

s

size=3

n=1

The string Class with Reference Counting

We want the indexing operator to work correctly for reading and writing

We do not want reading of character to cause making a copy of the string

We can achieve this by returning in the indexing operator not the character reference, but the special class, Cref

class string{

...

};

string s1("ala");

string s2=s1;

char a=s2[0];

s2[0]='o';

The string Class with Reference Counting

The Cref behaves in the same way as char, but can distinguish between reading and writing

class string{

public:

string(char* s);

string& operator=(const string&);

~string();

void check(unsigned int i) const;

Cref operator[](unsigned int i);

char operator[](unsigned int i) const;

char string::read(unsigned int i) const;

void string::write(unsigned int i, char c){

data = data->detach();

data->s[i] = c;

}

...

};

string::Cref
string::operator[](unsigned int i)

{

check(i);

return Cref(*this,i);

};

class string::Cref

{

friend class string;

string& s;

unsigned int i;

Cref (string& ss, unsigned int ii)
:s(ss), i(ii) {};

public:

operator char() const

{

return s.read(i);

}

string::Cref& operator = (char c)

{

s.write(i,c);

return *this;

};

string::Cref& operator = (const Cref& ref)

{

return operator= ((char)ref);

};

};

rcstring and multithreading

Reference-counting implementation can cause problems in multithreaded programs

#include <stdio.h>

#include <pthread.h>

#include "rcstring.h"

rcstring s ("ala");

void * thread1 (void *p)

{

for (unsigned int i = 0;
i < 100000; i++)

{

rcstring s1 (s);

}

pthread_exit (p);

}

void * thread2 (void *p)

{

for (unsigned int i = 0;
i < 100000; i++)

{

rcstring s1 (s);

}

pthread_exit (p);

}

int main ()

{

pthread_t t1;

pthread_t t2;

pthread_create (&t1, NULL, thread1, NULL);

pthread_create (&t2, NULL, thread2, NULL);

pthread_join (t1, (void **) &retval1);

pthread_join (t2, (void **) &retval2);

printf ("RefCount=%d\n", s.getRefCount ());

};

inline rcstring::rcstring(const rcstring& x) {

x.data->n++;

data=x.data;

}

inline rcstring::~rcstring() {

if(--data->n==0)

delete data;

}

Two threads can simultaneously change n

rcstring and multithreading

Operation "n++" is not atomic

It is composed of three phases:

Reading the value from memory

Incrementation

Writing the updated value to memory

These operation can be interleaved in a few threads

In effect, the variable has the incorrect final value (incrementation by one, instead of two)

Need to use synchronization objects (semaphores) or the special assembler instructions

thread1: d0=n;

thread2: d0=n;

thread1: d0=d0+1;

thread2: d0=d0+1;

thread1: n=d0;

thread2: n=d0;

The volatile Specifier

The volatile specifier denotes, that the variable value can change outside the program and therefore forbids optimization regarding the variable (e.g. storing it in the processor registers)

Used, when the variable references are the references to the input/output device registers

Unfortunately, it will not help us in case of reference-counting string

The volatile Specifier

Adding the volatile specifier causes, that the program will behave according to our expectations (however, this is not guaranteed by the C standard)

#include <stdio.h>

#include <pthread.h>

int val = 0;

void * fun1 (void *)

{

val = 0;

while (1)

if (val != 0)

break;

printf ("out of the loop\n");

pthread_exit (NULL);

}

int main ()

{

pthread_t w;

pthread_create
(&w, NULL, fun1, NULL);

val = 1;

pthread_join (w, NULL);

};

#include <stdio.h>

#include <pthread.h>

volatile int val = 0;

void * fun1 (void *)

{

val = 0;

while (1)

if (val != 0)

break;

printf ("out of the loop\n");

pthread_exit (NULL);

}

int main ()

{

pthread_t w;

pthread_create
(&w, NULL, fun1, NULL);

val = 1;

pthread_join (w, NULL);

};

Semaphores

Critical section

data->n++

struct rcstring::rctext

{

char *s;

unsigned int size;

unsigned int n;

pthread_mutex_t mutex;

rctext (unsigned int nsize,
const char *p)

{

n = 1;

size = nsize;

s = new char[size + 1];

strncpy (s, p, size);

s[size] = '\0';

pthread_mutex_init
(&mutex, NULL);

};

unsigned int AtomicIncrement()

{

pthread_mutex_lock(&mutex);

unsigned int retval=n++;

pthread_mutex_unlock(&mutex);

return retval;

};

unsigned int AtomicDecrement()

{

pthread_mutex_lock(&mutex);

unsigned int retval=n--;

pthread_mutex_unlock(&mutex);

return retval;

};

//...

};

Programowanie obiektowe

gwj

2004-02-25T09:30:05