My Project
Loading...
Searching...
No Matches
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 short tmp;
284 memcpy(&tmp, db->dbm_pagbuf, sizeof(tmp));
285 if (tmp != 0)
286 {
287 item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
288 if (item.dptr != NULL)
289 {
290 db->dbm_keyptr += 2;
291 return (item);
292 }
293 db->dbm_keyptr = 0;
294 }
295 if (++db->dbm_blkptr >= statb.st_size)
296 break;
297 }
298err:
299 item.dptr = NULL;
300 item.dsize = 0;
301 return (item);
302}
303
304static void dbm_access(DBM *db, long hash)
305{
306 for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1)
307 {
308 db->dbm_blkno = hash & db->dbm_hmask;
309 db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
310 if (getbit(db) == 0)
311 break;
312 }
313 if (db->dbm_blkno != db->dbm_pagbno)
314 {
315 db->dbm_pagbno = db->dbm_blkno;
316 (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, SEEK_SET);
317 if (si_read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
318 memset(db->dbm_pagbuf, 0, PBLKSIZ);
319#ifdef DEBUG
320 else if (chkblk(db->dbm_pagbuf) < 0)
321 db->dbm_flags |= _DBM_IOERR;
322#endif
323 }
324}
325
326static int getbit(DBM *db)
327{
328 long bn;
329 int b, i, n;
330
331
332 if (db->dbm_bitno > db->dbm_maxbno)
333 return (0);
334 n = db->dbm_bitno % BYTESIZ;
335 bn = db->dbm_bitno / BYTESIZ;
336 i = bn % DBLKSIZ;
337 b = bn / DBLKSIZ;
338 if (b != db->dbm_dirbno)
339 {
340 db->dbm_dirbno = b;
341 (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, SEEK_SET);
342 if (si_read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
343 memset(db->dbm_dirbuf, 0, DBLKSIZ);
344 }
345 return (db->dbm_dirbuf[i] & (1<<n));
346}
347
348static void setbit(DBM *db)
349{
350 long bn;
351 int i, n, b;
352
353 if (db->dbm_bitno > db->dbm_maxbno)
354 db->dbm_maxbno = db->dbm_bitno;
355 n = db->dbm_bitno % BYTESIZ;
356 bn = db->dbm_bitno / BYTESIZ;
357 i = bn % DBLKSIZ;
358 b = bn / DBLKSIZ;
359 if (b != db->dbm_dirbno)
360 {
361 db->dbm_dirbno = b;
362 (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, SEEK_SET);
363 if (si_read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
364 memset(db->dbm_dirbuf, 0, DBLKSIZ);
365 }
366 db->dbm_dirbuf[i] |= 1<<n;
367 db->dbm_dirbno = b;
368 (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, SEEK_SET);
369 if (si_write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
370 db->dbm_flags |= _DBM_IOERR;
371}
372
373static datum makdatum(char buf[PBLKSIZ], int n)
374{
375 short *sp;
376 int t;
377 datum item;
378
379 sp = (short *)buf;
380 if ((unsigned)n >= (unsigned)sp[0])
381 {
382 item.dptr = NULL;
383 item.dsize = 0;
384 return (item);
385 }
386 t = PBLKSIZ;
387 if (n > 0)
388 t = sp[n];
389 item.dptr = buf+sp[n+1];
390 item.dsize = t - sp[n+1];
391 return (item);
392}
393
394static int finddatum(char buf[PBLKSIZ], datum item)
395{
396 short *sp;
397 int i, n, j;
398
399 sp = (short *)buf;
400 n = PBLKSIZ;
401 for (i=0, j=sp[0]; i<j; i+=2, n = sp[i])
402 {
403 n -= sp[i+1];
404 if (n != item.dsize)
405 continue;
406 if (n == 0 || memcmp(&buf[sp[i+1]], item.dptr, n) == 0)
407 return (i);
408 }
409 return (-1);
410}
411
412STATIC_VAR int hitab[16]
413/* ken's
414{
415 055,043,036,054,063,014,004,005,
416 010,064,077,000,035,027,025,071,
417};
418*/
419 = { 61, 57, 53, 49, 45, 41, 37, 33,
420 29, 25, 21, 17, 13, 9, 5, 1,
421};
422STATIC_VAR long hltab[64]
423 = {
424 06100151277L,06106161736L,06452611562L,05001724107L,
425 02614772546L,04120731531L,04665262210L,07347467531L,
426 06735253126L,06042345173L,03072226605L,01464164730L,
427 03247435524L,07652510057L,01546775256L,05714532133L,
428 06173260402L,07517101630L,02431460343L,01743245566L,
429 00261675137L,02433103631L,03421772437L,04447707466L,
430 04435620103L,03757017115L,03641531772L,06767633246L,
431 02673230344L,00260612216L,04133454451L,00615531516L,
432 06137717526L,02574116560L,02304023373L,07061702261L,
433 05153031405L,05322056705L,07401116734L,06552375715L,
434 06165233473L,05311063631L,01212221723L,01052267235L,
435 06000615237L,01075222665L,06330216006L,04402355630L,
436 01451177262L,02000133436L,06025467062L,07121076461L,
437 03123433522L,01010635225L,01716177066L,05161746527L,
438 01736635071L,06243505026L,03637211610L,01756474365L,
439 04723077174L,03642763134L,05750130273L,03655541561L,
440};
441
442static long dcalchash(datum item)
443{
444 int s, c, j;
445 char *cp;
446 unsigned long hashl;
447 unsigned int hashi;
448
449 hashl = 0;
450 hashi = 0;
451 for (cp = item.dptr, s=item.dsize; --s >= 0; )
452 {
453 c = *cp++;
454 for (j=0; j<BYTESIZ; j+=4)
455 {
456 hashi += hitab[c&017];
457 hashl += hltab[hashi&63];
458 c >>= 4;
459 }
460 }
461 return (long)(hashl);
462}
463
464/*
465 * Delete pairs of items (n & n+1).
466 */
467static int delitem(char buf[PBLKSIZ], int n)
468{
469 short *sp, *sp1;
470 int i1, i2;
471
472 sp = (short *)buf;
473 i2 = sp[0];
474 if ((unsigned)n >= (unsigned)i2 || (n & 1))
475 return (0);
476 if (n == i2-2)
477 {
478 sp[0] -= 2;
479 return (1);
480 }
481 i1 = PBLKSIZ;
482 if (n > 0)
483 i1 = sp[n];
484 i1 -= sp[n+2];
485 if (i1 > 0)
486 {
487 i2 = sp[i2];
488 bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
489 }
490 sp[0] -= 2;
491 for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
492 sp[0] = sp[2] + i1;
493 return (1);
494}
495
496/*
497 * Add pairs of items (item & item1).
498 */
499static int additem(char buf[PBLKSIZ], datum item, datum item1)
500{
501 short *sp;
502 int i1, i2, tmp;
503
504 sp = (short *)buf;
505 i1 = PBLKSIZ;
506 i2 = sp[0];
507 if (i2 > 0)
508 i1 = sp[i2];
509 i1 -= item.dsize + item1.dsize;
510 tmp = (i2+3) * sizeof(short);
511 if (i1 <= tmp) return (0);
512 sp[0] += 2;
513 sp[++i2] = i1 + item1.dsize;
514 bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
515 sp[++i2] = i1;
516 bcopy(item1.dptr, &buf[i1], item1.dsize);
517 return (1);
518}
519
520#ifdef DEBUG
521static chkblk(char buf[PBLKSIZ])
522{
523 short *sp;
524 int t, i;
525
526 sp = (short *)buf;
527 t = PBLKSIZ;
528 for (i=0; i<sp[0]; i++)
529 {
530 if (sp[i+1] > t)
531 return (-1);
532 t = sp[i+1];
533 }
534 if (t < (sp[0]+1)*sizeof(short))
535 return (-1);
536 return (0);
537}
538#endif
539
540#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:115
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:304
dbm_delete
int dbm_delete(DBM *db, datum key)
Definition: ndbm.cc:139
hltab
STATIC_VAR long hltab[64]
Definition: ndbm.cc:423
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:499
dbm_open
DBM * dbm_open(char *file, int flags, int mode)
Definition: ndbm.cc:59
setbit
static void setbit(DBM *db)
Definition: ndbm.cc:348
delitem
static int delitem(char buf[PBLKSIZ], int n)
Definition: ndbm.cc:467
getbit
static int getbit(DBM *db)
Definition: ndbm.cc:326
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:373
dbm_close
void dbm_close(DBM *db)
Definition: ndbm.cc:97
hitab
STATIC_VAR int hitab[16]
Definition: ndbm.cc:419
finddatum
static int finddatum(char buf[PBLKSIZ], datum item)
Definition: ndbm.cc:394
dcalchash
static long dcalchash(datum item)
Definition: ndbm.cc:442
_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
malloc
#define malloc
Definition: omAllocFunc.c:12
NULL
#define NULL
Definition: omList.c:12
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 Mon Feb 27 2023 10:53:50 for My Project by   doxygen 1.9.5 for Singular