CMU 15445 Project 1

Project 只能下到2017的了
https://15445.courses.cs.cmu.edu/fall2018/project1/

想要做的小伙伴可以来我的GIT上下载ZIP。就可以。
同时我自己加了更多的测试来测我写的代码。
代码文件我也会上传GIT，方便自学遇到困难的小伙伴。

因为这个PROJECT 比较简单，我花了2天时间搭建环境和学习C++，真正实现可能只花了一个上午。前提是我都有思路。

任务1

先说第一个任务就是EXTENDIABLE HASH
因为只要扩容，不要缩容，难度降低不少。
核心就是下面这张图

image.png

所以我们需要一个VECTOR放指向BUCKET的指针，同时我们还需要一些BUCKET来存数据。存的数据满足蓝色框里的特征。

为了缩减锁的粒度，我尽可能的不对整个HASHMAP上锁。而是对单个的BUCKET的上锁。除了扩容的时候。
所以BUCKET的数据结果我定义为

struct Bucket {
    Bucket(int depth) : localDepth(depth) {};
    int localDepth;
    map<K, V> kmap;
    mutex latch;
  };

这边我定义指针，用了C++的shared_ptr来减去了NEW,DELETE的麻烦。

vector<shared_ptr<Bucket>> buckets;

这个项目，唯一的难点是在INSERT

image.png

image.png

image.png

这个扩容可能一次还解决不了问题。比如BUCKET SIZE是2.
有一个BUCKET里有 00110,00100（local depth 是2），你要插入的是00101
先扩容一次，LOCAL DEPTH 变为3了，但是3个元素的头3位都是001，所以还是挤在一起了。所以要用WHILE 循环。
直到有足够的空间可以放了为止。

任务2

实现一个LRU，因为之前LEETCODE上刷过题，直到要用LISTNODE + HASHMAP的思想。所以很快就实现了。小伙伴们可以参考下图实现一下，开动脑筋实现一下。

image.png

任务3

这个任务是要做前2个实现的基础上，做一个BUFFER POOL MANAGER
属性 和 构造函数，PROJECT里都给你了。关系如下图。

image.png

接下来就是根据函数描述 来逐个实现，难度也不大。有不明白的可以参考的我的代码。

最后附上项目包，和我的作业以及测试文件。
https://github.com/yixuaz/CMU-15445