dependent.c 48.3 KB
Newer Older
1
/* vim: set sw=8: -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
Arturo Espinosa's avatar
Arturo Espinosa committed
2
/*
3
 * dependent.c:  Manage calculation dependencies between objects
Arturo Espinosa's avatar
Arturo Espinosa committed
4
 *
5
 * Copyright (C) 2000-2002
Jody Goldberg's avatar
Jody Goldberg committed
6
 *  Jody Goldberg   (jody@gnome.org)
Jody Goldberg's avatar
Jody Goldberg committed
7
 *
8 9 10
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of version 2 of the GNU General Public License as published
 * by the Free Software Foundation.
Jody Goldberg's avatar
Jody Goldberg committed
11 12 13 14 15 16 17 18 19 20
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
Arturo Espinosa's avatar
Arturo Espinosa committed
21
 */
22 23
#include <gnumeric-config.h>
#include "gnumeric.h"
24
#include "dependent.h"
25

26
#include "value.h"
27 28
#include "cell.h"
#include "sheet.h"
Jody Goldberg's avatar
Jody Goldberg committed
29
#include "expr.h"
30
#include "expr-impl.h"
31
#include "expr-name.h"
32 33 34 35
#include "workbook-view.h"
#include "workbook-private.h"
#include "rendered-value.h" /* FIXME : should not be needed with JIT-R */
#include "ranges.h"
36
#include "gutils.h"
Michael Meeks's avatar
Michael Meeks committed
37

38
#define BUCKET_SIZE	128
39

Jody Goldberg's avatar
Jody Goldberg committed
40
static GPtrArray *dep_classes = NULL;
Michael Meeks's avatar
Michael Meeks committed
41

Jody Goldberg's avatar
Jody Goldberg committed
42 43
void
dependent_types_init (void)
44
{
Jody Goldberg's avatar
Jody Goldberg committed
45
	g_return_if_fail (dep_classes == NULL);
46

Jody Goldberg's avatar
Jody Goldberg committed
47 48 49 50
	/* Init with a pair of NULL classes so we can access directly */
	dep_classes = g_ptr_array_new ();
	g_ptr_array_add	(dep_classes, NULL);
	g_ptr_array_add	(dep_classes, NULL);
51 52
}

Jody Goldberg's avatar
Jody Goldberg committed
53 54
void
dependent_types_shutdown (void)
55
{
Jody Goldberg's avatar
Jody Goldberg committed
56 57
	g_return_if_fail (dep_classes != NULL);
	g_ptr_array_free (dep_classes, TRUE);
58 59
}

Jody Goldberg's avatar
Jody Goldberg committed
60 61 62 63 64 65 66 67 68
/**
 * dependent_register_type :
 * @klass : A vtable
 *
 * Store the vtable and allocate an ID for a new class
 * of dependents.
 */
guint32
dependent_type_register (DependentClass const *klass)
69
{
Jody Goldberg's avatar
Jody Goldberg committed
70
	guint32 res;
71

Jody Goldberg's avatar
Jody Goldberg committed
72
	g_return_val_if_fail (dep_classes != NULL, 0);
73

Jody Goldberg's avatar
Jody Goldberg committed
74 75
	g_ptr_array_add	(dep_classes, (gpointer)klass);
	res = dep_classes->len-1;
76

Jody Goldberg's avatar
Jody Goldberg committed
77
	g_return_val_if_fail (res <= DEPENDENT_TYPE_MASK, res);
78

Jody Goldberg's avatar
Jody Goldberg committed
79
	return res;
80 81
}

82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
/*
 * dependent_flag_recalc:
 * @dep: the dependent that contains the expression needing recomputation.
 *
 * Marks @dep as needing recalculation
 * NOTE : it does NOT recursively dirty dependencies.
 */
#define dependent_flag_recalc(dep) \
  do { (dep)->flags |= DEPENDENT_NEEDS_RECALC; } while (0)

/**
 * dependent_changed:
 * @cell : the dependent that changed
 *
 * Links the dependent and queues a recalc.
 */
static void
dependent_changed (Dependent *dep)
{
	static CellPos const pos = { 0, 0 };

	/* A pos should not be necessary, but supply one just in case.  If a
	 * user specifies a relative reference this is probably what they want.
	 */
	dependent_link (dep, &pos);

	if (dep->sheet->workbook->priv->recursive_dirty_enabled)
		cb_dependent_queue_recalc (dep,  NULL);
	else
		dependent_flag_recalc (dep);
}
113

Jody Goldberg's avatar
Jody Goldberg committed
114 115 116
/**
 * dependent_set_expr :
 * @dep : The dependent we are interested in.
117
 * @new_expr : new expression.
Jody Goldberg's avatar
Jody Goldberg committed
118
 *
119 120
 * When the expression associated with a dependent needs to change this routine
 * dispatches to the virtual handler unlinking if necessary.
121 122
 * NOTE : it does NOT relink cells incase they are going to move later.
 * It does appear to relink objects ???
Michael Meeks's avatar
Michael Meeks committed
123
 */
