/*

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

 * All rights reserved.

 * This component and the accompanying materials are made available

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

 * which accompanies this distribution, and is available

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

 *

 * Initial Contributors:

 * Nokia Corporation - initial contribution.

 *

 * Contributors:

 *

 * Description: 

 *

 */

package com.nokia.carbide.cpp.internal.pi.resolvers;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.Comparator;

import java.util.Hashtable;

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

import com.nokia.carbide.cpp.internal.pi.model.Function;

import com.nokia.carbide.cpp.internal.pi.model.FunctionResolver;

// re-implement SymbolFileParser for supporting 

// cached resolver with ROFS symbols

public abstract class CachedFunctionResolver implements FunctionResolver {

	protected SymbolFileDllItem[] dllList = null;

	// cache

	private int cacheSize = 0;

	private long cacheAddressTable[] = new long[cacheSize];

	private long mostPopularCache[] = new long[cacheSize];

	private SymbolFileFunctionItem[] cacheOrderTable = new SymbolFileFunctionItem[cacheSize];

	private SymbolFileFunctionItem[] mostPopularCacheTable = new SymbolFileFunctionItem[cacheSize];

	//private int mostPopularHitCount[] = new int[cacheSize];

	private int mostPopularTableIndex = 0;

	private int cacheIndex = 0;

	//private int cacheFoundPopular = 0;

	//private int cacheFound = 0;

	//private int cacheNotFound = 0;

	// whether the resolver has enough information to resolve anything

	protected boolean ableToResolve = false;

	private Hashtable<String,Function> knownFunctions = new Hashtable<String,Function>();

	private Hashtable<String,Binary> knownBinaries = new Hashtable<String,Binary>();

	protected static class SymbolFileFunctionItem

	{

		public String name;

		public long address;

	    public long length;

	    public SymbolFileDllItem dll;

	    public SymbolFileFunctionItem(String name, long address, long length, SymbolFileDllItem dll)

	    {

	    	this.name = name;

	    	this.length = length;

	    	this.address = address;

	    	this.dll = dll;

	    }

	}

	protected static class SymbolFileDllItem

	{

		public String name;

		public long start;

	    public long end;

	    public ArrayList<SymbolFileFunctionItem> data;

	    public boolean uninitialised;

	    public SymbolFileDllItem()

	    {

	      start = 0;

	      end = 0;

	      name = null;

	      data = new ArrayList<SymbolFileFunctionItem>();

	      uninitialised = true;

	    }

	}

	// must implement some way to form a DLL list e.g. read rom/rofs symbol file, read obyfile

	public abstract void parseAndProcessSymbolFile(java.io.File symbolFile);

	public void addAllToDllList(Collection<SymbolFileDllItem> list) {

		// if the dll array is empty, create an array based on the input list

		if (dllList == null) {

			dllList = new SymbolFileDllItem[list.size()];

			dllList = list.toArray(dllList);

		} else {

			// add the input list to the existing dll array

			SymbolFileDllItem[] oldList = dllList;

			Object[] objects = list.toArray();

			dllList = new SymbolFileDllItem[dllList.length + list.size()];

			int i = 0;

			for (int j = 0; j < oldList.length; j++)

				dllList[i++] = oldList[j];

			for (int j = 0; j < list.size(); j++)

				dllList[i++] = (SymbolFileDllItem) objects[j];

		}

		// sort the dll list

		Arrays.sort(dllList, new Comparator<Object>() {

			public int compare(Object arg0, Object arg1)

			{

				return (int) (((SymbolFileDllItem)arg0).start - ((SymbolFileDllItem)arg1).start);

			}

		});	

	}

	public void clearDllList()

	{

		dllList = null;

	}

	public CachedFunctionResolver()

	{

		this.clearDllList();

		this.initializeCache(250);

	}

