{"action":"created","comment":{"url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments/61537187","id":61537187,"diff_hunk":"@@ -0,0 +1,153 @@\n+/**\n+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,\n+ *     University of Wisconsin—Madison.\n+ *\n+ *   Licensed under the Apache License, Version 2.0 (the \"License\");\n+ *   you may not use this file except in compliance with the License.\n+ *   You may obtain a copy of the License at\n+ *\n+ *       http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ *   Unless required by applicable law or agreed to in writing, software\n+ *   distributed under the License is distributed on an \"AS IS\" BASIS,\n+ *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ *   See the License for the specific language governing permissions and\n+ *   limitations under the License.\n+ **/\n+\n+#ifndef QUICKSTEP_TRANSACTION_DEAD_LOCK_DETECTOR_HPP_\n+#define QUICKSTEP_TRANSACTION_DEAD_LOCK_DETECTOR_HPP_\n+\n+#include <atomic>\n+#include <memory>\n+#include <unordered_map>\n+#include <vector>\n+\n+#include \"transaction/DirectedGraph.hpp\"\n+#include \"transaction/Lock.hpp\"\n+#include \"transaction/LockTable.hpp\"\n+#include \"transaction/ResourceId.hpp\"\n+#include \"transaction/Transaction.hpp\"\n+#include \"threading/Thread.hpp\"\n+\n+namespace quickstep {\n+namespace transaction {\n+\n+/** \\addtogroup Transaction\n+ *  @{\n+ */\n+\n+/**\n+ * @brief Notification mechanism between LockManager and DeadLockDetector.\n+ **/\n+enum class DeadLockDetectorStatus {\n+  kNotReady = 0,\n+  kDone,\n+  kQuit,\n+};\n+\n+/**\n+ * @brief Class for deadlock detection on wait-for graph.\n+ **/\n+class DeadLockDetector : public Thread {\n+ public:\n+  typedef std::unordered_map<transaction_id, DirectedGraph::node_id>\n+      transaction_id_node_map;\n+  /**\n+   * @brief Constructor for DeadLockDetector.\n+   *\n+   * @param lock_table Pointer to lock table, which this class gets the\n+   *        necessary information.\n+   * @param status Pointer to status object which will act as a message\n+   *        passing algorithm between LockManager.\n+   * @paramsstd::atomic<DeadLockDetectorStatus> &status_;\n+   **/\n+  DeadLockDetector(LockTable *lock_table,\n+                   std::atomic<DeadLockDetectorStatus> *status,\n+                   std::vector<DirectedGraph::node_id> *victims);\n+\n+  void run() override;\n+\n+  /**\n+   * @brief Adds pending information based on a resource conflict.\n+   *\n+   * @param pending Id of the transaction that waits for the resource lock.\n+   * @param owner Id of the transaction that owns the resource lock.\n+   */\n+  void addPendingInfo(transaction_id pending,\n+                      transaction_id owner);\n+\n+  /**\n+   * @brief Deletes pending information on a resource.\n+   *\n+   * @param pending Id of the transaction that waits for the resource lock.\n+   * @param owner Id of the transaction that owns the resource lock.\n+   *\n+   * @warning This method is not implemented yet.\n+   */\n+  void deletePendingInfo(transaction_id pending,\n+                         transaction_id owner);\n+\n+  /**\n+   * @brief Check whether first transaction waits for the latter.\n+   *\n+   * @param pending Id of the transaction which will be checked whether\n+   *        it waits for the other.\n+   * @param owner Id of the transaction which will be checked whether\n+   *        it is waited by the first.\n+   *\n+   * @warning This method is not implemented yet.\n+   */\n+  bool isDependent(transaction_id pending, transaction_id owner);\n+\n+  /**\n+   * @brief Gives the ids of transactions that wait for the owner transaction.\n+   *\n+   * @param owner Id of the transaction whose the penders will be returned.\n+   * @return Vector of transaction ids that wait for owner.\n+   */\n+  std::vector<transaction_id> getAllDependents(transaction_id owner);\n+\n+  /**\n+   * @brief Gives the ids of transaction that the pending transaction waits for.\n+   * @warning This method is not implemented yet.\n+\n+   * @param pending Id of the transaction that is pending.\n+   * @return Vector of transaction ids which the pending transaction waits for.\n+   */\n+  std::vector<transaction_id> getAllDependees(transaction_id pending);\n+\n+  /**\n+   * @brief Gives the list of victims whose the terminations will end the cycle.\n+   *\n+   * @return Vector of victim transaction ids.\n+   */\n+  std::vector<transaction_id> getAllVictims();\n+\n+ private:\n+  static constexpr std::int64_t kSleepDuration = 5;\n+\n+  DirectedGraph::node_id getNodeId(transaction_id tid);\n+\n+  DirectedGraph::node_id addNode(transaction_id tid);","path":"transaction/DeadLockDetector.hpp","position":132,"original_position":132,"commit_id":"97060a5cb62eaa6df1807059edab9c787a0111fd","original_commit_id":"97060a5cb62eaa6df1807059edab9c787a0111fd","user":{"login":"zuyu","id":2245572,"avatar_url":"https://avatars.githubusercontent.com/u/2245572?v=3","gravatar_id":"","url":"https://api.github.com/users/zuyu","html_url":"https://github.com/zuyu","followers_url":"https://api.github.com/users/zuyu/followers","following_url":"https://api.github.com/users/zuyu/following{/other_user}","gists_url":"https://api.github.com/users/zuyu/gists{/gist_id}","starred_url":"https://api.github.com/users/zuyu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/zuyu/subscriptions","organizations_url":"https://api.github.com/users/zuyu/orgs","repos_url":"https://api.github.com/users/zuyu/repos","events_url":"https://api.github.com/users/zuyu/events{/privacy}","received_events_url":"https://api.github.com/users/zuyu/received_events","type":"User","site_admin":false},"body":"In this file, please mark arguments `const` when possible.","created_at":"2016-04-29T06:10:22Z","updated_at":"2016-04-29T06:10:22Z","html_url":"https://github.com/pivotalsoftware/quickstep/pull/187#discussion_r61537187","pull_request_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/187","_links":{"self":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments/61537187"},"html":{"href":"https://github.com/pivotalsoftware/quickstep/pull/187#discussion_r61537187"},"pull_request":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/187"}}},"pull_request":{"url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/187","id":67446262,"html_url":"https://github.com/pivotalsoftware/quickstep/pull/187","diff_url":"https://github.com/pivotalsoftware/quickstep/pull/187.diff","patch_url":"https://github.com/pivotalsoftware/quickstep/pull/187.patch","issue_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/187","number":187,"state":"open","locked":false,"title":"Transaction Part 4: LockManager, CycleDetector and DeadLockDetector.","user":{"login":"hakanmemisoglu","id":2506341,"avatar_url":"https://avatars.githubusercontent.com/u/2506341?v=3","gravatar_id":"","url":"https://api.github.com/users/hakanmemisoglu","html_url":"https://github.com/hakanmemisoglu","followers_url":"https://api.github.com/users/hakanmemisoglu/followers","following_url":"https://api.github.com/users/hakanmemisoglu/following{/other_user}","gists_url":"https://api.github.com/users/hakanmemisoglu/gists{/gist_id}","starred_url":"https://api.github.com/users/hakanmemisoglu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hakanmemisoglu/subscriptions","organizations_url":"https://api.github.com/users/hakanmemisoglu/orgs","repos_url":"https://api.github.com/users/hakanmemisoglu/repos","events_url":"https://api.github.com/users/hakanmemisoglu/events{/privacy}","received_events_url":"https://api.github.com/users/hakanmemisoglu/received_events","type":"User","site_admin":false},"body":"This PR introduces the last piece of the transaction module:\r\n\r\n- LockManager: This is the entry point for the module. All outside interaction will happen via this class.\r\n\r\n- DeadLockDetector: This class contains the logic for deadlock detection and selection of victims.\r\n\r\n- CycleDetector: This class will be used by DeadLockDetector for detection of the cycles in the wait-for graph.","created_at":"2016-04-22T01:19:18Z","updated_at":"2016-04-29T06:10:22Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0269501dcfbfa0b99db95a4ecd64743fa1fd02ee","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/187/commits","review_comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/187/comments","review_comment_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments{/number}","comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/187/comments","statuses_url":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/97060a5cb62eaa6df1807059edab9c787a0111fd","head":{"label":"pivotalsoftware:transaction-part4","ref":"transaction-part4","sha":"97060a5cb62eaa6df1807059edab9c787a0111fd","user":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"repo":{"id":45578105,"name":"quickstep","full_name":"pivotalsoftware/quickstep","owner":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pivotalsoftware/quickstep","description":"Quickstep Project","fork":false,"url":"https://api.github.com/repos/pivotalsoftware/quickstep","forks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/forks","keys_url":"https://api.github.com/repos/pivotalsoftware/quickstep/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pivotalsoftware/quickstep/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pivotalsoftware/quickstep/teams","hooks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/hooks","issue_events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/events{/number}","events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/events","assignees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/assignees{/user}","branches_url":"https://api.github.com/repos/pivotalsoftware/quickstep/branches{/branch}","tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/tags","blobs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/refs{/sha}","trees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/{sha}","languages_url":"https://api.github.com/repos/pivotalsoftware/quickstep/languages","stargazers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/stargazers","contributors_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contributors","subscribers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscribers","subscription_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscription","commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/commits{/sha}","git_commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/commits{/sha}","comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/comments{/number}","issue_comment_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/comments{/number}","contents_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contents/{+path}","compare_url":"https://api.github.com/repos/pivotalsoftware/quickstep/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pivotalsoftware/quickstep/merges","archive_url":"https://api.github.com/repos/pivotalsoftware/quickstep/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pivotalsoftware/quickstep/downloads","issues_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues{/number}","pulls_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls{/number}","milestones_url":"https://api.github.com/repos/pivotalsoftware/quickstep/milestones{/number}","notifications_url":"https://api.github.com/repos/pivotalsoftware/quickstep/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pivotalsoftware/quickstep/labels{/name}","releases_url":"https://api.github.com/repos/pivotalsoftware/quickstep/releases{/id}","deployments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/deployments","created_at":"2015-11-05T01:06:50Z","updated_at":"2016-04-26T18:43:31Z","pushed_at":"2016-04-29T05:27:31Z","git_url":"git://github.com/pivotalsoftware/quickstep.git","ssh_url":"git@github.com:pivotalsoftware/quickstep.git","clone_url":"https://github.com/pivotalsoftware/quickstep.git","svn_url":"https://github.com/pivotalsoftware/quickstep","homepage":null,"size":9041,"stargazers_count":16,"watchers_count":16,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":10,"mirror_url":null,"open_issues_count":22,"forks":10,"open_issues":22,"watchers":16,"default_branch":"master"}},"base":{"label":"pivotalsoftware:master","ref":"master","sha":"e372e1c8296fdb674cc035ddc98259dcbc4660b4","user":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"repo":{"id":45578105,"name":"quickstep","full_name":"pivotalsoftware/quickstep","owner":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pivotalsoftware/quickstep","description":"Quickstep Project","fork":false,"url":"https://api.github.com/repos/pivotalsoftware/quickstep","forks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/forks","keys_url":"https://api.github.com/repos/pivotalsoftware/quickstep/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pivotalsoftware/quickstep/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pivotalsoftware/quickstep/teams","hooks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/hooks","issue_events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/events{/number}","events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/events","assignees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/assignees{/user}","branches_url":"https://api.github.com/repos/pivotalsoftware/quickstep/branches{/branch}","tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/tags","blobs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/refs{/sha}","trees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/{sha}","languages_url":"https://api.github.com/repos/pivotalsoftware/quickstep/languages","stargazers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/stargazers","contributors_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contributors","subscribers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscribers","subscription_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscription","commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/commits{/sha}","git_commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/commits{/sha}","comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/comments{/number}","issue_comment_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/comments{/number}","contents_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contents/{+path}","compare_url":"https://api.github.com/repos/pivotalsoftware/quickstep/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pivotalsoftware/quickstep/merges","archive_url":"https://api.github.com/repos/pivotalsoftware/quickstep/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pivotalsoftware/quickstep/downloads","issues_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues{/number}","pulls_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls{/number}","milestones_url":"https://api.github.com/repos/pivotalsoftware/quickstep/milestones{/number}","notifications_url":"https://api.github.com/repos/pivotalsoftware/quickstep/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pivotalsoftware/quickstep/labels{/name}","releases_url":"https://api.github.com/repos/pivotalsoftware/quickstep/releases{/id}","deployments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/deployments","created_at":"2015-11-05T01:06:50Z","updated_at":"2016-04-26T18:43:31Z","pushed_at":"2016-04-29T05:27:31Z","git_url":"git://github.com/pivotalsoftware/quickstep.git","ssh_url":"git@github.com:pivotalsoftware/quickstep.git","clone_url":"https://github.com/pivotalsoftware/quickstep.git","svn_url":"https://github.com/pivotalsoftware/quickstep","homepage":null,"size":9041,"stargazers_count":16,"watchers_count":16,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":10,"mirror_url":null,"open_issues_count":22,"forks":10,"open_issues":22,"watchers":16,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/187"},"html":{"href":"https://github.com/pivotalsoftware/quickstep/pull/187"},"issue":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/187"},"comments":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/187/comments"},"review_comments":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/187/comments"},"review_comment":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/187/commits"},"statuses":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/97060a5cb62eaa6df1807059edab9c787a0111fd"}}}}