Doma | Code

Intro

Cache memory is a chip-based computer component that makes retrieving data from the computer's memory more efficient. It acts as a temporary storage area that the computer's processor can retrieve data from easily.

— Ben Lutkevich, Cache Memory

The cache hierarchy implemented in this project has three levels: L1, L2, & L3. These levels are organized using a hash table. Each level of the cache will constructed using a linked list. The data for a cache entry will be stored as an object within the linked list's node. This implementation is shown in the figure below.

A cache eviction algorithm is a way of deciding which element to evict when the cache is full. When the store gets full, elements are evicted.

— Cache Eviction Policy

An essential part of the design is the eviction policy, either MRU (most recently used) or LRU (least recently used). When the cache is full, the given eviction policy will delete nodes from the linked list to make space for what is being inserted.

Specifications

The project specifications include object attributes and special methods, as well as function types and descriptions.

Design

This object is the foundation of the data stored within the cache. Its attributes include an ID, size, header information, and the data being stored. This object contains the method __hash__ which is essential for the implementation of the hash table.

This object is a simple node required to implement the linked list.

This object is a linked list with modified logic. The put() function is modified to accept an eviction policy for replacing nodes. The put() function uses two helper functions, lurEvict() & mruEvict, to apply the correlating eviction policy. All other function within this object contribute to the linked list logic.

This object represents the top level of the cache hierarchy. From here you can insert, update, and retrieve data, as well as clear the cache. This class contains a comprehensive doctest to test the cache’s overall functionallity.

Results

Running the doctest with:

python -m doctest -v HW4.py

~/CS-132$ # Run the doctest on HW4.py
~/CS-132$ cd Hw_4
~/CS-132/Hw_4$ python -m doctest -v HW4.py
Trying:
    cache = Cache()
Expecting nothing
ok
Trying:
    content1 = ContentItem(1000, 10, 'Content-Type: 0', '0xA')
Expecting nothing
ok
Trying:
    content2 = ContentItem(1003, 13, 'Content-Type: 0', '0xD')
Expecting nothing
ok
Trying:
    content3 = ContentItem(1008, 242, 'Content-Type: 0', '0xF2')
Expecting nothing
ok
Trying:
    content4 = ContentItem(1004, 50, 'Content-Type: 1', '110010')
Expecting nothing
ok
Trying:
    content5 = ContentItem(1001, 51, 'Content-Type: 1', '110011')
Expecting nothing
ok
Trying:
    content6 = ContentItem(1007, 155, 'Content-Type: 1', '10011011')
Expecting nothing
ok
Trying:
    content7 = ContentItem(1005, 18, 'Content-Type: 2', '<html><p>'CMPSC132'</p></html>')
Expecting nothing
ok
Trying:
    content8 = ContentItem(1002, 14, 'Content-Type: 2', '<html><h2>'PSU'</h2></html>')
Expecting nothing
ok
Trying:
    content9 = ContentItem(1006, 170, 'Content-Type: 2', '<html><button>'Click Me'</button></html>')
