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 */ |
44 unsigned length; /* # nodes in use */ |
45 unsigned ntcapacity; /* # nodes allocated */ |
45 unsigned capacity; /* # nodes allocated */ |
46 int ntdepth; /* maximum depth of tree */ |
46 int depth; /* maximum depth of tree */ |
47 int ntsplits; /* # splits performed */ |
47 int splits; /* # splits performed */ |
48 } nodetree; |
48 } nodetree; |
49 |
49 |
50 /* |
50 /* |
51 * This class has two behaviors. |
51 * This class has two behaviors. |
52 * |
52 * |
370 istat(length, "revs in memory"); |
370 istat(length, "revs in memory"); |
371 istat(ntlookups, "node trie lookups"); |
371 istat(ntlookups, "node trie lookups"); |
372 istat(ntmisses, "node trie misses"); |
372 istat(ntmisses, "node trie misses"); |
373 istat(ntrev, "node trie last rev scanned"); |
373 istat(ntrev, "node trie last rev scanned"); |
374 if (self->nt) { |
374 if (self->nt) { |
375 istat(nt->ntcapacity, "node trie capacity"); |
375 istat(nt->capacity, "node trie capacity"); |
376 istat(nt->ntdepth, "node trie depth"); |
376 istat(nt->depth, "node trie depth"); |
377 istat(nt->ntlength, "node trie count"); |
377 istat(nt->length, "node trie count"); |
378 istat(nt->ntsplits, "node trie splits"); |
378 istat(nt->splits, "node trie splits"); |
379 } |
379 } |
380 |
380 |
381 #undef istat |
381 #undef istat |
382 |
382 |
383 return obj; |
383 return obj; |
1016 } |
1016 } |
1017 |
1017 |
1018 static int nt_new(indexObject *self) |
1018 static int nt_new(indexObject *self) |
1019 { |
1019 { |
1020 nodetree *nt = self->nt; |
1020 nodetree *nt = self->nt; |
1021 if (nt->ntlength == nt->ntcapacity) { |
1021 if (nt->length == nt->capacity) { |
1022 if (nt->ntcapacity >= INT_MAX / (sizeof(nodetreenode) * 2)) { |
1022 if (nt->capacity >= INT_MAX / (sizeof(nodetreenode) * 2)) { |
1023 PyErr_SetString(PyExc_MemoryError, |
1023 PyErr_SetString(PyExc_MemoryError, |
1024 "overflow in nt_new"); |
1024 "overflow in nt_new"); |
1025 return -1; |
1025 return -1; |
1026 } |
1026 } |
1027 nt->ntcapacity *= 2; |
1027 nt->capacity *= 2; |
1028 nt->nodes = realloc(nt->nodes, |
1028 nt->nodes = realloc(nt->nodes, |
1029 nt->ntcapacity * sizeof(nodetreenode)); |
1029 nt->capacity * sizeof(nodetreenode)); |
1030 if (nt->nodes == NULL) { |
1030 if (nt->nodes == NULL) { |
1031 PyErr_SetString(PyExc_MemoryError, "out of memory"); |
1031 PyErr_SetString(PyExc_MemoryError, "out of memory"); |
1032 return -1; |
1032 return -1; |
1033 } |
1033 } |
1034 memset(&nt->nodes[nt->ntlength], 0, |
1034 memset(&nt->nodes[nt->length], 0, |
1035 sizeof(nodetreenode) * (nt->ntcapacity - nt->ntlength)); |
1035 sizeof(nodetreenode) * (nt->capacity - nt->length)); |
1036 } |
1036 } |
1037 return nt->ntlength++; |
1037 return nt->length++; |
1038 } |
1038 } |
1039 |
1039 |
1040 static int nt_insert(indexObject *self, const char *node, int rev) |
1040 static int nt_insert(indexObject *self, const char *node, int rev) |
1041 { |
1041 { |
1042 int level = 0; |
1042 int level = 0; |
1070 /* self->nt->nodes may have been changed by realloc */ |
1070 /* self->nt->nodes may have been changed by realloc */ |
1071 self->nt->nodes[off].children[k] = noff; |
1071 self->nt->nodes[off].children[k] = noff; |
1072 off = noff; |
1072 off = noff; |
1073 n = &self->nt->nodes[off]; |
1073 n = &self->nt->nodes[off]; |
1074 n->children[nt_level(oldnode, ++level)] = v; |
1074 n->children[nt_level(oldnode, ++level)] = v; |
1075 if (level > self->nt->ntdepth) |
1075 if (level > self->nt->depth) |
1076 self->nt->ntdepth = level; |
1076 self->nt->depth = level; |
1077 self->nt->ntsplits += 1; |
1077 self->nt->splits += 1; |
1078 } else { |
1078 } else { |
1079 level += 1; |
1079 level += 1; |
1080 off = v; |
1080 off = v; |
1081 } |
1081 } |
1082 } |
1082 } |
1100 } |
1100 } |
1101 if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) { |
1101 if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) { |
1102 PyErr_SetString(PyExc_ValueError, "overflow in nt_init"); |
1102 PyErr_SetString(PyExc_ValueError, "overflow in nt_init"); |
1103 return -1; |
1103 return -1; |
1104 } |
1104 } |
1105 self->nt->ntcapacity = self->raw_length < 4 |
1105 self->nt->capacity = self->raw_length < 4 |
1106 ? 4 : (int)self->raw_length / 2; |
1106 ? 4 : (int)self->raw_length / 2; |
1107 |
1107 |
1108 self->nt->nodes = calloc(self->nt->ntcapacity, sizeof(nodetreenode)); |
1108 self->nt->nodes = calloc(self->nt->capacity, sizeof(nodetreenode)); |
1109 if (self->nt->nodes == NULL) { |
1109 if (self->nt->nodes == NULL) { |
1110 free(self->nt); |
1110 free(self->nt); |
1111 self->nt = NULL; |
1111 self->nt = NULL; |
1112 PyErr_NoMemory(); |
1112 PyErr_NoMemory(); |
1113 return -1; |
1113 return -1; |
1114 } |
1114 } |
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; |
1118 self->nt->depth = 0; |
1119 self->nt->ntsplits = 0; |
1119 self->nt->splits = 0; |
1120 self->nt->ntlength = 1; |
1120 self->nt->length = 1; |
1121 if (nt_insert(self, nullid, -1) == -1) { |
1121 if (nt_insert(self, nullid, -1) == -1) { |
1122 free(self->nt->nodes); |
1122 free(self->nt->nodes); |
1123 free(self->nt); |
1123 free(self->nt); |
1124 self->nt = NULL; |
1124 self->nt = NULL; |
1125 return -1; |
1125 return -1; |