124
#warning fix the semantics of this
Jody Goldberg's avatar
Jody Goldberg committed
125
void
126
dependent_set_expr (Dependent *dep, GnmExpr const *new_expr)
Michael Meeks's avatar
Michael Meeks committed
127
{
128
	int const t = dependent_type (dep);
Jody Goldberg's avatar
Jody Goldberg committed
129

130 131 132 133 134 135 136 137
#if 0
{
	ParsePos pos;
	char *str;

	parse_pos_init_dep (&pos, dep);
	dependent_debug_name (dep, stdout);

138
	str = gnm_expr_as_string (new_expr, &pos);
139 140 141
	printf(" new = %s\n", str);
	g_free (str);

142
	str = gnm_expr_as_string (dep->expression, &pos);
143 144 145 146 147 148 149 150
	printf("\told = %s\n", str);
	g_free (str);
}
#endif

	if (dependent_is_linked (dep))
		dependent_unlink (dep, NULL);

Jody Goldberg's avatar
Jody Goldberg committed
151 152 153 154 155
	if (t == DEPENDENT_CELL) {
		/*
		 * Explicitly do not check for array subdivision, we may be
		 * replacing the corner of an array.
		 */
156
		cell_set_expr_unsafe (DEP_TO_CELL (dep), new_expr);
Jody Goldberg's avatar
Jody Goldberg committed
157 158 159 160
	} else {
		DependentClass *klass = g_ptr_array_index (dep_classes, t);

		g_return_if_fail (klass);
161 162
		if (new_expr != NULL)
			gnm_expr_ref (new_expr);
163 164 165 166
		if (klass->set_expr != NULL)
			(*klass->set_expr) (dep, new_expr);

		if (dep->expression != NULL)
167
			gnm_expr_unref (dep->expression);
168 169
		dep->expression = new_expr;
		if (new_expr != NULL)
170
			dependent_changed (dep);
Jody Goldberg's avatar
Jody Goldberg committed
171
	}
Michael Meeks's avatar
Michael Meeks committed
172 173
}

Jody Goldberg's avatar
fix.  
Jody Goldberg committed
174 175 176 177 178 179 180 181 182 183 184 185 186 187
/**
 * dependent_set_sheet
 * @dep :
 * @sheet :
 */
void
dependent_set_sheet (Dependent *dep, Sheet *sheet)
{
	g_return_if_fail (dep != NULL);
	g_return_if_fail (dep->sheet == NULL);
	g_return_if_fail (!dependent_is_linked (dep));

	dep->sheet = sheet;
	if (dep->expression != NULL)
188
		dependent_changed (dep);
Jody Goldberg's avatar
fix.  
Jody Goldberg committed
189 190
}

191 192
static void
cb_cell_list_deps (Dependent *dep, gpointer user)
193
{
194 195 196
	GSList **list = (GSList **)user;
	*list = g_slist_prepend (*list, dep);
}
197

198 199 200 201 202 203
static GSList *
cell_list_deps (const Cell *cell)
{
	GSList *deps = NULL;
	cell_foreach_dep (cell, cb_cell_list_deps, &deps);
	return deps;
204 205 206
}


Jody Goldberg's avatar
Jody Goldberg committed
207 208 209 210 211
/**
 * dependent_queue_recalc_list :
 * @list :
 *
 * Queues any elements of @list for recalc that are not already queued,
212
 * and marks all elements as needing a recalc.
Jody Goldberg's avatar
Jody Goldberg committed
213 214
 */
static void
215
dependent_queue_recalc_list (GSList *list)
216
{
217 218
	GSList *work = NULL;

Jody Goldberg's avatar
Jody Goldberg committed
219 220
	for (; list != NULL ; list = list->next) {
		Dependent *dep = list->data;
221
		if (!dependent_needs_recalc (dep)) {
222
			dependent_flag_recalc (dep);
223
			work = g_slist_prepend (work, dep);
224 225
		}
	}
226

227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
	/*
	 * Work is now a list of marked cells whose dependencies need
	 * to be marked.  Marking early guarentees that we will not
	 * get duplicates.  (And it thus limits the length of the list.)
	 * We treat work as a stack.
	 */

	while (work) {
		Dependent *dep = work->data;

		/* Pop the top element.  */
		list = work;
		work = work->next;
		g_slist_free_1 (list);

242
		if (dependent_is_cell (dep)) {
243
			GSList *deps = cell_list_deps (DEP_TO_CELL (dep));
244 245 246
			GSList *waste = NULL;
			GSList *next;
			for (list = deps; list != NULL ; list = next) {
247
				Dependent *dep = list->data;
248
				next = list->next;
249
				if (dependent_needs_recalc (dep)) {
250 251 252
					list->next = waste;
					waste = list;
				} else {
253
					dependent_flag_recalc (dep);
254 255
					list->next = work;
					work = list;
256 257
				}
			}
258
			g_slist_free (waste);
259
		}
Jody Goldberg's avatar
Jody Goldberg committed
260
	}
261 262
}