	public Binary findBinaryForAddress(long address) {

	  	SymbolFileDllItem item = this.getDllItemForAddress(address);

	  	if (item != null)

	  	{

	  		Binary b = this.knownBinaries.get(item.name);

	  		if (b == null) {

		  		b = new Binary(item.name);

		  		b.length = (int)(item.end-item.start);

		  		b.offsetToCodeStart = 0;

		  		b.startAddress = item.start;

				this.knownBinaries.put(item.name, b);

	  		}

	  		return b;

	  	}

	  	else

	  		return null;

//	  	{

//	  		String bName = "Binary at 0x"+Long.toHexString(address)+" not found;

//

//	  		Binary b = this.knownBinaries.get(bName);

//	  		

//	  		if (b == null) {

//		  		b = new Binary(bName);

//		  		b.length = 0;

//		  		b.offsetToCodeStart = 0;

//		  		b.startAddress = address;

//				this.knownBinaries.put(bName, b);

//			}

//	  		return b;

//	  	}

	}

	public String findBinaryNameForAddress(long address) {

	    SymbolFileDllItem foundDllItem = this.getDllItemForAddress(address);

	    if (foundDllItem != null)

	    	return foundDllItem.name;

	    else

	    	return Messages.getString("CachedFunctionResolver.dllForAddress")+Long.toHexString(address)+Messages.getString("CachedFunctionResolver.notFound");   //$NON-NLS-1$ //$NON-NLS-2$

	}

	public Function findFunctionForAddress(long address) {

	  	SymbolFileFunctionItem item = this.getFunctionItemForAddress(address);

	  	if (item != null)

	  	{

	  		String search = item.name + item.dll.name;

	 		Function f = this.knownFunctions.get(search);

	  		if (f == null) {

		  		f = new Function(item.name,new Long(item.address),item.dll.name);

		  		f.offsetFromBinaryStart = item.address-item.dll.start;

		  		f.length = item.length;

		  		this.knownFunctions.put(search, f);

	  		}

	  		return f;

	  	}

	  	else

	  	{

	//System.out.println(Long.toHexString(address));

	  		SymbolFileDllItem dllItem = this.getDllItemForAddress(address);

	  		if (dllItem != null)

	  		{

	  			String fName = Messages.getString("CachedFunctionResolver.functionNotFound1")+Long.toHexString(address)+Messages.getString("CachedFunctionResolver.functionNotFound2"); //$NON-NLS-1$ //$NON-NLS-2$

	  			Function f = this.knownFunctions.get(fName);

	  	  		if (f == null ) {

	  	  			f = new Function(fName, new Long(dllItem.start), dllItem.name);

		  			f.offsetFromBinaryStart = address-dllItem.start;

		  			f.length = 0;

		  			this.knownFunctions.put(fName, f);

	  	  		}

	  	  		return f;

	  		}

	  		else

	  			return null;

//	  		{

//	  			String fName = Messages.getString("CachedFunctionResolver.functionNotFound1")+Long.toHexString(address)+Messages.getString("CachedFunctionResolver.functionNotFound2"); //$NON-NLS-1$ //$NON-NLS-2$

//	  			

//	  			Function f = this.knownFunctions.get(fName);

//

//	  	  		if (f == null ) {

//	  	  			f = new Function(fName, new Long(address),

//	  	  							 "Binary at 0x" + 

//									 Long.toHexString(address)+" not found");

//	  	  			f.offsetFromBinaryStart = 0;

//	  	  			this.knownFunctions.put(fName, f);

//	  	  		}

//

//	  			return f;

//	  		}

	  	}

	}

	public String findFunctionNameForAddress(long address) {

	  	SymbolFileFunctionItem item = this.getFunctionItemForAddress(address);

	  	if (item != null)

	  	{

	  		return item.name;

	  	}

	  	else

	  	{

	  		return Messages.getString("CachedFunctionResolver.functionForAddress")+Long.toHexString(address)+Messages.getString("CachedFunctionResolver.notFound");   //$NON-NLS-1$ //$NON-NLS-2$

	  	}

	}

	public String getResolverName() {

		return Messages.getString("CachedFunctionResolver.symbol");  //$NON-NLS-1$

	}

