// -*- c-basic-offset: 4; related-file-name: "../include/click/ino.hh" -*-
/*
 * ino.{cc,hh} -- inode numbers for Click file systems
 * Eddie Kohler
 *
 * Copyright (c) 2002 International Computer Science Institute
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software")
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file is
 * legally binding.
 */

#include <click/config.h>
#include <click/glue.hh>
#include <click/ino.hh>
#include <click/router.hh>
#if INO_DEBUG
# include <click/straccum.hh>
#endif
CLICK_DECLS

void
ClickIno::initialize()
{
    _x = 0;
    _nentries = _cap = 0;
    _router = 0;
    _generation = 0;
}

void
ClickIno::cleanup()
{
    for (int i = 0; i < _cap; i++)
	_x[i].name.~String();
    delete[] ((uint8_t *)_x);
    initialize();
}

int
ClickIno::grow(int min_size)
{
    if (_cap >= min_size)
	return 0;
    int new_cap = (_cap ? _cap : 128);
    while (new_cap < min_size)
	new_cap *= 2;
    // cheat on memory: bad me!
    Entry *nse = (Entry *)(new uint8_t[sizeof(Entry) * new_cap]);
    if (!nse)
	return -ENOMEM;
    memcpy(nse, _x, sizeof(Entry) * _cap);
    for (int i = _cap; i < new_cap; i++)
	new((void *)&nse[i]) String();
    delete[] ((uint8_t *)_x);
    _x = nse;
    _cap = new_cap;
    return 0;
}


static int
entry_compar(const void *v1, const void *v2)
{
    const ClickIno::Entry *a = reinterpret_cast<const ClickIno::Entry *>(v1);
    const ClickIno::Entry *b = reinterpret_cast<const ClickIno::Entry *>(v2);
    return String::compare(a->name, b->name);
}

int
ClickIno::true_prepare(Router *r, uint32_t generation)
{
    // config lock must be held!

    int nelem = (r ? r->nelements() : 0) + 1;
    if (grow(nelem) < 0)
	return -ENOMEM;

    // add sentinel entry
    _x[0].name = String();
    _x[0].elementno_plus1 = 0;
    _x[0].xindex = 0;
    _x[0].skip = 0;
    _x[0].flags = 0;
    _nentries = 1;

    // exit early if router is empty
    if (nelem == 1) {
	_generation = generation;
	_router = r;
	_x[0].flags = X_SUBDIR_CONFLICTS_CALCULATED;
	return 0;
    }

    // add entries for actual elements
    for (int i = 1; i < nelem; i++) {
	_x[i].name = r->ename(i - 1);
	_x[i].elementno_plus1 = i;
	_x[i].skip = 0;
	_x[i].flags = 0;
    }

    // sort _x
    click_qsort(&_x[1], nelem - 1, sizeof(Entry), entry_compar);

    // add new _x entries for intermediate directories
    int n = nelem;
    for (int i = 1; i < nelem; i++) {
	// make local copies of the names since we might resize _x
	String name = _x[i].name;
	String last_name = _x[i-1].name;
	int slash = name.find_right('/');
	// rely on '/' being less than any other valid name character in
	// ASCII. If the prefix of "last_name" matches the part of "name"
	// before a slash, then we know that "last_name" matches the whole
	// component (rather than a fake match like "a/b/cc" <-> "a/b/c/e").
	while (slash >= 0 && (last_name.length() < slash || memcmp(name.data(), last_name.data(), slash) != 0)) {
	    if (n >= _cap && grow(n + 1) < 0)
		return -ENOMEM;
	    _x[n].name = name.substring(0, slash);
	    _x[n].elementno_plus1 = n;
	    _x[n].skip = 0;
	    _x[n].flags = X_FAKE;
	    slash = _x[n].name.find_right('/');
	    n++;
	}
    }
 
    // resort _x if necessary
    if (n != nelem)
	click_qsort(&_x[1], n - 1, sizeof(Entry), entry_compar);

    // calculate 'skip'
    _x[0].skip = n - 1;
    for (int i = 1; i < n - 1; i++) {
	const String &name = _x[i].name;
	int length = name.length();
	int j = i + 1;
	while (j < n && _x[j].name.length() > length
	       && _x[j].name[length] == '/') {
	    assert(_x[j].name.substring(0, length) == name);
	    _x[i].skip++;
	    j++;
	}
    }

    // calculate 'xindex'
    for (int i = 1; i < n; i++)
	_x[_x[i].elementno_plus1].xindex = i;

    // done
    _nentries = n;
    _generation = generation;
    _router = r;
    return 0;
}


static int
string_compar(const void *v1, const void *v2)
{
    const String *a = reinterpret_cast<const String *>(v1);
    const String *b = reinterpret_cast<const String *>(v2);
    return String::compare(*a, *b);
}

