Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd1698fc

Browse files
committed
Move blockmem implementation out of the main raftable module.
1 parentd7f5052 commitd1698fc

File tree

4 files changed

+272
-0
lines changed

4 files changed

+272
-0
lines changed

‎contrib/raftable/blockmem.c‎

Lines changed: 168 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,168 @@
1+
#include"blockmem.h"
2+
3+
#include<stddef.h>
4+
#include<assert.h>
5+
#include<stdbool.h>
6+
#include<string.h>
7+
8+
#defineBLOCK_LEN (256)
9+
#defineBLOCK_DATA_LEN ((BLOCK_LEN) - offsetof(block_t, data))
10+
#defineMETA(ORIGIN) ((meta_t *)(ORIGIN))
11+
#defineBLOCK(ORIGIN,ID) ((block_t *)((char *)(ORIGIN) + BLOCK_LEN * ID))
12+
#defineTAIL(ORIGIN,ID) (BLOCK(ORIGIN, ID)->next)
13+
#defineUSED(ORIGIN,ID) (BLOCK(ORIGIN, ID)->used)
14+
#defineLEN(ORIGIN,ID) (BLOCK(ORIGIN, ID)->len)
15+
#defineDATA(ORIGIN,ID) (BLOCK(ORIGIN, ID)->data)
16+
#defineFREE(ORIGIN) (META(ORIGIN)->freeblock)
17+
18+
typedefstructmeta_t
19+
{
20+
intfreeblock;/* the id of first free block, or -1 if none */
21+
chardata[1];
22+
}meta_t;
23+
24+
typedefstructblock_t
25+
{
26+
boolused;
27+
intnext;
28+
intlen;
29+
chardata[1];
30+
}block_t;
31+
32+
int
33+
blockmem_format(void*origin,size_tsize)
34+
{
35+
block_t*block;
36+
meta_t*meta;
37+
intid;
38+
intblocks= (size-1) /BLOCK_LEN;
39+
if (blocks <=0)return0;
40+
41+
FREE(origin)=1;
42+
43+
for (id=1;id <=blocks;id++)
44+
{
45+
USED(origin,id)=0;
46+
TAIL(origin,id)=id+1;
47+
}
48+
TAIL(origin,blocks)=0;/* the last block has no tail */
49+
50+
return1;
51+
}
52+
53+
staticsize_t
54+
block_fill(void*origin,intid,void*src,size_tlen)
55+
{
56+
if (len>BLOCK_DATA_LEN)
57+
len=BLOCK_DATA_LEN;
58+
LEN(origin,id)=len;
59+
memcpy(DATA(origin,id),src,len);
60+
returnlen;
61+
}
62+
63+
void
64+
block_clear(void*origin,intid)
65+
{
66+
TAIL(origin,id)=0;
67+
USED(origin,id)= true;
68+
LEN(origin,id)=0;
69+
}
70+
71+
staticint
72+
block_alloc(void*origin)
73+
{
74+
intnewborn=FREE(origin);
75+
if (!newborn)return0;
76+
77+
FREE(origin)=TAIL(origin,newborn);
78+
block_clear(origin,newborn);
79+
returnnewborn;
80+
}
81+
82+
staticvoid
83+
block_free(void*origin,intid)
84+
{
85+
/* behead the victim, and repeat for the tail */
86+
while (id>0)
87+
{
88+
inttail;
89+
assert(USED(origin,id));
90+
91+
USED(origin,id)= false;
92+
tail=TAIL(origin,id);
93+
TAIL(origin,id)=FREE(origin);
94+
FREE(origin)=id;
95+
id=tail;
96+
}
97+
}
98+
99+
int
100+
blockmem_put(void*origin,void*src,size_tlen)
101+
{
102+
inthead=0;
103+
intid=0;
104+
char*cursor=src;
105+
size_tbytesleft=len;
106+
107+
while (bytesleft>0)
108+
{
109+
intcopied;
110+
intnewid=block_alloc(origin);
111+
if (!newid) gotofailure;
112+
113+
copied=block_fill(origin,newid,cursor,bytesleft);
114+
115+
cursor+=copied;
116+
bytesleft-=copied;
117+
if (id)
118+
TAIL(origin,id)=newid;
119+
else
120+
head=newid;
121+
id=newid;
122+
}
123+
124+
returnhead;
125+
failure:
126+
block_free(origin,head);
127+
return-1;
128+
}
129+
130+
size_t
131+
blockmem_len(void*origin,intid)
132+
{
133+
size_tlen=0;
134+
while (id>0)
135+
{
136+
assert(USED(origin,id));
137+
len+=LEN(origin,id);
138+
id=TAIL(origin,id);
139+
}
140+
assert(len>0);
141+
returnlen;
142+
}
143+
144+
size_t
145+
blockmem_get(void*origin,intid,void*dst,size_tlen)
146+
{
147+
size_tcopied=0;
148+
char*cursor=dst;
149+
while ((id>0)&& (copied<len))
150+
{
151+
size_ttocopy=LEN(origin,id);
152+
if (tocopy>len-copied)
153+
tocopy=len-copied;
154+
assert(tocopy>0);
155+
assert(USED(origin,id));
156+
memcpy(cursor,DATA(origin,id),tocopy);
157+
copied+=tocopy;
158+
cursor+=tocopy;
159+
id=TAIL(origin,id);
160+
}
161+
returnlen;
162+
}
163+
164+
void
165+
blockmem_forget(void*origin,intid)
166+
{
167+
block_free(origin,id);
168+
}