263 264 265 266 267 268

void
cb_dependent_queue_recalc (Dependent *dep, gpointer ignore)
{
	g_return_if_fail (dep != NULL);

269
	if (!dependent_needs_recalc (dep)) {
270 271
		GSList listrec;
		listrec.next = NULL;
272
		listrec.data = dep;
273
		dependent_queue_recalc_list (&listrec);
274 275 276
	}
}

277
/**************************************************************************/
Jody Goldberg's avatar
Jody Goldberg committed
278
#define ENABLE_MICRO_HASH
279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
#ifdef ENABLE_MICRO_HASH
typedef struct {
	gint     num_buckets;
	gint     num_elements;
	union {
		GSList **buckets;
		GSList *singleton;
	} u;
} MicroHash;

#define MICRO_HASH_MIN_SIZE 11
#define MICRO_HASH_MAX_SIZE 13845163
#define MICRO_HASH_RESIZE(hash_table)				\
G_STMT_START {							\
	if ((hash_table->num_buckets > MICRO_HASH_MIN_SIZE &&		\
	     hash_table->num_buckets >= 3 * hash_table->num_elements) || 	\
	    (hash_table->num_buckets < MICRO_HASH_MAX_SIZE &&		\
	     3 * hash_table->num_buckets <= hash_table->num_elements))	\
		micro_hash_resize (hash_table);			\
} G_STMT_END

/* The records are aligned so the bottom few bits don't hold much
 * entropy
 */
#define MICRO_HASH_hash(key)	((guint)((int) (key) >> 9))

static void
micro_hash_resize (MicroHash *hash_table)
{
	GSList **new_buckets, *node, *next;
	guint bucket;
	gint old_num_buckets = hash_table->num_buckets;
311 312 313 314 315 316
	gint new_num_buckets = g_spaced_primes_closest (hash_table->num_elements);

	if (new_num_buckets < MICRO_HASH_MIN_SIZE)
		new_num_buckets = MICRO_HASH_MIN_SIZE;
	else if (new_num_buckets > MICRO_HASH_MAX_SIZE)
		new_num_buckets = MICRO_HASH_MAX_SIZE;
317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342

	if (old_num_buckets <= 1) {
		if (new_num_buckets == 1)
			return;
		new_buckets = g_new0 (GSList *, new_num_buckets);
		for (node = hash_table->u.singleton; node; node = next) {
			next = node->next;
			bucket =  MICRO_HASH_hash (node->data) % new_num_buckets;
			node->next = new_buckets [bucket];
			new_buckets [bucket] = node;
		}
		hash_table->u.buckets = new_buckets;
	} else if (new_num_buckets > 1) {
		new_buckets = g_new0 (GSList *, new_num_buckets);
		for (old_num_buckets = hash_table->num_buckets; old_num_buckets-- > 0 ; )
			for (node = hash_table->u.buckets [old_num_buckets]; node; node = next) {
				next = node->next;
				bucket =  MICRO_HASH_hash (node->data) % new_num_buckets;
				node->next = new_buckets [bucket];
				new_buckets [bucket] = node;
			}
		g_free (hash_table->u.buckets);
		hash_table->u.buckets = new_buckets;
	} else {
		GSList *singleton = NULL;
		while (old_num_buckets-- > 0)
Jody Goldberg's avatar
Jody Goldberg committed
343
			singleton = g_slist_concat (hash_table->u.buckets [old_num_buckets], singleton);
344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411
		g_free (hash_table->u.buckets);
		hash_table->u.singleton = singleton;
	}

	hash_table->num_buckets = new_num_buckets;
}

static void
micro_hash_insert (MicroHash *hash_table, gpointer key)
{
	GSList **head;
	int const hash_size = hash_table->num_buckets;

	if (hash_size > 1) {
		guint const bucket = MICRO_HASH_hash (key) % hash_size;
		head = hash_table->u.buckets + bucket;
	} else
		head = & (hash_table->u.singleton);

	if (g_slist_find (*head, key) == NULL) {
		*head = g_slist_prepend (*head, key);
		hash_table->num_elements++;
		MICRO_HASH_RESIZE (hash_table);
	}
}

static void
micro_hash_remove (MicroHash *hash_table, gpointer key)
{
	GSList **head;
	int const hash_size = hash_table->num_buckets;

	if (hash_size > 1) {
		guint const bucket = MICRO_HASH_hash (key) % hash_size;
		head = hash_table->u.buckets + bucket;
	} else
		head = & (hash_table->u.singleton);

	for (; *head != NULL ; head = &((*head)->next))
		if ((*head)->data == key) {
			*head = (*head)->next;
			hash_table->num_elements--;
			MICRO_HASH_RESIZE (hash_table);
			return;
		}
}

