SHARE
TWEET

Untitled

a guest Jun 25th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.HashMap;
  2. import java.util.Map;
  3. import java.util.concurrent.ConcurrentHashMap;
  4. import java.util.concurrent.ExecutorService;
  5. import java.util.concurrent.Executors;
  6. import java.util.concurrent.ThreadLocalRandom;
  7. import java.util.concurrent.locks.ReadWriteLock;
  8. import java.util.concurrent.locks.ReentrantReadWriteLock;
  9. import java.util.stream.IntStream;
  10.  
  11.  
  12. class LRUCache {
  13.  
  14.     /*
  15.       Our internal definition of a doubly linked list
  16.       node, put in this class for convenience since
  17.       this is submitted in one file on Leetcode
  18.     */
  19.     private class DNode {
  20.         int key;
  21.         int value;
  22.         DNode prev;
  23.         DNode next;
  24.     }
  25.  
  26.     private Map<Integer, DNode> hashtable = new HashMap<>();
  27.     private DNode head, tail;
  28.     private int totalItemsInCache;
  29.     private int maxCapacity;
  30.     private ReadWriteLock lock = new ReentrantReadWriteLock();
  31.  
  32.  
  33.     public LRUCache(int maxCapacity) {
  34.  
  35.         // Cache starts empty and capacity is set by client
  36.         totalItemsInCache = 0;
  37.         this.maxCapacity = maxCapacity;
  38.  
  39.         // Initialize the dummy head of the cache
  40.         head = new DNode();
  41.         head.prev = null;
  42.  
  43.         // Init the dummy tail of the cache
  44.         tail = new DNode();
  45.         tail.next = null;
  46.  
  47.         // Wire the head and tail together
  48.         head.next = tail;
  49.         tail.prev = head;
  50.     }
  51.  
  52.     public int getSize() {
  53.         return totalItemsInCache;
  54.     }
  55.  
  56.     /*
  57.       Retrieve an item from the cache
  58.     */
  59.     // make get operation thread safe. Could use a reentrant read lock here for finer control.
  60.     public synchronized int get(int key) {
  61.  
  62.         DNode node = hashtable.get(key);
  63.         boolean itemFoundInCache = node != null;
  64.  
  65.         // Empty state check. Should raise exception here.
  66.         if (!itemFoundInCache) {
  67.             return -1;
  68.         }
  69.  
  70.         // Item has been accessed. Move to the front of the list.
  71.         moveToHead(node);
  72.  
  73.         return node.value;
  74.     }
  75.  
  76.     /*
  77.       Add an item to the cache if it is not already there,
  78.       if it is already there update the value and move it
  79.       to the front of the cache
  80.     */
  81.     public synchronized void put(int key, int value) {
  82.  
  83.             DNode node = hashtable.get(key);
  84.             boolean itemFoundInCache = node != null;
  85.  
  86.             if(!itemFoundInCache){
  87.  
  88.                 // Create a new node
  89.                 DNode newNode = new DNode();
  90.                 newNode.key = key;
  91.                 newNode.value = value;
  92.  
  93.                 // Add to the hashtable and the doubly linked list
  94.                 hashtable.put(key, newNode);
  95.                 addNode(newNode);
  96.  
  97.                 // We just added an item to the cache
  98.                 totalItemsInCache++;
  99.  
  100.                 // If over capacity evict an item with LRU cache eviction policy
  101.                 if(totalItemsInCache > maxCapacity){
  102.                     removeLRUEntryFromStructure();
  103.                 }
  104.  
  105.             } else {
  106.                 // If item is in cache just update and move it to the head
  107.                 node.value = value;
  108.                 moveToHead(node);
  109.             }
  110.         }
  111.  
  112.     /*
  113.       Remove the least used entry from the doubly linked
  114.       list as well as the hashtable. Hence it is evicted
  115.       from the whole LRUCache structure
  116.     */
  117.     // don't think I need to make it  here right if I have made the helper methods thread safe?
  118.     private  void removeLRUEntryFromStructure() {
  119.         DNode tail = popTail();
  120.         hashtable.remove(tail.key);
  121.         --totalItemsInCache;
  122.     }
  123.  
  124.     /*
  125.       Insertions to the doubly linked list will always
  126.       be right after the dummy head
  127.     */
  128.     private  void addNode(DNode node){
  129.  
  130.         // Wire the node being inserted
  131.         node.prev = head;
  132.         node.next = head.next;
  133.  
  134.         // Re-wire the head's old next
  135.         head.next.prev = node;
  136.  
  137.         // Re-wire the head to point to the inserted node
  138.         head.next = node;
  139.     }
  140.  
  141.     /*
  142.       Remove the given node from the doubly linked list
  143.     */
  144.     private  void removeNode(DNode node){
  145.  
  146.         // Grab reference to the prev and next of the node
  147.         DNode savedPrev = node.prev;
  148.         DNode savedNext = node.next;
  149.  
  150.         // Cut out going forwards
  151.         savedPrev.next = savedNext;
  152.  
  153.         // Cut out going backards
  154.         savedNext.prev = savedPrev;
  155.     }
  156.  
  157.     /*
  158.       Move a node to the head of the doubly linked lsit
  159.     */
  160.     // don't think I need to make it  here right if I have made the helper methods thread safe?
  161.     private  void moveToHead(DNode node){
  162.         removeNode(node);
  163.         addNode(node);
  164.     }
  165.  
  166.     /*
  167.       Pop the last item from the structure
  168.     */
  169.     private  DNode popTail(){
  170.         DNode itemBeingRemoved = tail.prev;
  171.         removeNode(itemBeingRemoved);
  172.         return itemBeingRemoved;
  173.     }
  174.  
  175.     public static void main(String[] args) {
  176.        import java.util.HashMap;
  177. import java.util.Map;
  178. import java.util.concurrent.ConcurrentHashMap;
  179. import java.util.concurrent.ExecutorService;
  180. import java.util.concurrent.Executors;
  181. import java.util.concurrent.ThreadLocalRandom;
  182. import java.util.concurrent.locks.ReadWriteLock;
  183. import java.util.concurrent.locks.ReentrantReadWriteLock;
  184. import java.util.stream.IntStream;
  185.  
  186.  
  187. class LRUCache {
  188.  
  189.     /*
  190.       Our internal definition of a doubly linked list
  191.       node, put in this class for convenience since
  192.       this is submitted in one file on Leetcode
  193.     */
  194.     private class DNode {
  195.         int key;
  196.         int value;
  197.         DNode prev;
  198.         DNode next;
  199.     }
  200.  
  201.     private Map<Integer, DNode> hashtable = new HashMap<>();
  202.     private DNode head, tail;
  203.     private int totalItemsInCache;
  204.     private int maxCapacity;
  205.     private ReadWriteLock lock = new ReentrantReadWriteLock();
  206.  
  207.  
  208.     public LRUCache(int maxCapacity) {
  209.  
  210.         // Cache starts empty and capacity is set by client
  211.         totalItemsInCache = 0;
  212.         this.maxCapacity = maxCapacity;
  213.  
  214.         // Initialize the dummy head of the cache
  215.         head = new DNode();
  216.         head.prev = null;
  217.  
  218.         // Init the dummy tail of the cache
  219.         tail = new DNode();
  220.         tail.next = null;
  221.  
  222.         // Wire the head and tail together
  223.         head.next = tail;
  224.         tail.prev = head;
  225.     }
  226.  
  227.     public int getSize() {
  228.         return totalItemsInCache;
  229.     }
  230.  
  231.     /*
  232.       Retrieve an item from the cache
  233.     */
  234.     // make get operation thread safe. Could use a reentrant read lock here for finer control.
  235.     public synchronized int get(int key) {
  236.  
  237.         DNode node = hashtable.get(key);
  238.         boolean itemFoundInCache = node != null;
  239.  
  240.         // Empty state check. Should raise exception here.
  241.         if (!itemFoundInCache) {
  242.             return -1;
  243.         }
  244.  
  245.         // Item has been accessed. Move to the front of the list.
  246.         moveToHead(node);
  247.  
  248.         return node.value;
  249.     }
  250.  
  251.     /*
  252.       Add an item to the cache if it is not already there,
  253.       if it is already there update the value and move it
  254.       to the front of the cache
  255.     */
  256.     public synchronized void put(int key, int value) {
  257.  
  258.             DNode node = hashtable.get(key);
  259.             boolean itemFoundInCache = node != null;
  260.  
  261.             if(!itemFoundInCache){
  262.  
  263.                 // Create a new node
  264.                 DNode newNode = new DNode();
  265.                 newNode.key = key;
  266.                 newNode.value = value;
  267.  
  268.                 // Add to the hashtable and the doubly linked list
  269.                 hashtable.put(key, newNode);
  270.                 addNode(newNode);
  271.  
  272.                 // We just added an item to the cache
  273.                 totalItemsInCache++;
  274.  
  275.                 // If over capacity evict an item with LRU cache eviction policy
  276.                 if(totalItemsInCache > maxCapacity){
  277.                     removeLRUEntryFromStructure();
  278.                 }
  279.  
  280.             } else {
  281.                 // If item is in cache just update and move it to the head
  282.                 node.value = value;
  283.                 moveToHead(node);
  284.             }
  285.         }
  286.  
  287.     /*
  288.       Remove the least used entry from the doubly linked
  289.       list as well as the hashtable. Hence it is evicted
  290.       from the whole LRUCache structure
  291.     */
  292.     // don't think I need to make it  here right if I have made the helper methods thread safe?
  293.     private  void removeLRUEntryFromStructure() {
  294.         DNode tail = popTail();
  295.         hashtable.remove(tail.key);
  296.         --totalItemsInCache;
  297.     }
  298.  
  299.     /*
  300.       Insertions to the doubly linked list will always
  301.       be right after the dummy head
  302.     */
  303.     private void addNode(DNode node){
  304.  
  305.         // Wire the node being inserted
  306.         node.prev = head;
  307.         node.next = head.next;
  308.  
  309.         // Re-wire the head's old next
  310.         head.next.prev = node;
  311.  
  312.         // Re-wire the head to point to the inserted node
  313.         head.next = node;
  314.     }
  315.  
  316.     /*
  317.       Remove the given node from the doubly linked list
  318.     */
  319.     private  void removeNode(DNode node){
  320.  
  321.         // Grab reference to the prev and next of the node
  322.         DNode savedPrev = node.prev;
  323.         DNode savedNext = node.next;
  324.  
  325.         // Cut out going forwards
  326.         savedPrev.next = savedNext;
  327.  
  328.         // Cut out going backards
  329.         savedNext.prev = savedPrev;
  330.     }
  331.  
  332.     /*
  333.       Move a node to the head of the doubly linked lsit
  334.     */
  335.     // don't think I need to make it  here right if I have made the helper methods thread safe?
  336.     private  void moveToHead(DNode node){
  337.         removeNode(node);
  338.         addNode(node);
  339.     }
  340.  
  341.     /*
  342.       Pop the last item from the structure
  343.     */
  344.     private  DNode popTail(){
  345.         DNode itemBeingRemoved = tail.prev;
  346.         removeNode(itemBeingRemoved);
  347.         return itemBeingRemoved;
  348.     }
  349.  
  350.     public static void main(String[] args) {
  351.         final LRUCache cache = new LRUCache(10);
  352.         ExecutorService e = Executors.newFixedThreadPool(1000);
  353.         for (int i = 0; i < 500000; i++) {
  354.             e.submit(new Runnable() {
  355.                 @Override
  356.                 public void run() {
  357.                     int r = ThreadLocalRandom.current().nextInt();
  358.                     cache.put(Math.toIntExact(Thread.currentThread().getId()), Math.toIntExact(Thread.currentThread().getId()));
  359.                     int key = Math.toIntExact(Thread.currentThread().getId());
  360.                     if (cache.get(key) != key) {
  361.                         System.out.println("Get value for key " + key + " : " + cache.get(key));
  362.                     }
  363.                 }
  364.             });
  365.         }
  366.         e.shutdown();
  367. //        final Integer targetKey = 100; // 65 535
  368. //        final Integer targetValue = 2;
  369. //        cache.put(targetKey, targetValue);
  370. //
  371. //        new Thread(() -> {
  372. //            IntStream.range(0, targetKey).forEach(key -> cache.put(key, key+1));
  373. //        }).start();
  374. //
  375. //
  376. //        while (true) {
  377. //            if (!targetValue.equals(cache.get(targetKey))) {
  378. //                throw new RuntimeException("HashMap is not thread safe.");
  379. //            }
  380. //        }
  381.         // Create 10 Threads
  382. //        for (int i = 0; i < 10; i++) {
  383. //            Thread thread = new Thread(() -> {
  384. //
  385. //                // Let Each thread insert 3000 Items
  386. //                for (int j = 0; j < 3000; j++) {
  387. //                    cache.put(j,j);
  388. //                }
  389. //
  390. //            });
  391. //            thread.start();
  392. //        }
  393. //
  394. //        System.out.println("Count should be 30000, actual is : " + cache.getSize());
  395.        //  System.out.println("Size of cache is " + cache.size());
  396.     }
  397.  
  398. }
  399.  
  400. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top