My Project
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
49static void dbm_access(DBM *db, long hash);
50static int getbit(DBM *db);
51static void setbit(DBM *db);
52static datum makdatum(char buf[PBLKSIZ], int n);
53static int finddatum(char buf[PBLKSIZ], datum item);
54static long dcalchash(datum item);
55static int delitem(char buf[PBLKSIZ], int n);
56static int additem(char buf[PBLKSIZ], datum item, datum item1);
57extern "C" int singular_fstat(int fd, struct stat *buf);
58
59DBM * 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);
90bad1:
91 (void) si_close(db->dbm_pagf);
92bad:
93 free((char *)db);
94 return ((DBM *)0);
95}
96
97void 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
104long 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
119datum dbm_fetch(DBM *db, datum key)
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 }
133err:
134 item.dptr = NULL;
135 item.dsize = 0;
136 return (item);
137}
138
139int 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
167int 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
205split:
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
252datum dbm_firstkey(DBM *db)
253{
254
255 db->dbm_blkptr = 0L;
256 db->dbm_keyptr = 0;
257 return (dbm_nextkey(db));
258}
259
260datum dbm_nextkey(DBM *db)
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 }
296err:
297 item.dptr = NULL;
298 item.dsize = 0;
299 return (item);
300}
301
302static 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
324static 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
346static 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
371static 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
392static 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
410STATIC_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};
420STATIC_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
440static 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 */
465static 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 */
497static 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
519static 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 */
i
int i
Definition: cfEzgcd.cc:132
b
CanonicalForm b
Definition: cfModGcd.cc:4103
s
const CanonicalForm int s
Definition: facAbsFact.cc:51
bad
bool bad
Definition: facFactorize.cc:64
j
int j
Definition: facHensel.cc:110
split
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3469
STATIC_VAR
#define STATIC_VAR
Definition: globaldefs.h:7
SEEK_SET
#define SEEK_SET
Definition: mod2.h:113
dbm_store
int dbm_store(DBM *db, datum key, datum dat, int replace)
Definition: ndbm.cc:167
BYTESIZ
#define BYTESIZ
Definition: ndbm.cc:46
dbm_fetch
datum dbm_fetch(DBM *db, datum key)
Definition: ndbm.cc:119
singular_fstat
int singular_fstat(int fd, struct stat *buf)
Definition: misc_ip.cc:1082
dbm_access
static void dbm_access(DBM *db, long hash)
Definition: ndbm.cc:302
dbm_delete
int dbm_delete(DBM *db, datum key)
Definition: ndbm.cc:139
hltab
STATIC_VAR long hltab[64]
Definition: ndbm.cc:421
bcopy
#define bcopy(a, b, c)
Definition: ndbm.cc:43
dbm_nextkey
datum dbm_nextkey(DBM *db)
Definition: ndbm.cc:260
dbm_firstkey
datum dbm_firstkey(DBM *db)
Definition: ndbm.cc:252
additem
static int additem(char buf[PBLKSIZ], datum item, datum item1)
Definition: ndbm.cc:497
dbm_open
DBM * dbm_open(char *file, int flags, int mode)
Definition: ndbm.cc:59
setbit
static void setbit(DBM *db)
Definition: ndbm.cc:346
delitem
static int delitem(char buf[PBLKSIZ], int n)
Definition: ndbm.cc:465
getbit
static int getbit(DBM *db)
Definition: ndbm.cc:324
dbm_forder
long dbm_forder(DBM *db, datum key)
Definition: ndbm.cc:104
makdatum
static datum makdatum(char buf[PBLKSIZ], int n)
Definition: ndbm.cc:371
dbm_close
void dbm_close(DBM *db)
Definition: ndbm.cc:97
hitab
STATIC_VAR int hitab[16]
Definition: ndbm.cc:417
finddatum
static int finddatum(char buf[PBLKSIZ], datum item)
Definition: ndbm.cc:392
dcalchash
static long dcalchash(datum item)
Definition: ndbm.cc:440
_DBM_RDONLY
#define _DBM_RDONLY
Definition: ndbm.h:70
_DBM_IOERR
#define _DBM_IOERR
Definition: ndbm.h:71
datum::dptr
char * dptr
Definition: ndbm.h:84
DBM::dbm_dirbuf
char dbm_dirbuf[DBLKSIZ]
Definition: ndbm.h:67
dbm_rdonly
#define dbm_rdonly(db)
Definition: ndbm.h:73
DBM::dbm_keyptr
int dbm_keyptr
Definition: ndbm.h:62
dbm_error
#define dbm_error(db)
Definition: ndbm.h:75
DBM::dbm_pagbno
long dbm_pagbno
Definition: ndbm.h:64
DBM::dbm_hmask
long dbm_hmask
Definition: ndbm.h:60
DBM::dbm_pagf
int dbm_pagf
Definition: ndbm.h:56
DBM::dbm_flags
int dbm_flags
Definition: ndbm.h:57
datum::dsize
int dsize
Definition: ndbm.h:85
DBM::dbm_maxbno
long dbm_maxbno
Definition: ndbm.h:58
DBM::dbm_dirbno
long dbm_dirbno
Definition: ndbm.h:66
DBM::dbm_dirf
int dbm_dirf
Definition: ndbm.h:55
DBM::dbm_blkno
long dbm_blkno
Definition: ndbm.h:63
PBLKSIZ
#define PBLKSIZ
Definition: ndbm.h:50
DBM::dbm_pagbuf
char dbm_pagbuf[PBLKSIZ]
Definition: ndbm.h:65
DBM::dbm_bitno
long dbm_bitno
Definition: ndbm.h:59
DBLKSIZ
#define DBLKSIZ
Definition: ndbm.h:52
DBM::dbm_blkptr
long dbm_blkptr
Definition: ndbm.h:61
DBM
Definition: ndbm.h:54
datum
Definition: ndbm.h:83
free
#define free
Definition: omAllocFunc.c:14
NULL
#define NULL
Definition: omList.c:12
malloc
void * malloc(size_t size)
Definition: omalloc.c:85
si_signals.h
si_open
#define si_open(...)
flags
int status int void size_t count int const void size_t count const char int flags
Definition: si_signals.h:73
buf
int status int void * buf
Definition: si_signals.h:59
fd
int status int fd
Definition: si_signals.h:59
Generated on Sun Apr 17 2022 10:43:55 for My Project by   doxygen 1.9.3 for Singular