Mercurial > hg > index.cgi

comparison lwlib/lw_expr.c @ 337:3b5a45c6ab92

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Speed improvement to lw_expr Instead of using a singly linked list and doing the slow append algorithm when adding an operand to an expression (scan from the start to find the end), now maintain a tail pointer. Also maintain a previous pointer in each entry. Benchmarking suggests this yields a rougly 30% improvement in runtime. Also refactor some of the code in lw_expr.c to make it somewhat clearer to understand. For some values of clearer and understand.
author William Astle <lost@l-w.ca>
date Sat, 02 Aug 2014 10:08:01 -0600
parents 623b62ab774b
children 6138e304ab9a
comparison
equal deleted inserted replaced
336:30b2bad9b5eb 337:3b5a45c6ab92
103 { 103 {
104 lw_expr_t r; 104 lw_expr_t r;
105 105
106 r = lw_alloc(sizeof(struct lw_expr_priv)); 106 r = lw_alloc(sizeof(struct lw_expr_priv));
107 r -> operands = NULL; 107 r -> operands = NULL;
108 r -> operand_tail = NULL;
108 r -> value2 = NULL; 109 r -> value2 = NULL;
109 r -> type = lw_expr_type_int; 110 r -> type = lw_expr_type_int;
110 r -> value = 0; 111 r -> value = 0;
111 return r; 112 return r;
112 } 113 }
113 114
115 static lw_expr_t lw_expr_remove_operand(lw_expr_t E, struct lw_expr_opers *o)
116 {
117 lw_expr_t r;
118 if (E -> operands == o)
119 E -> operands = o -> next;
120 else
121 o -> prev -> next = o -> next;
122
123 if (E -> operand_tail == o)
124 E -> operand_tail = o -> prev;
125 else
126 o -> next -> prev = o -> prev;
127
128 r = o -> p;
129 lw_free(o);
130 return r;
131 }
132
133 void lw_expr_destroy(lw_expr_t E);
134 static void lw_expr_remove_operands(lw_expr_t E)
135 {
136 while (E -> operands)
137 lw_expr_destroy(lw_expr_remove_operand(E, E -> operands));
138 }
139
114 void lw_expr_destroy(lw_expr_t E) 140 void lw_expr_destroy(lw_expr_t E)
115 { 141 {
116 struct lw_expr_opers *o;
117 if (!E) 142 if (!E)
118 return; 143 return;
119 while (E -> operands) 144 lw_expr_remove_operands(E);
120 {
121 o = E -> operands;
122 E -> operands = o -> next;
123 lw_expr_destroy(o -> p);
124 lw_free(o);
125 }
126 if (E -> type == lw_expr_type_var) 145 if (E -> type == lw_expr_type_var)
127 lw_free(E -> value2); 146 lw_free(E -> value2);
128 lw_free(E); 147 lw_free(E);
129 } 148 }
130 149
151 return r; 170 return r;
152 } 171 }
153 172
154 void lw_expr_add_operand(lw_expr_t E, lw_expr_t O) 173 void lw_expr_add_operand(lw_expr_t E, lw_expr_t O)
155 { 174 {
156 struct lw_expr_opers *o, *t; 175 struct lw_expr_opers *o;
157 176
158 o = lw_alloc(sizeof(struct lw_expr_opers)); 177 o = lw_alloc(sizeof(struct lw_expr_opers));
159 o -> p = lw_expr_copy(O); 178 o -> p = lw_expr_copy(O);
160 o -> next = NULL; 179 o -> next = NULL;
161 for (t = E -> operands; t && t -> next; t = t -> next) 180 o -> prev = E -> operand_tail;
162 /* do nothing */ ; 181
163 182 if (E -> operands)
164 if (t) 183 E -> operand_tail -> next = o;
165 t -> next = o;
166 else 184 else
167 E -> operands = o; 185 E -> operands = o;
186 E -> operand_tail = o;
168 } 187 }
169 188
170 lw_expr_t lw_expr_build_aux(int exprtype, va_list args) 189 lw_expr_t lw_expr_build_aux(int exprtype, va_list args)
171 { 190 {
172 lw_expr_t r; 191 lw_expr_t r;
420 { 439 {
421 if (o -> p -> type == lw_expr_type_oper && (o -> p -> value == lw_expr_oper_times || o -> p -> value == lw_expr_oper_plus)) 440 if (o -> p -> type == lw_expr_type_oper && (o -> p -> value == lw_expr_oper_times || o -> p -> value == lw_expr_oper_plus))
422 lw_expr_simplify_sortconstfirst(o -> p); 441 lw_expr_simplify_sortconstfirst(o -> p);
423 } 442 }
424 443
425 for (o = E -> operands; o; o = o -> next) 444 for (o = E -> operands; o; )
426 { 445 {
446 struct lw_expr_opers *o2;
447 o2 = o -> next;
427 if (o -> p -> type == lw_expr_type_int && o != E -> operands) 448 if (o -> p -> type == lw_expr_type_int && o != E -> operands)
428 { 449 {
429 struct lw_expr_opers *o2; 450 // because o cannot be the first operand, we don't have to
430 for (o2 = E -> operands; o2 -> next != o; o2 = o2 -> next) 451 // handle the single element list here
431 /* do nothing */ ; 452 o2 = o -> next;
432 o2 -> next = o -> next; 453 if (E -> operand_tail == o)
454 E -> operand_tail = o -> prev;
455 o -> prev -> next = o -> next;
456 if (o -> next)
457 o -> next -> prev = o -> prev;
458 E -> operands -> prev = o;
433 o -> next = E -> operands; 459 o -> next = E -> operands;
460 o -> prev = NULL;
434 E -> operands = o; 461 E -> operands = o;
435 o = o2; 462 E -> operands = o;
436 } 463 }
464 o = o2;
437 } 465 }
438 } 466 }
439 467
440 void lw_expr_sortoperandlist(struct lw_expr_opers **o) 468 void lw_expr_sortoperandlist(struct lw_expr_opers **o)
441 { 469 {
583 lw_expr_destroy(o -> p); 611 lw_expr_destroy(o -> p);
584 if (E -> type == lw_expr_type_var) 612 if (E -> type == lw_expr_type_var)
585 lw_free(E -> value2); 613 lw_free(E -> value2);
586 *E = *te; 614 *E = *te;
587 E -> operands = NULL; 615 E -> operands = NULL;
588 616 E -> operand_tail = NULL;
617
589 if (te -> type == lw_expr_type_var) 618 if (te -> type == lw_expr_type_var)
590 E -> value2 = lw_strdup(te -> value2); 619 E -> value2 = lw_strdup(te -> value2);
591 for (o = te -> operands; o; o = o -> next) 620 for (o = te -> operands; o; o = o -> next)
592 { 621 {
593 lw_expr_t xxx; 622 lw_expr_t xxx;
614 lw_expr_destroy(o -> p); 643 lw_expr_destroy(o -> p);
615 if (E -> type == lw_expr_type_var) 644 if (E -> type == lw_expr_type_var)
616 lw_free(E -> value2); 645 lw_free(E -> value2);
617 *E = *te; 646 *E = *te;
618 E -> operands = NULL; 647 E -> operands = NULL;
648 E -> operand_tail = NULL;
619 649
620 if (te -> type == lw_expr_type_var) 650 if (te -> type == lw_expr_type_var)
621 E -> value2 = lw_strdup(te -> value2); 651 E -> value2 = lw_strdup(te -> value2);
622 for (o = te -> operands; o; o = o -> next) 652 for (o = te -> operands; o; o = o -> next)
623 { 653 {
639 tryagainplus: 669 tryagainplus:
640 for (o = E -> operands; o; o = o -> next) 670 for (o = E -> operands; o; o = o -> next)
641 { 671 {
642 if (o -> p -> type == lw_expr_type_oper && o -> p -> value == lw_expr_oper_plus) 672 if (o -> p -> type == lw_expr_type_oper && o -> p -> value == lw_expr_oper_plus)
643 { 673 {
644 struct lw_expr_opers *o2; 674 if (o -> p -> operands)
645 // we have a + operation - bring operands up 675 {
646 676 if (E -> operands == NULL)
647 for (o2 = E -> operands; o2 && o2 -> next != o; o2 = o2 -> next) 677 {
648 /* do nothing */ ; 678 E -> operands = o -> p -> operands;
649 if (o2) 679 E -> operand_tail = o -> p -> operand_tail;
650 o2 -> next = o -> p -> operands; 680 }
651 else 681 else
652 E -> operands = o -> p -> operands; 682 {
653 for (o2 = o -> p -> operands; o2 -> next; o2 = o2 -> next) 683 E -> operand_tail -> next = o -> p -> operands;
654 /* do nothing */ ; 684 o -> p -> operands -> prev = E -> operand_tail;
655 o2 -> next = o -> next; 685 E -> operand_tail = o -> p -> operand_tail;
686 }
687 o -> p -> operands = NULL;
688 o -> p -> operand_tail = NULL;
689 }
656 o -> p -> operands = NULL; 690 o -> p -> operands = NULL;
657 lw_expr_destroy(o -> p); 691 lw_expr_destroy(o -> p);
692 if (o -> prev)
693 o -> prev -> next = o -> next;
694 else
695 E -> operands = o -> next;
696 if (o -> next)
697 o -> next -> prev = o -> prev;
698 else
699 E -> operand_tail = o -> prev;
658 lw_free(o); 700 lw_free(o);
659 goto tryagainplus; 701 goto tryagainplus;
660 } 702 }
661 } 703 }
662 } 704 }
667 tryagaintimes: 709 tryagaintimes:
668 for (o = E -> operands; o; o = o -> next) 710 for (o = E -> operands; o; o = o -> next)
669 { 711 {
670 if (o -> p -> type == lw_expr_type_oper && o -> p -> value == lw_expr_oper_times) 712 if (o -> p -> type == lw_expr_type_oper && o -> p -> value == lw_expr_oper_times)
671 { 713 {
672 struct lw_expr_opers *o2; 714 if (o -> p -> operands)
673 // we have a + operation - bring operands up 715 {
674 716 if (E -> operands == NULL)
675 for (o2 = E -> operands; o2 && o2 -> next != o; o2 = o2 -> next) 717 {
676 /* do nothing */ ; 718 E -> operands = o -> p -> operands;
677 if (o2) 719 E -> operand_tail = o -> p -> operand_tail;
678 o2 -> next = o -> p -> operands; 720 }
679 else 721 else
680 E -> operands = o -> p -> operands; 722 {
681 for (o2 = o -> p -> operands; o2 -> next; o2 = o2 -> next) 723 E -> operand_tail -> next = o -> p -> operands;
682 /* do nothing */ ; 724 o -> p -> operands -> prev = E -> operand_tail;
683 o2 -> next = o -> next; 725 E -> operand_tail = o -> p -> operand_tail;
726 }
727 o -> p -> operands = NULL;
728 o -> p -> operand_tail = NULL;
729 }
684 o -> p -> operands = NULL; 730 o -> p -> operands = NULL;
685 lw_expr_destroy(o -> p); 731 lw_expr_destroy(o -> p);
732 if (o -> prev)
733 o -> prev -> next = o -> next;
734 else
735 E -> operands = o -> next;
736 if (o -> next)
737 o -> next -> prev = o -> prev;
738 else
739 E -> operand_tail = o -> prev;
686 lw_free(o); 740 lw_free(o);
687 goto tryagaintimes; 741 goto tryagaintimes;
688 } 742 }
689 } 743 }
690 } 744 }
783 tr = E -> operands -> p -> value || E -> operands -> next -> p -> value; 837 tr = E -> operands -> p -> value || E -> operands -> next -> p -> value;
784 break; 838 break;
785 839
786 } 840 }
787 841
788 while (E -> operands) 842 lw_expr_remove_operands(E);
789 {
790 o = E -> operands;
791 E -> operands = o -> next;
792 lw_expr_destroy(o -> p);
793 lw_free(o);
794 }
795 E -> type = lw_expr_type_int; 843 E -> type = lw_expr_type_int;
796 E -> value = tr; 844 E -> value = tr;
797 return; 845 return;
798 } 846 }
799 847
802 lw_expr_t e1; 850 lw_expr_t e1;
803 int cval = 0; 851 int cval = 0;
804 852
805 e1 = lw_expr_create(); 853 e1 = lw_expr_create();
806 e1 -> operands = E -> operands; 854 e1 -> operands = E -> operands;
855 e1 -> operand_tail = E -> operand_tail;
807 E -> operands = 0; 856 E -> operands = 0;
857 E -> operand_tail = NULL;
808 858
809 for (o = e1 -> operands; o; o = o -> next) 859 for (o = e1 -> operands; o; o = o -> next)
810 { 860 {
811 if (o -> p -> type == lw_expr_type_int) 861 if (o -> p -> type == lw_expr_type_int)
812 cval += o -> p -> value; 862 cval += o -> p -> value;
827 lw_expr_t e1; 877 lw_expr_t e1;
828 int cval = 1; 878 int cval = 1;
829 879
830 e1 = lw_expr_create(); 880 e1 = lw_expr_create();
831 e1 -> operands = E -> operands; 881 e1 -> operands = E -> operands;
882 e1 -> operand_tail = E -> operand_tail;
832 E -> operands = 0; 883 E -> operands = 0;
884 E -> operand_tail = NULL;
833 885
834 for (o = e1 -> operands; o; o = o -> next) 886 for (o = e1 -> operands; o; o = o -> next)
835 { 887 {
836 if (o -> p -> type == lw_expr_type_int) 888 if (o -> p -> type == lw_expr_type_int)
837 cval *= o -> p -> value; 889 cval *= o -> p -> value;
852 for (o = E -> operands; o; o = o -> next) 904 for (o = E -> operands; o; o = o -> next)
853 { 905 {
854 if (o -> p -> type == lw_expr_type_int && o -> p -> value == 0) 906 if (o -> p -> type == lw_expr_type_int && o -> p -> value == 0)
855 { 907 {
856 // one operand of times is 0, replace operation with 0 908 // one operand of times is 0, replace operation with 0
857 while (E -> operands) 909 lw_expr_remove_operands(E);
858 {
859 o = E -> operands;
860 E -> operands = o -> next;
861 lw_expr_destroy(o -> p);
862 lw_free(o);
863 }
864 E -> type = lw_expr_type_int; 910 E -> type = lw_expr_type_int;
865 E -> value = 0; 911 E -> value = 0;
866 return; 912 return;
867 } 913 }
868 } 914 }
962 o = E -> operands; 1008 o = E -> operands;
963 if (o -> p -> type != lw_expr_type_int || o -> p -> value != 0) 1009 if (o -> p -> type != lw_expr_type_int || o -> p -> value != 0)
964 { 1010 {
965 r = lw_expr_copy(o -> p); 1011 r = lw_expr_copy(o -> p);
966 } 1012 }
967 E -> operands = o -> next; 1013 lw_expr_destroy(lw_expr_remove_operand(E, E -> operands));
968 lw_expr_destroy(o -> p);
969 lw_free(o);
970 } 1014 }
971 *E = *r; 1015 *E = *r;
972 lw_free(r); 1016 lw_free(r);
973 return; 1017 return;
974 } 1018 }
975 else if (c == 0) 1019 else if (c == 0)
976 { 1020 {
977 // replace with 0 1021 // replace with 0
978 while (E -> operands) 1022 lw_expr_remove_operands(E);
979 {
980 o = E -> operands;
981 E -> operands = o -> next;
982 lw_expr_destroy(o -> p);
983 lw_free(o);
984 }
985 E -> type = lw_expr_type_int; 1023 E -> type = lw_expr_type_int;
986 E -> value = 0; 1024 E -> value = 0;
987 return; 1025 return;
988 } 1026 }
989 else if (c != t) 1027 else if (c != t)
990 { 1028 {
991 // collapse out zero terms 1029 // collapse out zero terms
992 struct lw_expr_opers *o2; 1030 struct lw_expr_opers *o2;
993 1031
994 for (o = E -> operands; o; o = o -> next) 1032 for (o = E -> operands; o; o = o2)
995 { 1033 {
1034 o2 = o -> next;
996 if (o -> p -> type == lw_expr_type_int && o -> p -> value == 0) 1035 if (o -> p -> type == lw_expr_type_int && o -> p -> value == 0)
997 { 1036 {
998 if (o == E -> operands) 1037 lw_expr_destroy(lw_expr_remove_operand(E, o));
999 {
1000 E -> operands = o -> next;
1001 lw_expr_destroy(o -> p);
1002 lw_free(o);
1003 o = E -> operands;
1004 }
1005 else
1006 {
1007 for (o2 = E -> operands; o2 -> next == o; o2 = o2 -> next)
1008 /* do nothing */ ;
1009 o2 -> next = o -> next;
1010 lw_expr_destroy(o -> p);
1011 lw_free(o);
1012 o = o2;
1013 }
1014 } 1038 }
1015 } 1039 }
1016 } 1040 }
1017 return; 1041 return;
1018 } 1042 }
1033 if (E2 -> type == lw_expr_type_oper && E2 -> value == lw_expr_oper_plus) 1057 if (E2 -> type == lw_expr_type_oper && E2 -> value == lw_expr_oper_plus)
1034 { 1058 {
1035 lw_free(E -> operands -> next); 1059 lw_free(E -> operands -> next);
1036 lw_free(E -> operands); 1060 lw_free(E -> operands);
1037 E -> operands = NULL; 1061 E -> operands = NULL;
1062 E -> operand_tail = NULL;
1038 E -> value = lw_expr_oper_plus; 1063 E -> value = lw_expr_oper_plus;
1039 1064
1040 for (o = E2 -> operands; o; o = o -> next) 1065 for (o = E2 -> operands; o; o = o -> next)
1041 { 1066 {
1042 t1 = lw_expr_build(lw_expr_type_oper, lw_expr_oper_times, E3, o -> p); 1067 t1 = lw_expr_build(lw_expr_type_oper, lw_expr_oper_times, E3, o -> p);
1043 lw_expr_add_operand(E, t1); 1068 lw_expr_add_operand(E, t1);
1044 lw_expr_destroy(t1); 1069 lw_expr_destroy(t1);
1045 } 1070 }
1046
1047 lw_expr_destroy(E2);
1048 lw_expr_destroy(E3);
1049 } 1071 }
1050 } 1072 }
1051 else if (E -> operands -> next -> p -> type == lw_expr_type_int) 1073 else if (E -> operands -> next -> p -> type == lw_expr_type_int)
1052 { 1074 {
1053 /* <other> TIMES <int> */ 1075 /* <other> TIMES <int> */
1056 if (E2 -> type == lw_expr_type_oper && E2 -> value == lw_expr_oper_plus) 1078 if (E2 -> type == lw_expr_type_oper && E2 -> value == lw_expr_oper_plus)
1057 { 1079 {
1058 lw_free(E -> operands -> next); 1080 lw_free(E -> operands -> next);
1059 lw_free(E -> operands); 1081 lw_free(E -> operands);
1060 E -> operands = NULL; 1082 E -> operands = NULL;
1083 E -> operand_tail = NULL;
1061 E -> value = lw_expr_oper_plus; 1084 E -> value = lw_expr_oper_plus;
1062 1085
1063 for (o = E2 -> operands; o; o = o -> next) 1086 for (o = E2 -> operands; o; o = o -> next)
1064 { 1087 {
1065 t1 = lw_expr_build(lw_expr_type_oper, lw_expr_oper_times, E3, o -> p); 1088 t1 = lw_expr_build(lw_expr_type_oper, lw_expr_oper_times, E3, o -> p);