static void
micro_hash_release (MicroHash *hash_table)
{
	guint i = hash_table->num_buckets;

	if (i > 1) {
		while (i-- > 0)
			g_slist_free (hash_table->u.buckets[i]);
		g_free (hash_table->u.buckets);
		hash_table->u.buckets = NULL;
	} else {
		g_slist_free (hash_table->u.singleton);
		hash_table->u.singleton = NULL;
	}
	hash_table->num_elements = 0;
	hash_table->num_buckets = 1;
}

static void
micro_hash_init (MicroHash *hash_table, gpointer key)
{
412
	hash_table->num_elements = 1;
413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476
	hash_table->num_buckets = 1;
	hash_table->u.singleton = g_slist_prepend (NULL, key);
}

/*************************************************************************/

typedef MicroHash	DepCollection;
#define dep_collection_init(dc, dep)	\
	micro_hash_init (&(dc), dep)
#define dep_collection_insert(dc, dep)	\
	micro_hash_insert (&(dc), dep)
#define dep_collection_remove(dc, dep)	\
	micro_hash_remove (&(dc), dep)
#define dep_collection_is_empty(dc)				\
	(dc.num_elements == 0)
#define dep_collection_foreach_dep(dc, dep, code) do {		\
	GSList *l;						\
	int i = dc.num_buckets;					\
	if (i <= 1) { 						\
		for (l = dc.u.singleton; l ; l = l->next) {	\
			Dependent *dep = l->data;		\
			code					\
		}						\
	} else while (i-- > 0) {				\
		for (l = dc.u.buckets [i]; l ; l = l->next) {	\
			Dependent *dep = l->data;		\
			code					\
		}						\
	}							\
} while (0)
#define dep_collection_foreach_list(dc, list, code) do {	\
	GSList *list;						\
	int i = dc.num_buckets;					\
	if (i <= 1) { 						\
		list = dc.u.singleton;				\
		code						\
	} else while (i-- > 0) {				\
		list = dc.u.buckets[i];				\
		code						\
	}							\
} while (0)
#else
typedef GSList *	DepCollection;
#define dep_collection_init(dc, dep)	\
	dc = g_slist_prepend (NULL, dep)
#define dep_collection_insert(dc, dep) \
	if (!g_slist_find (dc, dep)) dc = g_slist_prepend (dc, dep)
#define dep_collection_remove(dc, dep)	\
	dc = g_slist_remove (dc, dep);
#define dep_collection_is_empty(dc)	\
	(dc == NULL)
#define dep_collection_foreach_dep(dc, dep, code) do {		\
	GSList *l;						\
	for (l = dc; l != NULL ; l = l->next) {			\
		Dependent *dep = l->data;			\
		code						\
	}							\
} while (0)
#define dep_collection_foreach_list(dc, list, code) do {	\
	GSList *list = dc;					\
	code							\
} while (0)
#endif

Jody Goldberg's avatar
Jody Goldberg committed
477 478 479 480 481 482
/**************************************************************************
 * Data structures for managing dependencies between objects.
 *
 * The DependencyRange hash needs to be improved.  It is a huge
 * performance hit when there are large numbers of range depends.
 */
483

Jody Goldberg's avatar
Jody Goldberg committed
484 485 486 487 488
/*
 * A DependencyRange defines a range of cells whose values
 * are used by another objects in the spreadsheet.
 *
 * A change in those cells will trigger a recomputation on the
489
 * cells listed in deps.
Jody Goldberg's avatar
Jody Goldberg committed
490 491
 */
typedef struct {
492
	DepCollection	deps;	/* Must be first */
Jody Goldberg's avatar
Jody Goldberg committed
493 494
	Range  range;
} DependencyRange;
495

496
/*
497 498
 *  A DependencySingle stores a list of dependents that rely
 * on the cell at @pos.
Jody Goldberg's avatar
Jody Goldberg committed
499
 *
500
 * A change in this cell will trigger a recomputation on the
501
 * cells listed in deps.
502
 */
Jody Goldberg's avatar
Jody Goldberg committed
503
typedef struct {
504
	DepCollection	deps;	/* Must be first */
Jody Goldberg's avatar
Jody Goldberg committed
505 506 507
	CellPos pos;
} DependencySingle;

508 509
/* A utility type */
typedef struct {
510
	DepCollection	deps;	/* Must be first */
511 512 513
} DependencyAny;