void
ClickIno::calculate_handler_conflicts(int parent_elementno)
{
    // configuration lock must be held!
    
    // no conflicts if no router, no children, or this element is fake
    assert(parent_elementno >= -1 && parent_elementno < _nentries - 1);
    int parent_xindex = xindex(parent_elementno);
    if ((_x[parent_xindex].flags & (X_FAKE | X_SUBDIR_CONFLICTS_CALCULATED))
	|| _x[parent_xindex].skip == 0) {
	_x[parent_xindex].flags |= X_SUBDIR_CONFLICTS_CALCULATED;
	return;
    }

    // find the relevant handler indexes and names
    Vector<int> his;
    Router::element_hindexes(Router::element(_router, parent_elementno), his);
    Vector<String> names;
    for (int* hip = his.begin(); hip < his.end(); hip++) {
	const Handler* h = Router::handler(_router, *hip);
	if (h->visible())
	    names.push_back(h->name());
    }

    // sort names
    if (names.size())
	click_qsort(&names[0], names.size(), sizeof(String), string_compar);

    // run over the arrays, marking conflicts
    int xi = parent_xindex + 1;
    int next_xi = next_xindex(parent_elementno);
    int hi = 0;
    int name_start = (parent_xindex ? _x[parent_xindex].name.length() + 1 : 0);
    while (xi < next_xi && hi < names.size()) {
	int compare = String::compare(_x[xi].name.substring(name_start), names[hi]);
	if (compare == 0) {	// there is a conflict
	    _x[xi].flags |= X_HANDLER_CONFLICT;
	    xi += _x[xi].skip + 1;
	    hi++;
	} else if (compare < 0)
	    xi += _x[xi].skip + 1;
	else
	    hi++;
    }

    // mark subdirectory as calculated
    _x[parent_xindex].flags |= X_SUBDIR_CONFLICTS_CALCULATED;
}


int
ClickIno::nlink(ino_t ino)
{
    // must be called with config_lock held
    int elementno = INO_ELEMENTNO(ino);

    // it might be a handler
    if (INO_ISHANDLER(ino)) {
	int xi = xindex(elementno);
	// one for the number directory (or global directory), plus one if the
	// name directory exists (for element handlers whose element name
	// isn't a handler conflict)
	return 1 + (xi > 0 && !(_x[xi].flags & X_HANDLER_CONFLICT));
    }
    
    // otherwise, it is a directory
    int nlink = 2;
    if (INO_DT_HAS_U(ino) && _router)
	nlink += _router->nelements();
    if (INO_DT_HAS_N(ino)) {
	int xi = xindex(elementno) + 1;
	if (!(_x[xi - 1].flags & X_SUBDIR_CONFLICTS_CALCULATED))
	    calculate_handler_conflicts(elementno);
	int next_xi = next_xindex(elementno);
	while (xi < next_xi) {
	    if (!(_x[xi].flags & X_HANDLER_CONFLICT) || INO_DIRTYPE(ino) == INO_DT_N)
		nlink++;
	    xi += _x[xi].skip + 1;
	}
    }
    return nlink;
}

int
ClickIno::name_search(const String &n, int first_xi, int last_xi, int name_offset) const
{
    while (first_xi <= last_xi) {
	int mid = (first_xi + last_xi) >> 1;
	int cmp = String::compare(n, _x[mid].name.substring(name_offset));
	if (cmp == 0)
	    return mid;
	else if (cmp < 0)
	    last_xi = mid - 1;
	else
	    first_xi = mid + 1;
    }
    return -1;
}

ino_t
ClickIno::lookup(ino_t ino, const String &component)
{
    // must be called with config_lock held
    int elementno = INO_ELEMENTNO(ino);
    int nelements = (_router ? _router->nelements() : 0);

    // quit early on empty string
    if (!component.length())
	return 0;

    // quick check for dot
    if (component[0] == '.' && component.length() == 1)
	return ino;
    
    // look for numbers
    if (INO_DT_HAS_U(ino) && component[0] >= '1' && component[0] <= '9') {
	int eindex = component[0] - '0';
	for (int i = 1; i < component.length(); i++)
	    if (component[i] >= '0' && component[i] <= '9' && eindex < 1000000000)
		eindex = (eindex * 10) + component[i] - '0';
	    else
		goto number_failed;
	eindex--;
	if (!_router || eindex >= _router->nelements())
	    goto number_failed;
	return INO_MKHDIR(eindex);
    }
    
  number_failed:
    // look for handlers
    if (INO_DT_HAS_H(ino) && elementno < nelements) {
	Element *element = Router::element(_router, elementno);
	int hi = Router::hindex(element, component);
	if (hi >= 0)
	    if (Router::handler(_router, hi)->visible())
		return INO_MKHANDLER(elementno, hi);
    }

    // look for names
    if (INO_DT_HAS_N(ino)) {
	// delimit boundaries of search region
	int first_xi = xindex(elementno) + 1;
	int last_xi = next_xindex(elementno) - 1;
	int name_offset = _x[first_xi - 1].name.length() + 1;
	int found = name_search(component, first_xi, last_xi, (name_offset > 1 ? name_offset : 0));
	if (found >= 0) 
	    return INO_MKHNDIR(ClickIno::elementno(found));
    }

    // check for dot dot
    if (component[0] == '.' && component.length() == 2 && component[1] == '.') {
	int xi = xindex(elementno);
	int slash = _x[xi].name.find_right('/');
	if (slash < 0 || INO_DIRTYPE(ino) == INO_DT_H)
	    return INO_GLOBALDIR;
	int found = name_search(_x[xi].name.substring(0, slash - 1), 1, _nentries - 1, 0);
	if (found >= 0)
	    return INO_MKHNDIR(ClickIno::elementno(found));
	panic("clickfs: ..");	// should never happen
    }

    // no luck
    return 0;
}

