解题思路
本题要求计算一次写入数据包之后新的 write_index。
需要注意三点:
- 实际写入起点不是原始 write_index,而是从 write_index 开始向后找到的第一个满足对齐要求的位置。
- 如果对齐后的位置等于或超过 capacity,说明本次写入起点需要回绕到 0。
- 判断空间是否足够时,不能只看数据包长度,还要把为了对齐而跳过的空间也算入本次消耗。
P14189.循环内存存取计算(100分)
题目内容
1、当前有一段循环使用的内存来存放多个数据包,这块内存有两个索引:
- read_index:读索引,指向当前已存储的数据包的起始位置,读取数据后,read_index 会跳转到下一个存放数据的起点。
- write_index:写索引,指向当前可写入新数据包的起始位置,写入数据后,write_index 会跳转到下一个待写入数据包的起点。
2、整个循环内存对数据存放的起始地址有严格的对齐要求,通常字节对齐的值为 2 的整数倍,例如 2、4、8、16 等。
- 整个循环内存的长度本身满足对齐要求是字节对齐值的整数倍。
- 每个数据包存放的起始位置,必须是字节对齐的整数倍。
- 存放数据以后,计算新的 write_index 也必须满足字节对齐要求。
3、循环内存是环形的,如果存入新的数据时超出了缓冲区末尾,剩余部分将从索引0开始继续存储。
现在给定以下输入:
- capacity:内存的空间大小(capacity 的长度是字节对齐值的整数倍)
- align:字节对齐的值(align 的值是 2n)
- read_index:当前读索引的值
- write_index:当前写索引的值(如果输入的 write_index=read_index,代表当前缓冲区没有任何内容,容量是满的)
- pkt_size:写入的数据包的长度
请计算把数据包写入环形缓冲区后,write_index 的位置。如果在写入新的数据时,环形缓冲区放不下,则返回 −1。
样例1
输入
100,4,0,1,10
输出
14
说明
capacity=100,align=4,read_index=0,write_index=1,pkt_size=10。write_index=1 不对齐,下一个对齐点是 4,从位置 4 存入 10 字节, write_index 到达位置 14(14 不对齐,再下一次会从位置 16 开始存入)。
样例2
输入
100,1,20,10,15
输出
-1
说明
capacity=100,align=1,read_index=20,write_index=10,pkt_size=15。起始位置 10 存入 15 字节,到达 25。但 25 越过了 read_index=20,返回 −1。
样例3
输入
1024,16,512,1020,100
输出
100
说明
capacity=1024,align=16,read_index=512,write_index=1020,pkt_size=100。
write_index=1020 尝试对齐到 16,下一个点是 1024。因为 1024>=capacity,起始位置回绕到 0。从 0 存入 100 字节,write_index 到达位置 100。