1 /*

     2  * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). 

     3  * All rights reserved.

     4  * This component and the accompanying materials are made available

     5  * under the terms of the License "Eclipse Public License v1.0"

     6  * which accompanies this distribution, and is available

     7  * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8  *

     9  * Initial Contributors:

    10  * Nokia Corporation - initial contribution.

    11  *

    12  * Contributors:

    13  *

    14  * Description: 

    15  *

    16  */

    17 

    18 package com.nokia.carbide.cpp.pi.instr;

    19 

    20 import java.util.Enumeration;

    21 import java.util.Hashtable;

    22 import java.util.Vector;

    23 

    24 import com.nokia.carbide.cpp.internal.pi.model.Binary;

    25 

    26 

    27 public class UndecidedPool 

    28 {	

    29 	private Hashtable undecidedLocations;

    30 	private Vector unprocessed;

    31 	private AdvancedMemoryMap amm;

    32 	private Vector unDecided;

    33 	

    34 	public UndecidedPool(AdvancedMemoryMap amm)

    35 	{

    36 		this.amm = amm;

    37 		// keys will be the binary names, and values wile be

    38 		// their corresponding UndecidedLocation objects

    39 		this.undecidedLocations = new Hashtable();

    40 		

    41 		this.unprocessed = new Vector();

    42 		this.unDecided = new Vector();

    43 	}

    44 	

    45 	public Vector getUnprocessed()

    46 	{

    47 		return this.unprocessed;

    48 	}

    49 	

    50 	public void clearUnprocessed()

    51 	{

    52 		this.unprocessed = new Vector();

    53 	}

    54 	

    55 	public Vector getUndecided()

    56 	{

    57 		return this.unDecided;

    58 	}

    59 

    60 	public void insertSample(IttSample sample,int decisionBoundary)

    61 	{

    62 		if (!this.unDecided.contains(sample))

    63 			this.unDecided.add(sample);

    64 		

    65 		BinaryReaderResult brr = this.amm.getBinaryReader().findSequence(sample);

    66 		for (int i=0;i<brr.possibleBinaries.length;i++)

    67 		{

    68 			Binary possibleBinary = brr.possibleBinaries[i];

    69 			UndecidedLocation ul = 

    70 				(UndecidedLocation)undecidedLocations.get(possibleBinary.binaryName);

    71 			

    72 			if (ul != null)

    73 			{

    74 				ul.addSample(sample,possibleBinary.startAddress);

    75 			}

    76 			else

    77 			{

    78 				ul = new UndecidedLocation(possibleBinary); 

    79 				ul.addSample(sample,possibleBinary.startAddress);

    80 				this.undecidedLocations.put(possibleBinary.binaryName,ul);

    81 			}

    82 			

    83 			// the value of decisionBoundary has to be reduced in the future

    84 			// when no binaries can be resolved with the current value

    85 			if (ul.getDecidedAddress(decisionBoundary) != -1)

    86 			{

    87 			 	// location of the binary has been resolved

    88 				

    89 				// refresh the samples that belong to the decision

    90 				ul.refreshDecidedAndUndecidedSamples();

    91 				

    92 				// add all the samples that didn't fit to this binary, to

    93 				// the pool of unprocessed samples				

    94 				Vector undecided = ul.getUndecidedSamples();

    95 				// add only those samples that are not present in the undecided

    96 				// vector already

    97 				Enumeration unEnum = undecided.elements();

    98 				while(unEnum.hasMoreElements())

    99 				{

   100 					IttSample us = (IttSample)unEnum.nextElement();

   101 					if (!this.unprocessed.contains(us)) this.unprocessed.add(us);

   102 				}

   103 				

   104 				// then, pass the decision to the decidedPool

   105 				Vector decided = ul.getDecidedSamples();

   106 				this.amm.getDecidedPool().insertDecidedBinary(possibleBinary,decided);

   107 				

   108 				// then, remove the decided samples from all other possible binaries

   109 				Enumeration renum = decided.elements();

   110 				while(renum.hasMoreElements())

   111 				{

   112 					IttSample sampleToRemove = (IttSample)renum.nextElement();

   113 					this.removeSampleFromAllPossibleLocations(sampleToRemove);

   114 				}

   115 			}

   116 		}

   117 	}

   118 	

   119 	private void removeSampleFromAllPossibleLocations(IttSample sample)

   120 	{	

   121 		Enumeration renum = this.undecidedLocations.keys();

   122 		Vector removeList = new Vector();

   123 		

   124 		this.unDecided.remove(sample);

   125 		

   126 		while(renum.hasMoreElements())

   127 		{

   128 			String name = (String)renum.nextElement();

   129 			

   130 			UndecidedLocation ul = (UndecidedLocation)this.undecidedLocations.get(name);

   131 			ul.removeSample(sample);

   132 			

   133 			if (ul.samplesForLocations.size() == 0) removeList.add(name);

   134 		}

   135 		

   136 		if (removeList.size() > 0)

   137 		{

   138 			Enumeration enumer = removeList.elements();

   139 			while(enumer.hasMoreElements())

   140 			{

   141 				this.undecidedLocations.remove(enumer.nextElement());

   142 			}

   143 		}

   144 		

   145 		if (this.unprocessed.contains(sample))

   146 		{

   147 			this.unprocessed.remove(sample);

   148 		}

   149 	} 

   150 	

   151 	private static class UndecidedLocation

   152 	{

   153 		private Hashtable samplesForLocations;

   154 

   155 		private Binary binary;

   156 		

   157 		private int processedMostHits = 0;

   158 		private Long addressWithMostHits = null;

   159 		private Vector samplesWithMostHits = null;

   160 		

   161 		private boolean processedUndecided = false;

   162 		private Vector undecidedSamples = null;

   163 		private Vector decidedSamples = null; 

   164 		

   165 		public UndecidedLocation(Binary binary)

   166 		{

   167 			// key will be the address, and the value will be a

   168 			// vector with all samples that support that location 

   169 			this.samplesForLocations = new Hashtable();

   170 			this.binary = binary;

   171 		}

   172 		

   173 		public Binary getBinary()

   174 		{

   175 			return this.binary;

   176 		}

   177 		

   178 		public void addSample(IttSample sample,long startAddress)

   179 		{

   180 			// clear the flags so that the values will be recalculated if needed

   181 			this.processedMostHits = 0;

   182 			this.processedUndecided = false;

   183 			

   184 			Object o = this.samplesForLocations.get(new Long(startAddress));

   185 			

   186 			if (o != null)

   187 			{

   188 				// this location has already a vector associated with it

   189 				Vector sampleVec = (Vector)o;

   190 				

   191 				Enumeration sampleEnum = sampleVec.elements();

   192 				boolean isAlready = false;

   193 				

   194 				while(sampleEnum.hasMoreElements())

   195 				{

   196 					IttSample testSample = (IttSample)sampleEnum.nextElement();

   197 					if (testSample.programCounter == sample.programCounter && 

   198 							testSample.checksum == sample.checksum)

   199 						{

   200 							isAlready = true;

   201 							break;

   202 						}

   203 				}

   204 				// add the sample only if it is 

   205 				// different from the other samples

   206 				if (isAlready == false) 

   207 				{

   208 					//System.out.println("Added unique sample "+sample.programCounter+" to "+this.binary.binaryName);

   209 					sampleVec.add(sample);

   210 				}

   211 				else

   212 				{

   213 					//System.out.println("Discarded "+sample.programCounter+" to "+this.binary.binaryName);

   214 				}

   215 				

   216 			}

   217 			else

   218 			{

   219 				//System.out.println("Added unique sample "+sample.programCounter+" to "+this.binary.binaryName);

   220 				Vector sampleVec = new Vector();

   221 				sampleVec.add(sample);

   222 				samplesForLocations.put(new Long(startAddress),sampleVec);

   223 			}

   224 		}

   225 		

   226 		public void removeSample(IttSample sample)

   227 		{

   228 			// clear the flags so that the values will be recalculated if needed

   229 			this.processedMostHits = 0;

   230 			this.processedUndecided = false;

   231 

   232 			// remove this sample from all vectors, remove the vectors if they

   233 			// become empty

   234 			Enumeration enumer = this.samplesForLocations.keys();

   235 			Vector removeList = new Vector();

   236 			

   237 			while(enumer.hasMoreElements())

   238 			{

   239 				Long address = (Long)enumer.nextElement();

   240 				Vector v = (Vector)this.samplesForLocations.get(address);

   241 				

   242 				if (v.contains(sample)) 

   243 				{

   244 					v.remove(sample);

   245 					// do not remove the vector yet because

   246 					// it would mess the hashtable iteration

   247 					if (v.size() == 0) removeList.add(address);

   248 				}

   249 			}

   250 			

   251 			// finally, remove the vectors that 

   252 			// were emptied after removing the last sample

   253 			if (removeList.size() > 0) 

   254 			{

   255 				Enumeration renum = removeList.elements();

   256 				while(renum.hasMoreElements())

   257 				{

   258 					this.samplesForLocations.remove(renum.nextElement());

   259 				}

   260 			}

   261 		

   262 		}

   263 		

   264 		public long getDecidedAddress(int minSampleAmount)

   265 		{

   266 			if (minSampleAmount <= 0) return -1;

   267 			

   268 			if (this.processedMostHits == minSampleAmount)

   269 			{

   270 				// the function has been run with this value

   271 				return this.addressWithMostHits.longValue();

   272 			}

   273 			

   274 			Enumeration addresses = samplesForLocations.keys();

   275 			

   276 			int amountOfMaxValues = 0;

   277 			

   278 			while(addresses.hasMoreElements())

   279 			{

   280 				Long address = (Long)addresses.nextElement();

   281 				Vector samples = (Vector)samplesForLocations.get(address);

   282 				if (samples.size() >= minSampleAmount)

   283 				{

   284 					// there are at least minSampleAmount different samples

   285 					// that support this binary being in this place

   286 					if (samplesWithMostHits != null)

   287 					{

   288 						// there is already a value, check do we exceed it

   289 						if (samples.size() > samplesWithMostHits.size())

   290 						{

   291 							samplesWithMostHits = samples;

   292 							addressWithMostHits = address;

   293 							amountOfMaxValues = 1;

   294 						}

   295 						else if (samples.size() == samplesWithMostHits.size())

   296 						{

   297 							amountOfMaxValues++;

   298 						}

   299 					}

   300 					else

   301 					{

   302 						// there is no max value yet

   303 						samplesWithMostHits = samples;

   304 						addressWithMostHits = address;

   305 						amountOfMaxValues = 1;

   306 					}

   307 				}

   308 			}

   309 			

   310 			// this function does not need to be run again

   311 			// if the values do not change

   312 			this.processedMostHits = minSampleAmount;

   313 

   314 			// there are two or more max values

   315 			// or no max values at all

   316 			if (amountOfMaxValues != 1) return -1;

   317 				else return addressWithMostHits.longValue();

   318 		}

   319 		

   320 		public void refreshDecidedAndUndecidedSamples()

   321 		{

   322 			if (this.processedUndecided == true) return;

   323 			

   324 			this.undecidedSamples = new Vector();

   325 			this.decidedSamples = new Vector();

   326 			

   327 			Enumeration enumer = this.samplesForLocations.elements();

   328 			while(enumer.hasMoreElements())

   329 			{

   330 				Vector v = (Vector)enumer.nextElement();

   331 				

   332 				if (!v.equals(this.samplesWithMostHits))

   333 				{

   334 					// count all samples but the one with 

   335 					undecidedSamples.addAll(v);

   336 				}

   337 				else

   338 				{

   339 					// add the decided samples

   340 					this.decidedSamples.addAll(v);

   341 				}

   342 			}

   343 	

   344 			this.processedUndecided = true;

   345 		}

   346 		

   347 		public Vector getDecidedSamples()

   348 		{

   349 			// there is no value according to which the decision

   350 			// could base on

   351 			if (this.processedMostHits == 0) return new Vector();

   352 

   353 			this.refreshDecidedAndUndecidedSamples();

   354 			

   355 			return this.decidedSamples;

   356 		}

   357 		

   358 		public Vector getUndecidedSamples()

   359 		{

   360 			// there is no value according to which the decision

   361 			// could base on

   362 			if (this.processedMostHits == 0) return new Vector();

   363 

   364 			this.refreshDecidedAndUndecidedSamples();			

   365 			

   366 			return this.undecidedSamples;

   367 		}

   368 	}

   369 	

   370 }