"Fossies" - the Fresh Open Source Software Archive 
Member "perl-5.32.1/ext/SDBM_File/README" (18 Dec 2020, 11429 Bytes) of package /linux/misc/perl-5.32.1.tar.xz:
As a special service "Fossies" has tried to format the requested text file into HTML format (style:
standard) with prefixed line numbers.
Alternatively you can here
view or
download the uninterpreted source code file.
1
2
3
4
5
6
7 sdbm - Substitute DBM
8 or
9 Berkeley ndbm for Every UN*X[1] Made Simple
10
11 Ozan (oz) Yigit
12
13 The Guild of PD Software Toolmakers
14 Toronto - Canada
15
16 oz@nexus.yorku.ca
17
18
19
20 Implementation is the sincerest form of flattery. - L. Peter
21 Deutsch
22
23 A The Clone of the ndbm library
24
25 The sources accompanying this notice - sdbm - consti-
26 tute the first public release (Dec. 1990) of a complete
27 clone of the Berkeley UN*X ndbm library. The sdbm library is
28 meant to clone the proven functionality of ndbm as closely
29 as possible, including a few improvements. It is practical,
30 easy to understand, and compatible. The sdbm library is not
31 derived from any licensed, proprietary or copyrighted
32 software.
33
34 The sdbm implementation is based on a 1978 algorithm
35 [Lar78] by P.-A. (Paul) Larson known as "Dynamic Hashing".
36 In the course of searching for a substitute for ndbm, I pro-
37 totyped three different external-hashing algorithms [Lar78,
38 Fag79, Lit80] and ultimately chose Larson's algorithm as a
39 basis of the sdbm implementation. The Bell Labs dbm (and
40 therefore ndbm) is based on an algorithm invented by Ken
41 Thompson, [Tho90, Tor87] and predates Larson's work.
42
43 The sdbm programming interface is totally compatible
44 with ndbm and includes a slight improvement in database ini-
45 tialization. It is also expected to be binary-compatible
46 under most UN*X versions that support the ndbm library.
47
48 The sdbm implementation shares the shortcomings of the
49 ndbm library, as a side effect of various simplifications to
50 the original Larson algorithm. It does produce holes in the
51 page file as it writes pages past the end of file. (Larson's
52 paper include a clever solution to this problem that is a
53 result of using the hash value directly as a block address.)
54 On the other hand, extensive tests seem to indicate that
55 sdbm creates fewer holes in general, and the resulting page-
56 files are smaller. The sdbm implementation is also faster
57 than ndbm in database creation. Unlike the ndbm, the sdbm
58 _________________________
59
60 [1] UN*X is not a trademark of any (dis)organization.
61
62
63
64
65
66
67
68
69
70 - 2 -
71
72
73 store operation will not "wander away" trying to split its
74 data pages to insert a datum that cannot (due to elaborate
75 worst-case situations) be inserted. (It will fail after a
76 pre-defined number of attempts.)
77
78 Important Compatibility Warning
79
80 The sdbm and ndbm libraries cannot share databases: one
81 cannot read the (dir/pag) database created by the other.
82 This is due to the differences between the ndbm and sdbm
83 algorithms[2], and the hash functions used. It is easy to
84 convert between the dbm/ndbm databases and sdbm by ignoring
85 the index completely: see dbd, dbu etc.
86
87
88 Notice of Intellectual Property
89
90 The entire sdbm library package, as authored by me, Ozan S.
91 Yigit, is hereby placed in the public domain. As such, the
92 author is not responsible for the consequences of use of
93 this software, no matter how awful, even if they arise from
94 defects in it. There is no expressed or implied warranty for
95 the sdbm library.
96
97 Since the sdbm library package is in the public domain,
98 this original release or any additional public-domain
99 releases of the modified original cannot possibly (by defin-
100 ition) be withheld from you. Also by definition, You (singu-
101 lar) have all the rights to this code (including the right
102 to sell without permission, the right to hoard[3] and the
103 right to do other icky things as you see fit) but those
104 rights are also granted to everyone else.
105
106 Please note that all previous distributions of this
107 software contained a copyright (which is now dropped) to
108 protect its origins and its current public domain status
109 against any possible claims and/or challenges.
110
111 Acknowledgments
112
113 Many people have been very helpful and supportive. A
114 partial list would necessarily include Rayan Zacherissen
115 (who contributed the man page, and also hacked a MMAP
116 _________________________
117
118 [2] Torek's discussion [Tor87] indicates that
119 dbm/ndbm implementations use the hash value to traverse
120 the radix trie differently than sdbm and as a result,
121 the page indexes are generated in different order. For
122 more information, send e-mail to the author.
123 [3] You cannot really hoard something that is avail-
124 able to the public at large, but try if it makes you
125 feel any better.
126
127
128
129
130
131
132
133
134
135
136 - 3 -
137
138
139 version of sdbm), Arnold Robbins, Chris Lewis, Bill David-
140 sen, Henry Spencer, Geoff Collyer, Rich Salz (who got me
141 started in the first place), Johannes Ruschein (who did the
142 minix port) and David Tilbrook. I thank you all.
143
144 Distribution Manifest and Notes
145
146 This distribution of sdbm includes (at least) the following:
147
148 CHANGES change log
149 README this file.
150 biblio a small bibliography on external hashing
151 dba.c a crude (n/s)dbm page file analyzer
152 dbd.c a crude (n/s)dbm page file dumper (for conversion)
153 dbe.1 man page for dbe.c
154 dbe.c Janick's database editor
155 dbm.c a dbm library emulation wrapper for ndbm/sdbm
156 dbm.h header file for the above
157 dbu.c a crude db management utility
158 hash.c hashing function
159 makefile guess.
160 pair.c page-level routines (posted earlier)
161 pair.h header file for the above
162 readme.ms troff source for the README file
163 sdbm.3 man page
164 sdbm.c the real thing
165 sdbm.h header file for the above
166 tune.h place for tuning & portability thingies
167 util.c miscellaneous
168
169 dbu is a simple database manipulation program[4] that
170 tries to look like Bell Labs' cbt utility. It is currently
171 incomplete in functionality. I use dbu to test out the rou-
172 tines: it takes (from stdin) tab separated key/value pairs
173 for commands like build or insert or takes keys for commands
174 like delete or look.
175
176 dbu <build|creat|look|insert|cat|delete> dbmfile
177
178 dba is a crude analyzer of dbm/sdbm/ndbm page files. It
179 scans the entire page file, reporting page level statistics,
180 and totals at the end.
181
182 dbd is a crude dump program for dbm/ndbm/sdbm data-
183 bases. It ignores the bitmap, and dumps the data pages in
184 sequence. It can be used to create input for the dbu util-
185 ity. Note that dbd will skip any NULLs in the key and data
186 fields, thus is unsuitable to convert some peculiar
187 _________________________
188
189 [4] The dbd, dba, dbu utilities are quick hacks and
190 are not fit for production use. They were developed
191 late one night, just to test out sdbm, and convert some
192 databases.
193
194
195
196
197
198
199
200
201
202 - 4 -
203
204
205 databases that insist in including the terminating null.
206
207 I have also included a copy of the dbe (ndbm DataBase
208 Editor) by Janick Bergeron [janick@bnr.ca] for your pleas-
209 ure. You may find it more useful than the little dbu util-
210 ity.
211
212 dbm.[ch] is a dbm library emulation on top of ndbm (and
213 hence suitable for sdbm). Written by Robert Elz.
214
215 The sdbm library has been around in beta test for quite
216 a long time, and from whatever little feedback I received
217 (maybe no news is good news), I believe it has been func-
218 tioning without any significant problems. I would, of
219 course, appreciate all fixes and/or improvements. Portabil-
220 ity enhancements would especially be useful.
221
222 Implementation Issues
223
224 Hash functions: The algorithm behind sdbm implementa-
225 tion needs a good bit-scrambling hash function to be effec-
226 tive. I ran into a set of constants for a simple hash func-
227 tion that seem to help sdbm perform better than ndbm for
228 various inputs:
229
230 /*
231 * polynomial conversion ignoring overflows
232 * 65599 nice. 65587 even better.
233 */
234 long
235 dbm_hash(char *str, int len) {
236 unsigned long n = 0;
237
238 while (len--)
239 n = n * 65599 + *str++;
240 return n;
241 }
242
243 There may be better hash functions for the purposes of
244 dynamic hashing. Try your favorite, and check the pagefile.
245 If it contains too many pages with too many holes, (in rela-
246 tion to this one for example) or if sdbm simply stops work-
247 ing (fails after SPLTMAX attempts to split) when you feed
248 your NEWS history file to it, you probably do not have a
249 good hashing function. If you do better (for different
250 types of input), I would like to know about the function you
251 use.
252
253 Block sizes: It seems (from various tests on a few
254 machines) that a page file block size PBLKSIZ of 1024 is by
255 far the best for performance, but this also happens to limit
256 the size of a key/value pair. Depending on your needs, you
257 may wish to increase the page size, and also adjust PAIRMAX
258 (the maximum size of a key/value pair allowed: should always
259
260
261
262
263
264
265
266
267
268 - 5 -
269
270
271 be at least three words smaller than PBLKSIZ.) accordingly.
272 The system-wide version of the library should probably be
273 configured with 1024 (distribution default), as this appears
274 to be sufficient for most common uses of sdbm.
275
276 Portability
277
278 This package has been tested in many different UN*Xes
279 even including minix, and appears to be reasonably portable.
280 This does not mean it will port easily to non-UN*X systems.
281
282 Notes and Miscellaneous
283
284 The sdbm is not a very complicated package, at least
285 not after you familiarize yourself with the literature on
286 external hashing. There are other interesting algorithms in
287 existence that ensure (approximately) single-read access to
288 a data value associated with any key. These are directory-
289 less schemes such as linear hashing [Lit80] (+ Larson varia-
290 tions), spiral storage [Mar79] or directory schemes such as
291 extensible hashing [Fag79] by Fagin et al. I do hope these
292 sources provide a reasonable playground for experimentation
293 with other algorithms. See the June 1988 issue of ACM Com-
294 puting Surveys [Enb88] for an excellent overview of the
295 field.
296
297 References
298
299
300 [Lar78]
301 P.-A. Larson, "Dynamic Hashing", BIT, vol. 18, pp.
302 184-201, 1978.
303
304 [Tho90]
305 Ken Thompson, private communication, Nov. 1990
306
307 [Lit80]
308 W. Litwin, "Linear Hashing: A new tool for file and
309 table addressing", Proceedings of the 6th Conference on
310 Very Large Dabatases (Montreal), pp. 212-223, Very
311 Large Database Foundation, Saratoga, Calif., 1980.
312
313 [Fag79]
314 R. Fagin, J. Nievergelt, N. Pippinger, and H. R.
315 Strong, "Extendible Hashing - A Fast Access Method for
316 Dynamic Files", ACM Trans. Database Syst., vol. 4,
317 no.3, pp. 315-344, Sept. 1979.
318
319 [Wal84]
320 Rich Wales, "Discussion of 'dbm' data base system",
321 USENET newsgroup unix.wizards, Jan. 1984.
322
323 [Tor87]
324 Chris Torek, "Re: dbm.a and ndbm.a archives",
325
326
327
328
329
330
331
332
333
334 - 6 -
335
336
337 USENET newsgroup comp.unix, 1987.
338
339 [Mar79]
340 G. N. Martin, "Spiral Storage: Incrementally Augment-
341 able Hash Addressed Storage", Technical Report #27,
342 University of Varwick, Coventry, U.K., 1979.
343
344 [Enb88]
345 R. J. Enbody and H. C. Du, "Dynamic Hashing
346 Schemes",ACM Computing Surveys, vol. 20, no. 2, pp.
347 85-113, June 1988.
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396