‎contrib/raftable/blockmem.h‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
#ifndefBLOCKMEM_H
2+
#defineBLOCKMEM_H
3+
4+
#include<stdlib.h>
5+
6+
/*
7+
* Formats the memory region of 'size' bytes starting at 'origin'. Use this
8+
* before any other functions related to blockmem. Returns 1 on success,
9+
* 0 otherwise.
10+
*/
11+
intblockmem_format(void*origin,size_tsize);
12+
13+
/*
14+
* Allocates blocks in the formatted region starting at 'origin' and stores
15+
* 'len' bytes from 'src' inside those blocks. Returns the id for later _get(),
16+
* _len() and _forget() operations. Returns 0 if not enough free blocks.
17+
*/
18+
intblockmem_put(void*origin,void*src,size_tlen);
19+
20+
/*
21+
* Returns the length of data identified by 'id' that was previously stored
22+
* with a call to _put().
23+
*/
24+
size_tblockmem_len(void*origin,intid);
25+
26+
/*
27+
* Retrieves into 'dst' no more than 'len' bytes of data identified by 'id'
28+
* that were previously stored with a call to _put(). Returns the length of data
29+
* actually copied.
30+
*/
31+
size_tblockmem_get(void*origin,intid,void*dst,size_tlen);
32+
33+
/*
34+
* Frees the blocks occupied by data identified by 'id'.
35+
*/
36+
voidblockmem_forget(void*origin,intid);
37+
38+
#endif

‎contrib/raftable/test-blockmem.c‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
#include<stdio.h>
2+
#include<stdlib.h>
3+
#include<string.h>
4+
5+
#include"blockmem.h"
6+
7+
#defineBLOCKMEM_SIZE (1024 * 1024)
8+
#defineTEST_SIZE (10000)
9+
10+
int
11+
main()
12+
{
13+
intrc=EXIT_SUCCESS;
14+
void*origin=malloc(BLOCKMEM_SIZE);
15+
if (!blockmem_format(origin,BLOCKMEM_SIZE))
16+
{
17+
fprintf(stderr,"couldn't format the blockmem\n");
18+
rc=EXIT_FAILURE;
19+
}
20+
else
21+
{
22+
char*a,*b;
23+
inti,id;
24+
25+
a=malloc(TEST_SIZE);
26+
b=malloc(TEST_SIZE);
27+
28+
for (i=0;i<TEST_SIZE;i++)
29+
{
30+
a[i]=rand() % ('z'-'a'+1)+'a';
31+
b[i]='\0';
32+
}
33+
a[TEST_SIZE-1]='\0';
34+
35+
id=blockmem_put(origin,a,TEST_SIZE);
36+
i=blockmem_get(origin,id,b,TEST_SIZE);
37+
if (i!=TEST_SIZE)
38+
{
39+
fprintf(stderr,"got %d instead of %d\n",i,TEST_SIZE);
40+
rc=EXIT_FAILURE;
41+
}
42+
43+
if (strcmp(a,b))
44+
{
45+
fprintf(stderr,"did not get out what was put in\n");
46+
rc=EXIT_FAILURE;
47+
}
48+
49+
free(b);
50+
free(a);
51+
52+
free(origin);
53+
}
54+
55+
if (rc==EXIT_SUCCESS)
56+
fprintf(stderr,"blockmem test ok\n");
57+
else
58+
fprintf(stderr,"blockmem test failed\n");
59+
60+
returnrc;
61+
}

‎contrib/raftable/test.sh‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
#!/bin/sh
2+
CC=clang
3+
set -ex
4+
$CC -o test-blockmem test-blockmem.c blockmem.c
5+
./test-blockmem

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp