/* -*- LPC -*- */
/*
* $Locker: $
* $Id: clusters.c,v 1.17 2003/02/12 19:13:36 wodan Exp $
*
*/
#if !efun_defined(db_exec)
#define OLD
#else
#include <db.h>
#endif
#include <map.h>
#define SIZE 7 //don't make this too high
#define LEVEL(x) load(x)->level
#include <config.h>
nosave int maxnum = 0;
nosave int lasttime = 0;
nosave int count = 0;
nosave mapping used = ([ ]);
nosave mixed *todo= ({ });
nosave mapping cache = ([ ]);
nosave int setup_done = 1;
nosave int db;
nosave int setup_start_time;
class cluster{
mixed *members;
int level; //0 is cluster of rooms, 1 is cluster of cluster of rooms etc
int cluster_number; //in which cluster is this cluster
int this_cluster;
mixed *contacts;
}
#ifndef OLD
private int get_cluster(mixed);
private mixed cdb_fetch(int fd, int row){
mixed stuff = db_fetch(fd, row);
if(arrayp(stuff)){
mixed tmp, ret = ({});
foreach(tmp in stuff){
if(stringp(tmp)){
int i;
sscanf(tmp, "%d", i);
if(i || tmp == "0")
tmp = i;
}
ret += ({tmp});
}
stuff = ret;
}
return stuff;
}
#endif
private class cluster load(int x){
mixed rows;
class cluster tmp = new(class cluster);
if(cache[x])
return cache[x];
#ifdef OLD
cache[x] = restore_variable(unguarded((: read_file(sprintf("/save/clusters/%d",
(int)$(x))) :)));
#else
rows = db_exec(db, "select member from cluster_members where cluster_number = %d", x);
if(stringp(rows) || !rows)
return 0;
tmp->members = ({});
rows++;
while(--rows)
tmp->members += cdb_fetch(db, rows);
rows = db_exec(db, "select level, in_cluster from cluster_list where cluster_number = %d", x);
if(stringp(rows)){
//maybe the database handle died
db_close(db);
db = db_connect("localhost","discworld",CONFIG_DB_USER);
return 0;
}
rows = cdb_fetch(db, 1);
tmp->level = rows[0];
tmp->cluster_number = rows[1];
tmp->this_cluster = x;
rows = db_exec(db, "select contact from cluster_contacts where cluster_number = %d", x);
if(stringp(rows))
return 0;
tmp->contacts = ({});
rows++;
while(--rows)
tmp->contacts += cdb_fetch(db, rows);
cache[x] = tmp;
#endif
return cache[x];
}
private void save(class cluster x){
#ifdef OLD
unguarded((:write_file(sprintf("/save/clusters/%d", $(x->this_cluster)),
save_variable($(x)), 1):));
#else
db_exec(db, "insert into cluster_list values (%d, %d, %d)", x->this_cluster,
x->level, x->cluster_number);
map(x->members, (:db_exec(db, "insert into cluster_members values (%d, '%s')",
$(x->this_cluster), db_escape(""+$1)):));
map(x->contacts, (:db_exec(db, "insert into cluster_contacts values (%d, '%s')",
$(x->this_cluster), db_escape(""+$1)):));
#endif
cache[x->this_cluster] = x;
}
private void make_clusters(mixed);
nosave function fix_contacts;
nosave function fix_room_contacts;
private void create(){
#ifndef OLD
db = db_connect("localhost","discworld",CONFIG_DB_USER);
map(({"cluster_members", "cluster_list", "cluster_contacts"}),
(:db_exec(db, "delete from %s;", $1):));
#endif
fix_room_contacts = function(int i){
class cluster fixing = load(i);
if((sizeof(fixing->contacts)) && intp(fixing->contacts[0])){
error(sprintf("%d in two or more clusters", i));
return;
}
fixing->contacts = uniq_array(map(fixing->contacts,
#ifdef OLD
(:MAP->query_cluster($1):)
#else
(:cache[$1]:)
#endif
));
save(fixing);
};
fix_contacts = function (int i){
class cluster fixing = load(i);
reset_eval_cost();
if(fixing->level){
if((sizeof(fixing->contacts)) && (fixing->level ==
LEVEL(fixing->contacts[0]))){
error(sprintf("%d in two or more clusters", i));
return;
}
fixing->contacts = uniq_array(map(fixing->contacts,
(:load($1)->cluster_number:)));
save(fixing);
if(fixing->level > 1){
map(fixing->members, (:efun::call_out((fix_contacts), 0, $1):));
return;
}
map(fixing->members, fix_room_contacts);
}
};
#ifdef OLD
unguarded(function(){
string file, *files=get_dir("/save/clusters/");
foreach(file in files)
rm(sprintf("/save/clusters/%s", file));
});
#endif
}
private void make_clusters(mixed start){
//read at your own risk...
int count = 0, depth = -1, oldmax = maxnum, level = (stringp(start)? 0 :
load(start)->level + 1);
class cluster current;
mixed *list;
function qdd, real;
if(stringp(start)){ //normal rooms
qdd = function(string room){
//f leaves just the rooms with an exit back
function f = function(string there, string room){
mixed tmp;
return member_array(room,
(tmp = MAP->qdd(there), tmp? tmp : ({}))) + 1;
};
string *qdd = MAP->qdd(room);
return filter(allocate(sizeof(qdd) / 2, (:$(qdd)[$1 * 2 + 1]:)), f, room);
};
real = (:$1:);
} else {
qdd = (:load($1)->contacts:);
if(stringp(load(start)->contacts[0]))
real = (:cache[$1]:); //(:MAP->query_cluster($1):);
else
real = (:load($1)->cluster_number:);
}
current = new (class cluster, members:({start}),
level:level,
this_cluster:++maxnum,
contacts:({}));
list = ({start});
if(used[start])
error(sprintf("%O already in a cluster", start));
used[start] = 1;
while(++depth < sizeof(list) || sizeof(todo)){
mixed *exits;
mixed exit;
if(depth < sizeof(list))
exits = (*qdd)(list[depth]);
else {
count = SIZE + 1;
exits = ({});
}
foreach(exit in exits) {
if(!used[exit = (*real)(exit)]) {
current->members += ({exit});
list += ({exit});
used[exit] = 1;
if(++count > SIZE)
break;
}
}
if(count > SIZE || !(((1 + depth) < sizeof(list)) || sizeof(todo))){
mixed tmp, *contacts = ({});
count = 0;
foreach(tmp in current->members){
reset_eval_cost();
if(stringp(tmp)){
#ifdef OLD
MAP->set_cluster(tmp, current->this_cluster)
#endif
;
cache[tmp] = current->this_cluster;
}
else{
class cluster clust;
clust = load(tmp);
clust->cluster_number = current->this_cluster;
cache[tmp] = clust;
}
exits = (*qdd)(tmp);
if(exits){
function add_non_member, convert_and_add;
// and now we need to get the rooms this cluster connects to from the
// exits info.
add_non_member = (: (member_array($2, $(current->members)) == -1)?
($1 | ({ $2 })) : //don't want doubles
$1 //room was a member
:);
convert_and_add = (:evaluate($(add_non_member), $1,
evaluate($(real), $2)):);
contacts = implode(exits, convert_and_add, contacts);
}
}
//and now we generate exit names for them
current->contacts = contacts;
if(sizeof(contacts) || current->level > 1)
cache[current->this_cluster] = current;
else
maxnum--;
todo = filter(todo + list + contacts, (:!used[$1]:)); //rooms not yet
//in a cluster
depth = -1;
if(sizeof(todo)){
list = ({todo[0]});
todo = todo[1..];
if(used[list[0]])
error("corrupt todo list");
used[list[0]] = 1;
current = new (class cluster, members:({list[0]}),
level:level,
this_cluster:++maxnum,
contacts:({}));
} else
list = ({ });
}
}
if((maxnum - oldmax) > SIZE)
make_clusters(current->this_cluster - 1);
else { //fix contacts arrays
int i;
for(i = oldmax + 1; i <= maxnum; i++)
if(LEVEL(i))
efun::call_out(fix_contacts, 0, i);
else
efun::call_out(fix_room_contacts, 0, i);
}
used = ([]);
efun::call_out((:cache = ([]), setup_done = 1:), 2);
}
#ifndef OLD
private int get_cluster(mixed thing){
if(stringp(thing)){
mixed exret = db_exec(db, "select cluster_number from cluster_members where member = '%s'",
db_escape(thing));
if(!stringp(exret) && exret){
return cdb_fetch(db, 1)[0];
}
} else if(intp(thing)){
mixed exret = db_exec(db, "select in_cluster from cluster_list where cluster_number = %d",
thing);
if(!stringp(exret) && exret){
return cdb_fetch(db, 1)[0];
}
}
return 0;
}
#endif
private int query_top_cluster(string room){
int ret;
#ifdef OLD
ret = MAP->query_cluster(room);
if(ret && unguarded((:file_size(sprintf("/save/clusters/%d", $(ret))):)) > 0)
while(load(ret)->cluster_number){
int last = ret;
ret = load(ret)->cluster_number;
if(last == ret)
return ret;
}
#else
ret = get_cluster(room);
if(ret){
int last = ret;
ret = get_cluster(ret);
while(ret){
last = ret;
ret = get_cluster(ret);
}
return last;
}
#endif
else{ //new cluster space
setup_start_time = time();
setup_done = 0;
make_clusters(room);
}
return ret;
}
#ifndef OLD
private mixed *get_members(int clust){
mixed rows;
rows = db_exec(db, "select member from cluster_members where cluster_number = %d", clust);
if(stringp(rows))
return ({ });
return allocate(rows, (:cdb_fetch(db, $1 + 1)[0]:));
}
private mixed *get_contacts(int clust){
mixed rows;
rows = db_exec(db, "select contact from cluster_contacts where cluster_number = %d", clust);
if(stringp(rows))
return ({ });
return allocate(rows, (:cdb_fetch(db, $1 + 1)[0]:));
}
#endif
private mixed *find_places(int start, int end, int *places){
int found = 0, depth = 0;
int *key;
int *exits, bing, *result, ob, exit;
mapping search = ([]);
if(start == end){
#ifdef OLD
return load(start)->members;
#else
return get_members(start);
#endif
}
key = ({ start });
search[start] = "binglewop";
while (!found) {
reset_eval_cost();
ob = key[depth];
if (ob) {
/* Get the destinations */
#ifdef OLD
exits = load(ob)->contacts;
#else
exits = get_contacts(ob);
#endif
foreach(exit in exits) {
if ((!search[exit]) && (member_array(exit, places) != -1 ||
sizeof(places) == 0)) {
search[exit] = ob;
key += ({ exit });
if (exit == end)
found = 1;
}
}
}
if (!found && ++depth >= sizeof(key))
return 0;
}
exits = ({ });
bing = end;
result = ({ });
while (bing != start) {
reset_eval_cost();
#ifdef OLD
result += load(bing)->members;
#else
result += get_members(bing);
#endif
bing = search[bing];
}
#ifdef OLD
result += load(bing)->members;
#else
result += get_members(bing);
#endif
return result;
} /* find_places() */
private mixed find_route(mixed start, mixed end, string *places){
int found = 0, i, depth = 0;
string *key;
string *exits, bing, *result, ob;
mapping route = ([]), search = ([]);
int t = real_time();
if(start == end)
return ({});
key = ({ start });
route[start] = "binglewop";
while (!found) {
reset_eval_cost();
ob = key[depth];
if (ob) {
/* Get the destinations */
exits = MAP->qdd(ob);
for (i = 1; i < sizeof(exits); i += 2) {
mixed exit = exits[i];
if ((!route[exit]) && (member_array(exit, places) != -1 ||
sizeof(places) == 0)) {
route[exit] = exits[i - 1];
search[exit] = ob;
key += ({ exit });
if (exit == end)
found = 1;
}
}
}
if (!found && (++depth >= sizeof(key) || (real_time() - t) > 4))
return 0;
}
exits = ({ });
bing = end;
result = ({ });
while (bing != start) {
reset_eval_cost();
/* Create it backwards, we go from the destination to the source */
result = ({route[bing]}) + result;
bing = search[bing];
}
return result;
} /* find_route() */
nosave int debugging = 0;
private void debug(int *clusters){
int cluster;
if(debugging)
error("read the error trace");
debugging = 1;
reset_eval_cost();
while(intp(load(clusters[0])->members[0]))
clusters = implode(clusters, (:$1 + load($2)->members:), ({}));
foreach(cluster in clusters){
string *rooms = load(cluster)->members;
string room, room2;
reset_eval_cost();
foreach(room in rooms)
foreach(room2 in rooms)
if(!this_object()->get_route(room, room2))
error("cluster error");
}
}
/**
* Returns an array with move instructions from 'start' to 'end'
* @param start the start location
* @param end the end location
* @param callback the function to call back with the result
*/
string* get_route(string start, string end, function callback){
mixed *places = ({}), *oldplaces;
int sip = 0; //succes is possible
int from, to;
int level;
if(lasttime != time()){
lasttime = time();
count = 0;
} else {
if(count++ > 10) {
return ({}); //10 routes per second is madness, probably a broken npc
}
}
if(!setup_done){
if((time()-setup_start_time) < 5) {
return 0;
}
//looks like we're broken cp runtime logs.
#ifndef OLD
//catch(db_close(db));
#endif
catch(unguarded(function(){
cp("/log/runtime", "/w/wodan/clusterruntime");
cp("/log/catch", "/w/wodan/clustercatch");
}));
//destruct(this_object());
tell_creator("wodan", "would have dested");
setup_done = 1;
return 0;
}
if(!stringp(start)){
start = base_name(start);
if(!stringp(start))
error("illegal start point");
}
if(!stringp(end)){
end = base_name(end);
if(!stringp(end))
error("illegal end point");
}
if(catch(from = query_top_cluster(start))){
#ifndef OLD
//may have lost the database connection
db_close(db);
db = db_connect("localhost","discworld", CONFIG_DB_USER);
#endif
return 0;
}
if(!setup_done) {
return 0;
}
if(from) {
level = LEVEL(from);
}
to = query_top_cluster(end);
if(!to || (level != LEVEL(to))) {
return ({}); //a route can't exist
}
while (level) {
#ifdef OLD
from = MAP->query_cluster(start);
to = MAP->query_cluster(end);
#else
from = get_cluster(start);
to = get_cluster(end);
#endif
while((from != to) && (LEVEL(from) < level)){
from = load(from)->cluster_number;
to = load(to)->cluster_number;
}
level = LEVEL(from);
if(!level){ //this can only happen in the first loop
if(!sip) {
break;
}
error("wrong level");
}
oldplaces = places;
places = find_places(from, to, places);
//printf("level %d sizeof places %d\n", level, sizeof(places));
if(!places){
if(!sip) {
return ({});
}
debug(oldplaces);
error("this can't happen, honest!");
}
sip = 1;
level--;
}
// level is now 0
#ifdef OLD
from = MAP->query_cluster(start);
to = MAP->query_cluster(end);
#else
from = get_cluster(start);
to = get_cluster(end);
#endif
oldplaces = places;
places = find_places(from, to, places);
if(!places){
if(!sip) {
return ({});
}
debug(oldplaces);
error("this can't happen, honest!!");
}
//now places is an array of real rooms which should contain the rooms on the
//route from start to end
cache = ([]); // don't need to waste memory on the cache anymore
return find_route(start, end, places);
}
#ifndef OLD
void dest_me(){
db_close(db);
destruct(this_object());
}
#endif
