| 90 | } |
| 91 | |
| 92 | int DiskAnnAlgorithm::inter_insert(diskann_id_t id, |
| 93 | std::vector<diskann_id_t> &pruned_list, |
| 94 | DiskAnnContext *ctx) { |
| 95 | DistCalculator &dc = ctx->dist_calculator(); |
| 96 | |
| 97 | for (auto &des : pruned_list) { |
| 98 | std::vector<diskann_id_t> new_neighbors; |
| 99 | bool need_prune = false; |
| 100 | |
| 101 | { |
| 102 | auto lock = lock_for(des); |
| 103 | |
| 104 | auto neighbors = entity_.get_neighbors(des); |
| 105 | |
| 106 | bool found = false; |
| 107 | for (size_t i = 0; i < neighbors.first; ++i) { |
| 108 | if ((neighbors.second)[i] == id) { |
| 109 | found = true; |
| 110 | break; |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | if (!found) { |
| 115 | if (neighbors.first < |
| 116 | static_cast<uint64_t>(DiskAnnEntity::kDefaultGraphSlackFactor * |
| 117 | max_degree_)) { |
| 118 | int ret = entity_.add_neighbor(des, id); |
| 119 | if (ret != 0) return ret; |
| 120 | need_prune = false; |
| 121 | } else { |
| 122 | new_neighbors.resize(neighbors.first + 1); |
| 123 | memcpy(&new_neighbors[0], neighbors.second, |
| 124 | sizeof(diskann_id_t) * neighbors.first); |
| 125 | |
| 126 | new_neighbors[neighbors.first] = id; |
| 127 | |
| 128 | need_prune = true; |
| 129 | } |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | if (need_prune) { |
| 134 | std::set<diskann_id_t> new_visited; |
| 135 | std::vector<Neighbor> new_pool(0); |
| 136 | |
| 137 | size_t reserve_size = static_cast<size_t>(std::ceil( |
| 138 | 1.05 * DiskAnnEntity::kDefaultGraphSlackFactor * max_degree_)); |
| 139 | |
| 140 | new_pool.reserve(reserve_size); |
| 141 | |
| 142 | for (auto node_id : new_neighbors) { |
| 143 | if (new_visited.find(node_id) == new_visited.end() && node_id != des) { |
| 144 | float dist = dc.dist(des, node_id); |
| 145 | new_pool.emplace_back(Neighbor(node_id, dist)); |
| 146 | new_visited.insert(node_id); |
| 147 | } |
| 148 | } |
| 149 |
nothing calls this directly
no test coverage detected