static guint
Jody Goldberg's avatar
Jody Goldberg committed
514
deprange_hash (DependencyRange const *r)
515 516 517 518 519
{
	return ((((r->range.start.row << 8) + r->range.end.row) << 8) +
		(r->range.start.col << 8) + (r->range.end.col));
}
static gint
Jody Goldberg's avatar
Jody Goldberg committed
520
deprange_equal (DependencyRange const *r1, DependencyRange const *r2)
521
{
522
	return range_equal (&(r1->range), &(r2->range));
523 524 525
}

static guint
526
depsingle_hash (DependencySingle const *depsingle)
527
{
528
	return (depsingle->pos.row << 8) ^ depsingle->pos.col;
529 530
}
static gint
531
depsingle_equal (DependencySingle const *a, DependencySingle const *b)
532
{
533
	return (a->pos.row == b->pos.row && a->pos.col == b->pos.col);
534 535
}

536 537
static DependentFlags
link_single_dep (Dependent *dep, CellPos const *pos, CellRef const *ref)
Michael Meeks's avatar
Michael Meeks committed
538
{
539
	DependencySingle lookup;
540
	DependencySingle *single;
541
	GnmDepContainer *deps;
542 543 544 545 546 547 548 549 550
	DependentFlags flag = DEPENDENT_NO_FLAG;
 
	if (ref->sheet != NULL) {
		if (ref->sheet != dep->sheet)
			flag = (ref->sheet->workbook != dep->sheet->workbook)
				? DEPENDENT_GOES_INTERBOOK : DEPENDENT_GOES_INTERSHEET;
		deps = ref->sheet->deps;
	} else
		deps = dep->sheet->deps;
551 552

	/* Inserts if it is not already there */
553
	cellref_get_abs_pos (ref, pos, &lookup.pos);
554 555
	single = g_hash_table_lookup (deps->single_hash, &lookup);
	if (single == NULL) {
556
		single = gnm_mem_chunk_alloc (deps->single_pool);
557 558 559 560 561
		*single = lookup;
		dep_collection_init (single->deps, dep);
		g_hash_table_insert (deps->single_hash, single, single);
	} else
		dep_collection_insert (single->deps, dep);
562 563

	return flag;
564
}
565

566 567 568 569 570
static void
unlink_single_dep (Dependent *dep, CellPos const *pos, CellRef const *a)
{
	DependencySingle lookup;
	DependencySingle *single;
571
	GnmDepContainer *deps = eval_sheet (a->sheet, dep->sheet)->deps;
572

Jody Goldberg's avatar
Jody Goldberg committed
573
	if (!deps)
574 575
		return;

576
	cellref_get_abs_pos (a, pos, &lookup.pos);
Jody Goldberg's avatar
Jody Goldberg committed
577
	single = g_hash_table_lookup (deps->single_hash, &lookup);
578 579 580 581
	if (single != NULL) {
		dep_collection_remove (single->deps, dep);
		if (dep_collection_is_empty (single->deps)) {
			g_hash_table_remove (deps->single_hash, single);
582
			gnm_mem_chunk_free (deps->single_pool, single);
583
		}
584 585 586
	}
}

587
static void
588
link_range_dep (GnmDepContainer *deps, Dependent *dep,
589
		DependencyRange const *r)
590
{
591 592 593 594 595 596
	int i = r->range.start.row / BUCKET_SIZE;
	int const end = r->range.end.row / BUCKET_SIZE;

	for ( ; i <= end; i++) {
		/* Look it up */
		DependencyRange *result;
Jody Goldberg's avatar
Jody Goldberg committed
597

598
		if (deps->range_hash [i] == NULL) {
Jody Goldberg's avatar
Jody Goldberg committed
599 600 601
			deps->range_hash [i] = g_hash_table_new (
				(GHashFunc)  deprange_hash,
				(GEqualFunc) deprange_equal);
602 603 604 605
			result = NULL;
		} else {
			result = g_hash_table_lookup (deps->range_hash[i], r);
			if (result) {
606 607
				/* Inserts if it is not already there */
				dep_collection_insert (result->deps, dep);
Morten Welinder's avatar
Morten Welinder committed
608
				continue;
609 610
			}
		}
611

612
		/* Create a new DependencyRange structure */
613
		result = gnm_mem_chunk_alloc (deps->range_pool);
614
		*result = *r;
615
		dep_collection_init (result->deps, dep);
616 617
		g_hash_table_insert (deps->range_hash[i], result, result);
	}
618 619
}

Michael Meeks's avatar
Michael Meeks committed
620
static void
621
unlink_range_dep (GnmDepContainer *deps, Dependent *dep,
622
		  DependencyRange const *r)
