tag:blogger.com,1999:blog-47401062307025484972024-02-22T13:16:36.873-08:00Window Of My Soulsanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-4740106230702548497.post-81432670615838430732015-01-06T10:02:00.000-08:002015-01-06T10:02:15.262-08:00Arduino Interfaced with 8Segment Display<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
Got a 8segment display ordered from ebay<br />
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';">"MAX7219 EWG 8-Digit Digital Tube Display Control Module Red for arduino"</span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';"><br /></span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, Trebuchet MS;">Now connected it to arduino over SPI interface. The connectivity is as follows.</span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, Trebuchet MS;"><br /></span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, Trebuchet MS;"><br /></span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, Trebuchet MS;">Arduino Display</span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, Trebuchet MS;">Vcc(5v) -----> VCC</span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, Trebuchet MS;">GND -------> GND</span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, Trebuchet MS;">Pin 10 ------> CS(chip Select)</span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';">Pin 11 ------> DIN(data in)</span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';">Pin 13 ------> CLK</span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';"><br /></span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';"><br /></span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';">The Arduino Code is as follows. The code prints numbers from 0 to 100 on the display in a loop.</span><br />
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';"><br /></span>
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';"><br /></span>
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';"><br /></span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Trebuchet, 'Trebuchet MS';"><br /></span></div>
<div style="text-align: left;">
<span style="color: #333333; font-family: Courier New, Courier, monospace;">#include <spi .h=""></spi></span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">const int slaveSelectPin = 10;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">int num = 0;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"><br /></span>
<span style="color: #333333; font-family: Courier New, Courier, monospace;">void setup() {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"><br /></span>
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> Serial.begin(57600); //</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> while (!Serial) {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> ; // wait for serial port to connect. Needed for Leonardo only</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //Serial.println("Goodnight moon!");</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> // set the slaveSelectPin as an output:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //pinMode (slaveSelectPin, OUTPUT);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> // initialize SPI:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pinMode (slaveSelectPin, OUTPUT);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"><br /></span>
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.begin(); </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> initMax();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">}</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"><br /></span>
<span style="color: #333333; font-family: Courier New, Courier, monospace;">void pulseCS(void) {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> digitalWrite(slaveSelectPin, 1);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> delay(1);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> digitalWrite(slaveSelectPin, 0);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">}</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"><br /></span>
<span style="color: #333333; font-family: Courier New, Courier, monospace;">void initMax()</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">{</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> digitalWrite(slaveSelectPin, 0);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x09);//Decode Mode</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">// SPI.transfer(0xFF);//BCD decode for all digits</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x00); // No decode</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x0B);//Scan Limit</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x07);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x0A);//Intensity</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x01);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> for(int i=1; i<=8; i++) {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(i);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x00);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS(); </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x0C);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x01);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"><br /></span>
<br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //Serial.println("Display Init"); </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //numDigits(7);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">}</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"><br /></span>
<span style="color: #333333; font-family: Courier New, Courier, monospace;">int numDigits(int i)</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">{</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> int count = 1;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> while(1)</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> i = i /10;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> if (i != 0)</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> count ++;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> else</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> Serial.print("Num Digits :"); </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> Serial.println(count);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> return count;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">}</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">void displayNum(int i)</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">{</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> for(int i=1; i<=8; i++) {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(i);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(0x00);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS(); </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //Find how many digits</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> int numDig = numDigits(i);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> int pos = 1;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> while (1)</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> int k = i % 10;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(pos); </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> switch(k)</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 0:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B01111110);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 1:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B00110000);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 2:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B01101101);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 3:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B01111001);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 4:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B00110011);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 5:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B01011011);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 6:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B01011111);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 7:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B01110000);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 8:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B01111111);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> case 9:</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> SPI.transfer(B01111011);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break; </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> if (pos == numDig)</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> break;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> pos ++;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> i = i/10;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">}</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"><br /></span>
<span style="color: #333333; font-family: Courier New, Courier, monospace;">void loop() { </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> if (num <= 100)</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> displayNum(num);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> delay(1000);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> num++;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> else</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> {</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> num = 0;</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //SPI.transfer(1); </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //SPI.transfer(0x09);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //pulseCS();</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //delay(1000);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //SPI.transfer(2); </span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //SPI.transfer(0x08);</span><br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;"> //pulseCS();</span><br />
<br />
<span style="color: #333333; font-family: Courier New, Courier, monospace;">}</span><br />
<div>
<br /></div>
</div>
</div>
sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-79351331941932775642014-01-30T10:07:00.001-08:002014-01-30T10:10:06.828-08:00Smart Car Project<div dir="ltr" style="text-align: left;" trbidi="on">
<h2 style="text-align: left;">
<u>smart Car </u></h2>
<h3 style="text-align: left;">
</h3>
<div>
Connection diagram</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCRobibYBSxtj6HLk_iN5kIc-usqM1gDJLLjTcP0DtOyX0FvB8hrfDII7jkBhSR56g4afGbpzsa8ViNmLEqWnsKMSZ74VJK-HUGsLAked_qQZMV6JBzldDOjTDYieVwsvWFMqro87gGYDb/s1600/smartcar.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCRobibYBSxtj6HLk_iN5kIc-usqM1gDJLLjTcP0DtOyX0FvB8hrfDII7jkBhSR56g4afGbpzsa8ViNmLEqWnsKMSZ74VJK-HUGsLAked_qQZMV6JBzldDOjTDYieVwsvWFMqro87gGYDb/s1600/smartcar.jpg" height="114" width="320" /></a></div>
<br /></div>
<h3 style="text-align: left;">
</h3>
<h3 style="text-align: left;">
</h3>
<h3 style="text-align: left;">
</h3>
<h3 style="text-align: left;">
</h3>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<h3 style="text-align: left;">
Arduino code</h3>
<br />
#define led 13<br />
<br />
//for Fwd and Backward<br />
#define pin1 2<br />
#define pin2 4<br />
<br />
//for Right and left<br />
#define LR1 7<br />
#define LR2 8<br />
<br />
int inByte = 0;<br />
<br />
void setup()<br />
{<br />
Serial.begin(9600);<br />
Serial.println("Hello World");<br />
<br />
pinMode(led, OUTPUT);<br />
<br />
pinMode(pin1, OUTPUT);<br />
pinMode(pin2, OUTPUT);<br />
<br />
pinMode(LR1, OUTPUT);<br />
pinMode(LR2, OUTPUT);<br />
<br />
digitalWrite(pin1, LOW);<br />
digitalWrite(pin2, LOW);<br />
digitalWrite(LR1, LOW);<br />
digitalWrite(LR2, LOW);<br />
}<br />
<br />
void loop()<br />
{<br />
if (Serial.available() > 0)<br />
{<br />
inByte = Serial.read();<br />
int stp = 0; //Stop wheels<br />
int fwd = 1; //run in fwd direction<br />
int bw = 2; //backward dir<br />
int right = 3; //right<br />
int left = 4; //left<br />
<br />
Serial.println(inByte, DEC);<br />
if (inByte == stp)<br />
{<br />
digitalWrite(pin1, LOW);<br />
digitalWrite(pin2, LOW);<br />
Serial.println(stp, DEC);<br />
}<br />
if (inByte == fwd)<br />
{<br />
digitalWrite(pin1, HIGH);<br />
digitalWrite(pin2, LOW);<br />
Serial.println(fwd ,DEC);<br />
}<br />
if (inByte == bw)<br />
{<br />
digitalWrite(pin1, LOW);<br />
digitalWrite(pin2, HIGH);<br />
Serial.println(bw, DEC);<br />
}<br />
if (inByte == right)<br />
{<br />
digitalWrite(LR1, LOW);<br />
digitalWrite(LR2, HIGH);<br />
Serial.println(right, DEC);<br />
}<br />
if (inByte == left)<br />
{<br />
digitalWrite(LR1, HIGH);<br />
digitalWrite(LR2, LOW);<br />
Serial.println(left, DEC);<br />
}<br />
<br />
Serial.println("done");<br />
}<br />
}<br />
<br />
<br />
<h3 style="text-align: left;">
udp_server.c</h3>
<div>
<br />
<h3 style="text-align: left;">
Android code</h3>
<a href="https://github.com/sanjivko/SmartCar">https://github.com/sanjivko/SmartCar</a></div>
</div>
sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-22998229378279344812012-05-24T13:48:00.000-07:002012-05-24T13:49:49.871-07:00My experiments with tic tac toe<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
Was writing a tic tac toe app for android recently as was familiar with the rules of the game :-).<br />
The last time I wrote a tic tac toe game was in college time, and then most focus was on the gui design. The lousiest algorithm in the background.<br />
<br />
One of the algorithm was to check the state of the game i.e win or draw etc. Gave it a thought this time and made some optimization in the row, col, diagonal checks. Its mainly decided in the first nested loop if we need to check a particular column or diagonal. So, we avoid checking of columns or diagonals saving time. This makes big impact when the board size is more and a significant number of the cells are not filled.<br />
<br />
<br />
Next time I will post the nextMove implementation, for the computer to decide its next move.<br />
<br />
Here is the java code for the gamestate algorithm.<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span><span style="color: blue; font-family: 'Courier New', Courier, monospace;">int gameState(int values[][], int boardSz) {</span><br />
<span class="Apple-tab-span" style="color: blue; font-family: 'Courier New', Courier, monospace; white-space: pre;"> </span><br />
<span class="Apple-tab-span" style="color: blue; font-family: 'Courier New', Courier, monospace; white-space: pre;"> </span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>boolean colCheckNotRequired[] = new boolean[ boardSz ];</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>boolean diag1CheckNotRequired = false;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>boolean diag2CheckNotRequired = false;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>boolean allFilled = true;</span><br />
<span class="Apple-tab-span" style="color: blue; font-family: 'Courier New', Courier, monospace; white-space: pre;"> </span><br />
<span class="Apple-tab-span" style="color: blue; font-family: 'Courier New', Courier, monospace; white-space: pre;"> </span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>int x_count = 0;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>int o_count = 0;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* Check rows */</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>for (int i = 0; i < boardSz; i++) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>x_count = o_count = 0;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>for (int j = 0; j < boardSz; j++) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[i][j] == x_val)x_count++;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[i][j] == o_val)o_count++;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[i][j] == 0)</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>{</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>colCheckNotRequired[j] = true;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(i==j)diag1CheckNotRequired = true;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(i + j == boardSz - 1)diag2CheckNotRequired = true;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>allFilled = false;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>//No need check further</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>break;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(x_count == boardSz)return X_WIN;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(o_count == boardSz)return O_WIN;<span class="Apple-tab-span" style="white-space: pre;"> </span></span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span class="Apple-tab-span" style="color: blue; font-family: 'Courier New', Courier, monospace; white-space: pre;"> </span><br />
<span class="Apple-tab-span" style="color: blue; font-family: 'Courier New', Courier, monospace; white-space: pre;"> </span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* check cols */</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>for (int i = 0; i < boardSz; i++) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>x_count = o_count = 0;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(colCheckNotRequired[i] == false)</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>{</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>for (int j = 0; j < boardSz; j++) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[j][i] == x_val)x_count++;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[j][i] == o_val)o_count++;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>//No need check further</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[i][j] == 0)break;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(x_count == boardSz)return X_WIN;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(o_count == boardSz)return O_WIN;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span class="Apple-tab-span" style="color: blue; font-family: 'Courier New', Courier, monospace; white-space: pre;"> </span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>x_count = o_count = 0;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* check diagonal 1 */</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(diag1CheckNotRequired == false)</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>{</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>for (int i = 0; i < boardSz; i++) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[i][i] == x_val)x_count++;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[i][i] == o_val)o_count++;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[i][i] == 0)break;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(x_count == boardSz)return X_WIN;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(o_count == boardSz)return O_WIN;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span class="Apple-tab-span" style="color: blue; font-family: 'Courier New', Courier, monospace; white-space: pre;"> </span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>x_count = o_count = 0;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>/* check diagonal 2 */</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if( diag2CheckNotRequired == false)</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>{</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>for (int i = boardSz - 1,j = 0; i >= 0 && j < boardSz; i--,j++) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[j][i] == x_val)x_count++;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[j][i] == o_val)o_count++;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(values[j][i] == 0)break;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(x_count == boardSz)return X_WIN;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if(o_count == boardSz)return O_WIN;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>x_count = o_count = 0;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if( allFilled == true)</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>{</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>for (int i = 0; i < boardSz; i++) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>for (int j = 0; j < boardSz; j++) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if (values[i][j] == 0) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>allFilled = false;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>break;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}<span class="Apple-tab-span" style="white-space: pre;"> </span></span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if (allFilled == false) {</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>break;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if (allFilled)</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>return DRAW;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>return INPROGRESS;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<br />
<br /></div>sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-46306678247581303092012-05-17T04:10:00.000-07:002012-05-17T04:13:51.190-07:00Yet Another HashMap ...<div dir="ltr" style="text-align: left;" trbidi="on">
<h2 style="text-align: left;">
</h2>
<div>
There are several implementations of hashmaps available, this is just another implementation that I did when I was too lazy to google for existing implementations.</div>
<div>
<br /></div>
<div>
This implementation is having 2 basic traits:</div>
<div>
1. A strong hash function.</div>
<div>
2. An efficient tree</div>
<div>
<br /></div>
<div>
To implement this I have used the hash implementation provided by <span style="text-align: -webkit-auto;">Bob Jenkins <a href="http://burtleburtle.net/bob/hash/doobs.html">http://burtleburtle.net/bob/hash/doobs.html</a></span></div>
<div>
<br /></div>
<div>
And the tree chosen is a basic red black tree implementation. </div>
<div>
<br /></div>
<div>
A very simple API which enables insertion/deletion of the entries.</div>
<div>
<br /></div>
<div>
<u>To insert entries:</u></div>
<div>
<span style="color: blue; font-family: 'Courier New', Courier, monospace;">hash_insert(void* key, uint32 key_len, void* data, uint32 data_len);</span></div>
<div>
<br /></div>
<div>
<u>To Check if the entry is present in the table</u></div>
<div>
<span style="color: blue; font-family: 'Courier New', Courier, monospace;">hash_find(void* key, uint32 key_len);</span></div>
<div>
<br /></div>
<div>
<u>To retrieve the data for a key</u></div>
<div>
<span style="color: blue; font-family: 'Courier New', Courier, monospace;">hash_getData(void* key, uint32 key_len, void* data, uint16* data_len)</span></div>
<div>
<br /></div>
<div>
<u>To delete an entry</u></div>
<div>
<span style="color: blue; font-family: 'Courier New', Courier, monospace;">hash_deleteEntry(void* key, uint32 key_len);</span></div>
<div>
<br /></div>
<div>
Here is a sample code, to show how to use it.</div>
<div>
<br /></div>
<div style="text-align: left;">
<span style="color: blue; font-family: 'Courier New', Courier, monospace;">#include "hashmap.h"</span><span style="color: blue; font-family: 'Courier New', Courier, monospace;">#include <stdio.h><br /></stdio.h></span><span style="color: blue; font-family: 'Courier New', Courier, monospace;">#include <inttypes.h><br /></inttypes.h></span><span style="color: blue; font-family: 'Courier New', Courier, monospace;">#include <string.h></string.h></span><span style="color: blue; font-family: 'Courier New', Courier, monospace;"><br /></span><span style="color: blue; font-family: 'Courier New', Courier, monospace;">#define MAX_KEY_LEN 128</span><span style="color: blue; font-family: 'Courier New', Courier, monospace;"><br /></span><span style="color: blue; font-family: 'Courier New', Courier, monospace;">int main()</span><span style="color: blue; font-family: 'Courier New', Courier, monospace;">{</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> char key[MAX_KEY_LEN];</span><span style="color: blue; font-family: 'Courier New', Courier, monospace;"><br /></span><span style="color: blue; font-family: 'Courier New', Courier, monospace;"> uint16_t data;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> uint16_t dataLen;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> int i = 10000000;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> </span><span style="font-family: 'Courier New', Courier, monospace;"><span style="color: #e06666;">// First insert</span></span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> strcpy(key, "hello");</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> data = 123;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> hash_insert((void*)key, strlen(key), &data, sizeof(data));</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> </span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><span style="color: blue;"> </span><span style="color: #e06666;">//Lets retrieve it</span></span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> strcpy(key, "hello");</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> uint16_t temp;</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> hash_getData((void*)key, strlen(key), &temp, &dataLen);</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> </span><span style="color: #e06666; font-family: 'Courier New', Courier, monospace;">//Remove the entries</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> strcpy(key, "hello");</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"> hash_deleteEntry((void*)key, strlen(key));</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;">}</span></div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
The default number of entries in the hashmap is defined in hashmap.h as follows</div>
<div style="text-align: left;">
<span style="color: blue;"><br /></span></div>
<div style="text-align: left;">
<span style="color: blue;">#define HASH_MAX_CAPACITY 10000000</span></div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
This can be modified as per requirement.</div>
<div>
<br /></div>
<div>
How to Use</div>
<div>
<br /></div>
<div>
Just hit make in the extracted package. This generates a library libQuickHash.so and libQuickHash.a. There is a sample program testHash.c which can be of help. </div>
<div>
<br /></div>
<div>
The compressed package is here</div>
<div>
<a href="http://ubuntuone.com/6ZYiVy2gPiCJBy3AQuAT9j">http://ubuntuone.com/6ZYiVy2gPiCJBy3AQuAT9j</a></div>
<div>
<br /></div>
<div>
enjoy ...</div>
<div>
<br /></div>
</div>sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-31789077400933325422011-11-09T03:26:00.000-08:002011-11-09T03:54:55.677-08:00How smart are the smart pointers ?<html><head><title>Untitled document</title><style type="text/css">ol{margin:0;padding:0}p{margin:0}.c3{width:468pt;background-color:#ffffff;padding:72pt 72pt 72pt 72pt}.c0{color:#285bac;background-color:#fce5cd;font-family:Courier New}.c4{text-indent:36pt;margin-left:72pt}.c1{direction:ltr}.c2{height:11pt}body{color:#000000;font-size:11pt;font-family:Arial}h1{padding-top:24pt;color:#000000;font-size:24pt;font-family:Arial;font-weight:bold;padding-bottom:6pt}h2{padding-top:18pt;color:#000000;font-size:18pt;font-family:Arial;font-weight:bold;padding-bottom:4pt}h3{padding-top:14pt;color:#000000;font-size:14pt;font-family:Arial;font-weight:bold;padding-bottom:4pt}h4{padding-top:12pt;color:#000000;font-size:12pt;font-family:Arial;font-weight:bold;padding-bottom:2pt}h5{padding-top:11pt;color:#000000;font-size:11pt;font-family:Arial;font-weight:bold;padding-bottom:2pt}h6{padding-top:10pt;color:#000000;font-size:10pt;font-family:Arial;font-weight:bold;padding-bottom:2pt}</style></head><body class="c3"><p class="c1 c2"><span></span></p><p class="c1"><span>smart_pointer is a blessing for a carefree programmer who wants to allocate memory in heap and forget about deleting it. Sounds great. Its really tough to track a pointer and carefully release the heap memory captured. </span></p><p class="c1 c2"><span></span></p><p class="c1"><span>Also it relies on the fact that its easy to clear stack than heap. So, lets see how it works. </span></p><p class="c1 c2"><span></span></p><p class="c1"><span>First lets see, how can we use a smart pointer class in our program and then we will go ahead to implement it. Please follow the comments for understanding.</span></p><p class="c1 c2"><span></span></p><p class="c1 c2"><span></span></p><p class="c1"><span>We take an example class </span></p><p class="c1 c2"><span></span></p><p class="c1"><span class="c0">class A</span></p><p class="c1"><span class="c0">{</span></p><p class="c1"><span class="c0"> public:</span></p><p class="c1"><span class="c0"> //This variable is meant to track the </span></p><p class="c1"><span class="c0"> // number of instances of the class that are existing.</span></p><p class="c1"><span class="c0"> static int count; </span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> //Constructor</span></p><p class="c1"><span class="c0"> A()</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> //New instance is created so increment.</span></p><p class="c1"><span class="c0"> count++;</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> //Copy contstructor</span></p><p class="c1"><span class="c0"> A(A& obj)</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> //New instance is created so increment</span></p><p class="c1"><span class="c0"> count ++;</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> //Assignment operator</span></p><p class="c1"><span class="c0"> A& operator =(A& obj)</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> //New instance is created so increment</span></p><p class="c1"><span class="c0"> count ++;</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1"><span class="c0"> ~A()</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> //Instance removed, so decrement the value.</span></p><p class="c1"><span class="c0"> count --;</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> void display()</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> cout << "Its me \n";</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0">};</span></p><p class="c1 c2"><span></span></p><p class="c1"><span>Now we look at the main function where we will be using the smart_ptr class.</span></p><p class="c1 c2"><span></span></p><p class="c1 c2"><span></span></p><p class="c1"><span class="c0">int main()</span></p><p class="c1"><span class="c0">{</span></p><p class="c1"><span class="c0"> //This is how we create a smart_ptr object</span></p><p class="c1"><span class="c0"> // see the pointer of type A is stored inside the </span></p><p class="c1"><span class="c0"> // smart_ptr object</span></p><p class="c1"><span class="c0"> smart_ptr<A> ptr(new A());</span></p><p class="c1"><span class="c0"> smart_ptr<A> ptr1;</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> //Testing assignment operator</span></p><p class="c1"><span class="c0"> ptr1 = ptr;</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> //Testing self assignment</span></p><p class="c1"><span class="c0"> ptr = ptr;</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> // Verifying how many instances of A are there.</span></p><p class="c1"><span class="c0"> cout << "A::count = " << A::count << endl;</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> //Using overloaded -> operator to call </span></p><p class="c1"><span class="c0"> // member functions of class A</span></p><p class="c1"><span class="c0"> ptr->display();</span></p><p class="c1"><span class="c0">}</span></p><p class="c1 c2"><span></span></p><p class="c1 c2"><span></span></p><p class="c1"><span>Now we implement the smart_ptr class, as per the usage. So, here it is.</span></p><p class="c1 c2"><span></span></p><p class="c1"><span class="c0">template <class T></span></p><p class="c1"><span class="c0">class smart_ptr</span></p><p class="c1"><span class="c0">{</span></p><p class="c1"><span class="c0"> private:</span></p><p class="c1"><span class="c0"> // The pointer which is managed </span></p><p class="c1"><span class="c0"> // by the smart_ptr class</span></p><p class="c1"><span class="c0"> T* m_ptr;</span></p><p class="c1"><span class="c0"> //Keeps track of the number of references </span></p><p class="c1"><span class="c0"> //the allocated memmory.</span></p><p class="c1 c4"><span class="c0">int ref_count;</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> public:</span></p><p class="c1"><span class="c0"> smart_ptr()</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> m_ptr = 0;</span></p><p class="c1"><span class="c0"> ref_count = 0;</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1"><span class="c0"> smart_ptr(T* ptr)</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> m_ptr = ptr;</span></p><p class="c1"><span class="c0"> //increment the ref count </span></p><p class="c1"><span class="c0"> //as this is the first reference</span></p><p class="c1"><span class="c0"> ref_count = 1; </span></p><p class="c1"><span class="c0"> }</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> smart_ptr(smart_ptr& obj)</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> cout << "Copy Contstructor\n";</span></p><p class="c1"><span class="c0"> ref_count++;</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> //Assignment operator overload</span></p><p class="c1"><span class="c0"> smart_ptr* operator =(smart_ptr& obj)</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> if(&obj != this)</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> ref_count++;</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1"><span class="c0"> else</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> cout << "Self assignment\n";</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> // Destructor</span></p><p class="c1"><span class="c0"> ~smart_ptr()</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> cout << "Deleteing the smart_ptr instance\n";</span></p><p class="c1"><span class="c0"> // Decrement the reference count as</span></p><p class="c1"><span class="c0"> // the instance is released</span></p><p class="c1"><span class="c0"> ref_count --;</span></p><p class="c1"><span class="c0"> if(ref_count == 0)</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> // Delete the pointer</span></p><p class="c1"><span class="c0"> // as there are no references to it.</span></p><p class="c1"><span class="c0"> delete m_ptr;</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0"> T* operator ->()</span></p><p class="c1"><span class="c0"> {</span></p><p class="c1"><span class="c0"> return m_ptr;</span></p><p class="c1"><span class="c0"> }</span></p><p class="c1 c2"><span class="c0"></span></p><p class="c1"><span class="c0">};</span></p><p class="c1 c2"><span></span></p><p class="c1 c2"><span></span></p></body></html>sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-89264353198485421552011-10-11T03:47:00.000-07:002011-10-11T03:58:01.653-07:00A Gram of Anagram<div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">Last week attended an interview, and this was the question the interviewer came up with to test my problem solving.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">" Give a logic to generate valid anagrams of a word, provided you have a dictionary to confirm the validity"</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">After a while of scribbling on the blank paper I came up with the following answer. </span></div><div><span class="Apple-style-span"><br /></span></div><div><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">If I take a dictionary as a Hash Map as every word is unique and the Key is a binary(or Hex) representation of the word. Then if I have a word I can easily find the meaning of it with O(1) complexity.</span></p><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">Now, if we have to generate all the valid anagrams, we need to verify if the generated anagram is in the dictionary, if it is present in dictionary, its a valid one else we need to ignore that.</span></p><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">I will assume that there can be a word of max 100 characters(or more but there is a limit).</span></p><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">So any word we take it as a sequence of indexes like a word "hello" can be represented like "1234". Now the anagrams of "1234" are "1243", "1242" ..etc</span></p><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">The only thing we need to do is to store all such combinations of indexes for a particular number of characters. This is an one time task. And then words can be generated from the combinations by picking the characters from the index.Hence we get the anagrams.</span></p><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">To verify if the anagrams are valid or not, just index into the dictionary and validate.</span></p><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">The only thing need to be handled is the duplicates.That can be done easily. As an when we need to compare with the previous ones that has been searched in dictionary.</span></p><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">And I said the solution emphasizes on performance.</span></p><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">I don't know if this is the answer the interviewer was expecting or something else but I can guess it now as I did not get any response for further rounds. </span></p><p style="margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; vertical-align: baseline; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); clear: both; word-wrap: break-word; line-height: 18px; "><span class="Apple-style-span">Really need to work on my problem solving skills. </span></p></div>sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-55504907618989328302010-12-14T01:54:00.000-08:002010-12-14T07:31:59.030-08:00Multi Key Maps.. myth or reality<div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-color: transparent; "><span class="Apple-style-span" ><span class="Apple-style-span" style="font-size: 15px; white-space: pre-wrap;"><br /></span></span><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">What the heck ? Never heard of these, is it possible to access the same entry with multiple keys? Just somedays back thought of this, and said y not .</span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; font-size: 11pt; background-color: transparent;"></span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">Our good old friend Map allows us to have an unique key which is mapped to a value. To access a value we must have an index which is unique. But what if we want to access the same entry but using multiple indices we need a slightly different mechanism.</span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; font-size: 11pt; background-color: transparent;"></span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">Ok , so here I would discuss a way to achieve it. And we will put into use something we learned in school and that is Prime Number. These are basically the numbers that are divisible by themselves except 1. </span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; font-size: 11pt; background-color: transparent;"></span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">Euclid’s Fundamental Theorem of Arithmetic states that Every integer can be written as a product of primes in an essentially unique way. And </span><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">Euclid's second theorem states that the number of prime numbers is infinite.</span><br /><span class="Apple-style-span" ><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;"></span></span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">Now, as per the first rule we conclude that prime numbers are the ones upon multiplication of which we can generate any number. So, can we say they are the basic components of any number. </span><br /><span class="Apple-style-span" ><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;"></span></span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">Based on this we try to create a key of a map. Lets say we want to create a map in which a value can be accessed using 2 keys.</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">Here are the various keys that we are going to use and the index values they generate.</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">2*3 = 6</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">5*7 = 35</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">11*13 = 143 .. and so on. Note that each of the index has only 2 factors except 1.</span><br /><span class="Apple-style-span" ><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;"></span></span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">Now we create a map from integer to a string with the above indices</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">6 --> “Hello”</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">35 --> “ World”</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">143 ---> “Sanjiv”</span><br /><span class="Apple-style-span" ><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;"></span></span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">Say in c++, the search code will look something like this.</span><br /><span class="Apple-style-span" ><span style="font-size: 12pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; background-color: transparent;"></span></span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(19, 79, 92); background-color: rgb(255, 242, 204); font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">map<int,> my_map.begin ;</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(19, 79, 92); background-color: rgb(255, 242, 204); font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">string get(int key)</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(19, 79, 92); background-color: rgb(255, 242, 204); font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">{</span><br /><span style="font-size: 12pt; font-family: Arial; color: rgb(19, 79, 92); background-color: rgb(255, 242, 204); font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; "><span class="Apple-tab-span" style="white-space: pre; "> </span>for(map<int,>::iterator iter = my_map.begin(); iter != my_map.end(); iter++)</span><br /><p style="text-indent: 36pt; margin-top: 0pt; margin-bottom: 0pt; font-family: 'Times New Roman'; font-size: medium; "><span style="font-size: 12pt; font-family: Arial; color: rgb(19, 79, 92); background-color: rgb(255, 242, 204); font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">{</span></p><p style="text-indent: 36pt; margin-top: 0pt; margin-bottom: 0pt; font-family: 'Times New Roman'; font-size: medium; "><span style="font-size: 12pt; font-family: Arial; color: rgb(19, 79, 92); background-color: rgb(255, 242, 204); font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; "><span class="Apple-tab-span" style="white-space: pre; "> </span>if(iter->first % key == 0) //Key matches with the index</span></p><p style="text-indent: 36pt; margin-top: 0pt; margin-bottom: 0pt; font-family: 'Times New Roman'; font-size: medium; "><span style="font-size: 12pt; font-family: Arial; color: rgb(19, 79, 92); background-color: rgb(255, 242, 204); font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; "><span class="Apple-tab-span" style="white-space: pre; "> </span><span class="Apple-tab-span" style="white-space: pre; "> </span>return iter->second;</span></p><p style="text-indent: 36pt; margin-top: 0pt; margin-bottom: 0pt; font-family: 'Times New Roman'; font-size: medium; "><span style="font-size: 12pt; font-family: Arial; color: rgb(19, 79, 92); background-color: rgb(255, 242, 204); font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">}<span class="Apple-tab-span" style="white-space: pre; "> </span></span></p><span style="font-size: 12pt; font-family: Arial; color: rgb(19, 79, 92); background-color: rgb(255, 242, 204); font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">}</span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; font-size: 11pt; background-color: transparent;"></span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">It looks so dumb that we are have to traverse the whole map to find the match. This completely denies the whole purpose of an associated storage.</span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; font-size: 11pt; background-color: transparent;"></span><br /><span style="font-size: 11pt; font-family: Arial; color: rgb(0, 0, 0); background-color: transparent; font-weight: normal; font-style: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap; ">I hope I will be able to come up with a better way to do the same.</span></div>sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-57090138014596383282010-06-11T11:10:00.000-07:002010-06-11T11:41:31.449-07:00What the Hell are Allocators ???Writing this is like a compulsive need to understand wht the heck is all about Allocators in c++. I see these whenever I check a process core dump with vectors, maps etc , and they make the complete stack look so scary. And also not to mention the compilation errors. You do some teeny weeny mistake in vector or map or some crazy stl declaration and bammm the compilation error scares the hell out of you, and you wonder where did I declare with those allocators n all.<br /><br />Here I will try to get over my fears and try to understand properly what are these things. And not embarrass my self because of the fact that being a 3.5 years experienced c++ programmer c++ allocators have eluded me for a long, and will now make an attempt to do it along with explaining to you guys.<br /><br />The definition as understood by me is that an allocator is a class that handles the allocation/de-allocation of various STL, especially containers. For example take vector, its just a linked list. Whenever we call push_back() on a vector object, it has to allocate some memory for the entry and attache it to the existing linked list. This allocation of memory is hidden to us and is handled by a class specifically designed for the purpose i.e the allocator.<br />Now what is the functionality that we are looking for in the Allocator class<br />1. Allocation/Deallocation<br />2. Hopefully Thats it... <br /><br />Lets take it forward and try to implement an allocator.<br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">#include <iostream></span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">#include <vector></span></font><br style="background-color:#fff2cc"><br /><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">using namespace std;</span></font><br style="background-color:#fff2cc"><br /><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">template<typename T></span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">class Allocator</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">{</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> public:</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> typedef T value_type;</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> typedef value_type* pointer;</span></font><br style="background-color:#fff2cc"><br /><br style="background-color:#fff2cc"><br /><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> public:</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> inline explicit Allocator()</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> {</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> cout << "Constructor of Allocator\n";</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> }</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> inline ~Allocator()</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> {</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> cout << "destructor of Allocator\n";</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> }</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> inline explicit Allocator(Allocator const&) {}</span></font><br style="background-color:#fff2cc"><br /><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">};</span></font><br style="background-color:#fff2cc"><br /><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">int main()</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">{</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> vector<int, Allocator<int> > vec;</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">}</span></font><br /><br /><br />Guess what when I compiled I got a really long list of errors. Probably these compilation errors will help us understand Allocators better. So, here is the listing.<br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h: In instantiation of `std::vector<int, Allocator<int> >':</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">test_allocator.cxx:29: instantiated from here</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:152: error: no type named `const_pointer' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:153: error: no type named `reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:154: error: no type named `const_reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:157: error: no type named `const_pointer' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:158: error: no type named `const_pointer' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:322: error: no type named `const_pointer' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:338: error: no type named `const_pointer' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:354: error: no type named `const_pointer' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:370: error: no type named `const_pointer' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:462: error: no type named `reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:476: error: no type named `const_reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:500: error: no type named `reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:514: error: no type named `const_reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:521: error: no type named `reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:528: error: no type named `const_reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:535: error: no type named `reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:542: error: no type named `const_reference' in `class Allocator<int>'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">test_allocator.cxx: In function `int main()':</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">test_allocator.cxx:29: error: no matching function for call to `Allocator<int>::Allocator(Allocator<int>)'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:182: error: in passing argument 1 of `std::vector<_Tp, _Alloc>::vector(const typename std::_Vector_base<_Tp, _Alloc>::allocator_type&) [with _Tp = int, _Alloc = Allocator<int>]'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h: In member function `void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(_Tp*, size_t) [with _Tp = int, _Alloc = Allocator<int>]':</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:106: instantiated from `std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = int, _Alloc = Allocator<int>]'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:182: instantiated from `std::vector<_Tp, _Alloc>::vector(const typename std::_Vector_base<_Tp, _Alloc>::allocator_type&) [with _Tp = int, _Alloc = Allocator<int>]'</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">test_allocator.cxx:29: instantiated from here</span></font><br style="background-color:#fff2cc"><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:117: error: 'struct std::_Vector_base<int, Allocator<int> >::_Vector_impl' has no member named 'deallocate'</span></font><br style="background-color:#fff2cc"><br /><br /><br />So, you can see there are various declarations/definitions missing in the allocator class. I hate to tell this, but its a fact that allocators follow some C++ standards guideline as per how the class should look like. <br /><font class="Apple-style-span" face="arial, helvetica, sans-serif">(ISO C++ standard, section 20.4.1)</font><br />And it looks like the following. I have provided brief description next to each declaration.<br /><br />//Template definition for allocator as it will be used to allocate <br />// any pointer type<br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> template <class T> </span></font><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> </span></font><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc">class allocator {</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> public:</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> //Set of typedefs to be used in various<br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> //methods for allocation/deallocation/construction<br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // destruction etc.<br /></span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> typedef size_t size_type;</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> //<font class="Apple-style-span" face="arial, helvetica, sans-serif">Unsigned integral value that can represent the difference between two pointers</font></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> typedef ptrdiff_t difference_type;</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // Pointer type for the class<br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> typedef T* pointer;</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // Const pointer type for the class</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> typedef const T* const_pointer;</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> //Reference type for the class </span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> typedef T& reference;</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> //Const Reference for the class</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> typedef const T& const_reference;</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // Value type </span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> typedef T value_type;</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> </span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> //te<font class="Apple-style-span" face="arial, helvetica, sans-serif">mplate structure, which allows any allocator might allocate memory of another type indirectly.</font><br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> template <class U> struct rebind { typedef allocator<U></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> other; };</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> allocator() throw();</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> allocator(const allocator&) throw();</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> template <class U> allocator(const allocator<U>&) throw();</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> ~allocator() throw();</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> pointer address(reference x) const;</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> const_pointer address(const_reference x) const;</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // This function will be called, whenever a new memory </span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // allocation is required. As in vector push_back </span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> pointer allocate(size_type,</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> allocator<void>::const_pointer hint = 0);</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // This function will be called when the memory location needs to be <br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // freed.<br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> void deallocate(pointer p, size_type n);</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> size_type max_size() const throw();</span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // Following are required to initialize/de-initialize the allocated</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> </span></font><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> // memory location.</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> void construct(pointer p, const T& val);</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> void destroy(pointer p);</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> };</span></font><br /><br /><br />Now after we have understood how our Allocator class should look like, lets put some life into this class. Lets make it usable by defining atleast allocate/deallocate functions. <br /><br />Here is how I have defined it in my test program.<br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> pointer allocator::allocate(size_type sz, std::allocator<void>::const_pointer hint = 0)</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> {</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> cout << "Allocating\n";</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> char* ch = (char*)malloc(sizeof(sz));</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> return (pointer)(ch);</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> }</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> void allocator::deallocate(pointer p, size_type n)</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> {</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> cout << "De-Allocating\n";</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> free(p);</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> <br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> }</span></font><br /><br /><br />Now lets see, how does it work in real use.<br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> int main()</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> {</span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> vector<int> myVector;<br /></span></font><br /><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> myVector.push_back(1);<br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> <br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> }</span></font><br /><br />On compiling and running the program following out put is obtained.<br /> <font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> Allocating<br /></span></font><br /><font class="Apple-style-span"><span class="Apple-style-span" style="background-color:#fff2cc"> De-Allocating<br /></span></font><br /><br />At this point atleast we are aware of some internals of allocators, and we know "wht the hell allocators are" . Going further we can define our pool of memory and allocate from that pool and handle all allocations/deallocations in that chunk of memory using our own creative memory management algorithm. <br /><br />I hope I will cover that advanced topic some other day , till then cya .....sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-55179502414064587202010-02-04T01:01:00.000-08:002010-02-07T01:08:26.885-08:00Why Leaking Memory ?<span style="font-family:georgia;">This is a common practice programmers have , including myself not to check for any growth in memory of programs written unless someone asks to. </span><span style="font-family:georgia;"><br /><br />Here is a definition of Memory Leak.</span><br /><span style="font-family:georgia;">Memory leak is what happens when a program is unable to release memory allocated by it, back to the OS/kernel.</span><br /><br /><span style="font-family:georgia;">In simple terms I have borrowed something from a friend of mine and I lost it.Now I cannot return it to him. </span><span style="font-family:georgia;">No, I am not Amir Khan from Ghajni, I still remember who that friend of mine is . </span><span style="font-family:georgia;">Just that I am so much careless that I do not take care of stuffs borrowed from friends. </span><span style="font-family:georgia;"><br /><br />Now this inability of the program to release the memory back to the kernel, in a long run causes the system memory to be full and hence less memory availability for other process to run hence decrease in system performance and consequently bad days for the developer who did not fix the leak at the right time and so on.Hopefully I am still doing fine after ignoring so many memory leaks :-<br /><br />So, to avoid all that all we have to do is not waste time on facebook/orkut in office time, not spend time at tea or lunch discussing Kat-Salman relationship , not spend time on cracking stupid PJs at your workplace, but the easiest one will be to read further and get enlightened.<br /><br />Here I have tried to come up with a list of reasons of Memory Leaks and the possible solution for the same apart from not being drunk while writing a piece of code.<br /><br /></span><span style="font-family:georgia;">A very simple memory leak can be introduced as follows. </span><br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);">int main()</span></span></span><span style="font-family:courier new;color:#333399;"><br /><span><span style="background-color: rgb(255, 242, 204);">{</span></span></span><span style="font-family:courier new;color:#333399;"><br /><span><span style="background-color: rgb(255, 242, 204);"> char* ch = new char(100);</span></span></span><span style="font-family:courier new;color:#333399;"><br /><span><span style="background-color: rgb(255, 242, 204);"> //Do not free the pointer ch, using</span></span></span> <span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> //delete ch;</span></span></span><span style="font-family:courier new;color:#333399;"><br /><span><span style="background-color: rgb(255, 242, 204);"> //and you get a memory leak</span></span></span><span style="font-family:georgia;"><br /><span><span style="background-color: rgb(255, 242, 204);"> </span></span><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);">}</span></span></span><br /><br />This looks harmless but if we put the allocation in a while or a for loop to run indefinitely, it make matters worse.<br /><br />Here are few scenario I could come up with in which we can get memory leak.<br /><br />1. Assigning a pointer NULL after allocating memory.<br /><span style="font-family:courier new;"><span><span style="background-color: rgb(255, 242, 204);">{</span></span></span><br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> char *ch = new char(10);</span></span></span><br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> ch = NULL; </span></span></span><br /><span style="font-family:courier new;"><span><span style="background-color: rgb(255, 242, 204);">}</span></span></span><br /><br />Solution is to free the memory allocated before assigning NULL to the pointer.<br /><br />2. Freeing the memory using a pointer of different data type. Sounds rare but its possible.<br /></span><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);">{</span></span></span><br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> char* ch = new char(100);<br /></span></span></span><span><span style="background-color: rgb(255, 242, 204);"> </span></span><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> int *num = (int*)ch;<br /></span></span></span><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> delete num;</span></span></span> <span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> //Just frees sizeof(int) bytes<br /></span></span></span><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);">}</span></span></span><br /><br />Solution is to delete the pointer of same type which was used while memory allocation.<br /><br />3. In case of arrays missing [] with delete operator.<br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);">{<br /></span></span></span><span><span style="background-color: rgb(255, 242, 204);"> </span></span><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);">char* ch = new char[100];</span></span></span><br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> delete ch; //will free just 1byte </span></span></span> <span style="font-family:courier new;color:#333399;"><br /><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><br /><span style="font-family:georgia;"> Solution is to use [] while freeing memory allocated for arrays.<br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);">{</span></span></span><br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> char *ch = new char[100];</span></span></span><br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> <b>delete [] ch; // or delete ch[]</b></span></span></span><br /><span style="font-family:courier new;color:#333399;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /></span><br /><span style="font-family:georgia;">4. STL containers do not call delete if pointers are stored. For example<br /> a.<br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> vector<char*> list;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> list.push_back(new car(10));</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> list.push_back(new car(100));</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> list.clear();//Clearing pointers, not freeing memory</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /> b.<br /><span style="font-family:courier new;"><span><span style="background-color: rgb(255, 242, 204);"> <span style="color:#0b5394;"> { </span></span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> map<int, char*> myMap;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> myMap[1] = new char(10);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> myMap.clear();//Clearing pointers, not freeing memory</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><br /> Solution will be traverse the map or vector or any such container and free the allocated memory individually and then clear the container.<br /><br />5. Sometimes it happens that a function allocates and returns the pointer to the calling code, but the calling code does not free the pointer.<br /> a.<br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> void fun(char* * ch)</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> *ch = new char(10);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /> b.<br /><span style="color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> <span style="font-family:courier new;"> char* fun()</span></span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> char *ch = new char(10);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> return ch;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /> c.<br /> There are APIs provided by libraries, that provide documentation about the handling of the pointer deletion.<br /><br /> Solution is to free the pointer responsibly and follow the API documentation.<br /><br />6. Forgetting to delete the pointer member variable in the destructor.<br /><span style="color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> <span style="font-family:courier new;"> class A</span></span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> char* ch;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> public:</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> A()</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> ch = new char(100);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> ~A()</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> //ch not deleted, memory leak</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> //delete ch;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><br /> Solution is to free the memory allocated as follows in the destructor<br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> ~A()</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> <b> if(ch != NULL)</b></span></span></span><b style="color: rgb(11, 83, 148);font-family:Courier New;"><br /><span><span style="background-color: rgb(255, 242, 204);"> {</span></span><br /><span><span style="background-color: rgb(255, 242, 204);"> delete ch;</span></span><br /><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></b><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><br />7. Mistakenly Overwriting the pointer.This can happen in following possible ways.<br /> a.<br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> char *ch = new char(100);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> char *ch1 = new char(100);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> ch1 = ch;// We lost memory allocated by ch1 </span></span></span><br /><br /> b.<br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> vector<char*> list;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> list.push_back(new char(10));</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> list[0] = new char(100);//Overwriting the first pointer</span></span></span><br /><br /> c.<br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> map<int, char*> myMap;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> myMap[1] = new char(10);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> myMap[1] = new char(100);//Overwriting the pointer with key 1</span></span></span><br /><br /> The solution will be to be careful while assigning a pointer to other. It is advised to make sure that the pointer on left side is NULL.<br /><span><span style="background-color: rgb(255, 242, 204);"> </span></span><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);">{</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> char *ch = new char(100);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> char *ch1 = new char(200);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> <b> if(ch == NULL)</b></span></span></span><b style="background-color: rgb(255, 242, 204); color: rgb(11, 83, 148); font-family: Courier New;"><br /> {<br /> ch = ch1;<br /> }</b><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><br /> This is applicable to vectors/list/Maps or such STL containers also.<br /><br />8. In c++ deleting a pointer of base class type when its pointing to a child class object, can cause memory leak if the base class destructor is not declared virtual.<br /><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> class A</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> public:</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> A()</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> { }</span></span></span><br /><span><span style="background-color: rgb(255, 242, 204);"> </span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> ~A()</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> cout << "Destroy A" << endl;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> };</span></span></span><br /><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> class B : public A</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> private:</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> char *ch;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> public:</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> B()</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> ch = new char(100);</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> ~B()</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> delete ch;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> cout << "Destroy B" << endl;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> };</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> int main()</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> A* a = new B();</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> delete a;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><br /> The Solution is to declare the ~A() as virtual as follows<br /><b style="background-color: rgb(255, 242, 204); color: rgb(11, 83, 148); font-family: Courier New;"> virtual ~A(){ }</b><br /> This makes sure that the destructor of child class is called before the parent class destructor.<br /><br />So, this is the list that I could come up with. Some of the examples are very trivial, but in a real time code the same scenario occurs in a different way, may be spanning some functions/classes of files. So, its quite difficult to find some of those.<br /><br />But following of few prgramming practices can minimize the effort to debug the memory leaks.One of them is make sure pointer is NULL before allocating and explicitly assign that pointer to NULL after calling delete. The second one is because delete does not assign the pointer NULL after freeing the allocated memory.<br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> if(pointer == NULL)</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> //Allocate memory using the pointer</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> delete pointer;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> pointer = NULL;</span></span></span><br /><br />Another thing is to keep in mind while deleting a pointer is to check if its not NULL of already freed.This should be done to get rid of any double-delete issues.<br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> if(pointer != NULL)</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> {</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> delete pointer;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> pointer = NULL;</span></span></span><br /><span style="font-family:courier new;color:#0b5394;"><span><span style="background-color: rgb(255, 242, 204);"> }</span></span></span><br /><br />Wishing all of you programmers a best of luck in making your code Mem Leak free. Please provide comments or suggestions if any. Or please add any scenario if I have missed. Hope you will be able to spend time on facebook or orkut as much as possible but make sure your manager is not aware that you are freeeeee.<br /><br />cya !!!sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-69369912589472367812010-01-20T09:36:00.000-08:002010-01-21T01:03:11.399-08:00Object Serializing in C++<p>Why till date we do not have any standard way serialize/deserialize C++ like Java.This is some of the disadvantages C++ have apart from Reflection(as in Java).So I had to find a crude way of doing that which most of you will not like.</p><p><span style="color: rgb(204, 0, 0);">Part Zero
<br /></span></p><p><span style="color: rgb(0, 0, 0);">This technique is a cliche</span> in C++ object serializing topic.Implement a seialize() function in the class with putting of attributes to the ostringstream.For deserializing read from istringstream and update the variables.</p><p>Example:
<br />
<br /></p><p><span style="color: rgb(255, 0, 0);">Part1</span>
<br /></p><p>memcpy is faster than istringstream read or ostringstream write.
<br />Why dont we have functions written on top of memcpy to provide the interface to serialize/deserialize various variables?
<br />say serializeInt(int i) or serializeBool(bool b) .. etc as follows.
<br /><em style="color: rgb(0, 0, 153);">string serializeInt(int i)</em>
<br /><em style="color: rgb(0, 0, 153);">{</em>
<br /><em style="color: rgb(0, 0, 153);">string p = "1111";</em>
<br /><em style="color: rgb(0, 0, 153);">char* ch = (char*)p.c_str();</em>
<br /><em style="color: rgb(0, 0, 153);">memcpy(ch, &i, sizeof( i ));</em>
<br /><em style="color: rgb(0, 0, 153);">string temp;</em>
<br /><em style="color: rgb(0, 0, 153);">temp.assign(ch, sizeof( i ));</em>
<br /><em style="color: rgb(0, 0, 153);">return temp;</em>
<br /><em style="color: rgb(0, 0, 153);">}</em></p> <p>So we use it straight away as </p> <p style="color: rgb(0, 0, 153);"><em>string serialize()</em>
<br /><em>{</em>
<br />_string str;
<br /><em>str.append(serializeInt(10));</em>
<br /><em>str.append(serializeBool(true);</em>
<br />.....and so on
<br /><em>}</em></p> <h5><a name="SimplifiedSerializeandDeserializeInterface-Deserializeabitcrookedandlookslikethis"></a>Deserialize a bit crooked and looks like this</h5> <p style="color: rgb(0, 0, 153);"><em>int deserializeInt(char** ch)</em>
<br /><em>{</em>
<br /><em>int num;</em>
<br /><em>memcpy(&num, *ch, sizeof(num));</em>
<br /><em>*ch += sizeof(num);</em>
<br /><em>return num;</em>
<br /><em>}</em></p> <p> So we need to pass the address of string to the deserialize function which will after getting the value modify it to the next item to be deserialized.
<br />So, the deserialize function of the classes look as follows.
<br /><em style="color: rgb(0, 0, 153);">void deserialize(string str)</em>
<br /><em style="color: rgb(0, 0, 153);">{</em>
<br /><em style="color: rgb(0, 0, 153);">char* ch = (char*)str.c_str();</em>
<br /><em style="color: rgb(0, 0, 153);">int num = deserializeInt(&ch);</em>
<br /><em style="color: rgb(0, 0, 153);">bool f = deserializeBool(&ch);</em>
<br /><em style="color: rgb(0, 0, 153);">string str1 = deserializeString(&ch);</em>
<br /><em style="color: rgb(0, 0, 153);">}</em></p><p><span style="color: rgb(255, 0, 0);">Part2</span></p><p><span style="color: rgb(255, 0, 0);"><span style="color: rgb(0, 0, 0);">Now we need to come up with one class that can handle serializing of any class.Lets name it Serializer.Serializer needs to know the type and value of the attribute that it has to serialize.So, it has a multimap as a member variable. Why Multimap and not Map, because a class can have two integers as attributes or more than one float attribute.Those cannot be entered in map as the key i.e type is not unique. Serializer class also provides a function to insert the type and value to the map.</span></span></p><p><span style="color: rgb(255, 0, 0);"><span style="color: rgb(0, 0, 0);">Now how should the value be entered ??As we are using the multimap we cannot have different types</span> <span style="color: rgb(0, 0, 0);">for the value. So, we define the map with a pointer to char as multimap<string,>. Following is what the class looks like</string,></span></span></p><p style="font-style: italic; color: rgb(0, 0, 153);">class Serializer
<br />{
<br />private:
<br /> multimap<string,char> m_typeMap;
<br />public:
<br /> void insert(string type, char* ptr)
<br /> {
<br /> m_typeMap.insert(pair<string,char*>(type, ptr));
<br /> }
<br />
<br /> string serialize()
<br /> {
<br />ostringstream str;
<br />char *ptr = str.c_str();
<br /> for(multimap<string,char*>::iterator iter = m_typeMap.begin(); iter != m_typeMap.end(); iter++)
<br /> {
<br /> if(iter->first == "int")
<br /> {
<br />int val = *(int*)iter->second;
<br />str.write(reinterpret_cast<char*>(&val),sizeof(val));
<br />}
<br />}
<br />}
<br /></p><p style="font-style: italic; color: rgb(0, 0, 153);"><string,><string,><string,>void deserialize(string str)
<br />{
<br />//Deserialize and assign the value to the address Here
<br />istringstream str(str);
<br /></string,></string,></string,>for(multimap<string,char*>::iterator iter = m_typeMap.begin(); iter != m_typeMap.end(); iter++)
<br /> {
<br />if(iter->first == "int")
<br /> {
<br /><string,><string,><string,>int val;
<br />str.read(reinterpret_cast<char*>(&val), sizeof(val));
<br /></string,></string,></string,>*(int*)iter->second = val
<br /><string,><string,><string,>}
<br />}
<br />}
<br /></string,></string,></string,></p><p style="font-style: italic; color: rgb(0, 0, 153);"><string,><string,><string,>};</string,></string,></string,></p><p style="color: rgb(0, 0, 153);"><span style="color: rgb(0, 0, 0);">Now the Serializer class is having code to serialize integer data type only. This can be extended to support any data type.Now lets see how can we use this class.</span></p><p style="color: rgb(0, 0, 153);"><span style="color: rgb(0, 0, 0);">Following is the class A, which needs to be serialized.We inherit this class from our Serializer class and register the variables that we want to serialize.</span></p><p style="color: rgb(0, 0, 153);"><span style="color: rgb(0, 0, 0);"><span style="font-style: italic; color: rgb(0, 0, 153);">class A : public Serializer</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);">{</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> private:</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> int i;</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> public:</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> A()</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> {</span>
<br /><span style="color: rgb(0, 0, 153); font-style: italic;"> <span style="font-weight: bold;"> insert("int", (char*)&i); </span> </span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> }</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> int getVal()</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> {</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> return i;</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> }</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> void setVal(int j)</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> {</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> i = j;</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);"> }</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);">};</span>
<br /></span></p><p style="color: rgb(0, 0, 153);"><span style="color: rgb(0, 0, 0);">Now lets use this class in our main executable.</span></p><p style="color: rgb(0, 0, 153);"><span style="color: rgb(0, 0, 0);"><span style="font-style: italic; color: rgb(0, 0, 153);">int main()</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);">{</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);">A obj;</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);">obj.setVal(10);</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);">string str = obj.serialize();</span>
<br />
<br /><span style="font-style: italic; color: rgb(0, 0, 153);">B obj1;</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);">obj1.deserialize();</span>
<br /><span style="font-style: italic; color: rgb(0, 0, 153);">cout<<obj1.getValue();}</span></span></span></p><p><span style="color: rgb(255, 0, 0);"><span style="color: rgb(0, 0, 0);">Hope this helps in making serialize/deserialize of c++ objects in a more generic way instead of putting the serialize/deserialize functions in each n every class.
<br />
<br />More solutions are welcome.<b><b><b>
<br /></b></b></b></span></span></p>sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-39851743462639975082009-12-16T20:15:00.001-08:002009-12-16T20:15:23.929-08:00sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0tag:blogger.com,1999:blog-4740106230702548497.post-42556409648441473422009-12-16T19:59:00.000-08:002009-12-25T10:47:30.404-08:00Winning Cygwin ....<span style="color: rgb(153, 0, 0);font-family:arial;" >During my initial days at Wipro, I used to see lots of people in my team using Cygwin. I was a fresher back then in IT industry and also I spent most of the time during my engineering working on our friendly easy to use, Windows. So I felt this cygwin stuff is only for "advanced programmers". Being a fresher most of the times I was learning things fast, but only the things that are taught, but was a lousy self learner. On top of that So, I just stayed away from that.But still I had it installed in my system to open few Motif applications strictly for project reasons and no personal interests. Putty was my best friend then, still now it is. Two years passed by and my friendship with putty grew stronger and stronger. Now its just part n parcel of my life.</span><br /><br /><br /><span style="color: rgb(153, 0, 0);font-family:arial;" >But after Wipro, suddenly my inner Comp Engg woke up .. ya it took a really long time abt 2 years. It made me do experiments, ask questions(most of them silly) and li'l bit of careless attitude. After joining NSN, I got some platform to continue my experiments. And I got reminded of my days in wipro when I used to see my colleagues working on cygwin and me on dull putty. And thats how the conquest starts ...</span><br /><br /><span style="color: rgb(153, 0, 0);font-family:arial;" >To my luck I found cygwin already installed on my desktop. Cygwin comes with a default window manager i.e twm .Its very light but not attractive at all, you will start hating cygwin once you see that. Then I gave a search for various window managers for cygwin. I came across this link .</span><br /><a href="http://xwinman.org/others.php"><span style="color: rgb(153, 0, 0);font-family:arial;" >http://xwinman.org/others.php</span></a><br /><span style="color: rgb(153, 0, 0);font-family:arial;" >It has this big list of Windowmanagers that one can try out. From my faint memory of Wipro, I recollected that it was WindowMaker that everybody was using. That was it , I went to <a href="http://www.windowmaker.info/">http://www.windowmaker.info/</a> and downloaded the latest source(gzip). Cygwin also by default has another window manager, xwin. So, I was using it until I downloaded the source of WindowMaker.I was careful as it was the first time I was extracting a source and trying to build it.I extracted the source code and was ready to build it. But everyting I give "./configure" it failed giving an error "as not found" so I thought c++/g++ is not installed properly. So, wht I do is I download cygwin again and install it again, and then I found some people do not have admin rights to install any softwares. And supervisors are skeptic to provide the privileges to new joinees as though they will blow up the organization using admin rights. Whatever, I just suppressed my conquest for more resources(admin rights).</span><br /><br /><span style="color: rgb(153, 0, 0);font-family:arial;" >Eight months passed and I was still enjoying putty. Then on a lucky day my Dell360 crashed. Actually it was expected to crash as another colleague of mine had already faced it. And the IT guy is asking me "what the hell were you doing with the system?? " :-). And then I got even more luckier when that backup system that I got also crashed, and there were no backup desktops for me. Finally my manager had to request for a laptop. Ya, this is how I got my laptop. And the best part is all laptops have need to have admin privileges.</span><br /><br /><br /><span style="color: rgb(153, 0, 0);font-family:arial;" >Then bammm I installed cygwin will all the packages, necessary unnecessary. Then started the installation of Windowmaker. As I had the source I configured as usual and after hit "make" it went nicely for some time, then suddenly I see a scary compilation error. Though I can solve compilation error in code written by me but I had never faced compilation error in such kind of 3rd party code. Ok, the error said something like "undefined reference to __Xsetlocale" . Ok without wasting any time I copied the error and put in google with reference to Windowmaker. And to my luck there was thi sguy who had also faced the same problem and solved it .Its just a matter of changing the inclusion X11/Xlocale.h to locale.h in the files that were reporting errors.Cooool.</span><br /><br /><span style="color: rgb(153, 0, 0);font-family:arial;" >Now next step is to install it, so I gave "make install", so it installed the required libraries and binaries in required locations. I went ahead to make it start whenever I start cygwin. For that I had to edit /etc/X11/xinit/xinitrc file and add "wmaker&" at the end of file. Alternatively startxwin.bat file can be edited, but for me because of some paranormal forces it was not working out, so I made peace with it. So, I am proud to present my cygwin desktop running WindowMaker, and its just the beginning.</span><br /><a style="font-family: arial; color: rgb(153, 0, 0);" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh8GvXJcpwe7krGlmU7ndDwGFXxoUhHUoP0rD5KvzMLHSZ2-hxh6XrxQElr7cuDquRwVmN8dLLX4bsXWn13h4zEITEvUYT1lErwkkCaYWfowhFN_h6MJKw7QvqaI8h8CNGHVERagtlqBXl0/s1600-h/cyg_desk.JPG"><img style="cursor: pointer; width: 320px; height: 200px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh8GvXJcpwe7krGlmU7ndDwGFXxoUhHUoP0rD5KvzMLHSZ2-hxh6XrxQElr7cuDquRwVmN8dLLX4bsXWn13h4zEITEvUYT1lErwkkCaYWfowhFN_h6MJKw7QvqaI8h8CNGHVERagtlqBXl0/s320/cyg_desk.JPG" alt="" id="BLOGGER_PHOTO_ID_5419244469444048370" border="0" /></a>sanjivhttp://www.blogger.com/profile/14976403408079318033noreply@blogger.com0