int
ClickIno::readdir(ino_t ino, uint32_t &f_pos, filldir_t filldir, void *thunk)
{
    // File positions:
    // 0x00000-0x0FFFF  ignored
    // 0x10000-0x1FFFF  handlers
    // 0x20000-0x2FFFF  numbers
    // 0x30000-0x3FFFF	names

#define RD_HOFF		0x10000
#define RD_UOFF		0x20000
#define RD_NOFF		0x30000
#define RD_XOFF		0x40000
#define FILLDIR(a, b, c, d, e, f)  do { if (!filldir(a, b, c, d, e, f)) return 0; } while (0)
    
    int elementno = INO_ELEMENTNO(ino);
    int nelements = (_router ? _router->nelements() : 0);

    // handler names
    if (f_pos < RD_HOFF)
	f_pos = RD_HOFF;
    if (f_pos < RD_UOFF && INO_DT_HAS_H(ino) && elementno < nelements) {
	Element *element = Router::element(_router, elementno);
	Vector<int> his;
	Router::element_hindexes(element, his);
	while (f_pos >= RD_HOFF && f_pos < his.size() + RD_HOFF) {
	    const Handler* h = Router::handler(_router, his[f_pos - RD_HOFF]);
	    if (h->visible())
		FILLDIR(h->name().data(), h->name().length(), INO_MKHANDLER(elementno, his[f_pos - RD_HOFF]), DT_REG, f_pos, thunk);
	    f_pos++;
	}
    }

    // subdirectory numbers
    if (f_pos < RD_UOFF)
	f_pos = RD_UOFF;
    if (f_pos < RD_NOFF && INO_DT_HAS_U(ino) && _router) {
	char buf[10];
	int nelem = _router->nelements();
	while (f_pos >= RD_UOFF && f_pos < RD_UOFF + nelem) {
	    int elem = f_pos - RD_UOFF;
	    sprintf(buf, "%d", elem + 1);
	    FILLDIR(buf, strlen(buf), INO_MKHDIR(elem), DT_DIR, f_pos, thunk);
	    f_pos++;
	}
    }

    // figure out edges of directory
    int xi = xindex(elementno) + 1;
    int next_xi = next_xindex(elementno);

    // subdirectory names
    if (f_pos < RD_NOFF)
	f_pos = RD_NOFF;
    if (f_pos < RD_XOFF && INO_DT_HAS_N(ino)) {
	bool include_conflicts = (INO_DIRTYPE(ino) == INO_DT_N);
	if (!include_conflicts && !(_x[xi - 1].flags & X_SUBDIR_CONFLICTS_CALCULATED))
	    calculate_handler_conflicts(elementno);
	int name_offset = _x[xi - 1].name.length();
	if (name_offset > 0)
	    name_offset++;	// skip slash
	for (int j = RD_NOFF; xi < next_xi; xi += _x[xi].skip + 1, j++)
	    if (f_pos == j) {
		if (!(_x[xi].flags & X_HANDLER_CONFLICT) || include_conflicts)
		    FILLDIR(_x[xi].name.data() + name_offset, _x[xi].name.length() - name_offset, INO_MKHNDIR(ClickIno::elementno(xi)), DT_DIR, f_pos, thunk);
		f_pos++;
	    }
    }
    
    f_pos = RD_XOFF;
    return 1;
}

#if INO_DEBUG
String
ClickIno::info() const
{
    StringAccum sa;
    for (int i = 0; i < _nentries; i++) {
	sa << i << ". " << _x[i].name;
	if (_x[i].name.length() >= 40)
	    sa << ' ';
	else
	    sa.append("                                                                                                                                       ", 40 - _x[i].name.length());
	sa << 'E' << (_x[i].elementno_plus1 - 1) << '/'
	   << 'X' << _x[i].xindex << '\t'
	   << "->" << (i + 1 + _x[i].skip);
	if (_x[i].flags) {
	    sa << '\t';
	    if (_x[i].flags & X_FAKE)
		sa << 'F';
	    if (_x[i].flags & X_HANDLER_CONFLICT)
		sa << 'H';
	    if (_x[i].flags & X_SUBDIR_CONFLICTS_CALCULATED)
		sa << 'S';
	}
	sa << '\n';
    }
    return sa.take_string();
}
#endif

CLICK_ENDDECLS