Michael Meeks's avatar
Michael Meeks committed
623
{
624 625
	int i = r->range.start.row / BUCKET_SIZE;
	int const end = r->range.end.row / BUCKET_SIZE;
626
	DependencyRange *result;
627

Morten Welinder's avatar
Morten Welinder committed
628 629 630
	if (!deps)
		return;

631 632 633
	for ( ; i <= end; i++) {
		result = g_hash_table_lookup (deps->range_hash[i], r);
		if (result) {
634 635
			dep_collection_remove (result->deps, dep);
			if (dep_collection_is_empty (result->deps)) {
636
				g_hash_table_remove (deps->range_hash[i], result);
637
				gnm_mem_chunk_free (deps->range_pool, result);
638
			}
Michael Meeks's avatar
Michael Meeks committed
639
		}
Jody Goldberg's avatar
Jody Goldberg committed
640 641 642
	}
}

643
static DependentFlags
644 645
link_cellrange_dep (Dependent *dep, CellPos const *pos,
		    CellRef const *a, CellRef const *b)
646 647
{
	DependencyRange range;
648 649
	DependentFlags flag = DEPENDENT_NO_FLAG;
 
650 651 652 653
	cellref_get_abs_pos (a, pos, &range.range.start);
	cellref_get_abs_pos (b, pos, &range.range.end);
	range_normalize (&range.range);

654 655 656 657
	if (a->sheet != NULL) {
		if (a->sheet != dep->sheet)
			flag = (a->sheet->workbook != a->sheet->workbook)
				? DEPENDENT_GOES_INTERBOOK : DEPENDENT_GOES_INTERSHEET;
Michael Meeks's avatar
Michael Meeks committed
658

659 660 661 662 663
		if (b->sheet != NULL && a->sheet != b->sheet) {
			Workbook const *wb = a->sheet->workbook;
			int i = a->sheet->index_in_wb;
			int stop = b->sheet->index_in_wb;
			if (i < stop) { int tmp = i; i = stop ; stop = tmp; }
Michael Meeks's avatar
Michael Meeks committed
664

665
			g_return_val_if_fail (b->sheet->workbook == wb, flag);
666

667 668 669 670 671 672 673 674 675
			while (i <= stop) {
				Sheet *sheet = g_ptr_array_index (wb->sheets, i);
				link_range_dep (sheet->deps, dep, &range);
			}
			flag |= DEPENDENT_HAS_3D;
		} else
			link_range_dep (a->sheet->deps, dep, &range);
	} else
		link_range_dep (dep->sheet->deps, dep, &range);
676 677

	return flag;
678 679 680 681 682 683 684 685 686 687 688
}
static void
unlink_cellrange_dep (Dependent *dep, CellPos const *pos,
		      CellRef const *a, CellRef const *b)
{
	DependencyRange range;

	cellref_get_abs_pos (a, pos, &range.range.start);
	cellref_get_abs_pos (b, pos, &range.range.end);
	range_normalize (&range.range);

689 690 691 692 693 694 695 696
	if (a->sheet != NULL) {
		if (b->sheet != NULL && a->sheet != b->sheet) {
			Workbook const *wb = a->sheet->workbook;
			int i = a->sheet->index_in_wb;
			int stop = b->sheet->index_in_wb;
			if (i < stop) { int tmp = i; i = stop ; stop = tmp; }

			g_return_if_fail (b->sheet->workbook == wb);
697

698 699 700 701 702 703 704 705
			while (i <= stop) {
				Sheet *sheet = g_ptr_array_index (wb->sheets, i);
				unlink_range_dep (sheet->deps, dep, &range);
			}
		} else
			unlink_range_dep (a->sheet->deps, dep, &range);
	} else
		unlink_range_dep (dep->sheet->deps, dep, &range);
706 707
}