	public String getResolverString() {

	  	return Messages.getString("CachedFunctionResolver.symbolFile");  //$NON-NLS-1$

	}

	public SymbolFileDllItem getDllItemForAddress(long address)

	{

		if (dllList == null)

			return null;

		for (int i=0; i < this.dllList.length; i++)

		{

			SymbolFileDllItem dllItem = this.dllList[i];

			if (address >= dllItem.start && address < dllItem.end)

			{

				return dllItem;

			}

		}

		return null;

	}

	private void initializeCache(int size)

	{

	    cacheSize = size;

	    cacheAddressTable = new long[cacheSize];

	    mostPopularCache = new long[cacheSize];

	    cacheOrderTable = new SymbolFileFunctionItem[cacheSize];

	    mostPopularCacheTable = new SymbolFileFunctionItem[cacheSize];

//	    mostPopularHitCount = new int[cacheSize];

	    mostPopularTableIndex = 0;

	    for (int i=0;i<cacheSize;i++)

	    {

	      cacheAddressTable[i] = 0;

	      mostPopularCache[i] = 0;

	      cacheOrderTable[i] = null;

	      mostPopularCacheTable[i] = null;

//	      mostPopularHitCount[i] = 0;

	    }

	}

	private SymbolFileFunctionItem getFunctionItemForAddress(long address)

	{  	

		SymbolFileFunctionItem cached = findFromCache(address);

	    if (cached != null) return cached;

	    SymbolFileDllItem foundDllItem = null;

	    if (this.dllList != null)

	    	for (int i=0; i < this.dllList.length; i++)

		    {

		    	SymbolFileDllItem dllItem = this.dllList[i];

		    	if (address >= dllItem.start && address < dllItem.end)

		    	{

		    		foundDllItem = dllItem;

		    		break;

		    	}

		    }

	    if (foundDllItem != null)

	    {

	      int listSize = foundDllItem.data.size();

	      SymbolFileFunctionItem functionItem;

	      for (int i = 0; i + 1 < listSize; i++)

	      {

	        functionItem = (SymbolFileFunctionItem)foundDllItem.data.get(i);

	        if (address >= functionItem.address && address < functionItem.address+functionItem.length)

	        {

	            addToCache(functionItem,address);

	            return functionItem;

	        }

	      }

	      // if last item is an entry for a static function area, ignore it

	      functionItem = (SymbolFileFunctionItem)foundDllItem.data.get(listSize - 1);

	      if (!functionItem.name.startsWith(Messages.getString("CachedFunctionResolver.possibleStaticFunction1"))) {	//$NON-NLS-1$

	          addToCache(functionItem,address);

	          return functionItem;

	      }

	    }

	    return null;

	}

	  private SymbolFileFunctionItem findFromCache(long address)

	  {

	    SymbolFileFunctionItem item = null;

	    item = findFromMostPopular(address);

	    if (item!=null) return item;

	    for (int i=0;i<cacheSize;i++)

	    {

	      if (cacheAddressTable[i] == address)

	      {

	        item = cacheOrderTable[i];

	        //System.out.println("Found from cache,adding to most popular");

//	        cacheFound++;

	        addToMostPopular(item,address);

	        break;

	      }

	    }

//	    cacheNotFound++;

	    //if (item == null) System.out.println("Not found from the cache!!");

	    return item;

	  }

	  private void addToCache(SymbolFileFunctionItem item,long address)

	  {

	    if (cacheSize == 0) return;

	    cacheOrderTable[cacheIndex] = item;

	    cacheAddressTable[cacheIndex] = address;

	    cacheIndex++;

	    if (cacheIndex == cacheSize) cacheIndex = 0;

	  }

