Mercurial > vim

comparison src/textprop.c @ 29649:a3a966b8b7a7 v9.0.0165

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
patch 9.0.0165: looking up a text property type by ID is slow Commit: https://github.com/vim/vim/commit/e44336b00a6c51bef904450a8012e4982e38ba2d Author: Bram Moolenaar <Bram@vim.org> Date: Sun Aug 7 18:20:08 2022 +0100 patch 9.0.0165: looking up a text property type by ID is slow Problem: Looking up a text property type by ID is slow. Solution: Keep an array of property types sorted on ID.
author Bram Moolenaar <Bram@vim.org>
date Sun, 07 Aug 2022 19:30:03 +0200
parents dd96f3d8ed85
children aa83cf7bef1c
comparison
equal deleted inserted replaced
29648:49cdbb7997e9 29649:a3a966b8b7a7
9 9
10 /* 10 /*
11 * Text properties implementation. See ":help text-properties". 11 * Text properties implementation. See ":help text-properties".
12 * 12 *
13 * TODO: 13 * TODO:
14 * - Adjust text property column and length when text is inserted/deleted.
15 * -> search for changed_bytes() from misc1.c
16 * -> search for mark_col_adjust()
17 * - Perhaps we only need TP_FLAG_CONT_NEXT and can drop TP_FLAG_CONT_PREV?
18 * - Add an array for global_proptypes, to quickly lookup a prop type by ID
19 * - Add an array for b_proptypes, to quickly lookup a prop type by ID
20 * - Checking the text length to detect text properties is slow. Use a flag in 14 * - Checking the text length to detect text properties is slow. Use a flag in
21 * the index, like DB_MARKED? 15 * the index, like DB_MARKED?
22 * - Also test line2byte() with many lines, so that ml_updatechunk() is taken 16 * - Also test line2byte() with many lines, so that ml_updatechunk() is taken
23 * into account. 17 * into account.
24 * - Perhaps have a window-local option to disable highlighting from text 18 * - Perhaps have a window-local option to disable highlighting from text
40 #define HIKEY2PT(p) ((proptype_T *)((p) - offsetof(proptype_T, pt_name))) 34 #define HIKEY2PT(p) ((proptype_T *)((p) - offsetof(proptype_T, pt_name)))
41 #define HI2PT(hi) HIKEY2PT((hi)->hi_key) 35 #define HI2PT(hi) HIKEY2PT((hi)->hi_key)
42 36
43 // The global text property types. 37 // The global text property types.
44 static hashtab_T *global_proptypes = NULL; 38 static hashtab_T *global_proptypes = NULL;
39 static proptype_T **global_proparray = NULL;
45 40
46 // The last used text property type ID. 41 // The last used text property type ID.
47 static int proptype_id = 0; 42 static int proptype_id = 0;
48 43
49 /* 44 /*
50 * Find a property type by name, return the hashitem. 45 * Find a property type by name, return the hashitem.
51 * Returns NULL if the item can't be found. 46 * Returns NULL if the item can't be found.
52 */ 47 */
53 static hashitem_T * 48 static hashitem_T *
54 find_prop_hi(char_u *name, buf_T *buf) 49 find_prop_type_hi(char_u *name, buf_T *buf)
55 { 50 {
56 hashtab_T *ht; 51 hashtab_T *ht;
57 hashitem_T *hi; 52 hashitem_T *hi;
58 53
59 if (*name == NUL) 54 if (*name == NUL)
70 return NULL; 65 return NULL;
71 return hi; 66 return hi;
72 } 67 }
73 68
74 /* 69 /*
75 * Like find_prop_hi() but return the property type. 70 * Like find_prop_type_hi() but return the property type.
76 */ 71 */
77 static proptype_T * 72 static proptype_T *
78 find_prop(char_u *name, buf_T *buf) 73 find_prop_type(char_u *name, buf_T *buf)
79 { 74 {
80 hashitem_T *hi = find_prop_hi(name, buf); 75 hashitem_T *hi = find_prop_type_hi(name, buf);
81 76
82 if (hi == NULL) 77 if (hi == NULL)
83 return NULL; 78 return NULL;
84 return HI2PT(hi); 79 return HI2PT(hi);
85 } 80 }
89 * When not found return zero. 84 * When not found return zero.
90 */ 85 */
91 int 86 int
92 find_prop_type_id(char_u *name, buf_T *buf) 87 find_prop_type_id(char_u *name, buf_T *buf)
93 { 88 {
94 proptype_T *pt = find_prop(name, buf); 89 proptype_T *pt = find_prop_type(name, buf);
95 90
96 if (pt == NULL) 91 if (pt == NULL)
97 return 0; 92 return 0;
98 return pt->pt_id; 93 return pt->pt_id;
99 } 94 }
104 * When not found gives an error message and returns NULL. 99 * When not found gives an error message and returns NULL.
105 */ 100 */
106 static proptype_T * 101 static proptype_T *
107 lookup_prop_type(char_u *name, buf_T *buf) 102 lookup_prop_type(char_u *name, buf_T *buf)
108 { 103 {
109 proptype_T *type = find_prop(name, buf); 104 proptype_T *type = find_prop_type(name, buf);
110 105
111 if (type == NULL) 106 if (type == NULL)
112 type = find_prop(name, NULL); 107 type = find_prop_type(name, NULL);
113 if (type == NULL) 108 if (type == NULL)
114 semsg(_(e_type_not_exist), name); 109 semsg(_(e_type_not_exist), name);
115 return type; 110 return type;
116 } 111 }
117 112
728 curbuf->b_ml.ml_line_ptr = newtext; 723 curbuf->b_ml.ml_line_ptr = newtext;
729 curbuf->b_ml.ml_line_len += proplen; 724 curbuf->b_ml.ml_line_len += proplen;
730 curbuf->b_ml.ml_flags |= ML_LINE_DIRTY; 725 curbuf->b_ml.ml_flags |= ML_LINE_DIRTY;
731 } 726 }
732 727
728 /*
729 * Function passed to qsort() for sorting proptype_T on pt_id.
730 */
731 static int
732 compare_pt(const void *s1, const void *s2)
733 {
734 proptype_T *tp1 = *(proptype_T **)s1;
735 proptype_T *tp2 = *(proptype_T **)s2;
736
737 return tp1->pt_id == tp2->pt_id ? 0 : tp1->pt_id < tp2->pt_id ? -1 : 1;
738 }
739
733 static proptype_T * 740 static proptype_T *
734 find_type_by_id(hashtab_T *ht, int id) 741 find_type_by_id(hashtab_T *ht, proptype_T ***array, int id)
735 { 742 {
736 long todo; 743 int low = 0;
737 hashitem_T *hi; 744 int high;
738 745
739 if (ht == NULL) 746 if (ht == NULL)
740 return NULL; 747 return NULL;
741 748
742 // TODO: Make this faster by keeping a list of types sorted on ID and use 749 // Make the loopup faster by creating an array with pointers to
743 // a binary search. 750 // hashtable entries, sorted on pt_id.
744 751 if (*array == NULL)
745 todo = (long)ht->ht_used; 752 {
746 for (hi = ht->ht_array; todo > 0; ++hi) 753 long todo;
747 { 754 hashitem_T *hi;
748 if (!HASHITEM_EMPTY(hi)) 755 int i = 0;
749 { 756
750 proptype_T *prop = HI2PT(hi); 757 *array = ALLOC_MULT(proptype_T *, ht->ht_used);
751 758 if (*array == NULL)
752 if (prop->pt_id == id) 759 return NULL;
753 return prop; 760 todo = (long)ht->ht_used;
754 --todo; 761 for (hi = ht->ht_array; todo > 0; ++hi)
755 } 762 {
763 if (!HASHITEM_EMPTY(hi))
764 {
765 (*array)[i++] = HI2PT(hi);
766 --todo;
767 }
768 }
769 qsort((void *)*array, ht->ht_used, sizeof(proptype_T *), compare_pt);
770 }
771
772 // binary search in the sorted array
773 high = ht->ht_used;
774 while (high > low)
775 {
776 int m = (high + low) / 2;
777
778 if ((*array)[m]->pt_id == id)
779 return (*array)[m];
780 if ((*array)[m]->pt_id > id)
781 high = m;
782 else
783 low = m + 1;
756 } 784 }
757 return NULL; 785 return NULL;
758 } 786 }
759 787
760 /* 788 /*
770 dict_add_number(dict, "length", prop->tp_len); 798 dict_add_number(dict, "length", prop->tp_len);
771 dict_add_number(dict, "id", prop->tp_id); 799 dict_add_number(dict, "id", prop->tp_id);
772 dict_add_number(dict, "start", !(prop->tp_flags & TP_FLAG_CONT_PREV)); 800 dict_add_number(dict, "start", !(prop->tp_flags & TP_FLAG_CONT_PREV));
773 dict_add_number(dict, "end", !(prop->tp_flags & TP_FLAG_CONT_NEXT)); 801 dict_add_number(dict, "end", !(prop->tp_flags & TP_FLAG_CONT_NEXT));
774 802
775 pt = find_type_by_id(buf->b_proptypes, prop->tp_type); 803 pt = find_type_by_id(buf->b_proptypes, &buf->b_proparray, prop->tp_type);
776 if (pt == NULL) 804 if (pt == NULL)
777 { 805 {
778 pt = find_type_by_id(global_proptypes, prop->tp_type); 806 pt = find_type_by_id(global_proptypes, &global_proparray,
807 prop->tp_type);
779 buflocal = FALSE; 808 buflocal = FALSE;
780 } 809 }
781 if (pt != NULL) 810 if (pt != NULL)
782 dict_add_string(dict, "type", pt->pt_name); 811 dict_add_string(dict, "type", pt->pt_name);
783 812
794 proptype_T * 823 proptype_T *
795 text_prop_type_by_id(buf_T *buf, int id) 824 text_prop_type_by_id(buf_T *buf, int id)
796 { 825 {
797 proptype_T *type; 826 proptype_T *type;
798 827
799 type = find_type_by_id(buf->b_proptypes, id); 828 type = find_type_by_id(buf->b_proptypes, &buf->b_proparray, id);
800 if (type == NULL) 829 if (type == NULL)
801 type = find_type_by_id(global_proptypes, id); 830 type = find_type_by_id(global_proptypes, &global_proparray, id);
802 return type; 831 return type;
803 } 832 }
804 833
805 /* 834 /*
806 * prop_clear({lnum} [, {lnum_end} [, {bufnr}]]) 835 * prop_clear({lnum} [, {lnum_end} [, {bufnr}]])
1521 1550
1522 if (get_bufnr_from_arg(&argvars[1], &buf) == FAIL) 1551 if (get_bufnr_from_arg(&argvars[1], &buf) == FAIL)
1523 return; 1552 return;
1524 dict = argvars[1].vval.v_dict; 1553 dict = argvars[1].vval.v_dict;
1525 1554
1526 prop = find_prop(name, buf); 1555 prop = find_prop_type(name, buf);
1527 if (add) 1556 if (add)
1528 { 1557 {
1529 hashtab_T **htp; 1558 hashtab_T **htp;
1530 1559
1531 if (prop != NULL) 1560 if (prop != NULL)
1537 if (prop == NULL) 1566 if (prop == NULL)
1538 return; 1567 return;
1539 STRCPY(prop->pt_name, name); 1568 STRCPY(prop->pt_name, name);
1540 prop->pt_id = ++proptype_id; 1569 prop->pt_id = ++proptype_id;
1541 prop->pt_flags = PT_FLAG_COMBINE; 1570 prop->pt_flags = PT_FLAG_COMBINE;
1542 htp = buf == NULL ? &global_proptypes : &buf->b_proptypes; 1571 if (buf == NULL)
1572 {
1573 htp = &global_proptypes;
1574 VIM_CLEAR(global_proparray);
1575 }
1576 else
1577 {
1578 htp = &buf->b_proptypes;
1579 VIM_CLEAR(buf->b_proparray);
1580 }
1543 if (*htp == NULL) 1581 if (*htp == NULL)
1544 { 1582 {
1545 *htp = ALLOC_ONE(hashtab_T); 1583 *htp = ALLOC_ONE(hashtab_T);
1546 if (*htp == NULL) 1584 if (*htp == NULL)
1547 { 1585 {
1667 { 1705 {
1668 if (get_bufnr_from_arg(&argvars[1], &buf) == FAIL) 1706 if (get_bufnr_from_arg(&argvars[1], &buf) == FAIL)
1669 return; 1707 return;
1670 } 1708 }
1671 1709
1672 hi = find_prop_hi(name, buf); 1710 hi = find_prop_type_hi(name, buf);
1673 if (hi != NULL) 1711 if (hi != NULL)
1674 { 1712 {
1675 hashtab_T *ht; 1713 hashtab_T *ht;
1676 proptype_T *prop = HI2PT(hi); 1714 proptype_T *prop = HI2PT(hi);
1677 1715
1678 if (buf == NULL) 1716 if (buf == NULL)
1717 {
1679 ht = global_proptypes; 1718 ht = global_proptypes;
1719 VIM_CLEAR(global_proparray);
1720 }
1680 else 1721 else
1722 {
1681 ht = buf->b_proptypes; 1723 ht = buf->b_proptypes;
1724 VIM_CLEAR(buf->b_proparray);
1725 }
1682 hash_remove(ht, hi); 1726 hash_remove(ht, hi);
1683 vim_free(prop); 1727 vim_free(prop);
1684 } 1728 }
1685 } 1729 }
1686 1730
1712 { 1756 {
1713 if (get_bufnr_from_arg(&argvars[1], &buf) == FAIL) 1757 if (get_bufnr_from_arg(&argvars[1], &buf) == FAIL)
1714 return; 1758 return;
1715 } 1759 }
1716 1760
1717 prop = find_prop(name, buf); 1761 prop = find_prop_type(name, buf);
1718 if (prop != NULL) 1762 if (prop != NULL)
1719 { 1763 {
1720 dict_T *d = rettv->vval.v_dict; 1764 dict_T *d = rettv->vval.v_dict;
1721 1765
1722 if (prop->pt_hl_id > 0) 1766 if (prop->pt_hl_id > 0)
1816 void 1860 void
1817 clear_global_prop_types(void) 1861 clear_global_prop_types(void)
1818 { 1862 {
1819 clear_ht_prop_types(global_proptypes); 1863 clear_ht_prop_types(global_proptypes);
1820 global_proptypes = NULL; 1864 global_proptypes = NULL;
1865 VIM_CLEAR(global_proparray);
1821 } 1866 }
1822 #endif 1867 #endif
1823 1868
1824 /* 1869 /*
1825 * Free all property types for "buf". 1870 * Free all property types for "buf".
1827 void 1872 void
1828 clear_buf_prop_types(buf_T *buf) 1873 clear_buf_prop_types(buf_T *buf)
1829 { 1874 {
1830 clear_ht_prop_types(buf->b_proptypes); 1875 clear_ht_prop_types(buf->b_proptypes);
1831 buf->b_proptypes = NULL; 1876 buf->b_proptypes = NULL;
1877 VIM_CLEAR(buf->b_proparray);
1832 } 1878 }
1833 1879
1834 // Struct used to return two values from adjust_prop(). 1880 // Struct used to return two values from adjust_prop().
1835 typedef struct 1881 typedef struct
1836 { 1882 {