1 /* $Id: isam.c,v 1.28 2004-01-22 11:27:21 adam Exp $
2 Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
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, *pp[IS_MAX_BLOCKTYPES+1], m[2];
108 int num, size, rs, tmp, i;
112 logf (LOG_DEBUG, "is_open(%s, %s)", name, writeflag ? "RW" : "RDONLY");
115 statistics.total_merge_operations = 0;
116 statistics.total_items = 0;
117 statistics.dub_items_removed = 0;
118 statistics.new_items = 0;
119 statistics.failed_deletes = 0;
120 statistics.skipped_inserts = 0;
121 statistics.delete_insert_noop = 0;
122 statistics.delete_replace = 0;
123 statistics.deletes = 0;
124 statistics.remaps = 0;
125 statistics.new_tables = 0;
126 statistics.block_jumps = 0;
127 statistics.tab_deletes = 0;
130 inew = (ISAM) xmalloc(sizeof(*inew));
131 inew->writeflag = writeflag;
132 for (i = 0; i < IS_MAX_BLOCKTYPES; i++)
133 inew->types[i].index = 0; /* dummy */
135 /* determine number and size of blocktypes */
136 if (!(r = res_get_def(res,
137 nm = strconcat(name, ".",
138 "blocktypes", 0), "64 512 4K 32K")) ||
139 !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
141 logf (LOG_FATAL, "Failed to locate resource %s", nm);
144 inew->num_types = num;
145 for (i = 0; i < num; i++)
147 if ((rs = sscanf(pp[i], "%d%1[bBkKmM]", &size, m)) < 1)
149 logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
157 inew->types[i].blocksize = size; break;
159 inew->types[i].blocksize = size * 1024; break;
161 inew->types[i].blocksize = size * 1048576; break;
163 logf (LOG_FATAL, "Illegal size suffix: %c", *m);
166 inew->types[i].dbuf = (char *) xmalloc(inew->types[i].blocksize);
169 if (!(inew->types[i].bf = bf_open(bfs, strconcat(name, m, 0),
170 inew->types[i].blocksize, writeflag)))
172 logf (LOG_FATAL, "bf_open failed");
175 if ((rs = is_rb_read(&inew->types[i], &th)) > 0)
177 if (th.blocksize != inew->types[i].blocksize)
179 logf (LOG_FATAL, "File blocksize mismatch in %s", name);
182 inew->types[i].freelist = th.freelist;
183 inew->types[i].top = th.top;
185 else if (writeflag) /* write dummy superblock to determine top */
187 if ((rs = is_rb_write(&inew->types[i], &th)) <=0) /* dummy */
189 logf (LOG_FATAL, "Failed to write initial superblock.");
192 inew->types[i].freelist = -1;
193 inew->types[i].top = rs;
195 /* ELSE: this is an empty file opened in read-only mode. */
198 inew->keysize = keysize;
201 if (!(r = res_get_def(res, nm = strconcat(name, ".",
202 "keysize", 0), "4")))
204 logf (LOG_FATAL, "Failed to locate resource %s", nm);
207 if ((inew->keysize = atoi(r)) <= 0)
209 logf (LOG_FATAL, "Must specify positive keysize.");
214 /* determine repack percent */
215 if (!(r = res_get_def(res, nm = strconcat(name, ".", "repack",
216 0), IS_DEF_REPACK_PERCENT)))
218 logf (LOG_FATAL, "Failed to locate resource %s", nm);
221 inew->repack = atoi(r);
223 /* determine max keys/blocksize */
224 if (!(r = res_get_def(res,
225 nm = strconcat(name, ".",
226 "maxkeys", 0), "50 640 10000")) ||
227 !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
229 logf (LOG_FATAL, "Failed to locate resource %s", nm);
232 if (num < inew->num_types -1)
234 logf (LOG_FATAL, "Not enough elements in %s", nm);
237 for (i = 0; i < num; i++)
239 if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
241 logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
244 inew->types[i].max_keys = tmp;
247 /* determine max keys/block */
248 for (i = 0; i < inew->num_types; i++)
250 if (!inew->types[i].index)
252 inew->types[i].max_keys_block = (inew->types[i].blocksize - 2 *
253 sizeof(int)) / inew->keysize;
254 inew->types[i].max_keys_block0 = (inew->types[i].blocksize - 3 *
255 sizeof(int)) / inew->keysize;
258 inew->types[i].max_keys_block = inew->types[i].max_keys_block0 /
260 if (inew->types[i].max_keys_block0 < 1)
262 logf (LOG_FATAL, "Blocksize too small in %s", name);
267 /* determine nice fill rates */
268 if (!(r = res_get_def(res,
269 nm = strconcat(name, ".",
270 "nicefill", 0), "90 90 90 95")) ||
271 !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
273 logf (LOG_FATAL, "Failed to locate resource %s", nm);
276 if (num < inew->num_types)
278 logf (LOG_FATAL, "Not enough elements in %s", nm);
281 for (i = 0; i < num; i++)
283 if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
285 logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
288 inew->types[i].nice_keys_block = (inew->types[i].max_keys_block0 * tmp) /
290 if (inew->types[i].nice_keys_block < 1)
291 inew->types[i].nice_keys_block = 1;
294 inew->cmp = cmp ? cmp : is_default_cmp;
301 int is_close(ISAM is)
306 logf (LOG_DEBUG, "is_close()");
307 for (i = 0; i < is->num_types; i++)
313 th.blocksize = is->types[i].blocksize;
314 th.keysize = is->keysize;
315 th.freelist = is->types[i].freelist;
316 th.top = is->types[i].top;
317 if (is_rb_write(&is->types[i], &th) < 0)
319 logf (LOG_FATAL, "Failed to write headerblock");
323 bf_close(is->types[i].bf);
326 for (i = 0; i < is->num_types; i++)
327 xfree (is->types[i].dbuf);
331 logf(LOG_LOG, "ISAM statistics:");
332 logf(LOG_LOG, "total_merge_operations %d",
333 statistics.total_merge_operations);
334 logf(LOG_LOG, "total_items %d", statistics.total_items);
335 logf(LOG_LOG, "dub_items_removed %d",
336 statistics.dub_items_removed);
337 logf(LOG_LOG, "new_items %d", statistics.new_items);
338 logf(LOG_LOG, "failed_deletes %d",
339 statistics.failed_deletes);
340 logf(LOG_LOG, "skipped_inserts %d",
341 statistics.skipped_inserts);
342 logf(LOG_LOG, "delete_insert_noop %d",
343 statistics.delete_insert_noop);
344 logf(LOG_LOG, "delete_replace %d",
345 statistics.delete_replace);
346 logf(LOG_LOG, "delete %d", statistics.deletes);
347 logf(LOG_LOG, "remaps %d", statistics.remaps);
348 logf(LOG_LOG, "block_jumps %d", statistics.block_jumps);
349 logf(LOG_LOG, "tab_deletes %d", statistics.tab_deletes);
355 static ISAM_P is_address(int type, int pos)
364 ISAM_P is_merge(ISAM is, ISAM_P pos, int num, char *data)
368 char keybuf[IS_MAX_RECORD];
369 int oldnum, oldtype, i;
370 char operation, *record;
372 statistics.total_merge_operations++;
373 statistics.total_items += num;
375 statistics.new_tables++;
377 is_m_establish_tab(is, &tab, pos);
379 if (is_m_read_full(&tab, tab.data) < 0)
381 logf (LOG_FATAL, "read_full failed");
384 oldnum = tab.num_records;
385 oldtype = tab.pos_type;
388 operation = *(data)++;
389 record = (char*) data;
390 data += is_keysize(is);
392 while (num && !memcmp(record - 1, data, is_keysize(tab.is) + 1))
394 data += 1 + is_keysize(is);
396 statistics.dub_items_removed++;
398 if ((res = is_m_seek_record(&tab, record)) > 0) /* no match */
400 if (operation == KEYOP_INSERT)
402 logf (LOG_DEBUG, "XXInserting new record.");
403 is_m_write_record(&tab, record);
404 statistics.new_items++;
408 logf (LOG_DEBUG, "XXDeletion failed to find match.");
409 statistics.failed_deletes++;
412 else /* match found */
414 if (operation == KEYOP_INSERT)
416 logf (LOG_DEBUG, "XXSkipping insertion - match found.");
417 statistics.skipped_inserts++;
420 else if (operation == KEYOP_DELETE)
422 /* try to avoid needlessly moving data */
423 if (num && *(data) == KEYOP_INSERT)
425 /* next key is identical insert? - NOOP - skip it */
426 if (!memcmp(record, data + 1, is_keysize(is)))
428 logf (LOG_DEBUG, "XXNoop delete. skipping.");
429 data += 1 + is_keysize(is);
431 while (num && !memcmp(data, data + is_keysize(tab.is) +
432 1, is_keysize(tab.is) + 1))
434 data += 1 + is_keysize(is);
436 statistics.dub_items_removed++;
438 statistics.delete_insert_noop++;
441 /* else check if next key can fit in this position */
442 if (is_m_peek_record(&tab, keybuf) &&
443 (*is->cmp)(data + 1, keybuf) < 0)
445 logf (LOG_DEBUG, "XXReplacing record.");
446 is_m_replace_record(&tab, data + 1);
447 data += 1 + is_keysize(is);
449 while (num && !memcmp(data, data + is_keysize(tab.is) +
450 1, is_keysize(tab.is) + 1))
452 data += 1 + is_keysize(is);
454 statistics.dub_items_removed++;
456 statistics.delete_replace++;
460 logf (LOG_DEBUG, "Deleting record.");
461 is_m_delete_record(&tab);
462 statistics.deletes++;
467 while (i < tab.is->num_types - 1 && tab.num_records >
468 tab.is->types[i].max_keys)
470 if (i != tab.pos_type)
472 /* read remaining blocks */
473 for (; tab.cur_mblock; tab.cur_mblock = tab.cur_mblock->next)
474 if (tab.cur_mblock->state < IS_MBSTATE_CLEAN)
475 is_m_read_full(&tab, tab.cur_mblock);
479 statistics.block_jumps++;
481 if (!oldnum || tab.pos_type != oldtype || (abs(oldnum - tab.num_records) *
482 100) / oldnum > tab.is->repack)
492 pos = is_address(tab.pos_type, tab.data->diskpos);
497 statistics.tab_deletes++;
499 is_m_release_tab(&tab);
504 * Locate a table of keys in an isam file. The ISPT is an individual
505 * position marker for that table.
507 ISPT is_position(ISAM is, ISAM_P pos)
512 is_m_establish_tab(is, &p->tab, pos);
519 void is_pt_free(ISPT ip)
521 is_m_release_tab(&ip->tab);
526 * Read a key from a table.
528 int is_readkey(ISPT ip, void *buf)
530 return is_m_read_record(&ip->tab, buf, 0);
533 int is_numkeys(ISPT ip)
535 return is_m_num_records(&ip->tab);
538 void is_rewind(ISPT ip)
540 is_m_rewind(&ip->tab);