You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucy.apache.org by mi...@apache.org on 2010/10/14 10:48:40 UTC
[lucy-commits] svn commit: r1022422 [15/43] - in /incubator/lucy/trunk/import: ./
charmonizer/ charmonizer/src/ charmonizer/src/Charmonizer/
charmonizer/src/Charmonizer/Core/ charmonizer/src/Charmonizer/Probe/
charmonizer/src/Charmonizer/Test/ clownfish/ clownfish/li...
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/SortFieldWriter.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/SortFieldWriter.c?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/SortFieldWriter.c (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/SortFieldWriter.c Thu Oct 14 08:48:04 2010
@@ -0,0 +1,700 @@
+#define C_KINO_SORTFIELDWRITER
+#include "KinoSearch/Util/ToolSet.h"
+#include <math.h>
+
+#include "KinoSearch/Index/SortFieldWriter.h"
+#include "KinoSearch/Index/Inverter.h"
+#include "KinoSearch/Index/PolyReader.h"
+#include "KinoSearch/Index/Segment.h"
+#include "KinoSearch/Index/SegReader.h"
+#include "KinoSearch/Index/Snapshot.h"
+#include "KinoSearch/Index/SortCache.h"
+#include "KinoSearch/Index/SortCache/NumericSortCache.h"
+#include "KinoSearch/Index/SortCache/TextSortCache.h"
+#include "KinoSearch/Index/SortReader.h"
+#include "KinoSearch/Index/ZombieKeyedHash.h"
+#include "KinoSearch/Plan/FieldType.h"
+#include "KinoSearch/Plan/Schema.h"
+#include "KinoSearch/Store/Folder.h"
+#include "KinoSearch/Store/InStream.h"
+#include "KinoSearch/Store/OutStream.h"
+#include "KinoSearch/Util/Memory.h"
+#include "KinoSearch/Util/MemoryPool.h"
+#include "KinoSearch/Util/SortUtils.h"
+
+// Prepare to read back a run.
+static void
+S_flip_run(SortFieldWriter *run, size_t sub_thresh, InStream *ord_in,
+ InStream *ix_in, InStream *dat_in);
+
+// Write out a sort cache. Returns the number of unique values in the sort
+// cache.
+static int32_t
+S_write_files(SortFieldWriter *self, OutStream *ord_out, OutStream *ix_out,
+ OutStream *dat_out);
+
+typedef struct kino_SFWriterElem {
+ Obj *value;
+ int32_t doc_id;
+} kino_SFWriterElem;
+#define SFWriterElem kino_SFWriterElem
+
+SortFieldWriter*
+SortFieldWriter_new(Schema *schema, Snapshot *snapshot, Segment *segment,
+ PolyReader *polyreader, const CharBuf *field,
+ MemoryPool *memory_pool, size_t mem_thresh,
+ OutStream *temp_ord_out, OutStream *temp_ix_out,
+ OutStream *temp_dat_out)
+{
+ SortFieldWriter *self
+ = (SortFieldWriter*)VTable_Make_Obj(SORTFIELDWRITER);
+ return SortFieldWriter_init(self, schema, snapshot, segment, polyreader,
+ field, memory_pool, mem_thresh, temp_ord_out, temp_ix_out,
+ temp_dat_out);
+}
+
+SortFieldWriter*
+SortFieldWriter_init(SortFieldWriter *self, Schema *schema,
+ Snapshot *snapshot, Segment *segment,
+ PolyReader *polyreader, const CharBuf *field,
+ MemoryPool *memory_pool, size_t mem_thresh,
+ OutStream *temp_ord_out, OutStream *temp_ix_out,
+ OutStream *temp_dat_out)
+{
+ // Init.
+ SortEx_init((SortExternal*)self, sizeof(SFWriterElem));
+ self->null_ord = -1;
+ self->count = 0;
+ self->ord_start = 0;
+ self->ord_end = 0;
+ self->ix_start = 0;
+ self->ix_end = 0;
+ self->dat_start = 0;
+ self->dat_end = 0;
+ self->run_cardinality = -1;
+ self->run_max = -1;
+ self->sort_cache = NULL;
+ self->doc_map = NULL;
+ self->sorted_ids = NULL;
+ self->run_ord = 0;
+ self->run_tick = 0;
+ self->ord_width = 0;
+
+ // Assign.
+ self->field = CB_Clone(field);
+ self->schema = (Schema*)INCREF(schema);
+ self->snapshot = (Snapshot*)INCREF(snapshot);
+ self->segment = (Segment*)INCREF(segment);
+ self->polyreader = (PolyReader*)INCREF(polyreader);
+ self->mem_pool = (MemoryPool*)INCREF(memory_pool);
+ self->temp_ord_out = (OutStream*)INCREF(temp_ord_out);
+ self->temp_ix_out = (OutStream*)INCREF(temp_ix_out);
+ self->temp_dat_out = (OutStream*)INCREF(temp_dat_out);
+ self->mem_thresh = mem_thresh;
+
+ // Derive.
+ self->field_num = Seg_Field_Num(segment, field);
+ FieldType *type = (FieldType*)CERTIFY(
+ Schema_Fetch_Type(self->schema, field), FIELDTYPE);
+ self->type = (FieldType*)INCREF(type);
+ self->prim_id = FType_Primitive_ID(type);
+ if (self->prim_id == FType_TEXT || self->prim_id == FType_BLOB) {
+ self->var_width = true;
+ }
+ else {
+ self->var_width = false;
+ }
+ self->uniq_vals = (Hash*)ZKHash_new(memory_pool, self->prim_id);
+
+ return self;
+}
+
+void
+SortFieldWriter_clear_cache(SortFieldWriter *self)
+{
+ if (self->uniq_vals) {
+ Hash_Clear(self->uniq_vals);
+ }
+ SortFieldWriter_clear_cache_t super_clear_cache =
+ (SortFieldWriter_clear_cache_t)SUPER_METHOD(self->vtable,
+ SortFieldWriter, Clear_Cache);
+ super_clear_cache(self);
+}
+
+void
+SortFieldWriter_destroy(SortFieldWriter *self)
+{
+ DECREF(self->uniq_vals);
+ self->uniq_vals = NULL;
+ DECREF(self->field);
+ DECREF(self->schema);
+ DECREF(self->snapshot);
+ DECREF(self->segment);
+ DECREF(self->polyreader);
+ DECREF(self->type);
+ DECREF(self->mem_pool);
+ DECREF(self->temp_ord_out);
+ DECREF(self->temp_ix_out);
+ DECREF(self->temp_dat_out);
+ DECREF(self->ord_in);
+ DECREF(self->ix_in);
+ DECREF(self->dat_in);
+ DECREF(self->sort_cache);
+ DECREF(self->doc_map);
+ FREEMEM(self->sorted_ids);
+ SUPER_DESTROY(self, SORTFIELDWRITER);
+}
+
+int32_t
+SortFieldWriter_get_null_ord(SortFieldWriter *self) { return self->null_ord; }
+int32_t
+SortFieldWriter_get_ord_width(SortFieldWriter *self) { return self->ord_width; }
+
+static Obj*
+S_find_unique_value(Hash *uniq_vals, Obj *val)
+{
+ int32_t hash_sum = Obj_Hash_Sum(val);
+ Obj *uniq_val = Hash_Find_Key(uniq_vals, val, hash_sum);
+ if (!uniq_val) {
+ Hash_Store(uniq_vals, val, INCREF(&EMPTY));
+ uniq_val = Hash_Find_Key(uniq_vals, val, hash_sum);
+ }
+ return uniq_val;
+}
+
+void
+SortFieldWriter_add(SortFieldWriter *self, int32_t doc_id, Obj *value)
+{
+ // Uniq-ify the value, and record it for this document.
+ SFWriterElem elem;
+ elem.value = S_find_unique_value(self->uniq_vals, value);
+ elem.doc_id = doc_id;
+ SortFieldWriter_Feed(self, &elem);
+ self->count++;
+}
+
+void
+SortFieldWriter_add_segment(SortFieldWriter *self, SegReader *reader,
+ I32Array *doc_map, SortCache *sort_cache)
+{
+ if (!sort_cache) { return; }
+ SortFieldWriter *run = SortFieldWriter_new(self->schema, self->snapshot,
+ self->segment, self->polyreader, self->field, self->mem_pool,
+ self->mem_thresh, NULL, NULL, NULL);
+ run->sort_cache = (SortCache*)INCREF(sort_cache);
+ run->doc_map = (I32Array*)INCREF(doc_map);
+ run->run_max = SegReader_Doc_Max(reader);
+ run->run_cardinality = SortCache_Get_Cardinality(sort_cache);
+ run->null_ord = SortCache_Get_Null_Ord(sort_cache);
+ run->run_tick = 1;
+ SortFieldWriter_Add_Run(self, (SortExternal*)run);
+}
+
+static int32_t
+S_calc_width(int32_t cardinality)
+{
+ if (cardinality <= 0x00000002) { return 1; }
+ else if (cardinality <= 0x00000004) { return 2; }
+ else if (cardinality <= 0x0000000F) { return 4; }
+ else if (cardinality <= 0x000000FF) { return 8; }
+ else if (cardinality <= 0x0000FFFF) { return 16; }
+ else { return 32; }
+}
+
+static void
+S_write_ord(void *ords, int32_t width, int32_t doc_id, int32_t ord)
+{
+ switch (width) {
+ case 1: if (ord) { NumUtil_u1set(ords, doc_id); }
+ else { NumUtil_u1clear(ords, doc_id); }
+ break;
+ case 2: NumUtil_u2set(ords, doc_id, ord);
+ break;
+ case 4: NumUtil_u4set(ords, doc_id, ord);
+ break;
+ case 8: {
+ uint8_t *ints = (uint8_t*)ords;
+ ints[doc_id] = ord;
+ }
+ break;
+ case 16:
+ {
+ uint8_t *bytes = (uint8_t*)ords;
+ bytes += doc_id * sizeof(uint16_t);
+ NumUtil_encode_bigend_u16(ord, &bytes);
+ }
+ break;
+ case 32:
+ {
+ uint8_t *bytes = (uint8_t*)ords;
+ bytes += doc_id * sizeof(uint32_t);
+ NumUtil_encode_bigend_u32(ord, &bytes);
+ }
+ break;
+ default: THROW(ERR, "Invalid width: %i32", width);
+ }
+}
+
+static void
+S_write_val(Obj *val, int8_t prim_id, OutStream *ix_out, OutStream *dat_out,
+ int64_t dat_start)
+{
+ if (val) {
+ switch (prim_id & FType_PRIMITIVE_ID_MASK) {
+ case FType_TEXT: {
+ CharBuf *string = (CharBuf*)val;
+ int64_t dat_pos = OutStream_Tell(dat_out) - dat_start;
+ OutStream_Write_I64(ix_out, dat_pos);
+ OutStream_Write_Bytes(dat_out, (char*)CB_Get_Ptr8(string),
+ CB_Get_Size(string));
+ break;
+ }
+ case FType_BLOB: {
+ ByteBuf *byte_buf = (ByteBuf*)val;
+ int64_t dat_pos = OutStream_Tell(dat_out) - dat_start;
+ OutStream_Write_I64(ix_out, dat_pos);
+ OutStream_Write_Bytes(dat_out, BB_Get_Buf(byte_buf),
+ BB_Get_Size(byte_buf));
+ break;
+ }
+ case FType_INT32: {
+ Integer32 *i32 = (Integer32*)val;
+ OutStream_Write_I32(dat_out, Int32_Get_Value(i32));
+ break;
+ }
+ case FType_INT64: {
+ Integer64 *i64 = (Integer64*)val;
+ OutStream_Write_I64(dat_out, Int64_Get_Value(i64));
+ break;
+ }
+ case FType_FLOAT64: {
+ Float64 *float64 = (Float64*)val;
+ OutStream_Write_F64(dat_out, Float64_Get_Value(float64));
+ break;
+ }
+ case FType_FLOAT32: {
+ Float32 *float32 = (Float32*)val;
+ OutStream_Write_F32(dat_out, Float32_Get_Value(float32));
+ break;
+ }
+ default:
+ THROW(ERR, "Unrecognized primitive id: %i32", (int32_t)prim_id);
+ }
+ }
+ else {
+ switch (prim_id & FType_PRIMITIVE_ID_MASK) {
+ case FType_TEXT:
+ case FType_BLOB: {
+ int64_t dat_pos = OutStream_Tell(dat_out) - dat_start;
+ OutStream_Write_I64(ix_out, dat_pos);
+ }
+ break;
+ case FType_INT32:
+ OutStream_Write_I32(dat_out, 0);
+ break;
+ case FType_INT64:
+ OutStream_Write_I64(dat_out, 0);
+ break;
+ case FType_FLOAT64:
+ OutStream_Write_F64(dat_out, 0.0);
+ break;
+ case FType_FLOAT32:
+ OutStream_Write_F32(dat_out, 0.0f);
+ break;
+ default:
+ THROW(ERR, "Unrecognized primitive id: %i32", (int32_t)prim_id);
+ }
+ }
+}
+
+int
+SortFieldWriter_compare(SortFieldWriter *self, void *va, void *vb)
+{
+ SFWriterElem *a = (SFWriterElem*)va;
+ SFWriterElem *b = (SFWriterElem*)vb;
+ int32_t comparison
+ = FType_null_back_compare_values(self->type, a->value, b->value);
+ if (comparison == 0) { comparison = b->doc_id - a->doc_id; }
+ return comparison;
+}
+
+static int
+S_compare_doc_ids_by_ord_rev(void *context, const void *va, const void *vb)
+{
+ SortCache *sort_cache = (SortCache*)context;
+ int32_t a = *(int32_t*)va;
+ int32_t b = *(int32_t*)vb;
+ int32_t ord_a = SortCache_Ordinal(sort_cache, a);
+ int32_t ord_b = SortCache_Ordinal(sort_cache, b);
+ return ord_a - ord_b;
+}
+
+static void
+S_lazy_init_sorted_ids(SortFieldWriter *self)
+{
+ if (!self->sorted_ids) {
+ self->sorted_ids
+ = (int32_t*)MALLOCATE((self->run_max + 1) * sizeof(int32_t));
+ for (int32_t i = 0, max = self->run_max; i <= max; i++) {
+ self->sorted_ids[i] = i;
+ }
+ Sort_quicksort(self->sorted_ids + 1, self->run_max, sizeof(int32_t),
+ S_compare_doc_ids_by_ord_rev, self->sort_cache);
+ }
+}
+
+void
+SortFieldWriter_flush(SortFieldWriter *self)
+{
+ // Don't add a run unless we have data to put in it.
+ if (SortFieldWriter_Cache_Count(self) == 0) { return; }
+
+ OutStream *const temp_ord_out = self->temp_ord_out;
+ OutStream *const temp_ix_out = self->temp_ix_out;
+ OutStream *const temp_dat_out = self->temp_dat_out;
+
+ SortFieldWriter_Sort_Cache(self);
+ SortFieldWriter *run = SortFieldWriter_new(self->schema, self->snapshot,
+ self->segment, self->polyreader, self->field, self->mem_pool,
+ self->mem_thresh, NULL, NULL, NULL);
+
+ // Record stream starts and align.
+ run->ord_start = OutStream_Align(temp_ord_out, sizeof(int64_t));
+ if (self->var_width) {
+ run->ix_start = OutStream_Align(temp_ix_out, sizeof(int64_t));
+ }
+ run->dat_start = OutStream_Align(temp_dat_out, sizeof(int64_t));
+
+ // Have the run borrow the array of elems.
+ run->cache = self->cache;
+ run->cache_max = self->cache_max;
+ run->cache_tick = self->cache_tick;
+ run->cache_cap = self->cache_cap;
+
+ // Write files, record stats.
+ run->run_max = (int32_t)Seg_Get_Count(self->segment);
+ run->run_cardinality = S_write_files(run, temp_ord_out, temp_ix_out,
+ temp_dat_out);
+
+ // Reclaim the buffer from the run and empty it.
+ run->cache = NULL;
+ run->cache_max = 0;
+ run->cache_tick = 0;
+ run->cache_cap = 0;
+ self->cache_tick = self->cache_max;
+ SortFieldWriter_Clear_Cache(self);
+
+ // Record stream ends.
+ run->ord_end = OutStream_Tell(temp_ord_out);
+ if (self->var_width) {
+ run->ix_end = OutStream_Tell(temp_ix_out);
+ }
+ run->dat_end = OutStream_Tell(temp_dat_out);
+
+ // Add the run to the array.
+ SortFieldWriter_Add_Run(self, (SortExternal*)run);
+}
+
+uint32_t
+SortFieldWriter_refill(SortFieldWriter *self)
+{
+ if (!self->sort_cache) { return 0; }
+
+ // Sanity check, then reset the cache and prepare to start loading items.
+ uint32_t cache_count = SortFieldWriter_Cache_Count(self);
+ if (cache_count) {
+ THROW(ERR, "Refill called but cache contains %u32 items",
+ cache_count);
+ }
+ SortFieldWriter_Clear_Cache(self);
+ MemPool_Release_All(self->mem_pool);
+ S_lazy_init_sorted_ids(self);
+
+ const int32_t null_ord = self->null_ord;
+ Hash *const uniq_vals = self->uniq_vals;
+ I32Array *const doc_map = self->doc_map;
+ SortCache *const sort_cache = self->sort_cache;
+ Obj *const blank = SortCache_Make_Blank(sort_cache);
+
+ while ( self->run_ord < self->run_cardinality
+ && MemPool_Get_Consumed(self->mem_pool) < self->mem_thresh
+ ) {
+ Obj *val = SortCache_Value(sort_cache, self->run_ord, blank);
+ if (val) {
+ Hash_Store(uniq_vals, val, INCREF(&EMPTY));
+ break;
+ }
+ self->run_ord++;
+ }
+ uint32_t count = 0;
+ while (self->run_tick <= self->run_max) {
+ int32_t raw_doc_id = self->sorted_ids[self->run_tick];
+ int32_t ord = SortCache_Ordinal(sort_cache, raw_doc_id);
+ if (ord != null_ord) {
+ int32_t remapped = doc_map
+ ? I32Arr_Get(doc_map, raw_doc_id) : raw_doc_id;
+ if (remapped) {
+ Obj *val = SortCache_Value(sort_cache, ord, blank);
+ SortFieldWriter_Add(self, remapped, val);
+ count++;
+ }
+ }
+ else if (ord > self->run_ord) {
+ break;
+ }
+ self->run_tick++;
+ }
+ self->run_ord++;
+ SortFieldWriter_Sort_Cache(self);
+
+ if (self->run_ord >= self->run_cardinality) {
+ DECREF(self->sort_cache);
+ self->sort_cache = NULL;
+ }
+
+ DECREF(blank);
+ return count;
+}
+
+void
+SortFieldWriter_flip(SortFieldWriter *self)
+{
+ uint32_t num_items = SortFieldWriter_Cache_Count(self);
+ uint32_t num_runs = VA_Get_Size(self->runs);
+
+ if (self->flipped) { THROW(ERR, "Can't call Flip() twice"); }
+ self->flipped = true;
+
+ // Sanity check.
+ if (num_runs && num_items) {
+ THROW(ERR, "Sanity check failed: num_runs: %u32 num_items: %u32",
+ num_runs, num_items);
+ }
+
+ if (num_items) {
+ SortFieldWriter_Sort_Cache(self);
+ }
+ else if (num_runs) {
+ Folder *folder = PolyReader_Get_Folder(self->polyreader);
+ CharBuf *seg_name = Seg_Get_Name(self->segment);
+ CharBuf *filepath = CB_newf("%o/sort_ord_temp", seg_name);
+ self->ord_in = Folder_Open_In(folder, filepath);
+ if (!self->ord_in) { RETHROW(INCREF(Err_get_error())); }
+ if (self->var_width) {
+ CB_setf(filepath, "%o/sort_ix_temp", seg_name);
+ self->ix_in = Folder_Open_In(folder, filepath);
+ if (!self->ix_in) { RETHROW(INCREF(Err_get_error())); }
+ }
+ CB_setf(filepath, "%o/sort_dat_temp", seg_name);
+ self->dat_in = Folder_Open_In(folder, filepath);
+ if (!self->dat_in) { RETHROW(INCREF(Err_get_error())); }
+ DECREF(filepath);
+
+ // Assign streams and a slice of mem_thresh.
+ size_t sub_thresh = self->mem_thresh / num_runs;
+ if (sub_thresh < 65536) { sub_thresh = 65536; }
+ for (uint32_t i = 0; i < num_runs; i++) {
+ SortFieldWriter *run = (SortFieldWriter*)VA_Fetch(self->runs, i);
+ S_flip_run(run, sub_thresh, self->ord_in, self->ix_in,
+ self->dat_in);
+ }
+ }
+
+ self->flipped = true;
+}
+
+static int32_t
+S_write_files(SortFieldWriter *self, OutStream *ord_out, OutStream *ix_out,
+ OutStream *dat_out)
+{
+ int8_t prim_id = self->prim_id;
+ int32_t doc_max = (int32_t)Seg_Get_Count(self->segment);
+ bool_t has_nulls = self->count == doc_max ? false : true;
+ size_t size = (doc_max + 1) * sizeof(int32_t);
+ int32_t *ords = (int32_t*)MALLOCATE(size);
+ int32_t ord = 0;
+ int64_t dat_start = OutStream_Tell(dat_out);
+
+ // Assign -1 as a stand-in for the NULL ord.
+ for (int32_t i = 0; i <= doc_max; i++) {
+ ords[i] = -1;
+ }
+
+ // Grab the first item and record its ord. Add a dummy ord for invalid
+ // doc id 0.
+ SFWriterElem *elem = (SFWriterElem*)SortFieldWriter_Fetch(self);
+ ords[elem->doc_id] = ord;
+ ords[0] = 0;
+
+ // Build array of ords, write non-NULL sorted values.
+ Obj *val = Obj_Clone(elem->value);
+ Obj *last_val_address = elem->value;
+ S_write_val(elem->value, prim_id, ix_out, dat_out, dat_start);
+ while (NULL != (elem = (SFWriterElem*)SortFieldWriter_Fetch(self))) {
+ if (elem->value != last_val_address) {
+ int32_t comparison = FType_Compare_Values(self->type,
+ elem->value, val);
+ if (comparison != 0) {
+ ord++;
+ S_write_val(elem->value, prim_id, ix_out, dat_out, dat_start);
+ Obj_Mimic(val, elem->value);
+ }
+ last_val_address = elem->value;
+ }
+ ords[elem->doc_id] = ord;
+ }
+ DECREF(val);
+
+ // If there are NULL values, write one now and record the NULL ord.
+ if (has_nulls) {
+ S_write_val(NULL, prim_id, ix_out, dat_out, dat_start);
+ ord++;
+ self->null_ord = ord;
+ }
+ int32_t null_ord = self->null_ord;
+
+ // Write one extra file pointer so that we can always derive length.
+ if (self->var_width) {
+ OutStream_Write_I64(ix_out, OutStream_Tell(dat_out) - dat_start);
+ }
+
+ // Calculate cardinality and ord width.
+ int32_t cardinality = ord + 1;
+ self->ord_width = S_calc_width(cardinality);
+ int32_t ord_width = self->ord_width;
+
+ // Write ords.
+ const double BITS_PER_BYTE = 8.0;
+ double bytes_per_doc = ord_width / BITS_PER_BYTE;
+ double byte_count = ceil((doc_max + 1) * bytes_per_doc);
+ char *compressed_ords
+ = (char*)CALLOCATE((size_t)byte_count, sizeof(char));
+ for (int32_t i = 0; i <= doc_max; i++) {
+ int32_t real_ord = ords[i] == -1 ? null_ord : ords[i];
+ S_write_ord(compressed_ords, ord_width, i, real_ord);
+ }
+ OutStream_Write_Bytes(ord_out, compressed_ords, (size_t)byte_count);
+ FREEMEM(compressed_ords);
+
+ FREEMEM(ords);
+ return cardinality;
+}
+
+int32_t
+SortFieldWriter_finish(SortFieldWriter *self)
+{
+ // Bail if there's no data.
+ if (!SortFieldWriter_Peek(self)) { return 0; }
+
+ int32_t field_num = self->field_num;
+ Folder *folder = PolyReader_Get_Folder(self->polyreader);
+ CharBuf *seg_name = Seg_Get_Name(self->segment);
+ CharBuf *path = CB_newf("%o/sort-%i32.ord", seg_name, field_num);
+
+ // Open streams.
+ OutStream *ord_out = Folder_Open_Out(folder, path);
+ if (!ord_out) { RETHROW(INCREF(Err_get_error())); }
+ OutStream *ix_out = NULL;
+ if (self->var_width) {
+ CB_setf(path, "%o/sort-%i32.ix", seg_name, field_num);
+ ix_out = Folder_Open_Out(folder, path);
+ if (!ix_out) { RETHROW(INCREF(Err_get_error())); }
+ }
+ CB_setf(path, "%o/sort-%i32.dat", seg_name, field_num);
+ OutStream *dat_out = Folder_Open_Out(folder, path);
+ if (!dat_out) { RETHROW(INCREF(Err_get_error())); }
+ DECREF(path);
+
+ int32_t cardinality = S_write_files(self, ord_out, ix_out, dat_out);
+
+ // Close streams.
+ OutStream_Close(ord_out);
+ if (ix_out) { OutStream_Close(ix_out); }
+ OutStream_Close(dat_out);
+ DECREF(dat_out);
+ DECREF(ix_out);
+ DECREF(ord_out);
+
+ return cardinality;
+}
+
+static void
+S_flip_run(SortFieldWriter *run, size_t sub_thresh, InStream *ord_in,
+ InStream *ix_in, InStream *dat_in)
+{
+ if (run->flipped) { THROW(ERR, "Can't Flip twice"); }
+ run->flipped = true;
+
+ // Get our own MemoryPool, ZombieKeyedHash, and slice of mem_thresh.
+ DECREF(run->uniq_vals);
+ DECREF(run->mem_pool);
+ run->mem_pool = MemPool_new(0);
+ run->uniq_vals = (Hash*)ZKHash_new(run->mem_pool, run->prim_id);
+ run->mem_thresh = sub_thresh;
+
+ // Done if we already have a SortCache to read from.
+ if (run->sort_cache) { return; }
+
+ // Open the temp files for reading.
+ CharBuf *seg_name = Seg_Get_Name(run->segment);
+ size_t size = ZCB_size() + CB_Get_Size(seg_name) + 100;
+ CharBuf *alias = (CharBuf*)ZCB_newf(alloca(size), size, "");
+ CB_setf(alias, "%o/sort_ord_temp-%i64-to-%i64", seg_name,
+ run->ord_start, run->ord_end);
+ InStream *ord_in_dupe = InStream_Reopen(ord_in, alias,
+ run->ord_start, run->ord_end - run->ord_start);
+ InStream *ix_in_dupe = NULL;
+ if (run->var_width) {
+ CB_setf(alias, "%o/sort_ix_temp-%i64-to-%i64", seg_name,
+ run->ix_start, run->ix_end);
+ ix_in_dupe = InStream_Reopen(ix_in, alias,
+ run->ix_start, run->ix_end - run->ix_start);
+ }
+ CB_setf(alias, "%o/sort_dat_temp-%i64-to-%i64", seg_name,
+ run->dat_start, run->dat_end);
+ InStream *dat_in_dupe = InStream_Reopen(dat_in, alias,
+ run->dat_start, run->dat_end - run->dat_start);
+
+ // Get a SortCache.
+ CharBuf *field = Seg_Field_Name(run->segment, run->field_num);
+ switch (run->prim_id & FType_PRIMITIVE_ID_MASK) {
+ case FType_TEXT:
+ run->sort_cache = (SortCache*)TextSortCache_new(field,
+ run->type, run->run_cardinality, run->run_max, run->null_ord,
+ run->ord_width, ord_in_dupe, ix_in_dupe, dat_in_dupe);
+ break;
+ case FType_INT32:
+ run->sort_cache = (SortCache*)I32SortCache_new(field,
+ run->type, run->run_cardinality, run->run_max, run->null_ord,
+ run->ord_width, ord_in_dupe, dat_in_dupe);
+ break;
+ case FType_INT64:
+ run->sort_cache = (SortCache*)I64SortCache_new(field,
+ run->type, run->run_cardinality, run->run_max, run->null_ord,
+ run->ord_width, ord_in_dupe, dat_in_dupe);
+ break;
+ case FType_FLOAT32:
+ run->sort_cache = (SortCache*)F32SortCache_new(field,
+ run->type, run->run_cardinality, run->run_max, run->null_ord,
+ run->ord_width, ord_in_dupe, dat_in_dupe);
+ break;
+ case FType_FLOAT64:
+ run->sort_cache = (SortCache*)F64SortCache_new(field,
+ run->type, run->run_cardinality, run->run_max, run->null_ord,
+ run->ord_width, ord_in_dupe, dat_in_dupe);
+ break;
+ default:
+ THROW(ERR, "No SortCache class for %o", run->type);
+ }
+
+ DECREF(ord_in_dupe);
+ DECREF(ix_in_dupe);
+ DECREF(dat_in_dupe);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Propchange: incubator/lucy/trunk/import/core/KinoSearch/Index/SortFieldWriter.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/SortFieldWriter.cfh
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/SortFieldWriter.cfh?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/SortFieldWriter.cfh (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/SortFieldWriter.cfh Thu Oct 14 08:48:04 2010
@@ -0,0 +1,91 @@
+parcel KinoSearch cnick Kino;
+
+class KinoSearch::Index::SortFieldWriter
+ inherits KinoSearch::Util::SortExternal {
+ CharBuf *field;
+ Hash *uniq_vals;
+ Schema *schema;
+ Snapshot *snapshot;
+ Segment *segment;
+ PolyReader *polyreader;
+ FieldType *type;
+ I32Array *doc_map;
+ MemoryPool *mem_pool;
+ int32_t field_num;
+ int32_t null_ord;
+ int8_t prim_id;
+ int32_t count;
+ OutStream *temp_ord_out;
+ OutStream *temp_ix_out;
+ OutStream *temp_dat_out;
+ InStream *ord_in;
+ InStream *ix_in;
+ InStream *dat_in;
+ SortCache *sort_cache;
+ int64_t ord_start;
+ int64_t ord_end;
+ int64_t ix_start;
+ int64_t ix_end;
+ int64_t dat_start;
+ int64_t dat_end;
+ int32_t run_cardinality;
+ int32_t run_max;
+ bool_t var_width;
+ int32_t *sorted_ids;
+ int32_t run_ord;
+ int32_t run_tick;
+ int32_t ord_width;
+
+ inert incremented SortFieldWriter*
+ new(Schema *schema, Snapshot *snapshot, Segment *segment,
+ PolyReader *polyreader, const CharBuf *field, MemoryPool *memory_pool,
+ size_t mem_thresh, OutStream *temp_ord_out, OutStream *temp_ix_out,
+ OutStream *temp_dat_out);
+
+ inert SortFieldWriter*
+ init(SortFieldWriter *self, Schema *schema, Snapshot *snapshot,
+ Segment *segment, PolyReader *polyreader, const CharBuf *field,
+ MemoryPool *memory_pool, size_t mem_thresh, OutStream *temp_ord_out,
+ OutStream *temp_ix_out, OutStream *temp_dat_out);
+
+ void
+ Add(SortFieldWriter *self, int32_t doc_id, Obj *value);
+
+ void
+ Add_Segment(SortFieldWriter *self, SegReader *reader, I32Array *doc_map,
+ SortCache *sort_cache);
+
+ void
+ Flush(SortFieldWriter *self);
+
+ void
+ Flip(SortFieldWriter *self);
+
+ uint32_t
+ Refill(SortFieldWriter *self);
+
+ int32_t
+ Finish(SortFieldWriter *self);
+
+ int
+ Compare(SortFieldWriter *self, void *va, void *vb);
+
+ void
+ Clear_Cache(SortFieldWriter *self);
+
+ int32_t
+ Get_Null_Ord(SortFieldWriter *self);
+
+ int32_t
+ Get_Ord_Width(SortFieldWriter *self);
+
+ public void
+ Destroy(SortFieldWriter *self);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/SortReader.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/SortReader.c?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/SortReader.c (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/SortReader.c Thu Oct 14 08:48:04 2010
@@ -0,0 +1,260 @@
+#define C_KINO_SORTREADER
+#define C_KINO_DEFAULTSORTREADER
+#include "KinoSearch/Util/ToolSet.h"
+
+#include "KinoSearch/Index/SortReader.h"
+#include "KinoSearch/Index/Segment.h"
+#include "KinoSearch/Index/Snapshot.h"
+#include "KinoSearch/Index/SortCache/NumericSortCache.h"
+#include "KinoSearch/Index/SortCache/TextSortCache.h"
+#include "KinoSearch/Index/SortWriter.h"
+#include "KinoSearch/Plan/FieldType.h"
+#include "KinoSearch/Plan/Schema.h"
+#include "KinoSearch/Store/Folder.h"
+#include "KinoSearch/Store/InStream.h"
+
+SortReader*
+SortReader_init(SortReader *self, Schema *schema, Folder *folder,
+ Snapshot *snapshot, VArray *segments, int32_t seg_tick)
+{
+ DataReader_init((DataReader*)self, schema, folder, snapshot, segments,
+ seg_tick);
+ ABSTRACT_CLASS_CHECK(self, SORTREADER);
+ return self;
+}
+
+DataReader*
+SortReader_aggregator(SortReader *self, VArray *readers, I32Array *offsets)
+{
+ UNUSED_VAR(self);
+ UNUSED_VAR(readers);
+ UNUSED_VAR(offsets);
+ return NULL;
+}
+
+DefaultSortReader*
+DefSortReader_new(Schema *schema, Folder *folder, Snapshot *snapshot,
+ VArray *segments, int32_t seg_tick)
+{
+ DefaultSortReader *self
+ = (DefaultSortReader*)VTable_Make_Obj(DEFAULTSORTREADER);
+ return DefSortReader_init(self, schema, folder, snapshot, segments,
+ seg_tick);
+}
+
+DefaultSortReader*
+DefSortReader_init(DefaultSortReader *self, Schema *schema, Folder *folder,
+ Snapshot *snapshot, VArray *segments, int32_t seg_tick)
+{
+ Segment *segment;
+ Hash *metadata;
+ DataReader_init((DataReader*)self, schema, folder, snapshot, segments,
+ seg_tick);
+ segment = DefSortReader_Get_Segment(self);
+ metadata = (Hash*)Seg_Fetch_Metadata_Str(segment, "sort", 4);
+
+ // Check format.
+ self->format = 0;
+ if (metadata) {
+ Obj *format = Hash_Fetch_Str(metadata, "format", 6);
+ if (!format) { THROW(ERR, "Missing 'format' var"); }
+ else {
+ self->format = (int32_t)Obj_To_I64(format);
+ if (self->format < 2 || self->format > 3) {
+ THROW(ERR, "Unsupported sort cache format: %i32",
+ self->format);
+ }
+ }
+ }
+
+ // Init.
+ self->caches = Hash_new(0);
+
+ // Either extract or fake up the "counts", "null_ords", and "ord_widths"
+ // hashes.
+ if (metadata) {
+ self->counts = (Hash*)INCREF(CERTIFY(
+ Hash_Fetch_Str(metadata, "counts", 6), HASH));
+ self->null_ords = (Hash*)Hash_Fetch_Str(metadata, "null_ords", 9);
+ if (self->null_ords) {
+ CERTIFY(self->null_ords, HASH);
+ INCREF(self->null_ords);
+ }
+ else {
+ self->null_ords = Hash_new(0);
+ }
+ self->ord_widths = (Hash*)Hash_Fetch_Str(metadata, "ord_widths", 10);
+ if (self->ord_widths) {
+ CERTIFY(self->ord_widths, HASH);
+ INCREF(self->ord_widths);
+ }
+ else {
+ self->ord_widths = Hash_new(0);
+ }
+ }
+ else {
+ self->counts = Hash_new(0);
+ self->null_ords = Hash_new(0);
+ self->ord_widths = Hash_new(0);
+ }
+
+ return self;
+}
+
+void
+DefSortReader_close(DefaultSortReader *self)
+{
+ if (self->caches) {
+ Hash_Dec_RefCount(self->caches);
+ self->caches = NULL;
+ }
+ if (self->counts) {
+ Hash_Dec_RefCount(self->counts);
+ self->counts = NULL;
+ }
+ if (self->null_ords) {
+ Hash_Dec_RefCount(self->null_ords);
+ self->null_ords = NULL;
+ }
+ if (self->ord_widths) {
+ Hash_Dec_RefCount(self->ord_widths);
+ self->ord_widths = NULL;
+ }
+}
+
+void
+DefSortReader_destroy(DefaultSortReader *self)
+{
+ DECREF(self->caches);
+ DECREF(self->counts);
+ DECREF(self->null_ords);
+ DECREF(self->ord_widths);
+ SUPER_DESTROY(self, DEFAULTSORTREADER);
+}
+
+static int32_t
+S_calc_ord_width(int32_t cardinality)
+{
+ if (cardinality <= 0x00000002) { return 1; }
+ else if (cardinality <= 0x00000004) { return 2; }
+ else if (cardinality <= 0x0000000F) { return 4; }
+ else if (cardinality <= 0x000000FF) { return 8; }
+ else if (cardinality <= 0x0000FFFF) { return 16; }
+ else { return 32; }
+}
+
+static SortCache*
+S_lazy_init_sort_cache(DefaultSortReader *self, const CharBuf *field)
+{
+ // See if we have any values.
+ Obj *count_obj = Hash_Fetch(self->counts, (Obj*)field);
+ int32_t count = count_obj ? (int32_t)Obj_To_I64(count_obj) : 0;
+ if (!count) { return NULL; }
+
+ // Get a FieldType and sanity check that the field is sortable.
+ Schema *schema = DefSortReader_Get_Schema(self);
+ FieldType *type = Schema_Fetch_Type(schema, field);
+ if (!type || !FType_Sortable(type)) {
+ THROW(ERR, "'%o' isn't a sortable field", field);
+ }
+
+ // Open streams.
+ Folder *folder = DefSortReader_Get_Folder(self);
+ Segment *segment = DefSortReader_Get_Segment(self);
+ CharBuf *seg_name = Seg_Get_Name(segment);
+ size_t size = ZCB_size() + CB_Get_Size(seg_name) + 40;
+ CharBuf *path = (CharBuf*)ZCB_newf(alloca(size), size, "");
+ int32_t field_num = Seg_Field_Num(segment, field);
+ int8_t prim_id = FType_Primitive_ID(type);
+ bool_t var_width = (prim_id == FType_TEXT || prim_id == FType_BLOB)
+ ? true
+ : false;
+ CB_setf(path, "%o/sort-%i32.ord", seg_name, field_num);
+ InStream *ord_in = Folder_Open_In(folder, path);
+ if (!ord_in) {
+ THROW(ERR, "Error building sort cache for '%o': %o",
+ field, Err_get_error());
+ }
+ InStream *ix_in = NULL;
+ if (var_width) {
+ CB_setf(path, "%o/sort-%i32.ix", seg_name, field_num);
+ ix_in = Folder_Open_In(folder, path);
+ if (!ix_in) {
+ THROW(ERR, "Error building sort cache for '%o': %o",
+ field, Err_get_error());
+ }
+ }
+ CB_setf(path, "%o/sort-%i32.dat", seg_name, field_num);
+ InStream *dat_in = Folder_Open_In(folder, path);
+ if (!dat_in) {
+ THROW(ERR, "Error building sort cache for '%o': %o",
+ field, Err_get_error());
+ }
+
+ Obj *null_ord_obj = Hash_Fetch(self->null_ords, (Obj*)field);
+ int32_t null_ord = null_ord_obj ? (int32_t)Obj_To_I64(null_ord_obj) : -1;
+ Obj *ord_width_obj = Hash_Fetch(self->ord_widths, (Obj*)field);
+ int32_t ord_width = ord_width_obj
+ ? (int32_t)Obj_To_I64(ord_width_obj)
+ : S_calc_ord_width(count);
+ int32_t doc_max = (int32_t)Seg_Get_Count(segment);
+
+ SortCache *cache = NULL;
+ switch (prim_id & FType_PRIMITIVE_ID_MASK) {
+ case FType_TEXT:
+ cache = (SortCache*)TextSortCache_new(field, type, count,
+ doc_max, null_ord, ord_width, ord_in, ix_in, dat_in);
+ break;
+ case FType_INT32:
+ cache = (SortCache*)I32SortCache_new(field, type, count,
+ doc_max, null_ord, ord_width, ord_in, dat_in);
+ break;
+ case FType_INT64:
+ cache = (SortCache*)I64SortCache_new(field, type, count,
+ doc_max, null_ord, ord_width, ord_in, dat_in);
+ break;
+ case FType_FLOAT32:
+ cache = (SortCache*)F32SortCache_new(field, type, count,
+ doc_max, null_ord, ord_width, ord_in, dat_in);
+ break;
+ case FType_FLOAT64:
+ cache = (SortCache*)F64SortCache_new(field, type, count,
+ doc_max, null_ord, ord_width, ord_in, dat_in);
+ break;
+ default:
+ THROW(ERR, "No SortCache class for %o", type);
+ }
+ Hash_Store(self->caches, (Obj*)field, (Obj*)cache);
+
+ if (self->format == 2) { // bug compatibility
+ SortCache_Set_Native_Ords(cache, true);
+ }
+
+ DECREF(ord_in);
+ DECREF(ix_in);
+ DECREF(dat_in);
+
+ return cache;
+}
+
+SortCache*
+DefSortReader_fetch_sort_cache(DefaultSortReader *self, const CharBuf *field)
+{
+ SortCache *cache = NULL;
+
+ if (field) {
+ cache = (SortCache*)Hash_Fetch(self->caches, (Obj*)field);
+ if (!cache) {
+ cache = S_lazy_init_sort_cache(self, field);
+ }
+ }
+
+ return cache;
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Propchange: incubator/lucy/trunk/import/core/KinoSearch/Index/SortReader.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/SortReader.cfh
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/SortReader.cfh?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/SortReader.cfh (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/SortReader.cfh Thu Oct 14 08:48:04 2010
@@ -0,0 +1,56 @@
+parcel KinoSearch cnick Kino;
+
+/** Read a segment's sort caches.
+ */
+abstract class KinoSearch::Index::SortReader
+ inherits KinoSearch::Index::DataReader {
+
+ inert SortReader*
+ init(SortReader *self, Schema *schema = NULL, Folder *folder = NULL,
+ Snapshot *snapshot = NULL, VArray *segments = NULL,
+ int32_t seg_tick = -1);
+
+ abstract nullable SortCache*
+ Fetch_Sort_Cache(SortReader *self, const CharBuf *field);
+
+ /** Returns NULL, since multi-segment sort caches cannot be produced by
+ * the default implementation.
+ */
+ public incremented nullable DataReader*
+ Aggregator(SortReader *self, VArray *readers, I32Array *offsets);
+
+}
+
+class KinoSearch::Index::DefaultSortReader cnick DefSortReader
+ inherits KinoSearch::Index::SortReader {
+
+ Hash *caches;
+ Hash *counts;
+ Hash *null_ords;
+ Hash *ord_widths;
+ int32_t format;
+
+ inert incremented DefaultSortReader*
+ new(Schema *schema, Folder *folder, Snapshot *snapshot, VArray *segments,
+ int32_t seg_tick);
+
+ inert DefaultSortReader*
+ init(DefaultSortReader *self, Schema *schema, Folder *folder,
+ Snapshot *snapshot, VArray *segments, int32_t seg_tick);
+
+ nullable SortCache*
+ Fetch_Sort_Cache(DefaultSortReader *self, const CharBuf *field);
+
+ public void
+ Close(DefaultSortReader *self);
+
+ public void
+ Destroy(DefaultSortReader *self);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/SortWriter.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/SortWriter.c?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/SortWriter.c (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/SortWriter.c Thu Oct 14 08:48:04 2010
@@ -0,0 +1,252 @@
+#define C_KINO_SORTWRITER
+#include "KinoSearch/Util/ToolSet.h"
+#include <math.h>
+
+#include "KinoSearch/Index/SortWriter.h"
+#include "KinoSearch/Index/Inverter.h"
+#include "KinoSearch/Index/PolyReader.h"
+#include "KinoSearch/Index/Segment.h"
+#include "KinoSearch/Index/SegReader.h"
+#include "KinoSearch/Index/Snapshot.h"
+#include "KinoSearch/Index/SortCache.h"
+#include "KinoSearch/Index/SortFieldWriter.h"
+#include "KinoSearch/Index/SortReader.h"
+#include "KinoSearch/Plan/FieldType.h"
+#include "KinoSearch/Plan/Schema.h"
+#include "KinoSearch/Store/Folder.h"
+#include "KinoSearch/Store/InStream.h"
+#include "KinoSearch/Store/OutStream.h"
+#include "KinoSearch/Util/Memory.h"
+#include "KinoSearch/Util/MemoryPool.h"
+#include "KinoSearch/Util/SortUtils.h"
+
+int32_t SortWriter_current_file_format = 3;
+
+static size_t default_mem_thresh = 0x400000; // 4 MB
+
+SortWriter*
+SortWriter_new(Schema *schema, Snapshot *snapshot, Segment *segment,
+ PolyReader *polyreader)
+{
+ SortWriter *self = (SortWriter*)VTable_Make_Obj(SORTWRITER);
+ return SortWriter_init(self, schema, snapshot, segment, polyreader);
+}
+
+SortWriter*
+SortWriter_init(SortWriter *self, Schema *schema, Snapshot *snapshot,
+ Segment *segment, PolyReader *polyreader)
+{
+ uint32_t field_max = Schema_Num_Fields(schema) + 1;
+ DataWriter_init((DataWriter*)self, schema, snapshot, segment, polyreader);
+
+ // Init.
+ self->field_writers = VA_new(field_max);
+ self->counts = Hash_new(0);
+ self->null_ords = Hash_new(0);
+ self->ord_widths = Hash_new(0);
+ self->temp_ord_out = NULL;
+ self->temp_ix_out = NULL;
+ self->temp_dat_out = NULL;
+ self->mem_pool = MemPool_new(0);
+ self->mem_thresh = default_mem_thresh;
+ self->flush_at_finish = false;
+
+ return self;
+}
+
+void
+SortWriter_destroy(SortWriter *self)
+{
+ DECREF(self->field_writers);
+ DECREF(self->counts);
+ DECREF(self->null_ords);
+ DECREF(self->ord_widths);
+ DECREF(self->temp_ord_out);
+ DECREF(self->temp_ix_out);
+ DECREF(self->temp_dat_out);
+ DECREF(self->mem_pool);
+ SUPER_DESTROY(self, SORTWRITER);
+}
+
+void
+SortWriter_set_default_mem_thresh(size_t mem_thresh)
+{
+ default_mem_thresh = mem_thresh;
+}
+
+static SortFieldWriter*
+S_lazy_init_field_writer(SortWriter *self, int32_t field_num)
+{
+ SortFieldWriter *field_writer
+ = (SortFieldWriter*)VA_Fetch(self->field_writers, field_num);
+ if (!field_writer) {
+
+ // Open temp files.
+ if (!self->temp_ord_out) {
+ Folder *folder = self->folder;
+ CharBuf *seg_name = Seg_Get_Name(self->segment);
+ size_t size = ZCB_size() + CB_Get_Size(seg_name) + 50;
+ CharBuf *path = (CharBuf*)ZCB_newf(alloca(size), size, "");
+ CB_setf(path, "%o/sort_ord_temp", seg_name);
+ self->temp_ord_out = Folder_Open_Out(folder, path);
+ if (!self->temp_ord_out) { RETHROW(INCREF(Err_get_error())); }
+ CB_setf(path, "%o/sort_ix_temp", seg_name);
+ self->temp_ix_out = Folder_Open_Out(folder, path);
+ if (!self->temp_ix_out) { RETHROW(INCREF(Err_get_error())); }
+ CB_setf(path, "%o/sort_dat_temp", seg_name);
+ self->temp_dat_out = Folder_Open_Out(folder, path);
+ if (!self->temp_dat_out) { RETHROW(INCREF(Err_get_error())); }
+ }
+
+ CharBuf *field = Seg_Field_Name(self->segment, field_num);
+ field_writer = SortFieldWriter_new(self->schema, self->snapshot,
+ self->segment, self->polyreader, field, self->mem_pool,
+ self->mem_thresh, self->temp_ord_out, self->temp_ix_out,
+ self->temp_dat_out);
+ VA_Store(self->field_writers, field_num, (Obj*)field_writer);
+ }
+ return field_writer;
+}
+
+void
+SortWriter_add_inverted_doc(SortWriter *self, Inverter *inverter,
+ int32_t doc_id)
+{
+ int32_t field_num;
+
+ Inverter_Iterate(inverter);
+ while (0 != (field_num = Inverter_Next(inverter))) {
+ FieldType *type = Inverter_Get_Type(inverter);
+ if (FType_Sortable(type)) {
+ SortFieldWriter *field_writer
+ = S_lazy_init_field_writer(self, field_num);
+ SortFieldWriter_Add(field_writer, doc_id,
+ Inverter_Get_Value(inverter));
+ }
+ }
+
+ // If our SortFieldWriters have collectively passed the memory threshold,
+ // flush all of them, then release all unique values with a single action.
+ if (MemPool_Get_Consumed(self->mem_pool) > self->mem_thresh) {
+ for (uint32_t i = 0; i < VA_Get_Size(self->field_writers); i++) {
+ SortFieldWriter *const field_writer
+ = (SortFieldWriter*)VA_Fetch(self->field_writers, i);
+ if (field_writer) { SortFieldWriter_Flush(field_writer); }
+ }
+ MemPool_Release_All(self->mem_pool);
+ self->flush_at_finish = true;
+ }
+}
+
+void
+SortWriter_add_segment(SortWriter *self, SegReader *reader, I32Array *doc_map)
+{
+ VArray *fields = Schema_All_Fields(self->schema);
+
+ // Proceed field-at-a-time, rather than doc-at-a-time.
+ for (uint32_t i = 0, max = VA_Get_Size(fields); i < max; i++) {
+ CharBuf *field = (CharBuf*)VA_Fetch(fields, i);
+ SortReader *sort_reader = (SortReader*)SegReader_Fetch(reader,
+ VTable_Get_Name(SORTREADER));
+ SortCache *cache = sort_reader
+ ? SortReader_Fetch_Sort_Cache(sort_reader, field) : NULL;
+ if (cache) {
+ int32_t field_num = Seg_Field_Num(self->segment, field);
+ SortFieldWriter *field_writer
+ = S_lazy_init_field_writer(self, field_num);
+ SortFieldWriter_Add_Segment(field_writer, reader, doc_map, cache);
+ self->flush_at_finish = true;
+ }
+ }
+
+ DECREF(fields);
+}
+
+void
+SortWriter_finish(SortWriter *self)
+{
+ VArray *const field_writers = self->field_writers;
+
+ // If we have no data, bail out.
+ if (!self->temp_ord_out) { return; }
+
+ // If we've either flushed or added segments, flush everything so that any
+ // one field can use the entire margin up to mem_thresh.
+ if (self->flush_at_finish) {
+ for (uint32_t i = 1, max = VA_Get_Size(field_writers); i < max; i++) {
+ SortFieldWriter *field_writer
+ = (SortFieldWriter*)VA_Fetch(field_writers, i);
+ if (field_writer) {
+ SortFieldWriter_Flush(field_writer);
+ }
+ }
+ }
+
+ // Close down temp streams.
+ OutStream_Close(self->temp_ord_out);
+ OutStream_Close(self->temp_ix_out);
+ OutStream_Close(self->temp_dat_out);
+
+ for (uint32_t i = 1, max = VA_Get_Size(field_writers); i < max; i++) {
+ SortFieldWriter *field_writer
+ = (SortFieldWriter*)VA_Delete(field_writers, i);
+ if (field_writer) {
+ CharBuf *field = Seg_Field_Name(self->segment, i);
+ SortFieldWriter_Flip(field_writer);
+ int32_t count = SortFieldWriter_Finish(field_writer);
+ Hash_Store(self->counts, (Obj*)field,
+ (Obj*)CB_newf("%i32", count));
+ int32_t null_ord = SortFieldWriter_Get_Null_Ord(field_writer);
+ if (null_ord != -1) {
+ Hash_Store(self->null_ords, (Obj*)field,
+ (Obj*)CB_newf("%i32", null_ord));
+ }
+ int32_t ord_width = SortFieldWriter_Get_Ord_Width(field_writer);
+ Hash_Store(self->ord_widths, (Obj*)field,
+ (Obj*)CB_newf("%i32", ord_width));
+ }
+
+ DECREF(field_writer);
+ }
+ VA_Clear(field_writers);
+
+ // Store metadata.
+ Seg_Store_Metadata_Str(self->segment, "sort", 4,
+ (Obj*)SortWriter_Metadata(self));
+
+ // Clean up.
+ Folder *folder = self->folder;
+ CharBuf *seg_name = Seg_Get_Name(self->segment);
+ size_t size = ZCB_size() + CB_Get_Size(seg_name) + 40;
+ CharBuf *path = (CharBuf*)ZCB_newf(alloca(size), size, "");
+ CB_setf(path, "%o/sort_ord_temp", seg_name);
+ Folder_Delete(folder, path);
+ CB_setf(path, "%o/sort_ix_temp", seg_name);
+ Folder_Delete(folder, path);
+ CB_setf(path, "%o/sort_dat_temp", seg_name);
+ Folder_Delete(folder, path);
+}
+
+Hash*
+SortWriter_metadata(SortWriter *self)
+{
+ Hash *const metadata = DataWriter_metadata((DataWriter*)self);
+ Hash_Store_Str(metadata, "counts", 6, INCREF(self->counts));
+ Hash_Store_Str(metadata, "null_ords", 9, INCREF(self->null_ords));
+ Hash_Store_Str(metadata, "ord_widths", 10, INCREF(self->ord_widths));
+ return metadata;
+}
+
+int32_t
+SortWriter_format(SortWriter *self)
+{
+ UNUSED_VAR(self);
+ return SortWriter_current_file_format;
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Propchange: incubator/lucy/trunk/import/core/KinoSearch/Index/SortWriter.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/SortWriter.cfh
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/SortWriter.cfh?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/SortWriter.cfh (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/SortWriter.cfh Thu Oct 14 08:48:04 2010
@@ -0,0 +1,65 @@
+parcel KinoSearch cnick Kino;
+
+/** Writer for sortable fields.
+ *
+ * Changes for format version 3:
+ *
+ * * Big-endian byte order instead of native byte order for ".ord" files.
+ * * "ord_widths" key added to metadata.
+ * * In variable-width cache formats, NULL entries get a file pointer in the
+ * ".ix" file instead of -1.
+ */
+
+class KinoSearch::Index::SortWriter inherits KinoSearch::Index::DataWriter {
+
+ VArray *field_writers;
+ Hash *counts;
+ Hash *null_ords;
+ Hash *ord_widths;
+ OutStream *temp_ord_out;
+ OutStream *temp_ix_out;
+ OutStream *temp_dat_out;
+ MemoryPool *mem_pool;
+ size_t mem_thresh;
+ bool_t flush_at_finish;
+
+ inert int32_t current_file_format;
+
+ inert incremented SortWriter*
+ new(Schema *schema, Snapshot *snapshot, Segment *segment,
+ PolyReader *polyreader);
+
+ inert SortWriter*
+ init(SortWriter *self, Schema *schema, Snapshot *snapshot,
+ Segment *segment, PolyReader *polyreader);
+
+ /* Test only. */
+ inert void
+ set_default_mem_thresh(size_t mem_thresh);
+
+ public void
+ Add_Inverted_Doc(SortWriter *self, Inverter *inverter, int32_t doc_id);
+
+ public void
+ Add_Segment(SortWriter *self, SegReader *reader,
+ I32Array *doc_map = NULL);
+
+ public incremented Hash*
+ Metadata(SortWriter *self);
+
+ public int32_t
+ Format(SortWriter *self);
+
+ public void
+ Finish(SortWriter *self);
+
+ public void
+ Destroy(SortWriter *self);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/TermInfo.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/TermInfo.c?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/TermInfo.c (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/TermInfo.c Thu Oct 14 08:48:04 2010
@@ -0,0 +1,95 @@
+#define C_KINO_TERMINFO
+#include "KinoSearch/Util/ToolSet.h"
+
+#include "KinoSearch/Index/TermInfo.h"
+#include "KinoSearch/Util/StringHelper.h"
+
+TermInfo*
+TInfo_new(int32_t doc_freq)
+{
+ TermInfo *self = (TermInfo*)VTable_Make_Obj(TERMINFO);
+ return TInfo_init(self, doc_freq);
+}
+
+TermInfo*
+TInfo_init(TermInfo *self, int32_t doc_freq)
+{
+ self->doc_freq = doc_freq;
+ self->post_filepos = 0;
+ self->skip_filepos = 0;
+ self->lex_filepos = 0;
+ return self;
+}
+
+TermInfo*
+TInfo_clone(TermInfo *self)
+{
+ TermInfo *evil_twin = TInfo_new(self->doc_freq);
+ evil_twin->post_filepos = self->post_filepos;
+ evil_twin->skip_filepos = self->skip_filepos;
+ evil_twin->lex_filepos = self->lex_filepos;
+ return evil_twin;
+}
+
+int32_t
+TInfo_get_doc_freq(TermInfo *self) { return self->doc_freq; }
+int64_t
+TInfo_get_lex_filepos(TermInfo *self) { return self->lex_filepos; }
+int64_t
+TInfo_get_post_filepos(TermInfo *self) { return self->post_filepos; }
+int64_t
+TInfo_get_skip_filepos(TermInfo *self) { return self->skip_filepos; }
+
+void
+TInfo_set_doc_freq(TermInfo *self, int32_t doc_freq)
+ { self->doc_freq = doc_freq; }
+void
+TInfo_set_lex_filepos(TermInfo *self, int64_t filepos)
+ { self->lex_filepos = filepos; }
+void
+TInfo_set_post_filepos(TermInfo *self, int64_t filepos)
+ { self->post_filepos = filepos; }
+void
+TInfo_set_skip_filepos(TermInfo *self, int64_t filepos)
+ { self->skip_filepos = filepos; }
+
+// TODO: this should probably be some sort of Dump variant rather than
+// To_String.
+CharBuf*
+TInfo_to_string(TermInfo *self)
+{
+ return CB_newf(
+ "doc freq: %i32\n"
+ "post filepos: %i64\n"
+ "skip filepos: %i64\n"
+ "index filepos: %i64",
+ self->doc_freq, self->post_filepos,
+ self->skip_filepos, self->lex_filepos
+ );
+}
+
+void
+TInfo_mimic(TermInfo *self, Obj *other)
+{
+ TermInfo *evil_twin = (TermInfo*)CERTIFY(other, TERMINFO);
+ self->doc_freq = evil_twin->doc_freq;
+ self->post_filepos = evil_twin->post_filepos;
+ self->skip_filepos = evil_twin->skip_filepos;
+ self->lex_filepos = evil_twin->lex_filepos;
+}
+
+void
+TInfo_reset(TermInfo *self)
+{
+ self->doc_freq = 0;
+ self->post_filepos = 0;
+ self->skip_filepos = 0;
+ self->lex_filepos = 0;
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Propchange: incubator/lucy/trunk/import/core/KinoSearch/Index/TermInfo.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/TermInfo.cfh
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/TermInfo.cfh?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/TermInfo.cfh (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/TermInfo.cfh Thu Oct 14 08:48:04 2010
@@ -0,0 +1,71 @@
+parcel KinoSearch cnick Kino;
+
+/** Filepointer/statistical data for a Term.
+ *
+ * The TermInfo contains pointer data indicating where information about a
+ * term can be found in various files, plus the document frequency of the
+ * term.
+ *
+ * The lex_filepos member variable is only used if the TermInfo is part of the
+ * .lexx stream; it is a filepointer to a locations in the main .lex file.
+ */
+
+class KinoSearch::Index::TermInfo cnick TInfo inherits KinoSearch::Object::Obj {
+
+ int32_t doc_freq;
+ int64_t post_filepos;
+ int64_t skip_filepos;
+ int64_t lex_filepos;
+
+
+ inert incremented TermInfo*
+ new(int32_t doc_freq = 0);
+
+ inert TermInfo*
+ init(TermInfo *self, int32_t doc_freq = 0);
+
+ public int32_t
+ Get_Doc_Freq(TermInfo *self);
+
+ public int64_t
+ Get_Lex_FilePos(TermInfo *self);
+
+ public int64_t
+ Get_Post_FilePos(TermInfo *self);
+
+ public int64_t
+ Get_Skip_FilePos(TermInfo *self);
+
+ public void
+ Set_Doc_Freq(TermInfo *self, int32_t doc_freq);
+
+ public void
+ Set_Lex_FilePos(TermInfo *self, int64_t filepos);
+
+ public void
+ Set_Post_FilePos(TermInfo *self, int64_t filepos);
+
+ public void
+ Set_Skip_FilePos(TermInfo *self, int64_t filepos);
+
+ /** "Zero out" the TermInfo.
+ */
+ void
+ Reset(TermInfo *self);
+
+ public void
+ Mimic(TermInfo *self, Obj *other);
+
+ public incremented TermInfo*
+ Clone(TermInfo *self);
+
+ public incremented CharBuf*
+ To_String(TermInfo *self);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/TermStepper.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/TermStepper.c?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/TermStepper.c (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/TermStepper.c Thu Oct 14 08:48:04 2010
@@ -0,0 +1,50 @@
+#define C_KINO_TERMSTEPPER
+#include "KinoSearch/Util/ToolSet.h"
+
+#include "KinoSearch/Index/TermStepper.h"
+#include "KinoSearch/Plan/Schema.h"
+#include "KinoSearch/Store/InStream.h"
+#include "KinoSearch/Store/OutStream.h"
+#include "KinoSearch/Util/StringHelper.h"
+
+TermStepper*
+TermStepper_init(TermStepper *self)
+{
+ Stepper_init((Stepper*)self);
+ self->value = NULL;
+ return self;
+}
+
+void
+TermStepper_destroy(TermStepper *self)
+{
+ DECREF(self->value);
+ SUPER_DESTROY(self, TERMSTEPPER);
+}
+
+void
+TermStepper_reset(TermStepper *self)
+{
+ DECREF(self->value);
+ self->value = NULL;
+}
+
+Obj*
+TermStepper_get_value(TermStepper *self)
+{
+ return self->value;
+}
+
+void
+TermStepper_set_value(TermStepper *self, Obj *value)
+{
+ DECREF(self->value);
+ self->value = value ? INCREF(value) : NULL;
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Propchange: incubator/lucy/trunk/import/core/KinoSearch/Index/TermStepper.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/TermStepper.cfh
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/TermStepper.cfh?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/TermStepper.cfh (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/TermStepper.cfh Thu Oct 14 08:48:04 2010
@@ -0,0 +1,26 @@
+parcel KinoSearch cnick Kino;
+
+abstract class KinoSearch::Index::TermStepper
+ inherits KinoSearch::Util::Stepper {
+
+ Obj *value;
+
+ public inert TermStepper*
+ init(TermStepper *self);
+
+ public void
+ Set_Value(TermStepper *self, Obj *value = NULL);
+
+ public nullable Obj*
+ Get_Value(TermStepper *self);
+
+ public void
+ Destroy(TermStepper *self);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/TermVector.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/TermVector.c?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/TermVector.c (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/TermVector.c Thu Oct 14 08:48:04 2010
@@ -0,0 +1,143 @@
+#define C_KINO_TERMVECTOR
+#define C_KINO_I32ARRAY
+#include "KinoSearch/Util/ToolSet.h"
+
+#include "KinoSearch/Index/TermVector.h"
+#include "KinoSearch/Store/InStream.h"
+#include "KinoSearch/Store/OutStream.h"
+
+TermVector*
+TV_new(const CharBuf *field, const CharBuf *text, I32Array *positions,
+ I32Array *start_offsets, I32Array *end_offsets)
+{
+ TermVector *self = (TermVector*)VTable_Make_Obj(TERMVECTOR);
+ return TV_init(self, field, text, positions, start_offsets, end_offsets);
+}
+
+TermVector*
+TV_init(TermVector *self, const CharBuf *field, const CharBuf *text,
+ I32Array *positions, I32Array *start_offsets, I32Array *end_offsets)
+{
+ // Assign.
+ self->field = CB_Clone(field);
+ self->text = CB_Clone(text);
+ self->num_pos = I32Arr_Get_Size(positions);
+ self->positions = (I32Array*)INCREF(positions);
+ self->start_offsets = (I32Array*)INCREF(start_offsets);
+ self->end_offsets = (I32Array*)INCREF(end_offsets);
+
+ if ( I32Arr_Get_Size(start_offsets) != self->num_pos
+ || I32Arr_Get_Size(end_offsets) != self->num_pos
+ ) {
+ THROW(ERR, "Unbalanced arrays: %u32 %u32 %u32", self->num_pos,
+ I32Arr_Get_Size(start_offsets), I32Arr_Get_Size(end_offsets));
+ }
+
+ return self;
+}
+
+void
+TV_destroy(TermVector *self)
+{
+ DECREF(self->field);
+ DECREF(self->text);
+ DECREF(self->positions);
+ DECREF(self->start_offsets);
+ DECREF(self->end_offsets);
+ SUPER_DESTROY(self, TERMVECTOR);
+}
+
+I32Array*
+TV_get_positions(TermVector *self) { return self->positions; }
+I32Array*
+TV_get_start_offsets(TermVector *self) { return self->start_offsets; }
+I32Array*
+TV_get_end_offsets(TermVector *self) { return self->end_offsets; }
+
+void
+TV_serialize(TermVector *self, OutStream *target)
+{
+ uint32_t i;
+ int32_t *posits = self->positions->ints;
+ int32_t *starts = self->start_offsets->ints;
+ int32_t *ends = self->start_offsets->ints;
+
+ CB_Serialize(self->field, target);
+ CB_Serialize(self->text, target);
+ OutStream_Write_C32(target, self->num_pos);
+
+ for (i = 0; i < self->num_pos; i++) {
+ OutStream_Write_C32(target, posits[i]);
+ OutStream_Write_C32(target, starts[i]);
+ OutStream_Write_C32(target, ends[i]);
+ }
+}
+
+TermVector*
+TV_deserialize(TermVector *self, InStream *instream)
+{
+ uint32_t i;
+ CharBuf *field = (CharBuf*)CB_deserialize(NULL, instream);
+ CharBuf *text = (CharBuf*)CB_deserialize(NULL, instream);
+ uint32_t num_pos = InStream_Read_C32(instream);
+ int32_t *posits, *starts, *ends;
+ I32Array *positions, *start_offsets, *end_offsets;
+
+ // Read positional data.
+ posits = (int32_t*)MALLOCATE(num_pos * sizeof(int32_t));
+ starts = (int32_t*)MALLOCATE(num_pos * sizeof(int32_t));
+ ends = (int32_t*)MALLOCATE(num_pos * sizeof(int32_t));
+ for (i = 0; i < num_pos; i++) {
+ posits[i] = InStream_Read_C32(instream);
+ starts[i] = InStream_Read_C32(instream);
+ ends[i] = InStream_Read_C32(instream);
+ }
+ positions = I32Arr_new_steal(posits, num_pos);
+ start_offsets = I32Arr_new_steal(starts, num_pos);
+ end_offsets = I32Arr_new_steal(ends, num_pos);
+
+ self = self ? self : (TermVector*)VTable_Make_Obj(TERMVECTOR);
+ self = TV_init(self, field, text, positions, start_offsets, end_offsets);
+
+ DECREF(positions);
+ DECREF(start_offsets);
+ DECREF(end_offsets);
+ DECREF(text);
+ DECREF(field);
+
+ return self;
+}
+
+bool_t
+TV_equals(TermVector *self, Obj *other)
+{
+ TermVector *const evil_twin = (TermVector*)other;
+ uint32_t i;
+ int32_t *const posits = self->positions->ints;
+ int32_t *const starts = self->start_offsets->ints;
+ int32_t *const ends = self->start_offsets->ints;
+ int32_t *const other_posits = evil_twin->positions->ints;
+ int32_t *const other_starts = evil_twin->start_offsets->ints;
+ int32_t *const other_ends = evil_twin->start_offsets->ints;
+
+ if (evil_twin == self) return true;
+
+ if (!CB_Equals(self->field, (Obj*)evil_twin->field)) return false;
+ if (!CB_Equals(self->text, (Obj*)evil_twin->text)) return false;
+ if (self->num_pos != evil_twin->num_pos) return false;
+
+ for (i = 0; i < self->num_pos; i++) {
+ if (posits[i] != other_posits[i]) return false;
+ if (starts[i] != other_starts[i]) return false;
+ if (ends[i] != other_ends[i]) return false;
+ }
+
+ return true;
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Propchange: incubator/lucy/trunk/import/core/KinoSearch/Index/TermVector.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/TermVector.cfh
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/TermVector.cfh?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/TermVector.cfh (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/TermVector.cfh Thu Oct 14 08:48:04 2010
@@ -0,0 +1,54 @@
+parcel KinoSearch cnick Kino;
+
+/** Term freq and positional data.
+ */
+
+class KinoSearch::Index::TermVector cnick TV
+ inherits KinoSearch::Object::Obj {
+
+ CharBuf *field;
+ CharBuf *text;
+ uint32_t num_pos;
+ I32Array *positions;
+ I32Array *start_offsets;
+ I32Array *end_offsets;
+
+ /** Constructor. The object will assume ownership of the positions,
+ * start_offsets, and end_offsets arrays.
+ */
+ inert incremented TermVector*
+ new(const CharBuf *field, const CharBuf *text, I32Array *positions,
+ I32Array *start_offsets, I32Array *end_offsets);
+
+ inert TermVector*
+ init(TermVector *self, const CharBuf *field, const CharBuf *text,
+ I32Array *positions, I32Array *start_offsets, I32Array *end_offsets);
+
+ I32Array*
+ Get_Positions(TermVector *self);
+
+ I32Array*
+ Get_Start_Offsets(TermVector *self);
+
+ I32Array*
+ Get_End_Offsets(TermVector *self);
+
+ public incremented TermVector*
+ Deserialize(TermVector *self, InStream *instream);
+
+ public bool_t
+ Equals(TermVector *self, Obj *other);
+
+ public void
+ Destroy(TermVector *self);
+
+ public void
+ Serialize(TermVector *self, OutStream *outstream);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/ZombieKeyedHash.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/ZombieKeyedHash.c?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/ZombieKeyedHash.c (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/ZombieKeyedHash.c Thu Oct 14 08:48:04 2010
@@ -0,0 +1,96 @@
+#define C_KINO_ZOMBIEKEYEDHASH
+#include "KinoSearch/Util/ToolSet.h"
+
+#include "KinoSearch/Index/ZombieKeyedHash.h"
+#include "KinoSearch/Plan/FieldType.h"
+#include "KinoSearch/Util/MemoryPool.h"
+
+ZombieKeyedHash*
+ZKHash_new(MemoryPool *memory_pool, uint8_t primitive_id)
+{
+ ZombieKeyedHash *self
+ = (ZombieKeyedHash*)VTable_Make_Obj(ZOMBIEKEYEDHASH);
+ Hash_init((Hash*)self, 0);
+ self->mem_pool = (MemoryPool*)INCREF(memory_pool);
+ self->prim_id = primitive_id;
+ return self;
+}
+
+void
+ZKHash_destroy(ZombieKeyedHash *self)
+{
+ DECREF(self->mem_pool);
+ SUPER_DESTROY(self, ZOMBIEKEYEDHASH);
+}
+
+Obj*
+ZKHash_make_key(ZombieKeyedHash *self, Obj *key, int32_t hash_sum)
+{
+ UNUSED_VAR(hash_sum);
+ Obj *retval = NULL;
+ switch(self->prim_id & FType_PRIMITIVE_ID_MASK) {
+ case FType_TEXT: {
+ CharBuf *source = (CharBuf*)key;
+ size_t size = ZCB_size() + CB_Get_Size(source) + 1;
+ void *allocation = MemPool_grab(self->mem_pool, size);
+ retval = (Obj*)ZCB_newf(allocation, size, "%o", source);
+ }
+ break;
+ case FType_INT32: {
+ size_t size = VTable_Get_Obj_Alloc_Size(INTEGER32);
+ Integer32 *copy
+ = (Integer32*)MemPool_grab(self->mem_pool, size);
+ VTable_Init_Obj(INTEGER32, copy);
+ Int32_init(copy, 0);
+ Int32_Mimic(copy, key);
+ retval = (Obj*)copy;
+ }
+ break;
+ case FType_INT64: {
+ size_t size = VTable_Get_Obj_Alloc_Size(INTEGER64);
+ Integer64 *copy
+ = (Integer64*)MemPool_Grab(self->mem_pool, size);
+ VTable_Init_Obj(INTEGER64, copy);
+ Int64_init(copy, 0);
+ Int64_Mimic(copy, key);
+ retval = (Obj*)copy;
+ }
+ break;
+ case FType_FLOAT32: {
+ size_t size = VTable_Get_Obj_Alloc_Size(FLOAT32);
+ Float32 *copy = (Float32*)MemPool_Grab(self->mem_pool, size);
+ VTable_Init_Obj(FLOAT32, copy);
+ Float32_init(copy, 0);
+ Float32_Mimic(copy, key);
+ retval = (Obj*)copy;
+ }
+ break;
+ case FType_FLOAT64: {
+ size_t size = VTable_Get_Obj_Alloc_Size(FLOAT64);
+ Float64 *copy = (Float64*)MemPool_Grab(self->mem_pool, size);
+ VTable_Init_Obj(FLOAT64, copy);
+ Float64_init(copy, 0);
+ Float64_Mimic(copy, key);
+ retval = (Obj*)copy;
+ }
+ break;
+ default:
+ THROW(ERR, "Unrecognized primitive id: %i8", self->prim_id);
+ }
+
+ /* FIXME This is a hack. It will leak memory if host objects get cached,
+ * which in the present implementation will happen as soon as the refcount
+ * reaches 4. However, we must never call Destroy() for these objects,
+ * because they will try to free() their initial allocation, which is
+ * invalid because it's part of a MemoryPool arena. */
+ INCREF(retval);
+
+ return retval;
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Propchange: incubator/lucy/trunk/import/core/KinoSearch/Index/ZombieKeyedHash.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: incubator/lucy/trunk/import/core/KinoSearch/Index/ZombieKeyedHash.cfh
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Index/ZombieKeyedHash.cfh?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Index/ZombieKeyedHash.cfh (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Index/ZombieKeyedHash.cfh Thu Oct 14 08:48:04 2010
@@ -0,0 +1,26 @@
+parcel KinoSearch cnick Kino;
+
+/** Hash which creates keys allocated from a MemoryPool rather than malloc.
+ */
+class KinoSearch::Index::SortFieldWriter::ZombieKeyedHash cnick ZKHash
+ inherits KinoSearch::Object::Hash {
+
+ MemoryPool *mem_pool;
+ uint8_t prim_id;
+
+ inert incremented ZombieKeyedHash*
+ new(MemoryPool *memory_pool, uint8_t primitive_id);
+
+ public void
+ Destroy(ZombieKeyedHash *self);
+
+ public incremented Obj*
+ Make_Key(ZombieKeyedHash *self, Obj *key, int32_t hash_sum);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Added: incubator/lucy/trunk/import/core/KinoSearch/Object/BitVector.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Object/BitVector.c?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Object/BitVector.c (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Object/BitVector.c Thu Oct 14 08:48:04 2010
@@ -0,0 +1,404 @@
+#define C_KINO_BITVECTOR
+#include "KinoSearch/Util/ToolSet.h"
+
+#include <math.h>
+
+#include "KinoSearch/Object/BitVector.h"
+
+// Shared subroutine for performing both OR and XOR ops.
+#define DO_OR 1
+#define DO_XOR 2
+static void
+S_do_or_or_xor(BitVector *self, const BitVector *other, int operation);
+
+// Number of 1 bits given a u8 value.
+static const uint32_t BYTE_COUNTS[256] = {
+ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
+};
+
+
+BitVector*
+BitVec_new(uint32_t capacity)
+{
+ BitVector *self = (BitVector*)VTable_Make_Obj(BITVECTOR);
+ return BitVec_init(self, capacity);
+}
+
+BitVector*
+BitVec_init(BitVector *self, uint32_t capacity)
+{
+ const uint32_t byte_size = (uint32_t)ceil(capacity / 8.0);
+
+ // Derive.
+ self->bits = capacity
+ ? (uint8_t*)CALLOCATE(byte_size, sizeof(uint8_t))
+ : NULL;
+
+ // Assign.
+ self->cap = byte_size * 8;
+
+ return self;
+}
+
+void
+BitVec_destroy(BitVector* self)
+{
+ FREEMEM(self->bits);
+ SUPER_DESTROY(self, BITVECTOR);
+}
+
+BitVector*
+BitVec_clone(BitVector *self)
+{
+ BitVector *evil_twin = BitVec_new(self->cap);
+ uint32_t byte_size = (uint32_t)ceil(self->cap / 8.0);
+
+ // Forbid inheritance.
+ if (BitVec_Get_VTable(self) != BITVECTOR) {
+ THROW(ERR, "Attempt by %o to inherit BitVec_Clone",
+ BitVec_Get_Class_Name(self));
+ }
+
+ memcpy(evil_twin->bits, self->bits, byte_size * sizeof(uint8_t));
+
+ return evil_twin;
+}
+
+uint8_t*
+BitVec_get_raw_bits(BitVector *self) { return self->bits; }
+uint32_t
+BitVec_get_capacity(BitVector *self) { return self->cap; }
+
+void
+BitVec_mimic(BitVector *self, Obj *other)
+{
+ BitVector *evil_twin = (BitVector*)CERTIFY(other, BITVECTOR);
+ const uint32_t my_byte_size = (uint32_t)ceil(self->cap / 8.0);
+ const uint32_t evil_twin_byte_size = (uint32_t)ceil(evil_twin->cap / 8.0);
+ if (my_byte_size > evil_twin_byte_size) {
+ uint32_t space = my_byte_size - evil_twin_byte_size;
+ memset(self->bits + evil_twin_byte_size, 0, space);
+ }
+ else if (my_byte_size < evil_twin_byte_size) {
+ BitVec_Grow(self, evil_twin->cap - 1);
+ }
+ memcpy(self->bits, evil_twin->bits, evil_twin_byte_size);
+}
+
+void
+BitVec_grow(BitVector *self, uint32_t capacity)
+{
+ if (capacity > self->cap) {
+ const size_t old_byte_cap = (size_t)ceil(self->cap / 8.0);
+ const size_t new_byte_cap = (size_t)ceil((capacity + 1) / 8.0);
+ const size_t num_new_bytes = new_byte_cap - old_byte_cap;
+
+ self->bits = (uint8_t*)REALLOCATE(self->bits, new_byte_cap);
+ memset(self->bits + old_byte_cap, 0, num_new_bytes);
+ self->cap = new_byte_cap * 8;
+ }
+}
+
+void
+BitVec_set(BitVector *self, uint32_t tick)
+{
+ if (tick >= self->cap) {
+ uint32_t new_cap = (uint32_t)Memory_oversize(tick + 1, 0);
+ BitVec_Grow(self, new_cap);
+ }
+ NumUtil_u1set(self->bits, tick);
+}
+
+void
+BitVec_clear(BitVector *self, uint32_t tick)
+{
+ if (tick >= self->cap)
+ return;
+ NumUtil_u1clear(self->bits, tick);
+}
+
+void
+BitVec_clear_all(BitVector *self)
+{
+ const size_t byte_size = (size_t)ceil(self->cap / 8.0);
+ memset(self->bits, 0, byte_size);
+}
+
+bool_t
+BitVec_get(BitVector *self, uint32_t tick)
+{
+ if (tick >= self->cap)
+ return false;
+ return NumUtil_u1get(self->bits, tick);
+}
+
+static int32_t
+S_first_bit_in_nonzero_byte(uint8_t num)
+{
+ int32_t first_bit = 0;
+ if ((num & 0xF) == 0) { first_bit += 4; num >>= 4; }
+ if ((num & 0x3) == 0) { first_bit += 2; num >>= 2; }
+ if ((num & 0x1) == 0) { first_bit += 1; }
+ return first_bit;
+}
+
+int32_t
+BitVec_next_hit(BitVector *self, uint32_t tick)
+{
+ size_t byte_size = (size_t)ceil(self->cap / 8.0);
+ uint8_t *const limit = self->bits + byte_size;
+ uint8_t *ptr = self->bits + (tick >> 3);
+
+ if (ptr >= limit) {
+ return -1;
+ }
+ else if (*ptr != 0) {
+ // Special case the first byte.
+ const int32_t base = (ptr - self->bits) * 8;
+ const int32_t min_sub_tick = tick & 0x7;
+ unsigned int byte = *ptr >> min_sub_tick;
+ if (byte) {
+ const int32_t candidate = base + min_sub_tick +
+ S_first_bit_in_nonzero_byte(byte);
+ return candidate < (int32_t)self->cap ? candidate : -1;
+ }
+ }
+
+ for (ptr++ ; ptr < limit; ptr++) {
+ if (*ptr != 0) {
+ // There's a non-zero bit in this byte.
+ const int32_t base = (ptr - self->bits) * 8;
+ const int32_t candidate = base + S_first_bit_in_nonzero_byte(*ptr);
+ return candidate < (int32_t)self->cap ? candidate : -1;
+ }
+ }
+
+ return -1;
+}
+
+void
+BitVec_and(BitVector *self, const BitVector *other)
+{
+ uint8_t *bits_a = self->bits;
+ uint8_t *bits_b = other->bits;
+ const uint32_t min_cap = self->cap < other->cap
+ ? self->cap
+ : other->cap;
+ const size_t byte_size = (size_t)ceil(min_cap / 8.0);
+ uint8_t *const limit = bits_a + byte_size;
+
+ // Intersection.
+ while (bits_a < limit) {
+ *bits_a &= *bits_b;
+ bits_a++, bits_b++;
+ }
+
+ // Set all remaining to zero.
+ if (self->cap > min_cap) {
+ const size_t self_byte_size = (size_t)ceil(self->cap / 8.0);
+ memset(bits_a, 0, self_byte_size - byte_size);
+ }
+}
+
+void
+BitVec_or(BitVector *self, const BitVector *other)
+{
+ S_do_or_or_xor(self, other, DO_OR);
+}
+
+void
+BitVec_xor(BitVector *self, const BitVector *other)
+{
+ S_do_or_or_xor(self, other, DO_XOR);
+}
+
+static void
+S_do_or_or_xor(BitVector *self, const BitVector *other, int operation)
+{
+ uint8_t *bits_a, *bits_b;
+ uint32_t max_cap, min_cap;
+ uint8_t *limit;
+ double byte_size;
+
+ // Sort out what the minimum and maximum caps are.
+ if (self->cap < other->cap) {
+ max_cap = other->cap;
+ min_cap = self->cap;
+ }
+ else {
+ max_cap = self->cap;
+ min_cap = other->cap;
+ }
+
+ // Grow self if smaller than other, then calc pointers.
+ if (max_cap > self->cap) { BitVec_Grow(self, max_cap); }
+ bits_a = self->bits;
+ bits_b = other->bits;
+ byte_size = ceil(min_cap / 8.0);
+ limit = self->bits + (size_t)byte_size;
+
+ // Perform union of common bits.
+ if (operation == DO_OR) {
+ while (bits_a < limit) {
+ *bits_a |= *bits_b;
+ bits_a++, bits_b++;
+ }
+ }
+ else if (operation == DO_XOR) {
+ while (bits_a < limit) {
+ *bits_a ^= *bits_b;
+ bits_a++, bits_b++;
+ }
+ }
+ else {
+ THROW(ERR, "Unrecognized operation: %i32", (int32_t)operation);
+ }
+
+ // Copy remaining bits if other is bigger than self.
+ if (other->cap > min_cap) {
+ const double other_byte_size = ceil(other->cap / 8.0);
+ const size_t bytes_to_copy = (size_t)(other_byte_size - byte_size);
+ memcpy(bits_a, bits_b, bytes_to_copy);
+ }
+}
+
+void
+BitVec_and_not(BitVector *self, const BitVector *other)
+{
+ uint8_t *bits_a = self->bits;
+ uint8_t *bits_b = other->bits;
+ const uint32_t min_cap = self->cap < other->cap
+ ? self->cap
+ : other->cap;
+ const size_t byte_size = (size_t)ceil(min_cap / 8.0);
+ uint8_t *const limit = bits_a + byte_size;
+
+ // Clear bits set in other.
+ while (bits_a < limit) {
+ *bits_a &= ~(*bits_b);
+ bits_a++, bits_b++;
+ }
+}
+
+void
+BitVec_flip(BitVector *self, uint32_t tick)
+{
+ if (tick >= self->cap) {
+ uint32_t new_cap = (uint32_t)Memory_oversize(tick + 1, 0);
+ BitVec_Grow(self, new_cap);
+ }
+ NumUtil_u1flip(self->bits, tick);
+}
+
+void
+BitVec_flip_block(BitVector *self, uint32_t offset, uint32_t length)
+{
+ uint32_t first = offset;
+ uint32_t last = offset + length - 1;
+
+ // Bail if there's nothing to flip.
+ if (!length) { return; }
+
+ if (last >= self->cap) { BitVec_Grow(self, last + 1); }
+
+ // Flip partial bytes.
+ while (last % 8 != 0 && last > first) {
+ NumUtil_u1flip(self->bits, last);
+ last--;
+ }
+ while (first % 8 != 0 && first < last) {
+ NumUtil_u1flip(self->bits, first);
+ first++;
+ }
+
+ // Are first and last equal?
+ if (first == last) {
+ // There's only one bit left to flip.
+ NumUtil_u1flip(self->bits, last);
+ }
+ // They must be multiples of 8, then.
+ else {
+ const uint32_t start_tick = first >> 3;
+ const uint32_t limit_tick = last >> 3;
+ uint8_t *bits = self->bits + start_tick;
+ uint8_t *limit = self->bits + limit_tick;
+
+ // Last actually belongs to the following byte (e.g. 8, in byte 2).
+ NumUtil_u1flip(self->bits, last);
+
+ // Flip whole bytes.
+ for ( ; bits < limit; bits++) {
+ *bits = ~(*bits);
+ }
+ }
+}
+
+uint32_t
+BitVec_count(BitVector *self)
+{
+ uint32_t count = 0;
+ const size_t byte_size = (size_t)ceil(self->cap / 8.0);
+ uint8_t *ptr = self->bits;
+ uint8_t *const limit = ptr + byte_size;
+
+ for( ; ptr < limit; ptr++) {
+ count += BYTE_COUNTS[*ptr];
+ }
+
+ return count;
+}
+
+I32Array*
+BitVec_to_array(BitVector *self)
+{
+ uint32_t count = BitVec_Count(self);
+ uint32_t num_left = count;
+ const uint32_t capacity = self->cap;
+ uint32_t *const array = (uint32_t*)CALLOCATE(count, sizeof(uint32_t));
+ const size_t byte_size = (size_t)ceil(self->cap / 8.0);
+ uint8_t *const bits = self->bits;
+ uint8_t *const limit = bits + byte_size;
+ uint32_t num = 0;
+ uint32_t i = 0;
+
+ while (num_left) {
+ uint8_t *ptr = bits + (num >> 3);
+ while (ptr < limit && *ptr == 0) {
+ num += 8;
+ ptr++;
+ }
+ do {
+ if (BitVec_Get(self, num)) {
+ array[i++] = num;
+ if (--num_left == 0)
+ break;
+ }
+ if (num >= capacity)
+ THROW(ERR, "Exceeded capacity: %u32 %u32", num, capacity);
+ } while (++num % 8);
+ }
+
+ return I32Arr_new_steal((int32_t*)array, count);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+
Propchange: incubator/lucy/trunk/import/core/KinoSearch/Object/BitVector.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: incubator/lucy/trunk/import/core/KinoSearch/Object/BitVector.cfh
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/import/core/KinoSearch/Object/BitVector.cfh?rev=1022422&view=auto
==============================================================================
--- incubator/lucy/trunk/import/core/KinoSearch/Object/BitVector.cfh (added)
+++ incubator/lucy/trunk/import/core/KinoSearch/Object/BitVector.cfh Thu Oct 14 08:48:04 2010
@@ -0,0 +1,152 @@
+parcel KinoSearch cnick Kino;
+
+/** An array of bits.
+ *
+ * BitVector is a growable array of bits. All bits are initially zero.
+ */
+
+class KinoSearch::Object::BitVector cnick BitVec
+ inherits KinoSearch::Object::Obj {
+
+ uint32_t cap;
+ uint8_t *bits;
+
+ inert incremented BitVector*
+ new(uint32_t capacity = 0);
+
+ /**
+ * @param capacity The number of bits that the initial array should be
+ * able to hold.
+ */
+ public inert BitVector*
+ init(BitVector *self, uint32_t capacity = 0);
+
+ /** Return true if the bit at <code>tick</code> has been set, false if it
+ * hasn't (regardless of whether it lies within the bounds of the
+ * object's capacity).
+ *
+ * @param tick The requested bit.
+ */
+ public bool_t
+ Get(BitVector *self, uint32_t tick);
+
+ /** Set the bit at <code>tick</code> to 1.
+ *
+ * @param tick The bit to be set.
+ */
+ public void
+ Set(BitVector *self, uint32_t tick);
+
+ /** Accessor for the BitVector's underlying bit array.
+ */
+ nullable uint8_t*
+ Get_Raw_Bits(BitVector *self);
+
+ /** Accessor for capacity.
+ */
+ uint32_t
+ Get_Capacity(BitVector *self);
+
+ /** Returns the next set bit equal to or greater than <code>tick</code>,
+ * or -1 if no such bit exists.
+ */
+ public int32_t
+ Next_Hit(BitVector *self, uint32_t tick);
+
+ /** Clear the indicated bit. (i.e. set it to 0).
+ *
+ * @param tick The bit to be cleared.
+ */
+ public void
+ Clear(BitVector *self, uint32_t tick);
+
+ /** Clear all bits.
+ */
+ public void
+ Clear_All(BitVector *self);
+
+ /** If the BitVector does not already have enough room to hold the
+ * indicated number of bits, allocate more memory so that it can.
+ *
+ * @param capacity Least number of bits the BitVector should accomodate.
+ */
+ public void
+ Grow(BitVector *self, uint32_t capacity);
+
+ /** Modify the contents of this BitVector so that it has the same bits set
+ * as <code>other</code>.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ Mimic(BitVector *self, Obj *other);
+
+ /** Modify the BitVector so that only bits which remain set are those
+ * which 1) were already set in this BitVector, and 2) were also set in
+ * the other BitVector.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ And(BitVector *self, const BitVector *other);
+
+ /** Modify the BitVector, setting all bits which are set in the other
+ * BitVector if they were not already set.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ Or(BitVector *self, const BitVector *other);
+
+ /** Modify the BitVector, performing an XOR operation against the other.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ Xor(BitVector *self, const BitVector *other);
+
+ /** Modify the BitVector, clearing all bits which are set in the other.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ And_Not(BitVector *self, const BitVector *other);
+
+ /** Invert the value of a bit.
+ *
+ * @param tick The bit to invert.
+ */
+ public void
+ Flip(BitVector *self, uint32_t tick);
+
+ /** Invert each bit within a contiguous block.
+ *
+ * @param offset Lower bound.
+ * @param length The number of bits to flip.
+ */
+ public void
+ Flip_Block(BitVector *self, uint32_t offset, uint32_t length);
+
+ /** Return a count of the number of set bits.
+ */
+ public uint32_t
+ Count(BitVector *self);
+
+ /** Return an array where each element represents a set bit.
+ */
+ public incremented I32Array*
+ To_Array(BitVector *self);
+
+ public void
+ Destroy(BitVector *self);
+
+ public incremented BitVector*
+ Clone(BitVector *self);
+}
+
+/* Copyright 2006-2010 Marvin Humphrey
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * under the same terms as Perl itself.
+ */
+