#include <list>
#include <string>
#include <map>
#include <stdio.h>
#include <sys/stat.h>
#include <dirent.h>

class TraderCacheDir {
	list<string> contents;
public:
	TraderCacheDir()
	{
	}
	TraderCacheDir(const string &name)
	{
		add('N',name);
	}
	string name()
	{
		return get('N');
	}
	list<string> *enumerate(char c)
	{
		list<string> *result = new list<string>;
		list<string>::iterator ci;
		for(ci = contents.begin(); ci != contents.end(); ci++)
		{
			const string& s = *ci;
			if(s[0] == c)
				result->push_back(s.c_str()+1);
		}
		return result;
	}
	string get(char c)
	{
		list<string> *l = enumerate(c);
		assert(l->size() <= 1);

		string s = l->empty()?"":l->front();
		delete l;
		return s;
	}
	void set(char c, const string& entry)
	{
		clear(c);
		add(c,entry);
	}
	void add(char c, const string& entry)
	{
		contents.push_back(c+entry);
	}
	void clear(char c)
	{
		list<string>::iterator ci, ni;
		ci = contents.begin();
		while(ci != contents.end())
		{
			ni = ci; ++ni;

			const string& s = *ci;
			if(s[0] == c)
				contents.erase(ci);

			ci = ni;
		}
	}
	void remove(char c,const string &name)
	{
		list<string>::iterator ci, ni;
		ci = contents.begin();
		while(ci != contents.end())
		{
			ni = ci; ++ni;

			const string& s = *ci;
			if(s == (c+name))
				contents.erase(ci);

			ci = ni;
		}
	}
	void dump(FILE *out)
	{
		list<string>::iterator ci;
		for(ci = contents.begin(); ci != contents.end(); ci++)
		{
			const string& s = *ci;
			fprintf(out,"%s\n",s.c_str());
		}
	}

	string parent()
	{
		const string& n = name();
		int i = n.rfind("/",n.size());     
		return n.substr( 0, i );
	}

	string filename()
	{
		const string& n = name();
		int i = n.rfind("/",n.size());     
		return n.substr( i+1, n.size()-(i+1) );
	}
};

int changed = 0;
int cached = 0;

class TraderCache {
protected:
	map<string, TraderCacheDir*> contents;
	map<pair<int,int>, bool> inodesDone;
 	bool dirty;

public:
	void clear()
	{
		dirty = false;

		map<string,TraderCacheDir *>::iterator i;
		for(i = contents.begin(); i != contents.end(); i++)
		{
			TraderCacheDir *d = i->second;
			if(d) delete d;
		}
		contents.clear();
	}

	void read(const string& name)
	{
		clear();

		FILE *cache = fopen(name.c_str(),"r");
		if(!cache) return;

		/*
		 * if cache couldn't be read, or wasn't written completely,
		 * we will not rely on it (we see consistency via a +eof as last line)
		 */
		bool consistent = false;

		TraderCacheDir *dir = new TraderCacheDir();
		char buffer[1024];
		while(fgets(buffer,1024,cache) != 0)
		{
			if(buffer[0])
				buffer[strlen(buffer)-1] = 0;

			if(buffer[0] == '*')
			{
				if(dir->name() != "")
				{
					contents[dir->name()] = dir;
					dir = new TraderCacheDir();
				}
			}
			else if(buffer[0] == '+')
			{
				if(strcmp(buffer,"+eof") == 0)
					consistent = true;
			}
			else
			{
				dir->add(buffer[0], &buffer[1]);
			}
		}
		delete dir;

		if(!consistent)
			clear();

		fclose(cache);
	}

	void write(const string& name)
	{
		if(!dirty)
			return;
		dirty = false;

		FILE *cache = fopen(name.c_str(),"w");
		if(!cache) return;

		map<string,TraderCacheDir *>::iterator i;
		for(i = contents.begin(); i != contents.end(); i++)
		{
			TraderCacheDir *d = i->second;

			if(d && d->get('R') != "")
			{
				d->clear('R');
				d->dump(cache);
				fprintf(cache,"*\n");
			}
		}
		fprintf(cache,"+eof\n");
		fclose(cache);
	}

	void check(const string &name, bool first = true)
	{
		/* create a cache entry for the directory */
		TraderCacheDir *d = contents[name];

		if(d == 0)
		{
			d = new TraderCacheDir(name);
			contents[name] = d;
		}

		struct stat st;
		stat(name.c_str(),&st);

		/*
		 * check if we have already seen this, if yes, remove - this is against
		 * symlinks which backlink, so that we would scan the same stuff over
		 * and over again
		 */

		bool& done = inodesDone[make_pair(st.st_dev, st.st_ino)];
		bool remove = done;
		if(!done) done = true;

		/* needs to be updated? */
		time_t mtime = atol(d->get('T').c_str());
		if(st.st_mtime != mtime)
		{
			dirty = true;
			// printf("%s %d changed\n",d->name().c_str(),mtime);
			changed++;

			/* fill time */
			char mtime_buffer[100];
			sprintf(mtime_buffer,"%d",st.st_mtime);
			d->set('T',mtime_buffer);

			/* fill class */
			if(S_ISDIR(st.st_mode))
			{
				d->set('C',"dir");
				if(strstr(d->filename().c_str(),".") != 0
				|| strstr(d->filename().c_str(),"-") != 0
				|| strstr(d->filename().c_str(),":") != 0)
					remove = true;
			}
			else if(S_ISREG(st.st_mode))
			{
				d->set('C',"file");
				if(strstr(d->filename().c_str(),"mcop") == 0)
					remove = true;
			}
			else remove = true;

			d->clear('E');

			if(S_ISDIR(st.st_mode))
			{
				DIR *dir = opendir(name.c_str());
				if(dir)
				{
					struct dirent *de;
					while((de = readdir(dir)) != 0)
					{
						if(de->d_name[0] != '.')
							d->add('E', de->d_name);
					}
				}
				closedir(dir);
			}
		}
		else
		{
			cached++;
			//printf("%s cached\n",d->name().c_str());
		}
		
		if(remove && !first)
		{
			TraderCacheDir *parent = contents[d->parent()];
			if(parent)
				parent->remove('E',d->filename());
			return;
		}

		d->set('R',"reached");		// this will lead to saving the entry

		/* scan subdirectories */
		list<string> *entries = d->enumerate('E');
		list<string>::iterator ei;

		for(ei = entries->begin(); ei != entries->end(); ei++)
			check(name + "/" + *ei, false);
		delete entries;
	}
};

void main(int argc, char **argv)
{
	TraderCache c;

	c.read("cache");
	c.check((argc == 2)?argv[1]:"/usr/lib");
	c.write("cache");
	printf("%d entries, %d changed, %d cached\n", changed+cached, changed, cached);
}