		/* internal test function : comment out so code coverage looks

		 * good quantitatively

	  public void printMostPopularFromCache(int amountToPrint)

	  {

	    if (amountToPrint > cacheSize) amountToPrint = cacheSize;

	    System.out.println(Messages.getString("CachedFunctionResolver.mostPopularFromCache"));  //$NON-NLS-1$

	    for (int i=0;i<amountToPrint;i++)

	    {

	      SymbolFileFunctionItem item = mostPopularCacheTable[i];

	      if (item!=null) System.out.println(item.name+Messages.getString("CachedFunctionResolver.hits")+mostPopularHitCount[i]);  //$NON-NLS-1$

	      else break;

	    }

	    System.out.println(Messages.getString("CachedFunctionResolver.stats"));  //$NON-NLS-1$

	    int all = cacheFound+cacheFoundPopular+cacheNotFound;

	    System.out.println(Messages.getString("CachedFunctionResolver.foundFromMostPopularCache")+(cacheFoundPopular*100f/all)+Messages.getString("CachedFunctionResolver.percentageSign"));   //$NON-NLS-1$ //$NON-NLS-2$

	    System.out.println(Messages.getString("CachedFunctionResolver.foundFromCache")+(cacheFound*100f/all)+Messages.getString("CachedFunctionResolver.percentageSign"));   //$NON-NLS-1$ //$NON-NLS-2$

	    System.out.println(Messages.getString("CachedFunctionResolver.notFoundFromCache")+(cacheNotFound*100f/all)+Messages.getString("CachedFunctionResolver.percentageSign"));   //$NON-NLS-1$ //$NON-NLS-2$

	    System.out.println(Messages.getString("CachedFunctionResolver.end"));  //$NON-NLS-1$

	  }

	  *

	  */

	  private SymbolFileFunctionItem findFromMostPopular(long address)

	  {

	    SymbolFileFunctionItem item = null;

	    int i = 0;

	    // until there are a few entries in mostPopularCache[], it's faster not using a binary search

	    if (mostPopularCache[4] == 0) {

		    for (;i<cacheSize && mostPopularCache[i] > address;i++)

		    	;

	    } else {

			// use a binary search to find the item

			int lowerBound = 0;

			int upperBound = cacheSize - 1;

		    while (lowerBound <= upperBound) {

		    	i = (lowerBound + upperBound)/2;

				if (mostPopularCache[i] == address) {

					item = mostPopularCacheTable[i];

		            break;

				} else if (address > mostPopularCache[i])

		            upperBound = i - 1;

		        else

		        	lowerBound = i + 1;

		    }

//			// check binary search		    

//		    int j = 0;

//		    for (;j<cacheSize && mostPopularCache[j] > address;j++)

//		    	;

//		    if (j != i && mostPopularCache[j] > address)

//		    	System.out.println("binary search failed");

	    }

        if (mostPopularCache[i] == address)

        {

          item = mostPopularCacheTable[i];

//		  mostPopularHitCount[i]++;

//		  cacheFoundPopular++;

        }

	    return item;

	  }

	  private void addToMostPopular(SymbolFileFunctionItem item, long address)

	  {

	    // most popular cache is full, delete 20%

	    if (mostPopularTableIndex == cacheSize)

	    {

	       for (int i=(8*(cacheSize/10));i<cacheSize;i++)

	       {

	         mostPopularCache[i] = 0;

	         mostPopularCacheTable[i] = null;

//	         mostPopularHitCount[i] = 0;

	       }

	       mostPopularTableIndex = 8*(cacheSize/10);

	       //System.out.println("Clearing most popular ");

	    }

	    // add the new item in descending address order, so that we can bail out during search

	    int i = 0;

	    for ( ; i < mostPopularTableIndex && mostPopularCache[i] > address; i++)

	    	;

	    for (int j = mostPopularTableIndex; j > i; j--)

	    {

	        mostPopularCacheTable[j] = mostPopularCacheTable[j-1];

	        mostPopularCache[j] = mostPopularCache[j-1];

//	        mostPopularHitCount[j] = mostPopularHitCount[j-1];

	    }

    	mostPopularCache[i] = address;

    	mostPopularCacheTable[i] = item;

//    	mostPopularHitCount[i] = 2;

    	mostPopularTableIndex++;

	  }

	  public boolean canResolve() {

		  return this.ableToResolve;

	  }

}