source: git/Singular/ndbm.cc @ d7ad81

spielwiese
Last change on this file since d7ad81 was 6ce030f, checked in by Oleksandr Motsak <motsak@…>, 12 years ago
removal of the $Id$ svn tag from everywhere NOTE: the git SHA1 may be used instead (only on special places) NOTE: the libraries Singular/LIB/*.lib still contain the marker due to our current use of svn
  • Property mode set to 100644
File size: 12.7 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4
5//**************************************************************************/
6//
7//
8//**************************************************************************/
9// 'ndbm.cc' containes all low-level functions to manipulate dbm-files
10// for the original Copyright of this file and 'ndbm.h' see below .
11//
12// some minor change where needed to compile and run under MacOS/MPW
13//
14//**************************************************************************/
15
16#include "config.h"
17#include <kernel/mod2.h>
18#ifdef HAVE_DBM
19#ifndef HPUX_9
20#include <strings.h>
21#endif
22/*
23 * Copyright (c) 1983 Regents of the University of California.
24 * All rights reserved.  The Berkeley software License Agreement
25 * specifies the terms and conditions for redistribution.
26 * for details see ndbm.h
27 */
28
29#if defined(LIBC_SCCS) && !defined(lint)
30static char sccsid[] = "@(#)ndbm.c        5.3 (Berkeley) 3/9/86";
31#endif
32
33//**************************************************************************/
34
35#include <stdio.h>
36/* alternative:
37* #   define EPERM 1
38* #   define ENOMEM 23
39* #   define ENOSPC 28
40* #   define L_SET SEEK_SET
41*/
42#include <sys/types.h>
43#include <sys/stat.h>
44#include <sys/file.h>
45#include <errno.h>
46#include <stdlib.h>
47#include <string.h>
48#include <unistd.h>
49#include <fcntl.h>
50#ifndef HAVE_BCOPY
51#   define bcopy(a,b,c) memmove(b,a,c)
52#endif /* not HAVE_BCOPY */
53#include <Singular/ndbm.h>
54
55#define BYTESIZ 8
56#undef setbit
57
58static  void dbm_access(register DBM *db, long hash);
59static  int getbit(register DBM *db);
60static  void setbit(register DBM *db);
61static  datum makdatum(char buf[PBLKSIZ], int n);
62static  int finddatum(char buf[PBLKSIZ], datum item);
63static  long hashinc(register DBM *db, long hash);
64static  long dcalchash(datum item);
65static  int delitem(char buf[PBLKSIZ], int n);
66static  int additem(char buf[PBLKSIZ], datum item, datum item1);
67// extern  int errno;
68extern "C" int singular_fstat(int fd, struct stat *buf);
69
70DBM * dbm_open(char *file, int flags, int mode)
71{
72  struct stat statb;
73  register DBM *db;
74
75  if ((db = (DBM *)malloc(sizeof *db)) == 0)
76  {
77    errno = ENOMEM;
78    return ((DBM *)0);
79  }
80#ifdef MSDOS
81  // default mode of open is ascii, we need binary mode.
82  flags |= O_BINARY;
83#endif
84  db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
85  if ((flags & 03) == O_WRONLY)
86    flags = (flags & ~03) | O_RDWR;
87  strcpy(db->dbm_pagbuf, file);
88  strcat(db->dbm_pagbuf, ".pag");
89  db->dbm_pagf = open(db->dbm_pagbuf, flags, mode);
90  if (db->dbm_pagf < 0)
91    goto bad;
92  strcpy(db->dbm_pagbuf, file);
93  strcat(db->dbm_pagbuf, ".dir");
94  db->dbm_dirf = open(db->dbm_pagbuf, flags, mode);
95  if (db->dbm_dirf < 0)
96    goto bad1;
97  singular_fstat(db->dbm_dirf, &statb);
98  db->dbm_maxbno = statb.st_size*BYTESIZ-1;
99  db->dbm_pagbno = db->dbm_dirbno = -1;
100  return (db);
101bad1:
102  (void) close(db->dbm_pagf);
103bad:
104  free((char *)db);
105  return ((DBM *)0);
106}
107
108void dbm_close(DBM *db)
109{
110  (void) close(db->dbm_dirf);
111  (void) close(db->dbm_pagf);
112  free((char *)db);
113}
114
115long dbm_forder(register DBM *db, datum key)
116{
117  long hash;
118
119  hash = dcalchash(key);
120  for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1)
121  {
122    db->dbm_blkno = hash & db->dbm_hmask;
123    db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
124    if (getbit(db) == 0)
125      break;
126  }
127  return (db->dbm_blkno);
128}
129
130datum dbm_fetch(register DBM *db, datum key)
131{
132  register int i;
133  datum item;
134
135  if (dbm_error(db))
136    goto err;
137  dbm_access(db, dcalchash(key));
138  if ((i = finddatum(db->dbm_pagbuf, key)) >= 0)
139  {
140    item = makdatum(db->dbm_pagbuf, i+1);
141    if (item.dptr != NULL)
142      return (item);
143  }
144err:
145  item.dptr = NULL;
146  item.dsize = 0;
147  return (item);
148}
149
150int dbm_delete(register DBM *db, datum key)
151{
152  register int i;
153  datum item;
154
155  if (dbm_error(db))
156    return (-1);
157  if (dbm_rdonly(db))
158  {
159    errno = EPERM;
160    return (-1);
161  }
162  dbm_access(db, dcalchash(key));
163  if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
164    return (-1);
165  if (!delitem(db->dbm_pagbuf, i))
166    goto err;
167  db->dbm_pagbno = db->dbm_blkno;
168  (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
169  if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
170  {
171  err:
172    db->dbm_flags |= _DBM_IOERR;
173    return (-1);
174  }
175  return (0);
176}
177
178int dbm_store(register DBM *db, datum key, datum dat, int replace)
179{
180  register int i;
181  int ret;
182  datum item, item1;
183  char ovfbuf[PBLKSIZ];
184
185  if (dbm_error(db))
186    return (-1);
187  if (dbm_rdonly(db))
188  {
189    errno = EPERM;
190    return (-1);
191  }
192   
193_loop:
194  dbm_access(db, dcalchash(key));
195  if ((i = finddatum(db->dbm_pagbuf, key)) >= 0)
196  {
197    if (!replace)
198      return (1);
199    if (!delitem(db->dbm_pagbuf, i))
200    {
201      db->dbm_flags |= _DBM_IOERR;
202      return (-1);
203    }
204  }
205  if (!additem(db->dbm_pagbuf, key, dat))
206    goto split;
207  db->dbm_pagbno = db->dbm_blkno;
208  (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
209  if ( (ret=write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ)) != PBLKSIZ)
210  {
211    db->dbm_flags |= _DBM_IOERR;
212    return (-1);
213  }
214  return (0);
215
216split:
217  if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ)
218  {
219    db->dbm_flags |= _DBM_IOERR;
220    errno = ENOSPC;
221    return (-1);
222  }
223  memset(ovfbuf, 0, PBLKSIZ);
224  for (i=0;;) {
225    item = makdatum(db->dbm_pagbuf, i);
226    if (item.dptr == NULL)
227      break;
228    if (dcalchash(item) & (db->dbm_hmask+1))
229    {
230      item1 = makdatum(db->dbm_pagbuf, i+1);
231      if (item1.dptr == NULL) {
232        fprintf(stderr, "ndbm: split not paired\n");
233        db->dbm_flags |= _DBM_IOERR;
234        break;
235      }
236      if (!additem(ovfbuf, item, item1) ||
237          !delitem(db->dbm_pagbuf, i))
238      {
239        db->dbm_flags |= _DBM_IOERR;
240        return (-1);
241      }
242      continue;
243    }
244    i += 2;
245  }
246  db->dbm_pagbno = db->dbm_blkno;
247  (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
248  if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
249  {
250    db->dbm_flags |= _DBM_IOERR;
251    return (-1);
252  }
253  (void) lseek(db->dbm_pagf, (db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ, L_SET);
254  if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ)
255  {
256    db->dbm_flags |= _DBM_IOERR;
257    return (-1);
258  }
259  setbit(db);
260  goto _loop;
261}
262
263datum dbm_firstkey(DBM *db)
264{
265
266  db->dbm_blkptr = 0L;
267  db->dbm_keyptr = 0;
268  return (dbm_nextkey(db));
269}
270
271datum dbm_nextkey(register DBM *db)
272{
273  struct stat statb;
274  datum item;
275
276  if (dbm_error(db) 
277       || singular_fstat(db->dbm_pagf, &statb) < 0
278  )
279                goto err;
280  statb.st_size /= PBLKSIZ;
281  for (;;)
282  {
283    if (db->dbm_blkptr != db->dbm_pagbno)
284    {
285      db->dbm_pagbno = db->dbm_blkptr;
286      (void) lseek(db->dbm_pagf, db->dbm_blkptr*PBLKSIZ, L_SET);
287      if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
288        memset(db->dbm_pagbuf, 0, PBLKSIZ);
289#ifdef DEBUG
290      else if (chkblk(db->dbm_pagbuf) < 0)
291        db->dbm_flags |= _DBM_IOERR;
292#endif
293    }
294    if (((short *)db->dbm_pagbuf)[0] != 0)
295    {
296      item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
297      if (item.dptr != NULL)
298      {
299        db->dbm_keyptr += 2;
300        return (item);
301      }
302      db->dbm_keyptr = 0;
303    }
304    if (++db->dbm_blkptr >= statb.st_size)
305      break;
306  }
307err:
308  item.dptr = NULL;
309  item.dsize = 0;
310  return (item);
311}
312
313static void dbm_access(register DBM *db, long hash)
314{
315  for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1)
316  {
317    db->dbm_blkno = hash & db->dbm_hmask;
318    db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
319    if (getbit(db) == 0)
320      break;
321  }
322  if (db->dbm_blkno != db->dbm_pagbno)
323  {
324    db->dbm_pagbno = db->dbm_blkno;
325    (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
326    if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
327      memset(db->dbm_pagbuf, 0, PBLKSIZ);
328#ifdef DEBUG
329    else if (chkblk(db->dbm_pagbuf) < 0)
330      db->dbm_flags |= _DBM_IOERR;
331#endif
332  }
333}
334
335static int getbit(register DBM *db)
336{
337  long bn;
338  register int b, i, n;
339
340
341  if (db->dbm_bitno > db->dbm_maxbno)
342    return (0);
343  n = db->dbm_bitno % BYTESIZ;
344  bn = db->dbm_bitno / BYTESIZ;
345  i = bn % DBLKSIZ;
346  b = bn / DBLKSIZ;
347  if (b != db->dbm_dirbno)
348  {
349    db->dbm_dirbno = b;
350    (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
351    if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
352      memset(db->dbm_dirbuf, 0, DBLKSIZ);
353  }
354  return (db->dbm_dirbuf[i] & (1<<n));
355}
356
357static void setbit(register DBM *db)
358{
359  long bn;
360  register int i, n, b;
361
362  if (db->dbm_bitno > db->dbm_maxbno)
363    db->dbm_maxbno = db->dbm_bitno;
364  n = db->dbm_bitno % BYTESIZ;
365  bn = db->dbm_bitno / BYTESIZ;
366  i = bn % DBLKSIZ;
367  b = bn / DBLKSIZ;
368  if (b != db->dbm_dirbno)
369  {
370    db->dbm_dirbno = b;
371    (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
372    if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
373      memset(db->dbm_dirbuf, 0, DBLKSIZ);
374  }
375  db->dbm_dirbuf[i] |= 1<<n;
376  db->dbm_dirbno = b;
377  (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
378  if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
379    db->dbm_flags |= _DBM_IOERR;
380}
381
382static datum makdatum(char buf[PBLKSIZ], int n)
383{
384  register short *sp;
385  register int t;
386  datum item;
387
388  sp = (short *)buf;
389  if ((unsigned)n >= (unsigned)sp[0])
390  {
391    item.dptr = NULL;
392    item.dsize = 0;
393    return (item);
394  }
395  t = PBLKSIZ;
396  if (n > 0)
397    t = sp[n];
398  item.dptr = buf+sp[n+1];
399  item.dsize = t - sp[n+1];
400  return (item);
401}
402
403static int finddatum(char buf[PBLKSIZ], datum item)
404{
405  register short *sp;
406  register int i, n, j;
407
408  sp = (short *)buf;
409  n = PBLKSIZ;
410  for (i=0, j=sp[0]; i<j; i+=2, n = sp[i])
411  {
412    n -= sp[i+1];
413    if (n != item.dsize)
414      continue;
415    if (n == 0 || memcmp(&buf[sp[i+1]], item.dptr, n) == 0)
416      return (i);
417  }
418  return (-1);
419}
420
421static  int hitab[16]
422/* ken's
423{
424        055,043,036,054,063,014,004,005,
425        010,064,077,000,035,027,025,071,
426};
427*/
428 = {    61, 57, 53, 49, 45, 41, 37, 33,
429        29, 25, 21, 17, 13,  9,  5,  1,
430};
431static  long hltab[64]
432 = {
433        06100151277L,06106161736L,06452611562L,05001724107L,
434        02614772546L,04120731531L,04665262210L,07347467531L,
435        06735253126L,06042345173L,03072226605L,01464164730L,
436        03247435524L,07652510057L,01546775256L,05714532133L,
437        06173260402L,07517101630L,02431460343L,01743245566L,
438        00261675137L,02433103631L,03421772437L,04447707466L,
439        04435620103L,03757017115L,03641531772L,06767633246L,
440        02673230344L,00260612216L,04133454451L,00615531516L,
441        06137717526L,02574116560L,02304023373L,07061702261L,
442        05153031405L,05322056705L,07401116734L,06552375715L,
443        06165233473L,05311063631L,01212221723L,01052267235L,
444        06000615237L,01075222665L,06330216006L,04402355630L,
445        01451177262L,02000133436L,06025467062L,07121076461L,
446        03123433522L,01010635225L,01716177066L,05161746527L,
447        01736635071L,06243505026L,03637211610L,01756474365L,
448        04723077174L,03642763134L,05750130273L,03655541561L,
449};
450
451static long hashinc(register DBM *db, long hash)
452{
453  long bit;
454
455  hash &= db->dbm_hmask;
456  bit = db->dbm_hmask+1;
457  for (;;)
458  {
459    bit >>= 1;
460    if (bit == 0)
461      return (0L);
462    if ((hash & bit) == 0)
463      return (hash | bit);
464    hash &= ~bit;
465  }
466}
467
468static long dcalchash(datum item)
469{
470  register int s, c, j;
471  register char *cp;
472  register long hashl;
473  register int hashi;
474
475  hashl = 0;
476  hashi = 0;
477  for (cp = item.dptr, s=item.dsize; --s >= 0; )
478  {
479    c = *cp++;
480    for (j=0; j<BYTESIZ; j+=4)
481    {
482      hashi += hitab[c&017];
483      hashl += hltab[hashi&63];
484      c >>= 4;
485    }
486  }
487  return (hashl);
488}
489
490/*
491 * Delete pairs of items (n & n+1).
492 */
493static int delitem(char buf[PBLKSIZ], int n)
494{
495  register short *sp, *sp1;
496  register int i1, i2;
497
498  sp = (short *)buf;
499  i2 = sp[0];
500  if ((unsigned)n >= (unsigned)i2 || (n & 1))
501    return (0);
502  if (n == i2-2)
503  {
504    sp[0] -= 2;
505    return (1);
506  }
507  i1 = PBLKSIZ;
508  if (n > 0)
509    i1 = sp[n];
510  i1 -= sp[n+2];
511  if (i1 > 0)
512  {
513    i2 = sp[i2];
514    bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
515  }
516  sp[0] -= 2;
517  for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
518    sp[0] = sp[2] + i1;
519  return (1);
520}
521
522/*
523 * Add pairs of items (item & item1).
524 */
525static int additem(char buf[PBLKSIZ], datum item, datum item1)
526{
527  register short *sp;
528  register int i1, i2, tmp;
529
530  sp = (short *)buf;
531  i1 = PBLKSIZ;
532  i2 = sp[0];
533  if (i2 > 0)
534    i1 = sp[i2];
535  i1 -= item.dsize + item1.dsize;
536  tmp = (i2+3) * sizeof(short);
537  if (i1 <= tmp) return (0);
538  sp[0] += 2;
539  sp[++i2] = i1 + item1.dsize;
540  bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
541  sp[++i2] = i1;
542  bcopy(item1.dptr, &buf[i1], item1.dsize);
543  return (1);
544}
545
546#ifdef DEBUG
547static chkblk(char buf[PBLKSIZ])
548{
549  register short *sp;
550  register t, i;
551
552  sp = (short *)buf;
553  t = PBLKSIZ;
554  for (i=0; i<sp[0]; i++)
555  {
556    if (sp[i+1] > t)
557      return (-1);
558    t = sp[i+1];
559  }
560  if (t < (sp[0]+1)*sizeof(short))
561    return (-1);
562  return (0);
563}
564#endif
565
566#endif /* HAVE_DBM */
Note: See TracBrowser for help on using the repository browser.