Mercurial > hg-stable

comparison mercurial/cext/revlog.c @ 45131:61e7464477ac

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
phases: sparsify phaseroots and phasesets As final step of dealing with the holes in the phase numbers, make phaseroots and phasesets both dictionaries indexed by the phase number. Further adjust the interface of the C module by pushing the node to revision mapping down as it is cheaper on the C side to deal with revision numbers. Overall, the patch series improves a no-change "hg up" for my NetBSD test repository from 4.7s to 1.3s. Differential Revision: https://phab.mercurial-scm.org/D8698
author Joerg Sonnenberger <joerg@bec.de>
date Wed, 08 Jul 2020 00:36:36 +0200
parents 090a1a78be4a
children 9719e118e4af
comparison
equal deleted inserted replaced
45130:33524b6bef53 45131:61e7464477ac
107 static const char nullid[20] = {0}; 107 static const char nullid[20] = {0};
108 static const Py_ssize_t nullrev = -1; 108 static const Py_ssize_t nullrev = -1;
109 109
110 static Py_ssize_t inline_scan(indexObject *self, const char **offsets); 110 static Py_ssize_t inline_scan(indexObject *self, const char **offsets);
111 111
112 static int index_find_node(indexObject *self, const char *node,
113 Py_ssize_t nodelen);
114
112 #if LONG_MAX == 0x7fffffffL 115 #if LONG_MAX == 0x7fffffffL
113 static const char *const tuple_format = PY23("Kiiiiiis#", "Kiiiiiiy#"); 116 static const char *const tuple_format = PY23("Kiiiiiis#", "Kiiiiiiy#");
114 #else 117 #else
115 static const char *const tuple_format = PY23("kiiiiiis#", "kiiiiiiy#"); 118 static const char *const tuple_format = PY23("kiiiiiis#", "kiiiiiiy#");
116 #endif 119 #endif
573 Py_DECREF(result); 576 Py_DECREF(result);
574 return isfiltered; 577 return isfiltered;
575 } else { 578 } else {
576 return 0; 579 return 0;
577 } 580 }
578 }
579
580 static Py_ssize_t add_roots_get_min(indexObject *self, PyObject *list,
581 Py_ssize_t marker, char *phases)
582 {
583 PyObject *iter = NULL;
584 PyObject *iter_item = NULL;
585 Py_ssize_t min_idx = index_length(self) + 2;
586 long iter_item_long;
587
588 if (PyList_GET_SIZE(list) != 0) {
589 iter = PyObject_GetIter(list);
590 if (iter == NULL)
591 return -2;
592 while ((iter_item = PyIter_Next(iter))) {
593 if (!pylong_to_long(iter_item, &iter_item_long)) {
594 Py_DECREF(iter_item);
595 return -2;
596 }
597 Py_DECREF(iter_item);
598 if (iter_item_long < min_idx)
599 min_idx = iter_item_long;
600 phases[iter_item_long] = (char)marker;
601 }
602 Py_DECREF(iter);
603 }
604
605 return min_idx;
606 } 581 }
607 582
608 static inline void set_phase_from_parents(char *phases, int parent_1, 583 static inline void set_phase_from_parents(char *phases, int parent_1,
609 int parent_2, Py_ssize_t i) 584 int parent_2, Py_ssize_t i)
610 { 585 {
771 free(revstates); 746 free(revstates);
772 free(tovisit); 747 free(tovisit);
773 return NULL; 748 return NULL;
774 } 749 }
775 750
751 static int add_roots_get_min(indexObject *self, PyObject *roots, char *phases,
752 char phase)
753 {
754 Py_ssize_t len = index_length(self);
755 PyObject *iter;
756 PyObject *item;
757 PyObject *iterator;
758 int rev, minrev = -1;
759 char *node;
760
761 if (!PySet_Check(roots))
762 return -2;
763 iterator = PyObject_GetIter(roots);
764 if (iterator == NULL)
765 return -2;
766 while ((item = PyIter_Next(iterator))) {
767 if (node_check(item, &node) == -1)
768 goto failed;
769 rev = index_find_node(self, node, 20);
770 /* null is implicitly public, so negative is invalid */
771 if (rev < 0 || rev >= len)
772 goto failed;
773 phases[rev] = phase;
774 if (minrev == -1 || minrev > rev)
775 minrev = rev;
776 Py_DECREF(item);
777 }
778 Py_DECREF(iterator);
779 return minrev;
780 failed:
781 Py_DECREF(iterator);
782 Py_DECREF(item);
783 return -2;
784 }
785
776 static PyObject *compute_phases_map_sets(indexObject *self, PyObject *args) 786 static PyObject *compute_phases_map_sets(indexObject *self, PyObject *args)
777 { 787 {
788 /* 0: public (untracked), 1: draft, 2: secret, 32: archive,
789 96: internal */
790 static const char trackedphases[] = {1, 2, 32, 96};
791 PyObject *ret = NULL;
778 PyObject *roots = Py_None; 792 PyObject *roots = Py_None;
779 PyObject *ret = NULL; 793 PyObject *idx = NULL;
794 PyObject *pyphase = NULL;
795 PyObject *pyrev = NULL;
796 PyObject *phaseroots = NULL;
780 PyObject *phasessize = NULL; 797 PyObject *phasessize = NULL;
781 PyObject *phaseroots = NULL; 798 PyObject *phasesets[4] = {NULL, NULL, NULL, NULL};
782 PyObject *phaseset = NULL;
783 PyObject *phasessetlist = NULL;
784 PyObject *rev = NULL;
785 Py_ssize_t len = index_length(self); 799 Py_ssize_t len = index_length(self);
786 Py_ssize_t numphase = 0; 800 const char *currentphase;
787 Py_ssize_t minrevallphases = 0;
788 Py_ssize_t minrevphase = 0;
789 Py_ssize_t i = 0;
790 char *phases = NULL; 801 char *phases = NULL;
791 long phase; 802 int minphaserev = -1, rev, i;
803 const int numphases = (int)(sizeof(phasesets) / sizeof(phasesets[0]));
792 804
793 if (!PyArg_ParseTuple(args, "O", &roots)) 805 if (!PyArg_ParseTuple(args, "O", &roots))
794 goto done; 806 return NULL;
795 if (roots == NULL || !PyList_Check(roots)) { 807 if (roots == NULL || !PyDict_Check(roots)) {
796 PyErr_SetString(PyExc_TypeError, "roots must be a list"); 808 PyErr_SetString(PyExc_TypeError, "roots must be a dictionary");
797 goto done; 809 return NULL;
798 } 810 }
799 811
800 phases = calloc( 812 phases = calloc(len, 1);
801 len, 1); /* phase per rev: {0: public, 1: draft, 2: secret} */
802 if (phases == NULL) { 813 if (phases == NULL) {
803 PyErr_NoMemory(); 814 PyErr_NoMemory();
804 goto done; 815 return NULL;
805 } 816 }
806 /* Put the phase information of all the roots in phases */ 817
807 numphase = PyList_GET_SIZE(roots) + 1; 818 for (i = 0; i < numphases; ++i) {
808 minrevallphases = len + 1; 819 pyphase = PyInt_FromLong(trackedphases[i]);
809 phasessetlist = PyList_New(numphase); 820 if (pyphase == NULL)
810 if (phasessetlist == NULL)
811 goto done;
812
813 PyList_SET_ITEM(phasessetlist, 0, Py_None);
814 Py_INCREF(Py_None);
815
816 for (i = 0; i < numphase - 1; i++) {
817 phaseroots = PyList_GET_ITEM(roots, i);
818 phaseset = PySet_New(NULL);
819 if (phaseset == NULL)
820 goto release; 821 goto release;
821 PyList_SET_ITEM(phasessetlist, i + 1, phaseset); 822 phaseroots = PyDict_GetItem(roots, pyphase);
822 if (!PyList_Check(phaseroots)) { 823 Py_DECREF(pyphase);
823 PyErr_SetString(PyExc_TypeError, 824 if (phaseroots == NULL)
824 "roots item must be a list"); 825 continue;
826 rev = add_roots_get_min(self, phaseroots, phases, trackedphases[i]);
827 phaseroots = NULL;
828 if (rev == -2)
825 goto release; 829 goto release;
826 } 830 if (rev != -1 && (minphaserev == -1 || rev < minphaserev))
827 minrevphase = 831 minphaserev = rev;
828 add_roots_get_min(self, phaseroots, i + 1, phases); 832 }
829 if (minrevphase == -2) /* Error from add_roots_get_min */ 833
834 for (i = 0; i < numphases; ++i) {
835 phasesets[i] = PySet_New(NULL);
836 if (phasesets[i] == NULL)
830 goto release; 837 goto release;
831 minrevallphases = MIN(minrevallphases, minrevphase); 838 }
832 } 839
833 /* Propagate the phase information from the roots to the revs */ 840 if (minphaserev == -1)
834 if (minrevallphases != -1) { 841 minphaserev = len;
842 for (rev = minphaserev; rev < len; ++rev) {
835 int parents[2]; 843 int parents[2];
836 for (i = minrevallphases; i < len; i++) { 844 /*
837 if (index_get_parents(self, i, parents, (int)len - 1) < 845 * The parent lookup could be skipped for phaseroots, but
838 0) 846 * phase --force would historically not recompute them
839 goto release; 847 * correctly, leaving descendents with a lower phase around.
840 set_phase_from_parents(phases, parents[0], parents[1], 848 * As such, unconditionally recompute the phase.
841 i); 849 */
842 } 850 if (index_get_parents(self, rev, parents, (int)len - 1) < 0)
843 } 851 goto release;
844 /* Transform phase list to a python list */ 852 set_phase_from_parents(phases, parents[0], parents[1], rev);
853 switch (phases[rev]) {
854 case 0:
855 continue;
856 case 1:
857 pyphase = phasesets[0];
858 break;
859 case 2:
860 pyphase = phasesets[1];
861 break;
862 case 32:
863 pyphase = phasesets[2];
864 break;
865 case 96:
866 pyphase = phasesets[3];
867 break;
868 default:
869 goto release;
870 }
871 pyrev = PyInt_FromLong(rev);
872 if (pyrev == NULL)
873 goto release;
874 if (PySet_Add(pyphase, pyrev) == -1) {
875 Py_DECREF(pyrev);
876 goto release;
877 }
878 Py_DECREF(pyrev);
879 }
880 phaseroots = _dict_new_presized(numphases);
881 if (phaseroots == NULL)
882 goto release;
883 for (int i = 0; i < numphases; ++i) {
884 pyphase = PyInt_FromLong(trackedphases[i]);
885 if (pyphase == NULL)
886 goto release;
887 if (PyDict_SetItem(phaseroots, pyphase, phasesets[i]) == -1) {
888 Py_DECREF(pyphase);
889 goto release;
890 }
891 Py_DECREF(phasesets[i]);
892 phasesets[i] = NULL;
893 }
845 phasessize = PyInt_FromSsize_t(len); 894 phasessize = PyInt_FromSsize_t(len);
846 if (phasessize == NULL) 895 if (phasessize == NULL)
847 goto release; 896 goto release;
848 for (i = 0; i < len; i++) { 897
849 phase = phases[i]; 898 ret = PyTuple_Pack(2, phasessize, phaseroots);
850 /* We only store the sets of phase for non public phase, the 899 Py_DECREF(phasessize);
851 * public phase is computed as a difference */ 900 Py_DECREF(phaseroots);
852 if (phase != 0) { 901 return ret;
853 phaseset = PyList_GET_ITEM(phasessetlist, phase);
854 rev = PyInt_FromSsize_t(i);
855 if (rev == NULL)
856 goto release;
857 PySet_Add(phaseset, rev);
858 Py_XDECREF(rev);
859 }
860 }
861 ret = PyTuple_Pack(2, phasessize, phasessetlist);
862 902
863 release: 903 release:
864 Py_XDECREF(phasessize); 904 for (i = 0; i < numphases; ++i)
865 Py_XDECREF(phasessetlist); 905 Py_XDECREF(phasesets[i]);
866 done: 906 Py_XDECREF(phaseroots);
907
867 free(phases); 908 free(phases);
868 return ret; 909 return NULL;
869 } 910 }
870 911
871 static PyObject *index_headrevs(indexObject *self, PyObject *args) 912 static PyObject *index_headrevs(indexObject *self, PyObject *args)
872 { 913 {
873 Py_ssize_t i, j, len; 914 Py_ssize_t i, j, len;