source: git/Singular/links/ndbm.cc @ 27c79f

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