708
static DependentFlags
709
link_expr_dep (Dependent *dep, CellPos const *pos, GnmExpr const *tree)
710
{
711
	switch (tree->any.oper) {
712
	case GNM_EXPR_OP_ANY_BINARY:
713 714
		return  link_expr_dep (dep, pos, tree->binary.value_a) |
			link_expr_dep (dep, pos, tree->binary.value_b);
715 716
	case GNM_EXPR_OP_ANY_UNARY : return link_expr_dep (dep, pos, tree->unary.value);
	case GNM_EXPR_OP_CELLREF	    : return link_single_dep (dep, pos, &tree->cellref.ref);
Morten Welinder's avatar
Morten Welinder committed
717

718
	case GNM_EXPR_OP_CONSTANT:
719
		/* TODO: use implicit intersection */
720
		if (VALUE_CELLRANGE == tree->constant.value->type)
721
			return link_cellrange_dep (dep, pos,
722 723
				&tree->constant.value->v_range.cell.a,
				&tree->constant.value->v_range.cell.b);
724
		return DEPENDENT_NO_FLAG;
Morten Welinder's avatar
Morten Welinder committed
725

726
	/* TODO : Can we use argument types to be smarter here ? */
727 728
	case GNM_EXPR_OP_FUNCALL: {
		GnmExprList *l;
729
		DependentFlags flag = DEPENDENT_NO_FLAG;
730 731
		if (tree->func.func->fn_type == FUNCTION_NAMEONLY)
			func_def_load (tree->func.func);
732 733 734
		if (tree->func.func->link) {
			EvalPos		 ep;
			FunctionEvalInfo fei;
735
			fei.pos = eval_pos_init_dep (&ep, dep);
736
			fei.func_call = (GnmExprFunction const *)tree;
737
			flag = tree->func.func->link (&fei);
738 739
		}
		for (l = tree->func.arg_list; l; l = l->next)
740 741
			flag |= link_expr_dep (dep, pos, l->data);
		return flag;
742
	}
743

744
	case GNM_EXPR_OP_NAME:
745 746
		expr_name_add_dep (tree->name.name, dep);
		if (!tree->name.name->builtin && tree->name.name->active)
747 748
			return link_expr_dep (dep, pos, tree->name.name->t.expr_tree);
		return DEPENDENT_NO_FLAG;
749

750
	case GNM_EXPR_OP_ARRAY:
751 752 753 754 755 756 757
		if (tree->array.x != 0 || tree->array.y != 0) {
			/* Non-corner cells depend on the corner */
			CellRef a;

			/* We cannot support array expressions unless
			 * we have a position.
			 */
758
			g_return_val_if_fail (pos != NULL, DEPENDENT_NO_FLAG);
759 760 761 762 763 764

			a.col_relative = a.row_relative = FALSE;
			a.sheet = dep->sheet;
			a.col   = pos->col - tree->array.x;
			a.row   = pos->row - tree->array.y;

765
			return link_single_dep (dep, pos, &a);
766 767
		} else
			/* Corner cell depends on the contents of the expr */
768
			return link_expr_dep (dep, pos, tree->array.corner.expr);
769

770 771
	case GNM_EXPR_OP_SET: {
		GnmExprList *l;
Andreas J. Guelzow's avatar
Andreas J. Guelzow committed
772
		DependentFlags res = DEPENDENT_NO_FLAG;
773 774

		for (l = tree->set.set; l; l = l->next)
775 776
			res |= link_expr_dep (dep, pos, l->data);
		return res;
777 778
	}

779
	default:
780
		g_warning ("Unknown Operation type, dependencies lost");
781
	}
782
	return 0;
783 784 785
}

static void
786
unlink_expr_dep (Dependent *dep, CellPos const *pos, GnmExpr const *tree)
787
{
788
	switch (tree->any.oper) {
789
	case GNM_EXPR_OP_ANY_BINARY:
790 791
		unlink_expr_dep (dep, pos, tree->binary.value_a);
		unlink_expr_dep (dep, pos, tree->binary.value_b);
792 793
		return;

794
	case GNM_EXPR_OP_ANY_UNARY : unlink_expr_dep (dep, pos, tree->unary.value);
Morten Welinder's avatar
Morten Welinder committed
795
		return;
796
	case GNM_EXPR_OP_CELLREF	    : unlink_single_dep (dep, pos, &tree->cellref.ref);
797 798
		return;

799
	case GNM_EXPR_OP_CONSTANT:
800 801 802 803
		if (VALUE_CELLRANGE == tree->constant.value->type)
			unlink_cellrange_dep (dep, pos,
				&tree->constant.value->v_range.cell.a,
				&tree->constant.value->v_range.cell.b);
804
		return;
Jody Goldberg's avatar
Jody Goldberg committed
805

Michael Meeks's avatar
Michael Meeks committed
806 807 808 809
	/*
	 * FIXME: needs to be taught implicit intersection +
	 * more cunning handling of argument type matching.
	 */
810 811
	case GNM_EXPR_OP_FUNCALL: {
		GnmExprList *l;
812 813 814
		if (tree->func.func->unlink) {
			EvalPos		 ep;
			FunctionEvalInfo fei;
815
			fei.pos = eval_pos_init_dep (&ep, dep);
816
			fei.func_call = (GnmExprFunction const *)tree;
817
			tree->func.func->unlink (&fei);
818
		}
819
		for (l = tree->func.arg_list; l; l = l->next)
820
			unlink_expr_dep (dep, pos, l->data);
821
		return;
Jody Goldberg's avatar
Jody Goldberg committed
822
	}
823

824
	case GNM_EXPR_OP_NAME:
825
		expr_name_remove_dep (tree->name.name, dep);
Jody Goldberg's avatar
Jody Goldberg committed
826
		if (!tree->name.name->builtin && tree->name.name->active)
827
			unlink_expr_dep (dep, pos, tree->name.name->t.expr_tree);
Michael Meeks's avatar
Michael Meeks committed
828 829
		return;

830
	case GNM_EXPR_OP_ARRAY:
831
		if (tree->array.x != 0 || tree->array.y != 0) {
832
			/* Non-corner cells depend on the corner */
Michael Meeks's avatar
Michael Meeks committed
833 834
			CellRef a;

Morten Welinder's avatar
Morten Welinder committed
835
			/* We cannot support array expressions unless
836 837 838 839
			 * we have a position.
			 */
			g_return_if_fail (pos != NULL);

840
			a.col_relative = a.row_relative = FALSE;
841 842 843
			a.sheet = dep->sheet;
			a.col   = pos->col - tree->array.x;
			a.row   = pos->row - tree->array.y;
Michael Meeks's avatar
Michael Meeks committed
844

845
			unlink_single_dep (dep, pos, &a);
846 847
		} else
			/* Corner cell depends on the contents of the expr */
848
			unlink_expr_dep (dep, pos, tree->array.corner.expr);
849
		return;
850

851 852
	case GNM_EXPR_OP_SET: {
		GnmExprList *l;
853 854

		for (l = tree->set.set; l; l = l->next)
855
			unlink_expr_dep (dep, pos, l->data);
856 857 858
		return;
	}

859 860 861
	default:
		g_warning ("Unknown Operation type, dependencies lost");
		break;
862
	}
863 864
}

