Mercurial > vim

comparison src/structs.h @ 2730:e0a90042318d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
updated for version 7.3.143 Problem: Memfile is not tested sufficiently. Looking up blocks in a memfile is slow when there are many blocks. Solution: Add high level test and unittest. Adjust the number of hash buckets to the number of blocks. (Ivan Krasilnikov)
author Bram Moolenaar <bram@vim.org>
date Tue, 22 Mar 2011 18:10:45 +0100
parents cd3f52531f6c
children 8bd38abda314
comparison
equal deleted inserted replaced
2729:12f838be9c59 2730:e0a90042318d
376 typedef struct block_hdr bhdr_T; 376 typedef struct block_hdr bhdr_T;
377 typedef struct memfile memfile_T; 377 typedef struct memfile memfile_T;
378 typedef long blocknr_T; 378 typedef long blocknr_T;
379 379
380 /* 380 /*
381 * mf_hashtab_T is a chained hashtable with blocknr_T key and arbitrary
382 * structures as items. This is an intrusive data structure: we require
383 * that items begin with mf_hashitem_T which contains the key and linked
384 * list pointers. List of items in each bucket is doubly-linked.
385 */
386
387 typedef struct mf_hashitem_S mf_hashitem_T;
388
389 struct mf_hashitem_S
390 {
391 mf_hashitem_T *mhi_next;
392 mf_hashitem_T *mhi_prev;
393 blocknr_T mhi_key;
394 };
395
396 #define MHT_INIT_SIZE 64
397
398 typedef struct mf_hashtab_S
399 {
400 long_u mht_mask; /* mask used for hash value (nr of items
401 * in array is "mht_mask" + 1) */
402 long_u mht_count; /* nr of items inserted into hashtable */
403 mf_hashitem_T **mht_buckets; /* points to mht_small_buckets or
404 *dynamically allocated array */
405 mf_hashitem_T *mht_small_buckets[MHT_INIT_SIZE]; /* initial buckets */
406 char mht_fixed; /* non-zero value forbids growth */
407 } mf_hashtab_T;
408
409 /*
381 * for each (previously) used block in the memfile there is one block header. 410 * for each (previously) used block in the memfile there is one block header.
382 * 411 *
383 * The block may be linked in the used list OR in the free list. 412 * The block may be linked in the used list OR in the free list.
384 * The used blocks are also kept in hash lists. 413 * The used blocks are also kept in hash lists.
385 * 414 *
392 * the contents of the block in the file (if any) is irrelevant. 421 * the contents of the block in the file (if any) is irrelevant.
393 */ 422 */
394 423
395 struct block_hdr 424 struct block_hdr
396 { 425 {
426 mf_hashitem_T bh_hashitem; /* header for hash table and key */
427 #define bh_bnum bh_hashitem.mhi_key /* block number, part of bh_hashitem */
428
397 bhdr_T *bh_next; /* next block_hdr in free or used list */ 429 bhdr_T *bh_next; /* next block_hdr in free or used list */
398 bhdr_T *bh_prev; /* previous block_hdr in used list */ 430 bhdr_T *bh_prev; /* previous block_hdr in used list */
399 bhdr_T *bh_hash_next; /* next block_hdr in hash list */
400 bhdr_T *bh_hash_prev; /* previous block_hdr in hash list */
401 blocknr_T bh_bnum; /* block number */
402 char_u *bh_data; /* pointer to memory (for used block) */ 431 char_u *bh_data; /* pointer to memory (for used block) */
403 int bh_page_count; /* number of pages in this block */ 432 int bh_page_count; /* number of pages in this block */
404 433
405 #define BH_DIRTY 1 434 #define BH_DIRTY 1
406 #define BH_LOCKED 2 435 #define BH_LOCKED 2
415 */ 444 */
416 typedef struct nr_trans NR_TRANS; 445 typedef struct nr_trans NR_TRANS;
417 446
418 struct nr_trans 447 struct nr_trans
419 { 448 {
420 NR_TRANS *nt_next; /* next nr_trans in hash list */ 449 mf_hashitem_T nt_hashitem; /* header for hash table and key */
421 NR_TRANS *nt_prev; /* previous nr_trans in hash list */ 450 #define nt_old_bnum nt_hashitem.mhi_key /* old, negative, number */
422 blocknr_T nt_old_bnum; /* old, negative, number */ 451
423 blocknr_T nt_new_bnum; /* new, positive, number */ 452 blocknr_T nt_new_bnum; /* new, positive, number */
424 }; 453 };
425 454
426 /* 455 /*
427 * structure used to store one block of the stuff/redo/recording buffers 456 * structure used to store one block of the stuff/redo/recording buffers
497 # endif 526 # endif
498 } cmdmod_T; 527 } cmdmod_T;
499 528
500 typedef struct file_buffer buf_T; /* forward declaration */ 529 typedef struct file_buffer buf_T; /* forward declaration */
501 530
502 /*
503 * Simplistic hashing scheme to quickly locate the blocks in the used list.
504 * 64 blocks are found directly (64 * 4K = 256K, most files are smaller).
505 */
506 #define MEMHASHSIZE 64
507 #define MEMHASH(nr) ((nr) & (MEMHASHSIZE - 1))
508 #define MF_SEED_LEN 8 531 #define MF_SEED_LEN 8
509 532
510 struct memfile 533 struct memfile
511 { 534 {
512 char_u *mf_fname; /* name of the file */ 535 char_u *mf_fname; /* name of the file */
515 bhdr_T *mf_free_first; /* first block_hdr in free list */ 538 bhdr_T *mf_free_first; /* first block_hdr in free list */
516 bhdr_T *mf_used_first; /* mru block_hdr in used list */ 539 bhdr_T *mf_used_first; /* mru block_hdr in used list */
517 bhdr_T *mf_used_last; /* lru block_hdr in used list */ 540 bhdr_T *mf_used_last; /* lru block_hdr in used list */
518 unsigned mf_used_count; /* number of pages in used list */ 541 unsigned mf_used_count; /* number of pages in used list */
519 unsigned mf_used_count_max; /* maximum number of pages in memory */ 542 unsigned mf_used_count_max; /* maximum number of pages in memory */
520 bhdr_T *mf_hash[MEMHASHSIZE]; /* array of hash lists */ 543 mf_hashtab_T mf_hash; /* hash lists */
521 NR_TRANS *mf_trans[MEMHASHSIZE]; /* array of trans lists */ 544 mf_hashtab_T mf_trans; /* trans lists */
522 blocknr_T mf_blocknr_max; /* highest positive block number + 1*/ 545 blocknr_T mf_blocknr_max; /* highest positive block number + 1*/
523 blocknr_T mf_blocknr_min; /* lowest negative block number - 1 */ 546 blocknr_T mf_blocknr_min; /* lowest negative block number - 1 */
524 blocknr_T mf_neg_count; /* number of negative blocks numbers */ 547 blocknr_T mf_neg_count; /* number of negative blocks numbers */
525 blocknr_T mf_infile_count; /* number of pages in the file */ 548 blocknr_T mf_infile_count; /* number of pages in the file */
526 unsigned mf_page_size; /* number of bytes in a page */ 549 unsigned mf_page_size; /* number of bytes in a page */