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