865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880
static void
workbook_link_3d_dep (Dependent *dep)
{
	if (dep->sheet->workbook->sheet_order_dependents == NULL)
		dep->sheet->workbook->sheet_order_dependents =
			g_hash_table_new (g_direct_hash, g_direct_equal);
	g_hash_table_insert (dep->sheet->workbook->sheet_order_dependents, dep, dep);
}

static void
workbook_unlink_3d_dep (Dependent *dep)
{
	g_return_if_fail (dep->sheet->workbook->sheet_order_dependents != NULL);
	g_hash_table_remove (dep->sheet->workbook->sheet_order_dependents, dep);
}

Jody Goldberg's avatar
Jody Goldberg committed
881 882 883 884 885 886 887 888
/**
 * dependent_link:
 * @dep : the dependent that changed
 * @pos: The optionally NULL position of the dependent.
 *
 * Adds the dependent to the workbook wide list of dependents.
 */
void
889
dependent_link (Dependent *dep, CellPos const *pos)
Jody Goldberg's avatar
Jody Goldberg committed
890
{
891
	Sheet *sheet;
Jody Goldberg's avatar
Jody Goldberg committed
892 893 894

	g_return_if_fail (dep != NULL);
	g_return_if_fail (dep->expression != NULL);
Jody Goldberg's avatar
Jody Goldberg committed
895
	g_return_if_fail (!(dep->flags & DEPENDENT_IS_LINKED));
Jody Goldberg's avatar
Jody Goldberg committed
896 897 898
	g_return_if_fail (IS_SHEET (dep->sheet));
	g_return_if_fail (dep->sheet->deps != NULL);

899
	sheet = dep->sheet;
Jody Goldberg's avatar
Jody Goldberg committed
900

901
	/* Make this the new head of the dependent list.  */
902
	dep->prev_dep = NULL;
903
	dep->next_dep = sheet->deps->dependent_list;
904 905
	if (dep->next_dep)
		dep->next_dep->prev_dep = dep;
906
	sheet->deps->dependent_list = dep;
907 908 909
	dep->flags |=
		DEPENDENT_IS_LINKED |
		link_expr_dep (dep, pos, dep->expression);
910 911 912

	if (dep->flags & DEPENDENT_HAS_3D)
		workbook_link_3d_dep (dep);
Jody Goldberg's avatar
Jody Goldberg committed
913 914 915 916 917 918 919
}

/**
 * dependent_unlink:
 * @dep : the dependent that changed
 * @pos: The optionally NULL position of the dependent.
 *
920 921
 * Removes the dependent from its containers set of dependents and always
 * removes the linkages to what it depends on.
Jody Goldberg's avatar
Jody Goldberg committed
922 923 924 925
 */
void
dependent_unlink (Dependent *dep, CellPos const *pos)
{
926
	static CellPos const dummy = { 0, 0 };
Jody Goldberg's avatar
Jody Goldberg committed
927

928
	g_return_if_fail (dep != NULL);
929 930 931 932
	g_return_if_fail (dependent_is_linked (dep));
	g_return_if_fail (dep->expression != NULL);
	g_return_if_fail (IS_SHEET (dep->sheet));

933
	if (pos == NULL)
Jody Goldberg's avatar
typo  
Jody Goldberg committed
934
		pos = &dummy;
935

936
	unlink_expr_dep (dep, pos, dep->expression);
937 938 939 940 941 942 943
	if (dep->sheet->deps != NULL) {
		if (dep->sheet->deps->dependent_list == dep)
			dep->sheet->deps->dependent_list = dep->next_dep;
		if (dep->next_dep)
			dep->next_dep->prev_dep = dep->prev_dep;
		if (dep->prev_dep)
			dep->prev_dep->next_dep = dep->next_dep