kissdb.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447
  1. /* (Keep It) Simple Stupid Database
  2. *
  3. * Written by Adam Ierymenko <[email protected]>
  4. * KISSDB is in the public domain and is distributed with NO WARRANTY. */
  5. /* Compile with KISSDB_TEST to build as a test program. */
  6. /* Note: big-endian systems will need changes to implement byte swapping
  7. * on hash table file I/O. Or you could just use it as-is if you don't care
  8. * that your database files will be unreadable on little-endian systems. */
  9. #define _FILE_OFFSET_BITS 64
  10. #include "kissdb.h"
  11. #include <string.h>
  12. #include <stdlib.h>
  13. #include <stdint.h>
  14. #ifdef _WIN32
  15. #define fseeko _fseeki64
  16. #define ftello _ftelli64
  17. #endif
  18. #define KISSDB_HEADER_SIZE ((sizeof(uint64_t) * 3) + 4)
  19. /* djb2 hash function */
  20. static uint64_t KISSDB_hash(const void *b,unsigned long len)
  21. {
  22. unsigned long i;
  23. uint64_t hash = 5381;
  24. for(i=0;i<len;++i)
  25. hash = ((hash << 5) + hash) + (uint64_t)(((const uint8_t *)b)[i]);
  26. return hash;
  27. }
  28. int KISSDB_open(
  29. KISSDB *db,
  30. const char *path,
  31. int mode,
  32. unsigned long hash_table_size,
  33. unsigned long key_size,
  34. unsigned long value_size)
  35. {
  36. uint64_t tmp;
  37. uint8_t tmp2[4];
  38. uint64_t *httmp;
  39. uint64_t *hash_tables_rea;
  40. #ifdef _WIN32
  41. db->f = (FILE *)0;
  42. fopen_s(&db->f,path,((mode == KISSDB_OPEN_MODE_RWREPLACE) ? "w+b" : (((mode == KISSDB_OPEN_MODE_RDWR)||(mode == KISSDB_OPEN_MODE_RWCREAT)) ? "r+b" : "rb")));
  43. #else
  44. db->f = fopen(path,((mode == KISSDB_OPEN_MODE_RWREPLACE) ? "w+b" : (((mode == KISSDB_OPEN_MODE_RDWR)||(mode == KISSDB_OPEN_MODE_RWCREAT)) ? "r+b" : "rb")));
  45. #endif
  46. if (!db->f) {
  47. if (mode == KISSDB_OPEN_MODE_RWCREAT) {
  48. #ifdef _WIN32
  49. db->f = (FILE *)0;
  50. fopen_s(&db->f,path,"w+b");
  51. #else
  52. db->f = fopen(path,"w+b");
  53. #endif
  54. }
  55. if (!db->f)
  56. return KISSDB_ERROR_IO;
  57. }
  58. if (fseeko(db->f,0,SEEK_END)) {
  59. fclose(db->f);
  60. return KISSDB_ERROR_IO;
  61. }
  62. if (ftello(db->f) < KISSDB_HEADER_SIZE) {
  63. /* write header if not already present */
  64. if ((hash_table_size)&&(key_size)&&(value_size)) {
  65. if (fseeko(db->f,0,SEEK_SET)) { fclose(db->f); return KISSDB_ERROR_IO; }
  66. tmp2[0] = 'K'; tmp2[1] = 'd'; tmp2[2] = 'B'; tmp2[3] = KISSDB_VERSION;
  67. if (fwrite(tmp2,4,1,db->f) != 1) { fclose(db->f); return KISSDB_ERROR_IO; }
  68. tmp = hash_table_size;
  69. if (fwrite(&tmp,sizeof(uint64_t),1,db->f) != 1) { fclose(db->f); return KISSDB_ERROR_IO; }
  70. tmp = key_size;
  71. if (fwrite(&tmp,sizeof(uint64_t),1,db->f) != 1) { fclose(db->f); return KISSDB_ERROR_IO; }
  72. tmp = value_size;
  73. if (fwrite(&tmp,sizeof(uint64_t),1,db->f) != 1) { fclose(db->f); return KISSDB_ERROR_IO; }
  74. fflush(db->f);
  75. } else {
  76. fclose(db->f);
  77. return KISSDB_ERROR_INVALID_PARAMETERS;
  78. }
  79. } else {
  80. if (fseeko(db->f,0,SEEK_SET)) { fclose(db->f); return KISSDB_ERROR_IO; }
  81. if (fread(tmp2,4,1,db->f) != 1) { fclose(db->f); return KISSDB_ERROR_IO; }
  82. if ((tmp2[0] != 'K')||(tmp2[1] != 'd')||(tmp2[2] != 'B')||(tmp2[3] != KISSDB_VERSION)) {
  83. fclose(db->f);
  84. return KISSDB_ERROR_CORRUPT_DBFILE;
  85. }
  86. if (fread(&tmp,sizeof(uint64_t),1,db->f) != 1) { fclose(db->f); return KISSDB_ERROR_IO; }
  87. if (!tmp) {
  88. fclose(db->f);
  89. return KISSDB_ERROR_CORRUPT_DBFILE;
  90. }
  91. hash_table_size = (unsigned long)tmp;
  92. if (fread(&tmp,sizeof(uint64_t),1,db->f) != 1) { fclose(db->f); return KISSDB_ERROR_IO; }
  93. if (!tmp) {
  94. fclose(db->f);
  95. return KISSDB_ERROR_CORRUPT_DBFILE;
  96. }
  97. key_size = (unsigned long)tmp;
  98. if (fread(&tmp,sizeof(uint64_t),1,db->f) != 1) { fclose(db->f); return KISSDB_ERROR_IO; }
  99. if (!tmp) {
  100. fclose(db->f);
  101. return KISSDB_ERROR_CORRUPT_DBFILE;
  102. }
  103. value_size = (unsigned long)tmp;
  104. }
  105. db->hash_table_size = hash_table_size;
  106. db->key_size = key_size;
  107. db->value_size = value_size;
  108. db->hash_table_size_bytes = sizeof(uint64_t) * (hash_table_size + 1); /* [hash_table_size] == next table */
  109. httmp = malloc(db->hash_table_size_bytes);
  110. if (!httmp) {
  111. fclose(db->f);
  112. return KISSDB_ERROR_MALLOC;
  113. }
  114. db->num_hash_tables = 0;
  115. db->hash_tables = (uint64_t *)0;
  116. while (fread(httmp,db->hash_table_size_bytes,1,db->f) == 1) {
  117. hash_tables_rea = realloc(db->hash_tables,db->hash_table_size_bytes * (db->num_hash_tables + 1));
  118. if (!hash_tables_rea) {
  119. KISSDB_close(db);
  120. free(httmp);
  121. return KISSDB_ERROR_MALLOC;
  122. }
  123. db->hash_tables = hash_tables_rea;
  124. memcpy(((uint8_t *)db->hash_tables) + (db->hash_table_size_bytes * db->num_hash_tables),httmp,db->hash_table_size_bytes);
  125. ++db->num_hash_tables;
  126. if (httmp[db->hash_table_size]) {
  127. if (fseeko(db->f,httmp[db->hash_table_size],SEEK_SET)) {
  128. KISSDB_close(db);
  129. free(httmp);
  130. return KISSDB_ERROR_IO;
  131. }
  132. } else break;
  133. }
  134. free(httmp);
  135. return 0;
  136. }
  137. void KISSDB_close(KISSDB *db)
  138. {
  139. if (db->hash_tables)
  140. free(db->hash_tables);
  141. if (db->f)
  142. fclose(db->f);
  143. memset(db,0,sizeof(KISSDB));
  144. }
  145. int KISSDB_get(KISSDB *db,const void *key,void *vbuf)
  146. {
  147. uint8_t tmp[4096];
  148. const uint8_t *kptr;
  149. unsigned long klen,i;
  150. uint64_t hash = KISSDB_hash(key,db->key_size) % (uint64_t)db->hash_table_size;
  151. uint64_t offset;
  152. uint64_t *cur_hash_table;
  153. long n;
  154. cur_hash_table = db->hash_tables;
  155. for(i=0;i<db->num_hash_tables;++i) {
  156. offset = cur_hash_table[hash];
  157. if (offset) {
  158. if (fseeko(db->f,offset,SEEK_SET))
  159. return KISSDB_ERROR_IO;
  160. kptr = (const uint8_t *)key;
  161. klen = db->key_size;
  162. while (klen) {
  163. n = (long)fread(tmp,1,(klen > sizeof(tmp)) ? sizeof(tmp) : klen,db->f);
  164. if (n > 0) {
  165. if (memcmp(kptr,tmp,n))
  166. goto get_no_match_next_hash_table;
  167. kptr += n;
  168. klen -= (unsigned long)n;
  169. } else return 1; /* not found */
  170. }
  171. if (fread(vbuf,db->value_size,1,db->f) == 1)
  172. return 0; /* success */
  173. else return KISSDB_ERROR_IO;
  174. } else return 1; /* not found */
  175. get_no_match_next_hash_table:
  176. cur_hash_table += db->hash_table_size + 1;
  177. }
  178. return 1; /* not found */
  179. }
  180. int KISSDB_put(KISSDB *db,const void *key,const void *value)
  181. {
  182. uint8_t tmp[4096];
  183. const uint8_t *kptr;
  184. unsigned long klen,i;
  185. uint64_t hash = KISSDB_hash(key,db->key_size) % (uint64_t)db->hash_table_size;
  186. uint64_t offset;
  187. uint64_t htoffset,lasthtoffset;
  188. uint64_t endoffset;
  189. uint64_t *cur_hash_table;
  190. uint64_t *hash_tables_rea;
  191. long n;
  192. lasthtoffset = htoffset = KISSDB_HEADER_SIZE;
  193. cur_hash_table = db->hash_tables;
  194. for(i=0;i<db->num_hash_tables;++i) {
  195. offset = cur_hash_table[hash];
  196. if (offset) {
  197. /* rewrite if already exists */
  198. if (fseeko(db->f,offset,SEEK_SET))
  199. return KISSDB_ERROR_IO;
  200. kptr = (const uint8_t *)key;
  201. klen = db->key_size;
  202. while (klen) {
  203. n = (long)fread(tmp,1,(klen > sizeof(tmp)) ? sizeof(tmp) : klen,db->f);
  204. if (n > 0) {
  205. if (memcmp(kptr,tmp,n))
  206. goto put_no_match_next_hash_table;
  207. kptr += n;
  208. klen -= (unsigned long)n;
  209. }
  210. }
  211. if (fwrite(value,db->value_size,1,db->f) == 1) {
  212. fflush(db->f);
  213. return 0; /* success */
  214. } else return KISSDB_ERROR_IO;
  215. } else {
  216. /* add if an empty hash table slot is discovered */
  217. if (fseeko(db->f,0,SEEK_END))
  218. return KISSDB_ERROR_IO;
  219. endoffset = ftello(db->f);
  220. if (fwrite(key,db->key_size,1,db->f) != 1)
  221. return KISSDB_ERROR_IO;
  222. if (fwrite(value,db->value_size,1,db->f) != 1)
  223. return KISSDB_ERROR_IO;
  224. if (fseeko(db->f,htoffset + (sizeof(uint64_t) * hash),SEEK_SET))
  225. return KISSDB_ERROR_IO;
  226. if (fwrite(&endoffset,sizeof(uint64_t),1,db->f) != 1)
  227. return KISSDB_ERROR_IO;
  228. cur_hash_table[hash] = endoffset;
  229. fflush(db->f);
  230. return 0; /* success */
  231. }
  232. put_no_match_next_hash_table:
  233. lasthtoffset = htoffset;
  234. htoffset = cur_hash_table[db->hash_table_size];
  235. cur_hash_table += (db->hash_table_size + 1);
  236. }
  237. /* if no existing slots, add a new page of hash table entries */
  238. if (fseeko(db->f,0,SEEK_END))
  239. return KISSDB_ERROR_IO;
  240. endoffset = ftello(db->f);
  241. hash_tables_rea = realloc(db->hash_tables,db->hash_table_size_bytes * (db->num_hash_tables + 1));
  242. if (!hash_tables_rea)
  243. return KISSDB_ERROR_MALLOC;
  244. db->hash_tables = hash_tables_rea;
  245. cur_hash_table = &(db->hash_tables[(db->hash_table_size + 1) * db->num_hash_tables]);
  246. memset(cur_hash_table,0,db->hash_table_size_bytes);
  247. cur_hash_table[hash] = endoffset + db->hash_table_size_bytes; /* where new entry will go */
  248. if (fwrite(cur_hash_table,db->hash_table_size_bytes,1,db->f) != 1)
  249. return KISSDB_ERROR_IO;
  250. if (fwrite(key,db->key_size,1,db->f) != 1)
  251. return KISSDB_ERROR_IO;
  252. if (fwrite(value,db->value_size,1,db->f) != 1)
  253. return KISSDB_ERROR_IO;
  254. if (db->num_hash_tables) {
  255. if (fseeko(db->f,lasthtoffset + (sizeof(uint64_t) * db->hash_table_size),SEEK_SET))
  256. return KISSDB_ERROR_IO;
  257. if (fwrite(&endoffset,sizeof(uint64_t),1,db->f) != 1)
  258. return KISSDB_ERROR_IO;
  259. db->hash_tables[((db->hash_table_size + 1) * (db->num_hash_tables - 1)) + db->hash_table_size] = endoffset;
  260. }
  261. ++db->num_hash_tables;
  262. fflush(db->f);
  263. return 0; /* success */
  264. }
  265. void KISSDB_Iterator_init(KISSDB *db,KISSDB_Iterator *dbi)
  266. {
  267. dbi->db = db;
  268. dbi->h_no = 0;
  269. dbi->h_idx = 0;
  270. }
  271. int KISSDB_Iterator_next(KISSDB_Iterator *dbi,void *kbuf,void *vbuf)
  272. {
  273. uint64_t offset;
  274. if ((dbi->h_no < dbi->db->num_hash_tables)&&(dbi->h_idx < dbi->db->hash_table_size)) {
  275. while (!(offset = dbi->db->hash_tables[((dbi->db->hash_table_size + 1) * dbi->h_no) + dbi->h_idx])) {
  276. if (++dbi->h_idx >= dbi->db->hash_table_size) {
  277. dbi->h_idx = 0;
  278. if (++dbi->h_no >= dbi->db->num_hash_tables)
  279. return 0;
  280. }
  281. }
  282. if (fseeko(dbi->db->f,offset,SEEK_SET))
  283. return KISSDB_ERROR_IO;
  284. if (fread(kbuf,dbi->db->key_size,1,dbi->db->f) != 1)
  285. return KISSDB_ERROR_IO;
  286. if (fread(vbuf,dbi->db->value_size,1,dbi->db->f) != 1)
  287. return KISSDB_ERROR_IO;
  288. if (++dbi->h_idx >= dbi->db->hash_table_size) {
  289. dbi->h_idx = 0;
  290. ++dbi->h_no;
  291. }
  292. return 1;
  293. }
  294. return 0;
  295. }
  296. #ifdef KISSDB_TEST
  297. #include <inttypes.h>
  298. int main(int argc,char **argv)
  299. {
  300. uint64_t i,j;
  301. uint64_t v[8];
  302. KISSDB db;
  303. KISSDB_Iterator dbi;
  304. char got_all_values[10000];
  305. int q;
  306. printf("Opening new empty database test.db...\n");
  307. if (KISSDB_open(&db,"test.db",KISSDB_OPEN_MODE_RWREPLACE,1024,8,sizeof(v))) {
  308. printf("KISSDB_open failed\n");
  309. return 1;
  310. }
  311. printf("Adding and then re-getting 10000 64-byte values...\n");
  312. for(i=0;i<10000;++i) {
  313. for(j=0;j<8;++j)
  314. v[j] = i;
  315. if (KISSDB_put(&db,&i,v)) {
  316. printf("KISSDB_put failed (%"PRIu64")\n",i);
  317. return 1;
  318. }
  319. memset(v,0,sizeof(v));
  320. if ((q = KISSDB_get(&db,&i,v))) {
  321. printf("KISSDB_get (1) failed (%"PRIu64") (%d)\n",i,q);
  322. return 1;
  323. }
  324. for(j=0;j<8;++j) {
  325. if (v[j] != i) {
  326. printf("KISSDB_get (1) failed, bad data (%"PRIu64")\n",i);
  327. return 1;
  328. }
  329. }
  330. }
  331. printf("Getting 10000 64-byte values...\n");
  332. for(i=0;i<10000;++i) {
  333. if ((q = KISSDB_get(&db,&i,v))) {
  334. printf("KISSDB_get (2) failed (%"PRIu64") (%d)\n",i,q);
  335. return 1;
  336. }
  337. for(j=0;j<8;++j) {
  338. if (v[j] != i) {
  339. printf("KISSDB_get (2) failed, bad data (%"PRIu64")\n",i);
  340. return 1;
  341. }
  342. }
  343. }
  344. printf("Closing and re-opening database in read-only mode...\n");
  345. KISSDB_close(&db);
  346. if (KISSDB_open(&db,"test.db",KISSDB_OPEN_MODE_RDONLY,1024,8,sizeof(v))) {
  347. printf("KISSDB_open failed\n");
  348. return 1;
  349. }
  350. printf("Getting 10000 64-byte values...\n");
  351. for(i=0;i<10000;++i) {
  352. if ((q = KISSDB_get(&db,&i,v))) {
  353. printf("KISSDB_get (3) failed (%"PRIu64") (%d)\n",i,q);
  354. return 1;
  355. }
  356. for(j=0;j<8;++j) {
  357. if (v[j] != i) {
  358. printf("KISSDB_get (3) failed, bad data (%"PRIu64")\n",i);
  359. return 1;
  360. }
  361. }
  362. }
  363. printf("Iterator test...\n");
  364. KISSDB_Iterator_init(&db,&dbi);
  365. i = 0xdeadbeef;
  366. memset(got_all_values,0,sizeof(got_all_values));
  367. while (KISSDB_Iterator_next(&dbi,&i,&v) > 0) {
  368. if (i < 10000)
  369. got_all_values[i] = 1;
  370. else {
  371. printf("KISSDB_Iterator_next failed, bad data (%"PRIu64")\n",i);
  372. return 1;
  373. }
  374. }
  375. for(i=0;i<10000;++i) {
  376. if (!got_all_values[i]) {
  377. printf("KISSDB_Iterator failed, missing value index %"PRIu64"\n",i);
  378. return 1;
  379. }
  380. }
  381. KISSDB_close(&db);
  382. printf("All tests OK!\n");
  383. return 0;
  384. }
  385. #endif