1 /* $Id: isam.c,v 1.27 2002-08-02 19:26:56 adam Exp $
2 Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
5 This file is part of the Zebra server.
7 Zebra is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with Zebra; see the file LICENSE.zebra. If not, write to the
19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
37 static ispt_struct *ispt_freelist = 0;
41 int total_merge_operations;
43 int dub_items_removed;
47 int delete_insert_noop;
56 static ISPT ispt_alloc()
63 ispt_freelist = ispt_freelist->next;
66 p = (ISPT) xmalloc(sizeof(ispt_struct));
70 static void ispt_free(ISPT pt)
72 pt->next = ispt_freelist;
76 static int splitargs(const char *s, char *bf[], int max)
81 while (*s && isspace(*s))
89 logf (LOG_WARN, "Ignoring extra args to is resource");
93 while (*s && !isspace(*s))
102 ISAM is_open(BFiles bfs, const char *name,
103 int (*cmp)(const void *p1, const void *p2),
104 int writeflag, int keysize, Res res)
107 char *nm, *r, *pp[IS_MAX_BLOCKTYPES+1], m[2];
108 int num, size, rs, tmp, i;
111 logf (LOG_DEBUG, "is_open(%s, %s)", name, writeflag ? "RW" : "RDONLY");
114 statistics.total_merge_operations = 0;
115 statistics.total_items = 0;
116 statistics.dub_items_removed = 0;
117 statistics.new_items = 0;
118 statistics.failed_deletes = 0;
119 statistics.skipped_inserts = 0;
120 statistics.delete_insert_noop = 0;
121 statistics.delete_replace = 0;
122 statistics.deletes = 0;
123 statistics.remaps = 0;
124 statistics.new_tables = 0;
125 statistics.block_jumps = 0;
126 statistics.tab_deletes = 0;
129 inew = (ISAM) xmalloc(sizeof(*inew));
130 inew->writeflag = writeflag;
131 for (i = 0; i < IS_MAX_BLOCKTYPES; i++)
132 inew->types[i].index = 0; /* dummy */
134 /* determine number and size of blocktypes */
135 if (!(r = res_get_def(res,
136 nm = strconcat(name, ".",
137 "blocktypes", 0), "64 512 4K 32K")) ||
138 !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
140 logf (LOG_FATAL, "Failed to locate resource %s", nm);
143 inew->num_types = num;
144 for (i = 0; i < num; i++)
146 if ((rs = sscanf(pp[i], "%d%1[bBkKmM]", &size, m)) < 1)
148 logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
156 inew->types[i].blocksize = size; break;
158 inew->types[i].blocksize = size * 1024; break;
160 inew->types[i].blocksize = size * 1048576; break;
162 logf (LOG_FATAL, "Illegal size suffix: %c", *m);
165 inew->types[i].dbuf = (char *) xmalloc(inew->types[i].blocksize);
168 if (!(inew->types[i].bf = bf_open(bfs, strconcat(name, m, 0),
169 inew->types[i].blocksize, writeflag)))
171 logf (LOG_FATAL, "bf_open failed");
174 if ((rs = is_rb_read(&inew->types[i], &th)) > 0)
176 if (th.blocksize != inew->types[i].blocksize)
178 logf (LOG_FATAL, "File blocksize mismatch in %s", name);
181 inew->types[i].freelist = th.freelist;
182 inew->types[i].top = th.top;
184 else if (writeflag) /* write dummy superblock to determine top */
186 if ((rs = is_rb_write(&inew->types[i], &th)) <=0) /* dummy */
188 logf (LOG_FATAL, "Failed to write initial superblock.");
191 inew->types[i].freelist = -1;
192 inew->types[i].top = rs;
194 /* ELSE: this is an empty file opened in read-only mode. */
197 inew->keysize = keysize;
200 if (!(r = res_get_def(res, nm = strconcat(name, ".",
201 "keysize", 0), "4")))
203 logf (LOG_FATAL, "Failed to locate resource %s", nm);
206 if ((inew->keysize = atoi(r)) <= 0)
208 logf (LOG_FATAL, "Must specify positive keysize.");
213 /* determine repack percent */
214 if (!(r = res_get_def(res, nm = strconcat(name, ".", "repack",
215 0), IS_DEF_REPACK_PERCENT)))
217 logf (LOG_FATAL, "Failed to locate resource %s", nm);
220 inew->repack = atoi(r);
222 /* determine max keys/blocksize */
223 if (!(r = res_get_def(res,
224 nm = strconcat(name, ".",
225 "maxkeys", 0), "50 640 10000")) ||
226 !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
228 logf (LOG_FATAL, "Failed to locate resource %s", nm);
231 if (num < inew->num_types -1)
233 logf (LOG_FATAL, "Not enough elements in %s", nm);
236 for (i = 0; i < num; i++)
238 if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
240 logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
243 inew->types[i].max_keys = tmp;
246 /* determine max keys/block */
247 for (i = 0; i < inew->num_types; i++)
249 if (!inew->types[i].index)
251 inew->types[i].max_keys_block = (inew->types[i].blocksize - 2 *
252 sizeof(int)) / inew->keysize;
253 inew->types[i].max_keys_block0 = (inew->types[i].blocksize - 3 *
254 sizeof(int)) / inew->keysize;
257 inew->types[i].max_keys_block = inew->types[i].max_keys_block0 /
259 if (inew->types[i].max_keys_block0 < 1)
261 logf (LOG_FATAL, "Blocksize too small in %s", name);
266 /* determine nice fill rates */
267 if (!(r = res_get_def(res,
268 nm = strconcat(name, ".",
269 "nicefill", 0), "90 90 90 95")) ||
270 !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
272 logf (LOG_FATAL, "Failed to locate resource %s", nm);
275 if (num < inew->num_types)
277 logf (LOG_FATAL, "Not enough elements in %s", nm);
280 for (i = 0; i < num; i++)
282 if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
284 logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
287 inew->types[i].nice_keys_block = (inew->types[i].max_keys_block0 * tmp) /
289 if (inew->types[i].nice_keys_block < 1)
290 inew->types[i].nice_keys_block = 1;
293 inew->cmp = cmp ? cmp : is_default_cmp;
300 int is_close(ISAM is)
305 logf (LOG_DEBUG, "is_close()");
306 for (i = 0; i < is->num_types; i++)
312 th.blocksize = is->types[i].blocksize;
313 th.keysize = is->keysize;
314 th.freelist = is->types[i].freelist;
315 th.top = is->types[i].top;
316 if (is_rb_write(&is->types[i], &th) < 0)
318 logf (LOG_FATAL, "Failed to write headerblock");
322 bf_close(is->types[i].bf);
325 for (i = 0; i < is->num_types; i++)
326 xfree (is->types[i].dbuf);
330 logf(LOG_LOG, "ISAM statistics:");
331 logf(LOG_LOG, "total_merge_operations %d",
332 statistics.total_merge_operations);
333 logf(LOG_LOG, "total_items %d", statistics.total_items);
334 logf(LOG_LOG, "dub_items_removed %d",
335 statistics.dub_items_removed);
336 logf(LOG_LOG, "new_items %d", statistics.new_items);
337 logf(LOG_LOG, "failed_deletes %d",
338 statistics.failed_deletes);
339 logf(LOG_LOG, "skipped_inserts %d",
340 statistics.skipped_inserts);
341 logf(LOG_LOG, "delete_insert_noop %d",
342 statistics.delete_insert_noop);
343 logf(LOG_LOG, "delete_replace %d",
344 statistics.delete_replace);
345 logf(LOG_LOG, "delete %d", statistics.deletes);
346 logf(LOG_LOG, "remaps %d", statistics.remaps);
347 logf(LOG_LOG, "block_jumps %d", statistics.block_jumps);
348 logf(LOG_LOG, "tab_deletes %d", statistics.tab_deletes);
354 static ISAM_P is_address(int type, int pos)
363 ISAM_P is_merge(ISAM is, ISAM_P pos, int num, char *data)
367 char keybuf[IS_MAX_RECORD];
368 int oldnum, oldtype, i;
369 char operation, *record;
371 statistics.total_merge_operations++;
372 statistics.total_items += num;
374 statistics.new_tables++;
376 is_m_establish_tab(is, &tab, pos);
378 if (is_m_read_full(&tab, tab.data) < 0)
380 logf (LOG_FATAL, "read_full failed");
383 oldnum = tab.num_records;
384 oldtype = tab.pos_type;
387 operation = *(data)++;
388 record = (char*) data;
389 data += is_keysize(is);
391 while (num && !memcmp(record - 1, data, is_keysize(tab.is) + 1))
393 data += 1 + is_keysize(is);
395 statistics.dub_items_removed++;
397 if ((res = is_m_seek_record(&tab, record)) > 0) /* no match */
399 if (operation == KEYOP_INSERT)
401 logf (LOG_DEBUG, "XXInserting new record.");
402 is_m_write_record(&tab, record);
403 statistics.new_items++;
407 logf (LOG_DEBUG, "XXDeletion failed to find match.");
408 statistics.failed_deletes++;
411 else /* match found */
413 if (operation == KEYOP_INSERT)
415 logf (LOG_DEBUG, "XXSkipping insertion - match found.");
416 statistics.skipped_inserts++;
419 else if (operation == KEYOP_DELETE)
421 /* try to avoid needlessly moving data */
422 if (num && *(data) == KEYOP_INSERT)
424 /* next key is identical insert? - NOOP - skip it */
425 if (!memcmp(record, data + 1, is_keysize(is)))
427 logf (LOG_DEBUG, "XXNoop delete. skipping.");
428 data += 1 + is_keysize(is);
430 while (num && !memcmp(data, data + is_keysize(tab.is) +
431 1, is_keysize(tab.is) + 1))
433 data += 1 + is_keysize(is);
435 statistics.dub_items_removed++;
437 statistics.delete_insert_noop++;
440 /* else check if next key can fit in this position */
441 if (is_m_peek_record(&tab, keybuf) &&
442 (*is->cmp)(data + 1, keybuf) < 0)
444 logf (LOG_DEBUG, "XXReplacing record.");
445 is_m_replace_record(&tab, data + 1);
446 data += 1 + is_keysize(is);
448 while (num && !memcmp(data, data + is_keysize(tab.is) +
449 1, is_keysize(tab.is) + 1))
451 data += 1 + is_keysize(is);
453 statistics.dub_items_removed++;
455 statistics.delete_replace++;
459 logf (LOG_DEBUG, "Deleting record.");
460 is_m_delete_record(&tab);
461 statistics.deletes++;
466 while (i < tab.is->num_types - 1 && tab.num_records >
467 tab.is->types[i].max_keys)
469 if (i != tab.pos_type)
471 /* read remaining blocks */
472 for (; tab.cur_mblock; tab.cur_mblock = tab.cur_mblock->next)
473 if (tab.cur_mblock->state < IS_MBSTATE_CLEAN)
474 is_m_read_full(&tab, tab.cur_mblock);
478 statistics.block_jumps++;
480 if (!oldnum || tab.pos_type != oldtype || (abs(oldnum - tab.num_records) *
481 100) / oldnum > tab.is->repack)
491 pos = is_address(tab.pos_type, tab.data->diskpos);
496 statistics.tab_deletes++;
498 is_m_release_tab(&tab);
503 * Locate a table of keys in an isam file. The ISPT is an individual
504 * position marker for that table.
506 ISPT is_position(ISAM is, ISAM_P pos)
511 is_m_establish_tab(is, &p->tab, pos);
518 void is_pt_free(ISPT ip)
520 is_m_release_tab(&ip->tab);
525 * Read a key from a table.
527 int is_readkey(ISPT ip, void *buf)
529 return is_m_read_record(&ip->tab, buf, 0);
532 int is_numkeys(ISPT ip)
534 return is_m_num_records(&ip->tab);
537 void is_rewind(ISPT ip)
539 is_m_rewind(&ip->tab);