Lines Matching +full:node +full:- +full:version
3 // Licensed under the Apache License, Version 2.0 (the "License");
7 // https://www.apache.org/licenses/LICENSE-2.0
25 // (1) Maintain a rank for each node that is consistent
28 // (2) When a new edge (x->y) is inserted, do nothing if rank[x] < rank[y].
32 // This file is a no-op if the required LowLevelAlloc support is missing.
90 const T& back() const { return ptr_[size_-1]; } in back()
91 void pop_back() { size_--; } in pop_back()
113 if (src->ptr_ == src->space_) { in MoveFrom()
115 resize(src->size_); in MoveFrom()
116 std::copy(src->ptr_, src->ptr_ + src->size_, ptr_); in MoveFrom()
117 src->size_ = 0; in MoveFrom()
120 ptr_ = src->ptr_; in MoveFrom()
121 size_ = src->size_; in MoveFrom()
122 capacity_ = src->capacity_; in MoveFrom()
123 src->Init(); in MoveFrom()
159 // A hash set of non-negative int32_t that uses Vec for its underlying storage.
179 if (occupied_ >= table_.size() - table_.size()/4) Grow(); in insert()
192 // HASH_FOR_EACH(elem, node->out) { ... }
208 enum : int32_t { kEmpty = -1, kDel = -2 };
210 uint32_t occupied_; // Count of non-empty slots (includes deleted slots)
217 const uint32_t mask = table_.size() - 1; in FindIndex()
219 int deleted_index = -1; // If >= 0, index of first deleted element we see in FindIndex()
258 // We encode a node index and a node version in GraphId. The version
262 inline GraphId MakeId(int32_t index, uint32_t version) { in MakeId() argument
265 (static_cast<uint64_t>(version) << 32) | static_cast<uint32_t>(index); in MakeId()
277 struct Node { struct
278 int32_t rank; // rank number assigned by Pearce-Kelly algorithm
279 uint32_t version; // Current version number member
281 bool visited; // Temporary marker used by depth-first-search
282 uintptr_t masked_ptr; // User-supplied pointer
287 void* stack[40]; // stack[0,nstack-1] holds stack trace for node.
290 // Hash table for pointer to node index lookups.
293 explicit PointerMap(const Vec<Node*>* nodes) : nodes_(nodes) { in PointerMap()
294 table_.fill(-1); in PointerMap()
299 for (int32_t i = table_[Hash(ptr)]; i != -1;) { in Find()
300 Node* n = (*nodes_)[i]; in Find()
301 if (n->masked_ptr == masked) return i; in Find()
302 i = n->next_hash; in Find()
304 return -1; in Find()
309 (*nodes_)[i]->next_hash = *head; in Add()
317 for (int32_t* slot = &table_[Hash(ptr)]; *slot != -1; ) { in Remove()
319 Node* n = (*nodes_)[index]; in Remove()
320 if (n->masked_ptr == masked) { in Remove()
321 *slot = n->next_hash; // Remove n from linked list in Remove()
322 n->next_hash = -1; in Remove()
325 slot = &n->next_hash; in Remove()
327 return -1; in Remove()
334 const Vec<Node*>* nodes_;
345 Vec<Node*> nodes_;
354 Vec<int32_t> stack_; // Emulates recursion stack for depth-first searches
359 static Node* FindNode(GraphCycles::Rep* rep, GraphId id) { in FindNode()
360 Node* n = rep->nodes_[NodeIndex(id)]; in FindNode()
361 return (n->version == NodeVersion(id)) ? n : nullptr; in FindNode()
371 for (auto* node : rep_->nodes_) { in ~GraphCycles() local
372 node->Node::~Node(); in ~GraphCycles()
373 base_internal::LowLevelAlloc::Free(node); in ~GraphCycles()
375 rep_->Rep::~Rep(); in ~GraphCycles()
382 for (uint32_t x = 0; x < r->nodes_.size(); x++) { in CheckInvariants()
383 Node* nx = r->nodes_[x]; in CheckInvariants()
384 void* ptr = base_internal::UnhidePtr<void>(nx->masked_ptr); in CheckInvariants()
385 if (ptr != nullptr && static_cast<uint32_t>(r->ptrmap_.Find(ptr)) != x) { in CheckInvariants()
386 ABSL_RAW_LOG(FATAL, "Did not find live node in hash table %u %p", x, ptr); in CheckInvariants()
388 if (nx->visited) { in CheckInvariants()
389 ABSL_RAW_LOG(FATAL, "Did not clear visited marker on node %u", x); in CheckInvariants()
391 if (!ranks.insert(nx->rank)) { in CheckInvariants()
392 ABSL_RAW_LOG(FATAL, "Duplicate occurrence of rank %d", nx->rank); in CheckInvariants()
394 HASH_FOR_EACH(y, nx->out) { in CheckInvariants()
395 Node* ny = r->nodes_[y]; in CheckInvariants()
396 if (nx->rank >= ny->rank) { in CheckInvariants()
397 ABSL_RAW_LOG(FATAL, "Edge %u->%d has bad rank assignment %d->%d", x, y, in CheckInvariants()
398 nx->rank, ny->rank); in CheckInvariants()
406 int32_t i = rep_->ptrmap_.Find(ptr); in GetId()
407 if (i != -1) { in GetId()
408 return MakeId(i, rep_->nodes_[i]->version); in GetId()
409 } else if (rep_->free_nodes_.empty()) { in GetId()
410 Node* n = in GetId()
411 new (base_internal::LowLevelAlloc::AllocWithArena(sizeof(Node), arena)) in GetId()
412 Node; in GetId()
413 n->version = 1; // Avoid 0 since it is used by InvalidGraphId() in GetId()
414 n->visited = false; in GetId()
415 n->rank = rep_->nodes_.size(); in GetId()
416 n->masked_ptr = base_internal::HidePtr(ptr); in GetId()
417 n->nstack = 0; in GetId()
418 n->priority = 0; in GetId()
419 rep_->nodes_.push_back(n); in GetId()
420 rep_->ptrmap_.Add(ptr, n->rank); in GetId()
421 return MakeId(n->rank, n->version); in GetId()
424 // a permutation of [0,rep_->nodes_.size()-1]. in GetId()
425 int32_t r = rep_->free_nodes_.back(); in GetId()
426 rep_->free_nodes_.pop_back(); in GetId()
427 Node* n = rep_->nodes_[r]; in GetId()
428 n->masked_ptr = base_internal::HidePtr(ptr); in GetId()
429 n->nstack = 0; in GetId()
430 n->priority = 0; in GetId()
431 rep_->ptrmap_.Add(ptr, r); in GetId()
432 return MakeId(r, n->version); in GetId()
437 int32_t i = rep_->ptrmap_.Remove(ptr); in RemoveNode()
438 if (i == -1) { in RemoveNode()
441 Node* x = rep_->nodes_[i]; in RemoveNode()
442 HASH_FOR_EACH(y, x->out) { in RemoveNode()
443 rep_->nodes_[y]->in.erase(i); in RemoveNode()
445 HASH_FOR_EACH(y, x->in) { in RemoveNode()
446 rep_->nodes_[y]->out.erase(i); in RemoveNode()
448 x->in.clear(); in RemoveNode()
449 x->out.clear(); in RemoveNode()
450 x->masked_ptr = base_internal::HidePtr<void>(nullptr); in RemoveNode()
451 if (x->version == std::numeric_limits<uint32_t>::max()) { in RemoveNode()
454 x->version++; // Invalidates all copies of node. in RemoveNode()
455 rep_->free_nodes_.push_back(i); in RemoveNode()
460 Node* n = FindNode(rep_, id); in Ptr()
462 : base_internal::UnhidePtr<void>(n->masked_ptr); in Ptr()
465 bool GraphCycles::HasNode(GraphId node) { in HasNode() argument
466 return FindNode(rep_, node) != nullptr; in HasNode()
470 Node* xn = FindNode(rep_, x); in HasEdge()
471 return xn && FindNode(rep_, y) && xn->out.contains(NodeIndex(y)); in HasEdge()
475 Node* xn = FindNode(rep_, x); in RemoveEdge()
476 Node* yn = FindNode(rep_, y); in RemoveEdge()
478 xn->out.erase(NodeIndex(y)); in RemoveEdge()
479 yn->in.erase(NodeIndex(x)); in RemoveEdge()
488 static void Sort(const Vec<Node*>&, Vec<int32_t>* delta);
496 Node* nx = FindNode(r, idx); in InsertEdge()
497 Node* ny = FindNode(r, idy); in InsertEdge()
501 if (!nx->out.insert(y)) { in InsertEdge()
506 ny->in.insert(x); in InsertEdge()
508 if (nx->rank <= ny->rank) { in InsertEdge()
514 // We only need to consider nodes that fall in the range [ny->rank,nx->rank]. in InsertEdge()
515 if (!ForwardDFS(r, y, nx->rank)) { in InsertEdge()
517 nx->out.erase(y); in InsertEdge()
518 ny->in.erase(x); in InsertEdge()
521 for (const auto& d : r->deltaf_) { in InsertEdge()
522 r->nodes_[d]->visited = false; in InsertEdge()
526 BackwardDFS(r, x, ny->rank); in InsertEdge()
534 r->deltaf_.clear(); in ForwardDFS()
535 r->stack_.clear(); in ForwardDFS()
536 r->stack_.push_back(n); in ForwardDFS()
537 while (!r->stack_.empty()) { in ForwardDFS()
538 n = r->stack_.back(); in ForwardDFS()
539 r->stack_.pop_back(); in ForwardDFS()
540 Node* nn = r->nodes_[n]; in ForwardDFS()
541 if (nn->visited) continue; in ForwardDFS()
543 nn->visited = true; in ForwardDFS()
544 r->deltaf_.push_back(n); in ForwardDFS()
546 HASH_FOR_EACH(w, nn->out) { in ForwardDFS()
547 Node* nw = r->nodes_[w]; in ForwardDFS()
548 if (nw->rank == upper_bound) { in ForwardDFS()
551 if (!nw->visited && nw->rank < upper_bound) { in ForwardDFS()
552 r->stack_.push_back(w); in ForwardDFS()
560 r->deltab_.clear(); in BackwardDFS()
561 r->stack_.clear(); in BackwardDFS()
562 r->stack_.push_back(n); in BackwardDFS()
563 while (!r->stack_.empty()) { in BackwardDFS()
564 n = r->stack_.back(); in BackwardDFS()
565 r->stack_.pop_back(); in BackwardDFS()
566 Node* nn = r->nodes_[n]; in BackwardDFS()
567 if (nn->visited) continue; in BackwardDFS()
569 nn->visited = true; in BackwardDFS()
570 r->deltab_.push_back(n); in BackwardDFS()
572 HASH_FOR_EACH(w, nn->in) { in BackwardDFS()
573 Node* nw = r->nodes_[w]; in BackwardDFS()
574 if (!nw->visited && lower_bound < nw->rank) { in BackwardDFS()
575 r->stack_.push_back(w); in BackwardDFS()
582 Sort(r->nodes_, &r->deltab_); in Reorder()
583 Sort(r->nodes_, &r->deltaf_); in Reorder()
586 r->list_.clear(); in Reorder()
587 MoveToList(r, &r->deltab_, &r->list_); in Reorder()
588 MoveToList(r, &r->deltaf_, &r->list_); in Reorder()
591 r->merged_.resize(r->deltab_.size() + r->deltaf_.size()); in Reorder()
592 std::merge(r->deltab_.begin(), r->deltab_.end(), in Reorder()
593 r->deltaf_.begin(), r->deltaf_.end(), in Reorder()
594 r->merged_.begin()); in Reorder()
597 for (uint32_t i = 0; i < r->list_.size(); i++) { in Reorder()
598 r->nodes_[r->list_[i]]->rank = r->merged_[i]; in Reorder()
602 static void Sort(const Vec<Node*>& nodes, Vec<int32_t>* delta) { in Sort()
604 const Vec<Node*>* nodes; in Sort()
606 return (*nodes)[a]->rank < (*nodes)[b]->rank; in Sort()
611 std::sort(delta->begin(), delta->end(), cmp); in Sort()
618 v = r->nodes_[w]->rank; // Replace v entry with its rank in MoveToList()
619 r->nodes_[w]->visited = false; // Prepare for future DFS calls in MoveToList()
620 dst->push_back(w); in MoveToList()
632 // As we descend into a node, we push it onto the path. in FindPath()
633 // As we leave a node, we remove it from the path. in FindPath()
637 r->stack_.clear(); in FindPath()
638 r->stack_.push_back(x); in FindPath()
639 while (!r->stack_.empty()) { in FindPath()
640 int32_t n = r->stack_.back(); in FindPath()
641 r->stack_.pop_back(); in FindPath()
643 // Marker to indicate that we are leaving a node in FindPath()
644 path_len--; in FindPath()
649 path[path_len] = MakeId(n, rep_->nodes_[n]->version); in FindPath()
652 r->stack_.push_back(-1); // Will remove tentative path entry in FindPath()
658 HASH_FOR_EACH(w, r->nodes_[n]->out) { in FindPath()
660 r->stack_.push_back(w); in FindPath()
674 Node* n = FindNode(rep_, id); in UpdateStackTrace()
675 if (n == nullptr || n->priority >= priority) { in UpdateStackTrace()
678 n->nstack = (*get_stack_trace)(n->stack, ABSL_ARRAYSIZE(n->stack)); in UpdateStackTrace()
679 n->priority = priority; in UpdateStackTrace()
683 Node* n = FindNode(rep_, id); in GetStackTrace()
688 *ptr = n->stack; in GetStackTrace()
689 return n->nstack; in GetStackTrace()