Mercurial Mercurial > public > mercurial-scm > hg / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
mercurial/cext/revlog.c
changeset 38913 c2c253558e3c
parent 38912 d1bc0e7c862b
child 38914 f28e64bbdd29
equal deleted inserted replaced
38912:d1bc0e7c862b 38913:c2c253558e3c 
    39  * Negative value is a leaf: -(rev + 2)
 
    39  * Negative value is a leaf: -(rev + 2)
 
    40  * Zero is empty
 
    40  * Zero is empty
 
    41  */
 
    41  */
 
    42 typedef struct {
 
    42 typedef struct {
 
    43 	nodetreenode *nodes;
 
    43 	nodetreenode *nodes;
 
       
    44 	unsigned ntlength;     /* # nodes in use */
 
       
    45 	unsigned ntcapacity;   /* # nodes allocated */
 
       
    46 	int ntdepth;           /* maximum depth of tree */
 
       
    47 	int ntsplits;          /* # splits performed */
 
    44 } nodetree;
 
    48 } nodetree;
 
    45 
    49 
    46 /*
 
    50 /*
 
    47  * This class has two behaviors.
 
    51  * This class has two behaviors.
 
    48  *
 
    52  *
 
    66 	Py_ssize_t length;     /* current number of elements */
 
    70 	Py_ssize_t length;     /* current number of elements */
 
    67 	PyObject *added;       /* populated on demand */
 
    71 	PyObject *added;       /* populated on demand */
 
    68 	PyObject *headrevs;    /* cache, invalidated on changes */
 
    72 	PyObject *headrevs;    /* cache, invalidated on changes */
 
    69 	PyObject *filteredrevs;/* filtered revs set */
 
    73 	PyObject *filteredrevs;/* filtered revs set */
 
    70 	nodetree *nt;          /* base-16 trie */
 
    74 	nodetree *nt;          /* base-16 trie */
 
    71 	unsigned ntlength;          /* # nodes in use */
 
       
    72 	unsigned ntcapacity;        /* # nodes allocated */
 
       
    73 	int ntdepth;           /* maximum depth of tree */
 
       
    74 	int ntsplits;          /* # splits performed */
 
       
    75 	int ntrev;             /* last rev scanned */
 
    75 	int ntrev;             /* last rev scanned */
 
    76 	int ntlookups;         /* # lookups */
 
    76 	int ntlookups;         /* # lookups */
 
    77 	int ntmisses;          /* # lookups that miss the cache */
 
    77 	int ntmisses;          /* # lookups that miss the cache */
 
    78 	int inlined;
 
    78 	int inlined;
 
    79 } indexObject;
 
    79 } indexObject;
 
   330 }
 
   330 }
 
   331 
   331 
   332 static PyObject *index_clearcaches(indexObject *self)
 
   332 static PyObject *index_clearcaches(indexObject *self)
 
   333 {
 
   333 {
 
   334 	_index_clearcaches(self);
 
   334 	_index_clearcaches(self);
 
   335 	self->ntlength = self->ntcapacity = 0;
 
       
   336 	self->ntdepth = self->ntsplits = 0;
 
       
   337 	self->ntrev = -1;
 
   335 	self->ntrev = -1;
 
   338 	self->ntlookups = self->ntmisses = 0;
 
   336 	self->ntlookups = self->ntmisses = 0;
 
   339 	Py_RETURN_NONE;
 
   337 	Py_RETURN_NONE;
 
   340 }
 
   338 }
 
   341 
   339 
   368 	}
 
   366 	}
 
   369 
   367 
   370 	if (self->raw_length != self->length - 1)
 
   368 	if (self->raw_length != self->length - 1)
 
   371 		istat(raw_length, "revs on disk");
 
   369 		istat(raw_length, "revs on disk");
 
   372 	istat(length, "revs in memory");
 
   370 	istat(length, "revs in memory");
 
   373 	istat(ntcapacity, "node trie capacity");
 
       
   374 	istat(ntdepth, "node trie depth");
 
       
   375 	istat(ntlength, "node trie count");
 
       
   376 	istat(ntlookups, "node trie lookups");
 
   371 	istat(ntlookups, "node trie lookups");
 
   377 	istat(ntmisses, "node trie misses");
 
   372 	istat(ntmisses, "node trie misses");
 
   378 	istat(ntrev, "node trie last rev scanned");
 
   373 	istat(ntrev, "node trie last rev scanned");
 
   379 	istat(ntsplits, "node trie splits");
 
   374 	if (self->nt) {
 
       
   375 		istat(nt->ntcapacity, "node trie capacity");
 
       
   376 		istat(nt->ntdepth, "node trie depth");
 
       
   377 		istat(nt->ntlength, "node trie count");
 
       
   378 		istat(nt->ntsplits, "node trie splits");
 
       
   379 	}
 
   380 
   380 
   381 #undef istat
 
   381 #undef istat
 
   382 
   382 
   383 	return obj;
 
   383 	return obj;
 
   384 
   384 
  1015 	return -4;
 
  1015 	return -4;
 
  1016 }
 
  1016 }
 
  1017 
  1017 
  1018 static int nt_new(indexObject *self)
 
  1018 static int nt_new(indexObject *self)
 
  1019 {
 
  1019 {
 
  1020 	if (self->ntlength == self->ntcapacity) {
 
  1020 	nodetree *nt = self->nt;
 
  1021 		if (self->ntcapacity >= INT_MAX / (sizeof(nodetreenode) * 2)) {
 
  1021 	if (nt->ntlength == nt->ntcapacity) {
 
       
  1022 		if (nt->ntcapacity >= INT_MAX / (sizeof(nodetreenode) * 2)) {
 
  1022 			PyErr_SetString(PyExc_MemoryError,
 
  1023 			PyErr_SetString(PyExc_MemoryError,
 
  1023 					"overflow in nt_new");
 
  1024 					"overflow in nt_new");
 
  1024 			return -1;
 
  1025 			return -1;
 
  1025 		}
 
  1026 		}
 
  1026 		self->ntcapacity *= 2;
 
  1027 		nt->ntcapacity *= 2;
 
  1027 		self->nt->nodes = realloc(self->nt->nodes,
 
  1028 		nt->nodes = realloc(nt->nodes,
 
  1028 					  self->ntcapacity * sizeof(nodetreenode));
 
  1029 				    nt->ntcapacity * sizeof(nodetreenode));
 
  1029 		if (self->nt->nodes == NULL) {
 
  1030 		if (nt->nodes == NULL) {
 
  1030 			PyErr_SetString(PyExc_MemoryError, "out of memory");
 
  1031 			PyErr_SetString(PyExc_MemoryError, "out of memory");
 
  1031 			return -1;
 
  1032 			return -1;
 
  1032 		}
 
  1033 		}
 
  1033 		memset(&self->nt->nodes[self->ntlength], 0,
 
  1034 		memset(&nt->nodes[nt->ntlength], 0,
 
  1034 		       sizeof(nodetreenode) * (self->ntcapacity - self->ntlength));
 
  1035 		       sizeof(nodetreenode) * (nt->ntcapacity - nt->ntlength));
 
  1035 	}
 
  1036 	}
 
  1036 	return self->ntlength++;
 
  1037 	return nt->ntlength++;
 
  1037 }
 
  1038 }
 
  1038 
  1039 
  1039 static int nt_insert(indexObject *self, const char *node, int rev)
 
  1040 static int nt_insert(indexObject *self, const char *node, int rev)
 
  1040 {
 
  1041 {
 
  1041 	int level = 0;
 
  1042 	int level = 0;
 
  1069 			/* self->nt->nodes may have been changed by realloc */
 
  1070 			/* self->nt->nodes may have been changed by realloc */
 
  1070 			self->nt->nodes[off].children[k] = noff;
 
  1071 			self->nt->nodes[off].children[k] = noff;
 
  1071 			off = noff;
 
  1072 			off = noff;
 
  1072 			n = &self->nt->nodes[off];
 
  1073 			n = &self->nt->nodes[off];
 
  1073 			n->children[nt_level(oldnode, ++level)] = v;
 
  1074 			n->children[nt_level(oldnode, ++level)] = v;
 
  1074 			if (level > self->ntdepth)
 
  1075 			if (level > self->nt->ntdepth)
 
  1075 				self->ntdepth = level;
 
  1076 				self->nt->ntdepth = level;
 
  1076 			self->ntsplits += 1;
 
  1077 			self->nt->ntsplits += 1;
 
  1077 		} else {
 
  1078 		} else {
 
  1078 			level += 1;
 
  1079 			level += 1;
 
  1079 			off = v;
 
  1080 			off = v;
 
  1080 		}
 
  1081 		}
 
  1081 	}
 
  1082 	}
 
  1099 		}
 
  1100 		}
 
  1100 		if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) {
 
  1101 		if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) {
 
  1101 			PyErr_SetString(PyExc_ValueError, "overflow in nt_init");
 
  1102 			PyErr_SetString(PyExc_ValueError, "overflow in nt_init");
 
  1102 			return -1;
 
  1103 			return -1;
 
  1103 		}
 
  1104 		}
 
  1104 		self->ntcapacity = self->raw_length < 4
 
  1105 		self->nt->ntcapacity = self->raw_length < 4
 
  1105 			? 4 : (int)self->raw_length / 2;
 
  1106 			? 4 : (int)self->raw_length / 2;
 
  1106 
  1107 
  1107 		self->nt->nodes = calloc(self->ntcapacity, sizeof(nodetreenode));
 
  1108 		self->nt->nodes = calloc(self->nt->ntcapacity, sizeof(nodetreenode));
 
  1108 		if (self->nt->nodes == NULL) {
 
  1109 		if (self->nt->nodes == NULL) {
 
  1109 			free(self->nt);
 
  1110 			free(self->nt);
 
  1110 			self->nt = NULL;
 
  1111 			self->nt = NULL;
 
  1111 			PyErr_NoMemory();
 
  1112 			PyErr_NoMemory();
 
  1112 			return -1;
 
  1113 			return -1;
 
  1113 		}
 
  1114 		}
 
  1114 		self->ntlength = 1;
 
       
  1115 		self->ntrev = (int)index_length(self);
 
  1115 		self->ntrev = (int)index_length(self);
 
  1116 		self->ntlookups = 1;
 
  1116 		self->ntlookups = 1;
 
  1117 		self->ntmisses = 0;
 
  1117 		self->ntmisses = 0;
 
       
  1118 		self->nt->ntdepth = 0;
 
       
  1119 		self->nt->ntsplits = 0;
 
       
  1120 		self->nt->ntlength = 1;
 
  1118 		if (nt_insert(self, nullid, -1) == -1) {
 
  1121 		if (nt_insert(self, nullid, -1) == -1) {
 
  1119 			free(self->nt->nodes);
 
  1122 			free(self->nt->nodes);
 
  1120 			free(self->nt);
 
  1123 			free(self->nt);
 
  1121 			self->nt = NULL;
 
  1124 			self->nt = NULL;
 
  1122 			return -1;
 
  1125 			return -1;
 
  1979 	size = self->buf.len;
 
  1982 	size = self->buf.len;
 
  1980 
  1983 
  1981 	self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
 
  1984 	self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
 
  1982 	self->data = data_obj;
 
  1985 	self->data = data_obj;
 
  1983 
  1986 
  1984 	self->ntlength = self->ntcapacity = 0;
 
       
  1985 	self->ntdepth = self->ntsplits = 0;
 
       
  1986 	self->ntlookups = self->ntmisses = 0;
 
  1987 	self->ntlookups = self->ntmisses = 0;
 
  1987 	self->ntrev = -1;
 
  1988 	self->ntrev = -1;
 
  1988 	Py_INCREF(self->data);
 
  1989 	Py_INCREF(self->data);
 
  1989 
  1990 
  1990 	if (self->inlined) {
 
  1991 	if (self->inlined) {
mercurial-scm/hg