Mercurial > emacs
comparison src/dispnew.c @ 29980:171ba59e1cb0
(struct row_entry): New structure.
(row_entry_pool, row_entry_pool_size, row_entry_idx, row_table)
(row_table_size, old_lines, new_lines, old_lines_size)
(new_lines_size, run_pool, runs_size, runs): New variables.
(add_row_entry): New function.
(scrolling_window): Use data structures allocated with xmalloc and
held in global variables, instead of allocing them with alloca and
holding them in local variables. Use a larger hash table whose
size depends on glyph matrix sizes. Don't use bzero to clear the
hash table; instead, clear used slots only.
author | Gerd Moellmann <gerd@gnu.org> |
---|---|
date | Wed, 28 Jun 2000 20:28:50 +0000 |
parents | 5d67ef29764b |
children | b20d72b7aa4b |
comparison
equal
deleted
inserted
replaced
29979:6fe8f444b6a3 | 29980:171ba59e1cb0 |
---|---|
4215 vpos = min (w->current_matrix->nrows - 1, vpos); | 4215 vpos = min (w->current_matrix->nrows - 1, vpos); |
4216 rif->cursor_to (vpos, hpos, cy, cx); | 4216 rif->cursor_to (vpos, hpos, cy, cx); |
4217 } | 4217 } |
4218 | 4218 |
4219 | 4219 |
4220 /* Set WINDOW->must_be_updated_p to ON_P for all windows in the window | |
4221 tree rooted at W. */ | |
4222 | |
4223 void | |
4224 set_window_update_flags (w, on_p) | |
4225 struct window *w; | |
4226 int on_p; | |
4227 { | |
4228 while (w) | |
4229 { | |
4230 if (!NILP (w->hchild)) | |
4231 set_window_update_flags (XWINDOW (w->hchild), on_p); | |
4232 else if (!NILP (w->vchild)) | |
4233 set_window_update_flags (XWINDOW (w->vchild), on_p); | |
4234 else | |
4235 w->must_be_updated_p = on_p; | |
4236 | |
4237 w = NILP (w->next) ? 0 : XWINDOW (w->next); | |
4238 } | |
4239 } | |
4240 | |
4241 | |
4242 | |
4243 /*********************************************************************** | |
4244 Window-Based Scrolling | |
4245 ***********************************************************************/ | |
4246 | |
4247 /* Structure describing rows in scrolling_window. */ | |
4248 | |
4249 struct row_entry | |
4250 { | |
4251 /* Number of occurrences of this row in desired and current matrix. */ | |
4252 int old_uses, new_uses; | |
4253 | |
4254 /* Vpos of row in new matrix. */ | |
4255 int new_line_number; | |
4256 | |
4257 /* Bucket index of this row_entry in the hash table row_table. */ | |
4258 int bucket; | |
4259 | |
4260 /* The row described by this entry. */ | |
4261 struct glyph_row *row; | |
4262 | |
4263 /* Hash collision chain. */ | |
4264 struct row_entry *next; | |
4265 }; | |
4266 | |
4267 /* A pool to allocate row_entry structures from, and the size of the | |
4268 pool. The pool is reallocated in scrolling_window when we find | |
4269 that we need a larger one. */ | |
4270 | |
4271 static struct row_entry *row_entry_pool; | |
4272 static int row_entry_pool_size; | |
4273 | |
4274 /* Index of next free entry in row_entry_pool. */ | |
4275 | |
4276 static int row_entry_idx; | |
4277 | |
4278 /* The hash table used during scrolling, and the table's size. This | |
4279 table is used to quickly identify equal rows in the desired and | |
4280 current matrix. */ | |
4281 | |
4282 static struct row_entry **row_table; | |
4283 static int row_table_size; | |
4284 | |
4285 /* Vectors of pointers to row_entry structures belonging to the | |
4286 current and desired matrix, and the size of the vectors. */ | |
4287 | |
4288 static struct row_entry **old_lines, **new_lines; | |
4289 static int old_lines_size, new_lines_size; | |
4290 | |
4291 /* A pool to allocate run structures from, and its size. */ | |
4292 | |
4293 static struct run *run_pool; | |
4294 static int runs_size; | |
4295 | |
4296 /* A vector of runs of lines found during scrolling. */ | |
4297 | |
4298 static struct run **runs; | |
4299 | |
4300 static struct row_entry *add_row_entry P_ ((struct window *, | |
4301 struct glyph_row *)); | |
4302 | |
4303 | |
4304 /* Add glyph row ROW to the scrolling hash table during the scrolling | |
4305 of window W. */ | |
4306 | |
4307 static INLINE struct row_entry * | |
4308 add_row_entry (w, row) | |
4309 struct window *w; | |
4310 struct glyph_row *row; | |
4311 { | |
4312 struct row_entry *entry; | |
4313 int i = row->hash % row_table_size; | |
4314 | |
4315 entry = row_table[i]; | |
4316 while (entry && !row_equal_p (w, entry->row, row)) | |
4317 entry = entry->next; | |
4318 | |
4319 if (entry == NULL) | |
4320 { | |
4321 entry = row_entry_pool + row_entry_idx++; | |
4322 entry->row = row; | |
4323 entry->old_uses = entry->new_uses = 0; | |
4324 entry->new_line_number = 0; | |
4325 entry->bucket = i; | |
4326 entry->next = row_table[i]; | |
4327 row_table[i] = entry; | |
4328 } | |
4329 | |
4330 return entry; | |
4331 } | |
4332 | |
4333 | |
4220 /* Try to reuse part of the current display of W by scrolling lines. | 4334 /* Try to reuse part of the current display of W by scrolling lines. |
4221 HEADER_LINE_P non-zero means W has a top mode line. | 4335 HEADER_LINE_P non-zero means W has a top mode line. |
4222 | 4336 |
4223 The algorithm is taken from Communications of the ACM, Apr78 "A | 4337 The algorithm is taken from Communications of the ACM, Apr78 "A |
4224 Technique for Isolating Differences Between Files." It should take | 4338 Technique for Isolating Differences Between Files." It should take |
4246 static int | 4360 static int |
4247 scrolling_window (w, header_line_p) | 4361 scrolling_window (w, header_line_p) |
4248 struct window *w; | 4362 struct window *w; |
4249 int header_line_p; | 4363 int header_line_p; |
4250 { | 4364 { |
4251 struct symbol | |
4252 { | |
4253 /* Number of occurrences of this line in old and new matrix. */ | |
4254 short old_uses, new_uses; | |
4255 | |
4256 /* Vpos of line in new matrix. */ | |
4257 short new_line_number; | |
4258 | |
4259 /* The line itself. */ | |
4260 struct glyph_row *row; | |
4261 | |
4262 /* Hash collision chain. */ | |
4263 struct symbol *next; | |
4264 }; | |
4265 | |
4266 int SYMBOL_TABLE_SIZE = 101; | |
4267 struct symbol **table; | |
4268 struct symbol **old_line_syms, **new_line_syms; | |
4269 int i, j, first_old, first_new, last_old, last_new; | |
4270 struct symbol *sym; | |
4271 struct run **runs; | |
4272 int nruns; | |
4273 struct glyph_matrix *desired_matrix = w->desired_matrix; | 4365 struct glyph_matrix *desired_matrix = w->desired_matrix; |
4274 struct glyph_matrix *current_matrix = w->current_matrix; | 4366 struct glyph_matrix *current_matrix = w->current_matrix; |
4275 int yb = window_text_bottom_y (w); | 4367 int yb = window_text_bottom_y (w); |
4368 int i, j, first_old, first_new, last_old, last_new; | |
4369 int nruns, nbytes, n, run_idx; | |
4370 struct row_entry *entry; | |
4276 | 4371 |
4277 /* Skip over rows equal at the start. */ | 4372 /* Skip over rows equal at the start. */ |
4278 i = header_line_p ? 1 : 0; | 4373 i = header_line_p ? 1 : 0; |
4279 while (i < current_matrix->nrows - 1 | 4374 while (i < current_matrix->nrows - 1 |
4280 && MATRIX_ROW_ENABLED_P (current_matrix, i) | 4375 && MATRIX_ROW_ENABLED_P (current_matrix, i) |
4281 && MATRIX_ROW_ENABLED_P (desired_matrix, i) | 4376 && MATRIX_ROW_ENABLED_P (desired_matrix, i) |
4282 && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (desired_matrix, i)) < yb | 4377 && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (desired_matrix, i)) <= yb |
4283 && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (current_matrix, i)) < yb | 4378 && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (current_matrix, i)) <= yb |
4284 && row_equal_p (w, | 4379 && row_equal_p (w, |
4285 MATRIX_ROW (desired_matrix, i), | 4380 MATRIX_ROW (desired_matrix, i), |
4286 MATRIX_ROW (current_matrix, i))) | 4381 MATRIX_ROW (current_matrix, i))) |
4287 { | 4382 { |
4288 assign_row (MATRIX_ROW (current_matrix, i), | 4383 assign_row (MATRIX_ROW (current_matrix, i), |
4300 /* Set last_new to the index + 1 of the last enabled row in the | 4395 /* Set last_new to the index + 1 of the last enabled row in the |
4301 desired matrix. */ | 4396 desired matrix. */ |
4302 i = first_new + 1; | 4397 i = first_new + 1; |
4303 while (i < desired_matrix->nrows - 1 | 4398 while (i < desired_matrix->nrows - 1 |
4304 && MATRIX_ROW (desired_matrix, i)->enabled_p | 4399 && MATRIX_ROW (desired_matrix, i)->enabled_p |
4305 && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (desired_matrix, i)) < yb) | 4400 && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (desired_matrix, i)) <= yb) |
4306 ++i; | 4401 ++i; |
4307 | 4402 |
4308 if (!MATRIX_ROW (desired_matrix, i)->enabled_p) | 4403 if (!MATRIX_ROW (desired_matrix, i)->enabled_p) |
4309 return 0; | 4404 return 0; |
4310 | 4405 |
4314 current matrix. We don't look at the enabled flag here because | 4409 current matrix. We don't look at the enabled flag here because |
4315 we plan to reuse part of the display even if other parts are | 4410 we plan to reuse part of the display even if other parts are |
4316 disabled. */ | 4411 disabled. */ |
4317 i = first_old + 1; | 4412 i = first_old + 1; |
4318 while (i < current_matrix->nrows - 1 | 4413 while (i < current_matrix->nrows - 1 |
4319 && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (current_matrix, i)) < yb) | 4414 && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (current_matrix, i)) <= yb) |
4320 ++i; | 4415 ++i; |
4321 last_old = i; | 4416 last_old = i; |
4322 | 4417 |
4323 /* Skip over rows equal at the bottom. */ | 4418 /* Skip over rows equal at the bottom. */ |
4324 i = last_new; | 4419 i = last_new; |
4337 | 4432 |
4338 /* Nothing to do if all rows are equal. */ | 4433 /* Nothing to do if all rows are equal. */ |
4339 if (last_new == first_new) | 4434 if (last_new == first_new) |
4340 return 0; | 4435 return 0; |
4341 | 4436 |
4342 /* Allocate a hash table in which all rows will be inserted. */ | 4437 /* Reallocate vectors, tables etc. if necessary. */ |
4343 table = (struct symbol **) alloca (SYMBOL_TABLE_SIZE * sizeof *table); | 4438 |
4344 bzero (table, SYMBOL_TABLE_SIZE * sizeof *table); | 4439 if (current_matrix->nrows > old_lines_size) |
4345 | 4440 { |
4346 /* For each row in the current matrix, record the symbol belonging | 4441 old_lines_size = current_matrix->nrows; |
4347 to the row in OLD_LINE_SYMS. */ | 4442 nbytes = old_lines_size * sizeof *old_lines; |
4348 old_line_syms = (struct symbol **) alloca (current_matrix->nrows | 4443 old_lines = (struct row_entry **) xrealloc (old_lines, nbytes); |
4349 * sizeof *old_line_syms); | 4444 } |
4350 new_line_syms = (struct symbol **) alloca (desired_matrix->nrows | 4445 |
4351 * sizeof *new_line_syms); | 4446 if (desired_matrix->nrows > new_lines_size) |
4352 | 4447 { |
4353 #define ADDSYM(ROW) \ | 4448 new_lines_size = desired_matrix->nrows; |
4354 do \ | 4449 nbytes = new_lines_size * sizeof *new_lines; |
4355 { \ | 4450 new_lines = (struct row_entry **) xrealloc (new_lines, nbytes); |
4356 struct glyph_row *row_ = (ROW); \ | 4451 } |
4357 int i_ = row_->hash % SYMBOL_TABLE_SIZE; \ | 4452 |
4358 sym = table[i_]; \ | 4453 n = desired_matrix->nrows + current_matrix->nrows; |
4359 while (sym && !row_equal_p (w, sym->row, row_)) \ | 4454 if (3 * n > row_table_size) |
4360 sym = sym->next; \ | 4455 { |
4361 if (sym == NULL) \ | 4456 row_table_size = next_almost_prime (3 * n); |
4362 { \ | 4457 nbytes = row_table_size * sizeof *row_table; |
4363 sym = (struct symbol *) alloca (sizeof *sym); \ | 4458 row_table = (struct row_entry **) xrealloc (row_table, nbytes); |
4364 sym->row = row_; \ | 4459 bzero (row_table, nbytes); |
4365 sym->old_uses = sym->new_uses = 0; \ | 4460 } |
4366 sym->next = table[i_]; \ | 4461 |
4367 table[i_] = sym; \ | 4462 if (n > row_entry_pool_size) |
4368 } \ | 4463 { |
4369 } \ | 4464 row_entry_pool_size = n; |
4370 while (0) | 4465 nbytes = row_entry_pool_size * sizeof *row_entry_pool; |
4371 | 4466 row_entry_pool = (struct row_entry *) xrealloc (row_entry_pool, nbytes); |
4372 /* Add current rows to the symbol table. */ | 4467 } |
4468 | |
4469 if (desired_matrix->nrows > runs_size) | |
4470 { | |
4471 runs_size = desired_matrix->nrows; | |
4472 nbytes = runs_size * sizeof *runs; | |
4473 runs = (struct run **) xrealloc (runs, nbytes); | |
4474 nbytes = runs_size * sizeof *run_pool; | |
4475 run_pool = (struct run *) xrealloc (run_pool, nbytes); | |
4476 } | |
4477 | |
4478 nruns = run_idx = 0; | |
4479 row_entry_idx = 0; | |
4480 | |
4481 /* Add rows from the current and desired matrix to the hash table | |
4482 row_hash_table to be able to find equal ones quickly. */ | |
4483 | |
4373 for (i = first_old; i < last_old; ++i) | 4484 for (i = first_old; i < last_old; ++i) |
4374 { | 4485 { |
4375 if (MATRIX_ROW (current_matrix, i)->enabled_p) | 4486 if (MATRIX_ROW (current_matrix, i)->enabled_p) |
4376 { | 4487 { |
4377 ADDSYM (MATRIX_ROW (current_matrix, i)); | 4488 entry = add_row_entry (w, MATRIX_ROW (current_matrix, i)); |
4378 old_line_syms[i] = sym; | 4489 old_lines[i] = entry; |
4379 ++sym->old_uses; | 4490 ++entry->old_uses; |
4380 } | 4491 } |
4381 else | 4492 else |
4382 old_line_syms[i] = NULL; | 4493 old_lines[i] = NULL; |
4383 } | 4494 } |
4384 | 4495 |
4385 /* Add desired rows to the symbol table. */ | |
4386 for (i = first_new; i < last_new; ++i) | 4496 for (i = first_new; i < last_new; ++i) |
4387 { | 4497 { |
4388 xassert (MATRIX_ROW_ENABLED_P (desired_matrix, i)); | 4498 xassert (MATRIX_ROW_ENABLED_P (desired_matrix, i)); |
4389 ADDSYM (MATRIX_ROW (desired_matrix, i)); | 4499 entry = add_row_entry (w, MATRIX_ROW (desired_matrix, i)); |
4390 ++sym->new_uses; | 4500 ++entry->new_uses; |
4391 new_line_syms[i] = sym; | 4501 entry->new_line_number = i; |
4392 sym->new_line_number = i; | 4502 new_lines[i] = entry; |
4393 } | 4503 } |
4394 | |
4395 #undef ADDSYM | |
4396 | |
4397 /* Record in runs which moves were found, ordered by pixel | |
4398 height of copied areas. */ | |
4399 nruns = 0; | |
4400 runs = (struct run **) alloca (desired_matrix->nrows * sizeof *runs); | |
4401 | 4504 |
4402 /* Identify moves based on lines that are unique and equal | 4505 /* Identify moves based on lines that are unique and equal |
4403 in both matrices. */ | 4506 in both matrices. */ |
4404 for (i = first_old; i < last_old;) | 4507 for (i = first_old; i < last_old;) |
4405 if (old_line_syms[i] | 4508 if (old_lines[i] |
4406 && old_line_syms[i]->old_uses == 1 | 4509 && old_lines[i]->old_uses == 1 |
4407 && old_line_syms[i]->new_uses == 1) | 4510 && old_lines[i]->new_uses == 1) |
4408 { | 4511 { |
4409 int j, k; | 4512 int j, k; |
4410 int new_line = old_line_syms[i]->new_line_number; | 4513 int new_line = old_lines[i]->new_line_number; |
4411 struct run *run = (struct run *) alloca (sizeof *run); | 4514 struct run *run = run_pool + run_idx++; |
4412 | 4515 |
4413 /* Record move. */ | 4516 /* Record move. */ |
4414 run->current_vpos = i; | 4517 run->current_vpos = i; |
4415 run->current_y = MATRIX_ROW (current_matrix, i)->y; | 4518 run->current_y = MATRIX_ROW (current_matrix, i)->y; |
4416 run->desired_vpos = new_line; | 4519 run->desired_vpos = new_line; |
4421 /* Extend backward. */ | 4524 /* Extend backward. */ |
4422 j = i - 1; | 4525 j = i - 1; |
4423 k = new_line - 1; | 4526 k = new_line - 1; |
4424 while (j > first_old | 4527 while (j > first_old |
4425 && k > first_new | 4528 && k > first_new |
4426 && old_line_syms[j] == new_line_syms[k]) | 4529 && old_lines[j] == new_lines[k]) |
4427 { | 4530 { |
4428 int h = MATRIX_ROW (current_matrix, j)->height; | 4531 int h = MATRIX_ROW (current_matrix, j)->height; |
4429 --run->current_vpos; | 4532 --run->current_vpos; |
4430 --run->desired_vpos; | 4533 --run->desired_vpos; |
4431 ++run->nrows; | 4534 ++run->nrows; |
4438 /* Extend forward. */ | 4541 /* Extend forward. */ |
4439 j = i + 1; | 4542 j = i + 1; |
4440 k = new_line + 1; | 4543 k = new_line + 1; |
4441 while (j < last_old | 4544 while (j < last_old |
4442 && k < last_new | 4545 && k < last_new |
4443 && old_line_syms[j] == new_line_syms[k]) | 4546 && old_lines[j] == new_lines[k]) |
4444 { | 4547 { |
4445 int h = MATRIX_ROW (current_matrix, j)->height; | 4548 int h = MATRIX_ROW (current_matrix, j)->height; |
4446 ++run->nrows; | 4549 ++run->nrows; |
4447 run->height += h; | 4550 run->height += h; |
4448 ++j, ++k; | 4551 ++j, ++k; |
4516 to->enabled_p = 1, from->enabled_p = 0; | 4619 to->enabled_p = 1, from->enabled_p = 0; |
4517 to->overlapped_p = to_overlapped_p; | 4620 to->overlapped_p = to_overlapped_p; |
4518 } | 4621 } |
4519 } | 4622 } |
4520 | 4623 |
4624 /* Clear the hash table, for the next time. */ | |
4625 for (i = 0; i < row_entry_idx; ++i) | |
4626 row_table[row_entry_pool[i].bucket] = NULL; | |
4627 | |
4521 /* Value is non-zero to indicate that we scrolled the display. */ | 4628 /* Value is non-zero to indicate that we scrolled the display. */ |
4522 return 1; | 4629 return 1; |
4523 } | 4630 } |
4524 | |
4525 | |
4526 /* Set WINDOW->must_be_updated_p TO ON_P for all windows WINDOW in the | |
4527 window tree rooted at W. */ | |
4528 | |
4529 void | |
4530 set_window_update_flags (w, on_p) | |
4531 struct window *w; | |
4532 int on_p; | |
4533 { | |
4534 while (w) | |
4535 { | |
4536 if (!NILP (w->hchild)) | |
4537 set_window_update_flags (XWINDOW (w->hchild), on_p); | |
4538 else if (!NILP (w->vchild)) | |
4539 set_window_update_flags (XWINDOW (w->vchild), on_p); | |
4540 else | |
4541 w->must_be_updated_p = on_p; | |
4542 | |
4543 w = NILP (w->next) ? 0 : XWINDOW (w->next); | |
4544 } | |
4545 } | |
4546 | 4631 |
4547 | 4632 |
4548 | 4633 |
4549 /************************************************************************ | 4634 /************************************************************************ |
4550 Frame-Based Updates | 4635 Frame-Based Updates |