home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / libdbm / dbm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-05-05  |  7.3 KB  |  466 lines
  1. #include    "dbm.h"
  2. #include    <sys/types.h>
  3. #include    <sys/stat.h>
  4.  
  5. dbminit(file)
  6. char *file;
  7. {
  8.     struct stat statb;
  9.  
  10.     strcpy(pagbuf, file);
  11.     strcat(pagbuf, ".pag");
  12.     pagf = open(pagbuf, 2);
  13.  
  14.     strcpy(pagbuf, file);
  15.     strcat(pagbuf, ".dir");
  16.     dirf = open(pagbuf, 2);
  17.     if(pagf < 0 || dirf < 0) {
  18.         printf("cannot open database %s\n", file);
  19.         return(-1);
  20.     }
  21.     fstat(dirf, &statb);
  22.     maxbno = statb.st_size*BYTESIZ-1;
  23.     return(0);
  24. }
  25.  
  26. long
  27. forder(key)
  28. datum key;
  29. {
  30.     long hash;
  31.  
  32.     hash = calchash(key);
  33.     for(hmask=0;; hmask=(hmask<<1)+1) {
  34.         blkno = hash & hmask;
  35.         bitno = blkno + hmask;
  36.         if(getbit() == 0)
  37.             break;
  38.     }
  39.     return(blkno);
  40. }
  41.  
  42. datum
  43. fetch(key)
  44. datum key;
  45. {
  46.     register i;
  47.     datum item;
  48.  
  49.     dbm_access(calchash(key));
  50.     for(i=0;; i+=2) {
  51.         item = makdatum(pagbuf, i);
  52.         if(item.dptr == NULL)
  53.             return(item);
  54.         if(cmpdatum(key, item) == 0) {
  55.             item = makdatum(pagbuf, i+1);
  56.             if(item.dptr == NULL)
  57.                 printf("items not in pairs\n");
  58.             return(item);
  59.         }
  60.     }
  61. }
  62.  
  63. delete(key)
  64. datum key;
  65. {
  66.     register i;
  67.     datum item;
  68.  
  69.     dbm_access(calchash(key));
  70.     for(i=0;; i+=2) {
  71.         item = makdatum(pagbuf, i);
  72.         if(item.dptr == NULL)
  73.             return(-1);
  74.         if(cmpdatum(key, item) == 0) {
  75.             delitem(pagbuf, i);
  76.             delitem(pagbuf, i);
  77.             break;
  78.         }
  79.     }
  80.     lseek(pagf, blkno*PBLKSIZ, 0);
  81.     write(pagf, pagbuf, PBLKSIZ);
  82.     return(0);
  83. }
  84.  
  85. store(key, dat)
  86. datum key, dat;
  87. {
  88.     register i;
  89.     datum item;
  90.     char ovfbuf[PBLKSIZ];
  91.  
  92. loop:
  93.     dbm_access(calchash(key));
  94.     for(i=0;; i+=2) {
  95.         item = makdatum(pagbuf, i);
  96.         if(item.dptr == NULL)
  97.             break;
  98.         if(cmpdatum(key, item) == 0) {
  99.             delitem(pagbuf, i);
  100.             delitem(pagbuf, i);
  101.             break;
  102.         }
  103.     }
  104.     i = additem(pagbuf, key);
  105.     if(i < 0)
  106.         goto split;
  107.     if(additem(pagbuf, dat) < 0) {
  108.         delitem(pagbuf, i);
  109.         goto split;
  110.     }
  111.     lseek(pagf, blkno*PBLKSIZ, 0);
  112.     write(pagf, pagbuf, PBLKSIZ);
  113.     return;
  114.  
  115. split:
  116.     if(key.dsize+dat.dsize+2*sizeof(short) >= PBLKSIZ) {
  117.         printf("entry too big\n");
  118.         return;
  119.     }
  120.     clrbuf(ovfbuf, PBLKSIZ);
  121.     for(i=0;;) {
  122.         item = makdatum(pagbuf, i);
  123.         if(item.dptr == NULL)
  124.             break;
  125.         if(calchash(item) & (hmask+1)) {
  126.             additem(ovfbuf, item);
  127.             delitem(pagbuf, i);
  128.             item = makdatum(pagbuf, i);
  129.             if(item.dptr == NULL) {
  130.                 printf("split not paired\n");
  131.                 break;
  132.             }
  133.             additem(ovfbuf, item);
  134.             delitem(pagbuf, i);
  135.             continue;
  136.         }
  137.         i += 2;
  138.     }
  139.     lseek(pagf, blkno*PBLKSIZ, 0);
  140.     write(pagf, pagbuf, PBLKSIZ);
  141.     lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
  142.     write(pagf, ovfbuf, PBLKSIZ);
  143.     setbit();
  144.     goto loop;
  145. }
  146.  
  147. datum
  148. firstkey()
  149. {
  150.     return(firsthash(0L));
  151. }
  152.  
  153. datum
  154. nextkey(key)
  155. datum key;
  156. {
  157.     register i;
  158.     datum item, bitem;
  159.     long hash;
  160.     int f;
  161.  
  162.     hash = calchash(key);
  163.     dbm_access(hash);
  164.     f = 1;
  165.     for(i=0;; i+=2) {
  166.         item = makdatum(pagbuf, i);
  167.         if(item.dptr == NULL)
  168.             break;
  169.         if(cmpdatum(key, item) <= 0)
  170.             continue;
  171.         if(f || cmpdatum(bitem, item) < 0) {
  172.             bitem = item;
  173.             f = 0;
  174.         }
  175.     }
  176.     if(f == 0)
  177.         return(bitem);
  178.     hash = hashinc(hash);
  179.     if(hash == 0)
  180.         return(item);
  181.     return(firsthash(hash));
  182. }
  183.  
  184. datum
  185. firsthash(hash)
  186. long hash;
  187. {
  188.     register i;
  189.     datum item, bitem;
  190.  
  191. loop:
  192.     dbm_access(hash);
  193.     bitem = makdatum(pagbuf, 0);
  194.     for(i=2;; i+=2) {
  195.         item = makdatum(pagbuf, i);
  196.         if(item.dptr == NULL)
  197.             break;
  198.         if(cmpdatum(bitem, item) < 0)
  199.             bitem = item;
  200.     }
  201.     if(bitem.dptr != NULL)
  202.         return(bitem);
  203.     hash = hashinc(hash);
  204.     if(hash == 0)
  205.         return(item);
  206.     goto loop;
  207. }
  208.  
  209. dbm_access(hash)
  210. long hash;
  211. {
  212.     static long oldb = -1;
  213.  
  214.     for(hmask=0;; hmask=(hmask<<1)+1) {
  215.         blkno = hash & hmask;
  216.         bitno = blkno + hmask;
  217.         if(getbit() == 0)
  218.             break;
  219.     }
  220.     if(blkno != oldb) {
  221.         clrbuf(pagbuf, PBLKSIZ);
  222.         lseek(pagf, blkno*PBLKSIZ, 0);
  223.         read(pagf, pagbuf, PBLKSIZ);
  224.         chkblk(pagbuf);
  225.         oldb = blkno;
  226.     }
  227. }
  228.  
  229. getbit()
  230. {
  231.     long bn;
  232.     register b, i, n;
  233.     static oldb = -1;
  234.  
  235.     if(bitno > maxbno)
  236.         return(0);
  237.     n = bitno % BYTESIZ;
  238.     bn = bitno / BYTESIZ;
  239.     i = bn % DBLKSIZ;
  240.     b = bn / DBLKSIZ;
  241.     if(b != oldb) {
  242.         clrbuf(dirbuf, DBLKSIZ);
  243.         lseek(dirf, (long)b*DBLKSIZ, 0);
  244.         read(dirf, dirbuf, DBLKSIZ);
  245.         oldb = b;
  246.     }
  247.     if(dirbuf[i] & (1<<n))
  248.         return(1);
  249.     return(0);
  250. }
  251.  
  252. setbit()
  253. {
  254.     long bn;
  255.     register i, n, b;
  256.  
  257.     if(bitno > maxbno) {
  258.         maxbno = bitno;
  259.         getbit();
  260.     }
  261.     n = bitno % BYTESIZ;
  262.     bn = bitno / BYTESIZ;
  263.     i = bn % DBLKSIZ;
  264.     b = bn / DBLKSIZ;
  265.     dirbuf[i] |= 1<<n;
  266.     lseek(dirf, (long)b*DBLKSIZ, 0);
  267.     write(dirf, dirbuf, DBLKSIZ);
  268. }
  269.  
  270. clrbuf(cp, n)
  271. register char *cp;
  272. register n;
  273. {
  274.  
  275.     do
  276.         *cp++ = 0;
  277.     while(--n);
  278. }
  279.  
  280. datum
  281. makdatum(buf, n)
  282. char buf[PBLKSIZ];
  283. {
  284.     register short *sp;
  285.     register t;
  286.     datum item;
  287.  
  288.     sp = (short *)buf;
  289.     if(n < 0 || n >= sp[0])
  290.         goto null;
  291.     t = PBLKSIZ;
  292.     if(n > 0)
  293.         t = sp[n+1-1];
  294.     item.dptr = buf+sp[n+1];
  295.     item.dsize = t - sp[n+1];
  296.     return(item);
  297.  
  298. null:
  299.     item.dptr = NULL;
  300.     item.dsize = 0;
  301.     return(item);
  302. }
  303.  
  304. cmpdatum(d1, d2)
  305. datum d1, d2;
  306. {
  307.     register n;
  308.     register char *p1, *p2;
  309.  
  310.     n = d1.dsize;
  311.     if(n != d2.dsize)
  312.         return(n - d2.dsize);
  313.     if(n == 0)
  314.         return(0);
  315.     p1 = d1.dptr;
  316.     p2 = d2.dptr;
  317.     do
  318.         if(*p1++ != *p2++)
  319.             return(*--p1 - *--p2);
  320.     while(--n);
  321.     return(0);
  322. }
  323.  
  324. int    hitab[16] = 
  325. {    61, 57, 53, 49, 45, 41, 37, 33,
  326.     29, 25, 21, 17, 13,  9,  5,  1,
  327. };
  328. long    hltab[64] = 
  329. {
  330.     06100151277L,06106161736L,06452611562L,05001724107L,
  331.     02614772546L,04120731531L,04665262210L,07347467531L,
  332.     06735253126L,06042345173L,03072226605L,01464164730L,
  333.     03247435524L,07652510057L,01546775256L,05714532133L,
  334.     06173260402L,07517101630L,02431460343L,01743245566L,
  335.     00261675137L,02433103631L,03421772437L,04447707466L,
  336.     04435620103L,03757017115L,03641531772L,06767633246L,
  337.     02673230344L,00260612216L,04133454451L,00615531516L,
  338.     06137717526L,02574116560L,02304023373L,07061702261L,
  339.     05153031405L,05322056705L,07401116734L,06552375715L,
  340.     06165233473L,05311063631L,01212221723L,01052267235L,
  341.     06000615237L,01075222665L,06330216006L,04402355630L,
  342.     01451177262L,02000133436L,06025467062L,07121076461L,
  343.     03123433522L,01010635225L,01716177066L,05161746527L,
  344.     01736635071L,06243505026L,03637211610L,01756474365L,
  345.     04723077174L,03642763134L,05750130273L,03655541561L,
  346. };
  347.  
  348. long
  349. hashinc(hash)
  350. long hash;
  351. {
  352.     long bit;
  353.  
  354.     hash &= hmask;
  355.     bit = hmask+1;
  356.     for(;;) {
  357.         bit >>= 1;
  358.         if(bit == 0)
  359.             return(0L);
  360.         if((hash&bit) == 0)
  361.             return(hash|bit);
  362.         hash &= ~bit;
  363.     }
  364. }
  365.  
  366. long
  367. calchash(item)
  368. datum item;
  369. {
  370.     register i, j, f;
  371.     long hashl;
  372.     int hashi;
  373.  
  374.     hashl = 0;
  375.     hashi = 0;
  376.     for(i=0; i<item.dsize; i++) {
  377.         f = item.dptr[i];
  378.         for(j=0; j<BYTESIZ; j+=4) {
  379.             hashi += hitab[f&017];
  380.             hashl += hltab[hashi&077];
  381.             f >>= 4;
  382.         }
  383.     }
  384.     return(hashl);
  385. }
  386.  
  387. delitem(buf, n)
  388. char buf[PBLKSIZ];
  389. {
  390.     register short *sp;
  391.     register i1, i2, i3;
  392.  
  393.     sp = (short *)buf;
  394.     if(n < 0 || n >= sp[0])
  395.         goto bad;
  396.     i1 = sp[n+1];
  397.     i2 = PBLKSIZ;
  398.     if(n > 0)
  399.         i2 = sp[n+1-1];
  400.     i3 = sp[sp[0]+1-1];
  401.     if(i2 > i1)
  402.     while(i1 > i3) {
  403.         i1--;
  404.         i2--;
  405.         buf[i2] = buf[i1];
  406.         buf[i1] = 0;
  407.     }
  408.     i2 -= i1;
  409.     for(i1=n+1; i1<sp[0]; i1++)
  410.         sp[i1+1-1] = sp[i1+1] + i2;
  411.     sp[0]--;
  412.     sp[sp[0]+1] = 0;
  413.     return;
  414.  
  415. bad:
  416.     printf("bad delitem\n");
  417.     abort();
  418. }
  419.  
  420. additem(buf, item)
  421. char buf[PBLKSIZ];
  422. datum item;
  423. {
  424.     register short *sp;
  425.     register i1, i2;
  426.  
  427.     sp = (short *)buf;
  428.     i1 = PBLKSIZ;
  429.     if(sp[0] > 0)
  430.         i1 = sp[sp[0]+1-1];
  431.     i1 -= item.dsize;
  432.     i2 = (sp[0]+2) * sizeof(short);
  433.     if(i1 <= i2)
  434.         return(-1);
  435.     sp[sp[0]+1] = i1;
  436.     for(i2=0; i2<item.dsize; i2++) {
  437.         buf[i1] = item.dptr[i2];
  438.         i1++;
  439.     }
  440.     sp[0]++;
  441.     return(sp[0]-1);
  442. }
  443.  
  444. chkblk(buf)
  445. char buf[PBLKSIZ];
  446. {
  447.     register short *sp;
  448.     register t, i;
  449.  
  450.     sp = (short *)buf;
  451.     t = PBLKSIZ;
  452.     for(i=0; i<sp[0]; i++) {
  453.         if(sp[i+1] > t)
  454.             goto bad;
  455.         t = sp[i+1];
  456.     }
  457.     if(t < (sp[0]+1)*sizeof(short))
  458.         goto bad;
  459.     return;
  460.  
  461. bad:
  462.     printf("bad block\n");
  463.     abort();
  464.     clrbuf(buf, PBLKSIZ);
  465. }
  466.