Expecting nothing
ok
Trying:
    cache.insert(content1, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'
ok
Trying:
    cache.insert(content2, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD'
ok
Trying:
    cache.insert(content3, 'lru')
Expecting:
    'Insertion not allowed. Content size is too large.'
ok
Trying:
    cache.insert(content4, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010'
ok
Trying:
    cache.insert(content5, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1001 SIZE: 51 HEADER: Content-Type: 1 CONTENT: 110011'
ok
Trying:
    cache.insert(content6, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1007 SIZE: 155 HEADER: Content-Type: 1 CONTENT: 10011011'
ok
Trying:
    cache.insert(content7, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1005 SIZE: 18 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>'
ok
Trying:
    cache.insert(content8, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1002 SIZE: 14 HEADER: Content-Type: 2 CONTENT: <html><h2>'PSU'</h2></html>'
ok
Trying:
    cache.insert(content9, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1006 SIZE: 170 HEADER: Content-Type: 2 CONTENT: <html><button>'Click Me'</button></html>'
ok
Trying:
    cache
Expecting:
    L1 CACHE:
    REMAINING SPACE:177
    ITEMS:2
    LIST:
    [CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD]
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    <BLANKLINE>
    L2 CACHE:
    REMAINING SPACE:45
    ITEMS:1
    LIST:
    [CONTENT ID: 1007 SIZE: 155 HEADER: Content-Type: 1 CONTENT: 10011011]
    <BLANKLINE>
    L3 CACHE:
    REMAINING SPACE:16
    ITEMS:2
    LIST:
    [CONTENT ID: 1006 SIZE: 170 HEADER: Content-Type: 2 CONTENT: <html><button>'Click Me'</button></html>]
    [CONTENT ID: 1002 SIZE: 14 HEADER: Content-Type: 2 CONTENT: <html><h2>'PSU'</h2></html>]
    <BLANKLINE>
    <BLANKLINE>
ok
Trying:
    cache.hierarchy[0].clear()
Expecting:
    'Cleared cache!'
ok
Trying:
    cache.hierarchy[1].clear()
Expecting:
    'Cleared cache!'
ok
Trying:
    cache.hierarchy[2].clear()
Expecting:
    'Cleared cache!'
ok
Trying:
    cache
Expecting:
    L1 CACHE:
    REMAINING SPACE:200
    ITEMS:0
    LIST:
    <BLANKLINE>
    L2 CACHE:
    REMAINING SPACE:200
    ITEMS:0
    LIST:
    <BLANKLINE>
    L3 CACHE:
    REMAINING SPACE:200
    ITEMS:0
    LIST:
    <BLANKLINE>
    <BLANKLINE>
ok
Trying:
    cache.insert(content1, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'
ok
Trying:
    cache.insert(content2, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD'
ok
Trying:
    cache.retrieveContent(content1)
Expecting:
    CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA
ok
Trying:
    cache.retrieveContent(content2)
Expecting:
    CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD
ok
Trying:
    cache.retrieveContent(content3)
Expecting:
    'Cache miss!'
ok
Trying:
    cache.insert(content5, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1001 SIZE: 51 HEADER: Content-Type: 1 CONTENT: 110011'
ok
Trying:
    cache.insert(content6, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1007 SIZE: 155 HEADER: Content-Type: 1 CONTENT: 10011011'
ok
Trying:
    cache.insert(content4, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010'
ok
Trying:
    cache.insert(content7, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1005 SIZE: 18 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>'
ok
Trying:
    cache.insert(content8, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1002 SIZE: 14 HEADER: Content-Type: 2 CONTENT: <html><h2>'PSU'</h2></html>'
ok
Trying:
    cache.insert(content9, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1006 SIZE: 170 HEADER: Content-Type: 2 CONTENT: <html><button>'Click Me'</button></html>'
ok
Trying:
    cache
Expecting:
    L1 CACHE:
    REMAINING SPACE:177
    ITEMS:2
    LIST:
    [CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD]
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    <BLANKLINE>
    L2 CACHE:
    REMAINING SPACE:150
    ITEMS:1
    LIST:
    [CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]
    <BLANKLINE>
    L3 CACHE:
    REMAINING SPACE:12
    ITEMS:2
    LIST:
    [CONTENT ID: 1006 SIZE: 170 HEADER: Content-Type: 2 CONTENT: <html><button>'Click Me'</button></html>]
    [CONTENT ID: 1005 SIZE: 18 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>]
    <BLANKLINE>
    <BLANKLINE>
ok
Trying:
    cache.clear()
Expecting:
    'Cache cleared!'
ok
Trying:
    contentA = ContentItem(2000, 52, 'Content-Type: 2', 'GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1')
Expecting nothing
ok
Trying:
    contentB = ContentItem(2001, 76, 'Content-Type: 2', 'GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1')
Expecting nothing
ok
Trying:
    contentC = ContentItem(2002, 11, 'Content-Type: 2', 'GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1')
Expecting nothing
ok
Trying:
    cache.insert(contentA, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1'
ok
Trying:
    cache.insert(contentB, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1'
ok
Trying:
    cache.insert(contentC, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1'
ok
Trying:
    cache.hierarchy[2]
Expecting:
    REMAINING SPACE:61
    ITEMS:3
    LIST:
    [CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]
    [CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]
    [CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1]
    <BLANKLINE>
ok
Trying:
    cache.retrieveContent(contentC)
Expecting:
    CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1
ok
Trying:
    cache.hierarchy[2]
Expecting:
    REMAINING SPACE:61
    ITEMS:3
    LIST:
    [CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]
    [CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]
    [CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1]
    <BLANKLINE>
ok
Trying:
    cache.retrieveContent(contentA)
Expecting:
    CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1
ok
Trying:
    cache.hierarchy[2]
Expecting:
    REMAINING SPACE:61
    ITEMS:3
    LIST:
    [CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1]
    [CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]
    [CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]
    <BLANKLINE>
ok
Trying:
    cache.retrieveContent(contentC)
Expecting:
    CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1
ok
Trying:
    cache.hierarchy[2]
Expecting:
    REMAINING SPACE:61
    ITEMS:3
    LIST:
    [CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]
    [CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1]
    [CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]
    <BLANKLINE>
ok
Trying:
    contentD = ContentItem(2002, 11, 'Content-Type: 2', 'GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1')
Expecting nothing
ok
Trying:
    cache.insert(contentD, 'lru')
Expecting:
    'Insertion of content item 2002 not allowed. Content already in cache.'
ok
Trying:
    contentE = ContentItem(2000, 52, 'Content-Type: 2', 'GET https://www.pro-football-reference.com/boxscores/201801210phi.htm HTTP/1.1')
Expecting nothing
ok
Trying:
    cache.updateContent(contentE)
Expecting:
    'UPDATED: CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201801210phi.htm HTTP/1.1'
ok
Trying:
    cache.hierarchy[2]
Expecting:
    REMAINING SPACE:61
    ITEMS:3
    LIST:
    [CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201801210phi.htm HTTP/1.1]
    [CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]
    [CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]
    <BLANKLINE>              
ok
Trying:
    content1 = ContentItem(1000, 10, 'Content-Type: 0', '0xA')
Expecting nothing
ok
Trying:
    content2 = ContentItem(1004, 50, 'Content-Type: 1', '110010')
Expecting nothing
ok
Trying:
    content3 = ContentItem(1005, 180, 'Content-Type: 2', '<html><p>'CMPSC132'</p></html>')
Expecting nothing
ok
Trying:
    content4 = ContentItem(1006, 18, 'another header', '111110')
Expecting nothing
ok
Trying:
    content5 = ContentItem(1008, 2, 'items', '11x1110')
Expecting nothing
ok
Trying:
    lst=CacheList(200)
Expecting nothing
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:200
    ITEMS:0
    LIST:
    <BLANKLINE>
ok
Trying:
    lst.put(content1, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'
ok
Trying:
    lst.put(content2, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010'
ok
Trying:
    lst.put(content4, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110'
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:122
    ITEMS:3
    LIST:
    [CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110]
    [CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    <BLANKLINE>
ok
Trying:
    lst.put(content5, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1008 SIZE: 2 HEADER: items CONTENT: 11x1110'
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:120
    ITEMS:4
    LIST:
    [CONTENT ID: 1008 SIZE: 2 HEADER: items CONTENT: 11x1110]
    [CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110]
    [CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    <BLANKLINE>
ok
Trying:
    lst.put(content3, 'lru')
Expecting:
    'INSERTED: CONTENT ID: 1005 SIZE: 180 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>'
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:0
    ITEMS:3
    LIST:
    [CONTENT ID: 1005 SIZE: 180 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>]
    [CONTENT ID: 1008 SIZE: 2 HEADER: items CONTENT: 11x1110]
    [CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110]
    <BLANKLINE>
ok
Trying:
    lst.put(content1, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:170
    ITEMS:3
    LIST:
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    [CONTENT ID: 1008 SIZE: 2 HEADER: items CONTENT: 11x1110]
    [CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110]
    <BLANKLINE>
ok
Trying:
    lst.find(1006)
Expecting:
    CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:170
    ITEMS:3
    LIST:
    [CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110]
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    [CONTENT ID: 1008 SIZE: 2 HEADER: items CONTENT: 11x1110]
    <BLANKLINE>
ok
Trying:
    contentExtra = ContentItem(1034, 2, 'items', 'other content')
Expecting nothing
ok
Trying:
    lst.update(1008, contentExtra)
Expecting:
    'UPDATED: CONTENT ID: 1034 SIZE: 2 HEADER: items CONTENT: other content'
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:170
    ITEMS:3
    LIST:
    [CONTENT ID: 1034 SIZE: 2 HEADER: items CONTENT: other content]
    [CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110]
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    <BLANKLINE>
ok
Trying:
    lst.clear()
Expecting:
    'Cleared cache!'
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:200
    ITEMS:0
    LIST:
    <BLANKLINE>
ok
Trying:
    content1 = ContentItem(1000, 10, 'Content-Type: 0', '0xA')
Expecting nothing
ok
Trying:
    content2 = ContentItem(1004, 50, 'Content-Type: 1', '110010')
Expecting nothing
ok
Trying:
    content3 = ContentItem(1005, 180, 'Content-Type: 2', '<html><p>'CMPSC132'</p></html>')
Expecting nothing
ok
Trying:
    lst = CacheList(300)
Expecting nothing
ok
Trying:
    lst.put(content1, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'
ok
Trying:
    lst.put(content2, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010'
ok
Trying:
    lst.put(content3, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1005 SIZE: 180 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>'
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:60
    ITEMS:3
    LIST:
    [CONTENT ID: 1005 SIZE: 180 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>]
    [CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    <BLANKLINE>
ok
Trying:
    lst.remove(1005)
Expecting nothing
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:240
    ITEMS:2
    LIST:
    [CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    <BLANKLINE>
ok
Trying:
    lst.put(content3, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1005 SIZE: 180 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>'
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:60
    ITEMS:3
    LIST:
    [CONTENT ID: 1005 SIZE: 180 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>]
    [CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    <BLANKLINE>
ok
Trying:
    lst.remove(1000)
Expecting nothing
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:70
    ITEMS:2
    LIST:
    [CONTENT ID: 1005 SIZE: 180 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>]
    [CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]
    <BLANKLINE>
ok
Trying:
    lst.put(content1, 'mru')
Expecting:
    'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:60
    ITEMS:3
    LIST:
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    [CONTENT ID: 1005 SIZE: 180 HEADER: Content-Type: 2 CONTENT: <html><p>'CMPSC132'</p></html>]
    [CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]
    <BLANKLINE>
ok
Trying:
    lst.remove(1005)
Expecting nothing
ok
Trying:
    lst
Expecting:
    REMAINING SPACE:240
    ITEMS:2
    LIST:
    [CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]
    [CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]
    <BLANKLINE>
ok
Trying:
    content1 = ContentItem(1000, 10, 'Content-Type: 0', '0xA')
Expecting nothing
ok
Trying:
    content2 = ContentItem(1004, 50, 'Content-Type: 1', '110010')
Expecting nothing
ok
Trying:
    content3 = ContentItem(1005, 18, 'Content-Type: 2', '<html><p>'CMPSC132'</p></html>')
Expecting nothing
ok
Trying:
    content4 = ContentItem(1005, 18, 'another header', '111110')
Expecting nothing
ok
Trying:
    hash(content1)
Expecting:
    0
ok
Trying:
    hash(content2)
Expecting:
    1
ok
Trying:
    hash(content3)
Expecting:
    2
ok
Trying:
    hash(content4)
Expecting:
    1
ok
23 items had no tests:
    HW4
    HW4.Cache.__init__
    HW4.Cache.__str__
    HW4.Cache.clear
    HW4.Cache.insert
    HW4.Cache.retrieveContent
    HW4.Cache.updateContent
    HW4.CacheList.__init__
    HW4.CacheList.__len__
    HW4.CacheList.__str__
    HW4.CacheList.clear
    HW4.CacheList.find
    HW4.CacheList.lruEvict
    HW4.CacheList.mruEvict
    HW4.CacheList.put
    HW4.CacheList.update
    HW4.ContentItem.__eq__
    HW4.ContentItem.__hash__
    HW4.ContentItem.__init__
    HW4.ContentItem.__str__
    HW4.Node
    HW4.Node.__init__
    HW4.Node.__str__
4 items passed all tests:
    55 tests in HW4.Cache
    24 tests in HW4.CacheList
    18 tests in HW4.CacheList.remove
    8 tests in HW4.ContentItem
105 tests in 27 items.
105 passed and 0 failed.
Test passed.
~/CS-132/Hw_4$

Running in interactive mode with:

python -i HW4.py

~/CS-132$ # Create a cache in interactive mode
~/CS-132$ 
~/CS-132$ cd Hw_4
~/CS-132/Hw_4$ python -i HW4.py
>>> cache = Cache()
>>> data_1 = ContentItem(4180, 74, 'Content-Type: 0', '0xF')
>>> data_2 = ContentItem(7532, 32, 'Content-Type: 1', '0xA')
>>> data_3 = ContentItem(3290, 96, 'Content-Type: 2', '0xE')
>>> cache.insert(data_1, 'lru')
'INSERTED: CONTENT ID: 4180 SIZE: 74 HEADER: Content-Type: 0 CONTENT: 0xF'
>>> cache.insert(data_2, 'lru')
'INSERTED: CONTENT ID: 7532 SIZE: 32 HEADER: Content-Type: 1 CONTENT: 0xA'
>>> cache
L1 CACHE:
REMAINING SPACE:126
ITEMS:1
LIST:
[CONTENT ID: 4180 SIZE: 74 HEADER: Content-Type: 0 CONTENT: 0xF]

L2 CACHE:
REMAINING SPACE:168
ITEMS:1
LIST:
[CONTENT ID: 7532 SIZE: 32 HEADER: Content-Type: 1 CONTENT: 0xA]

L3 CACHE:
REMAINING SPACE:200
ITEMS:0
LIST:

>>> cache.insert(data_1, 'lru')
'Insertion of content item 4180 not allowed. Content already in cache.'
>>> cache.insert(data_3, 'lru')
'INSERTED: CONTENT ID: 3290 SIZE: 96 HEADER: Content-Type: 2 CONTENT: 0xE'
>>> cache.retrieveContent(data_3)
CONTENT ID: 3290 SIZE: 96 HEADER: Content-Type: 2 CONTENT: 0xE
>>> cache.hierarchy[1]
REMAINING SPACE:168
ITEMS:1
LIST:
[CONTENT ID: 7532 SIZE: 32 HEADER: Content-Type: 1 CONTENT: 0xA]

>>> data_3 = ContentItem(8273, 200, 'Content-Type: 1', 'https://localhost')
>>> cache.insert(data_3, 'lru')
'Insertion not allowed. Content size is too large.'
>>> data_3 = ContentItem(8273, 175, 'Content-Type: 1', 'https://localhost')
>>> cache.insert(data_3, 'lru')
'INSERTED: CONTENT ID: 8273 SIZE: 175 HEADER: Content-Type: 1 CONTENT: https://localhost'
>>> cache.hierarchy[1]
REMAINING SPACE:25
ITEMS:1
LIST:
[CONTENT ID: 8273 SIZE: 175 HEADER: Content-Type: 1 CONTENT: https://localhost]

>>> cache
L1 CACHE:
REMAINING SPACE:126
ITEMS:1
LIST:
[CONTENT ID: 4180 SIZE: 74 HEADER: Content-Type: 0 CONTENT: 0xF]

L2 CACHE:
REMAINING SPACE:25
ITEMS:1
LIST:
[CONTENT ID: 8273 SIZE: 175 HEADER: Content-Type: 1 CONTENT: https://localhost]

L3 CACHE:
REMAINING SPACE:104
ITEMS:1
LIST:
[CONTENT ID: 3290 SIZE: 96 HEADER: Content-Type: 2 CONTENT: 0xE]

>>> data_1 = ContentItem(4180, 74, 'Content-Type: 0', 'ERROR')
>>> cache.updateContent(data_1)
'UPDATED: CONTENT ID: 4180 SIZE: 74 HEADER: Content-Type: 0 CONTENT: ERROR'
>>> cache
L1 CACHE:
REMAINING SPACE:126
ITEMS:1
LIST:
[CONTENT ID: 4180 SIZE: 74 HEADER: Content-Type: 0 CONTENT: ERROR]

L2 CACHE:
REMAINING SPACE:25
ITEMS:1
LIST:
[CONTENT ID: 8273 SIZE: 175 HEADER: Content-Type: 1 CONTENT: https://localhost]

L3 CACHE:
REMAINING SPACE:104
ITEMS:1
LIST:
[CONTENT ID: 3290 SIZE: 96 HEADER: Content-Type: 2 CONTENT: 0xE]

>>> cache.clear()
'Cache cleared!'
>>> cache
L1 CACHE:
REMAINING SPACE:200
ITEMS:0
LIST:

L2 CACHE:
REMAINING SPACE:200
ITEMS:0
LIST:

L3 CACHE:
REMAINING SPACE:200
ITEMS:0
LIST:

>>> exit()
~/CS-132/Hw_4$

Multi-level Cache

Intro

Specifications

Design

Results

Heroku app

Gameboy State Machine

Multi-level Cache

Intro

Specifications

Design

Content Item

Node

Cache List

Cache

Results

Related Projects

Heroku app

Gameboy State Machine