source: git/Singular/links/ndbm.cc @ ba5e9e

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