/*
* 疎行列を扱うためのコード
*
* (1) 行列(sparse_matrix)のインスタンスを作成し行列の要素を設定する
* (2) 行列から行列イメージ(matrix_image)を作成する
* * 行列イメージをnetwork byteorderでファイルに書き出す
* (3) 行列イメージを読み込み(or mmapする)要素にアクセスする
*
*/
/*
* sparse matrix crammer
*
* sparse matrix storage uses following 2 sparse arrays
* *array of row
* *array of cells in a row
*
*(1/2)
* sparse row crammed row
* 0:0 1:1
* 1:1 ---->> 3:1
* 2:0 hash(h)%m 7:1
* 3:1 /
* 4:0 /
* 5:0 /
* 6:0
* 7:1
* 8:0
* (?:1 means non-all 0 row)
*(2/2)
* crammed row cram shift count
* 1:1 . . -> .. shift 0
* 3:1 . . -> .. shift 2
* 7:1 . . . -> ... shift 4
*
* contents of |
* matrix \|/
*
* ....... unified array of (value.column) pair
*
* matrix image
* image[0] : length of hashed row array
* image[1] : length of crammed cell array
* image[2 ~ 2+image[0]-1] : hashed row array
* image[2+image[0] ~ 2+image[0]+image[1]-1] : hashed row array
*
* Copyright (C) 2005 TABATA Yusuke
*
*/
/*
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#include <stdio.h>
#include <stdlib.h>
#include <anthy/diclib.h>
/* public APIs */
#include <anthy/matrix.h>
/* maximum length allowed for hash chain */
#define MAX_FAILURE 50
struct list_elm {
int index;
int value;
void *ptr;
struct list_elm *next;
/* bypass to mitigate O(n) insertion cost */
struct list_elm *orig_next;
};
struct array_elm {
int index;
int value;
void *ptr;
};
/*
* sparse array has two representation
*
* (1) list and (2) hashed array
* build list first and sparse_array_make_array() to build hashed array
* this stores one value and one pointer
*
*/
struct sparse_array {
/* list representation */
int elm_count;
/* sorted */
struct list_elm head;
/* array representation */
int array_len;
struct array_elm *array;
};
static struct sparse_array *
sparse_array_new(void)
{
struct sparse_array *a = malloc(sizeof(struct sparse_array));
/**/
a->elm_count = 0;
a->head.next = NULL;
a->head.orig_next = NULL;
a->head.index = -1;
/**/
a->array_len = 0;
a->array = NULL;
return a;
}
static void
insert_elm_after(struct list_elm *elm, int idx, int val, void *ptr)
{
struct list_elm *new_elm = malloc(sizeof(struct list_elm));
new_elm->value = val;
new_elm->index = idx;
new_elm->ptr = ptr;
/**/
new_elm->next = elm->next;
new_elm->orig_next = elm->next;
elm->next = new_elm;
}
static void
sparse_array_set(struct sparse_array *sa, int idx, int val, void *ptr)
{
struct list_elm *e;
e = &sa->head;
while (e) {
if (e->index == idx) {
/* find same index and update */
e->value = val;
e->ptr = ptr;
return ;
}
/* search */
if (e->index < idx && (!e->next || idx < e->next->index)) {
insert_elm_after(e, idx, val, ptr);
/**/
sa->elm_count ++;
return ;
}
/* go next */
if (e->orig_next && e->orig_next->index < idx) {
/* leap ahead */
e = e->orig_next;
} else {
e = e->next;
}
}
}
static int
hash(int val, int max, int nth)
{
val += nth * 113;
if (val < 0) {
val = -val;
}
if (max == 0) {
return 0;
}
return val % max;
}
static int
sparse_array_try_make_array(struct sparse_array *s)
{
int i;
struct list_elm *e;
/* initialize */
free(s->array);
s->array = malloc(sizeof(struct array_elm) * s->array_len);
for (i = 0; i < s->array_len; i++) {
s->array[i].index = -1;
}
/* push */
for (e = s->head.next; e; e = e->next) {
int ok = 0;
int n = 0;
do {
int h = hash(e->index, s->array_len, n);
if (s->array[h].index == -1) {
/* find unused element in this array */
ok = 1;
s->array[h].index = e->index;
s->array[h].value = e->value;
s->array[h].ptr = e->ptr;
} else {
/* collision */
n ++;
if (n > MAX_FAILURE) {
/* too much collision */
return 1;
}
}
} while (!ok);
}
return 0;
}
static void
sparse_array_make_array(struct sparse_array *s)
{
/* estimate length */
if (s->elm_count == 1) {
s->array_len = 1;
} else {
s->array_len = s->elm_count;
}
while (sparse_array_try_make_array(s)) {
/* expand a little */
s->array_len ++;
s->array_len *= 9;
s->array_len /= 8;
}
}
static struct array_elm *
sparse_array_get(struct sparse_array *s, int index, struct array_elm *arg)
{
if (s->array) {
int n = 0;
while (1) {
int h = hash(index, s->array_len, n);
if (s->array[h].index == index) {
*arg = s->array[h];
return arg;
}
n ++;
if (n == MAX_FAILURE) {
return NULL;
}
}
} else {
struct list_elm *e = e = s->head.next;
while (e) {
if (e->index == index) {
arg->value = e->value;
arg->ptr = e->ptr;
return arg;
}
/* go next */
if (e->orig_next && e->orig_next->index < index) {
/* leap ahead */
e = e->orig_next;
} else {
e = e->next;
}
}
return NULL;
}
}
static int
sparse_array_get_int(struct sparse_array *s, int index)
{
struct array_elm elm;
if (sparse_array_get(s, index, &elm)) {
return elm.value;
}
return 0;
}
static void *
sparse_array_get_ptr(struct sparse_array *s, int index)
{
struct array_elm elm;
if (sparse_array_get(s, index, &elm)) {
return elm.ptr;
}
return NULL;
}
/**/
struct sparse_matrix {
/**/
struct sparse_array *row_array;
/* image information */
int nr_rows;
int array_length;
};
/* API */
struct sparse_matrix *
anthy_sparse_matrix_new()
{
struct sparse_matrix *m = malloc(sizeof(struct sparse_matrix));
m->row_array = sparse_array_new();
m->nr_rows = 0;
return m;
}
static struct sparse_array *
find_row(struct sparse_matrix *m, int row, int create)
{
struct sparse_array *a;
a = sparse_array_get_ptr(m->row_array, row);
if (a) {
return a;
}
if (!create) {
return NULL;
}
/* allocate a new row */
a = sparse_array_new();
sparse_array_set(m->row_array, row, 0, a);
m->nr_rows ++;
return a;
}
/* API */
void
anthy_sparse_matrix_set(struct sparse_matrix *m, int row, int column,
int value, void *ptr)
{
struct sparse_array *a;
a = find_row(m, row, 1);
sparse_array_set(a, column, value, ptr);
}
/* API */
int
anthy_sparse_matrix_get_int(struct sparse_matrix *m, int row, int column)
{
struct sparse_array *a;
struct list_elm *e;
a = find_row(m, row, 1);
if (!a) {
return 0;
}
for (e = &a->head; e; e = e->next) {
if (e->index == column) {
return e->value;
}
}
return 0;
}
/* API */
void
anthy_sparse_matrix_make_matrix(struct sparse_matrix *m)
{
struct array_elm *ae;
int i;
int offset = 0;
/**/
sparse_array_make_array(m->row_array);
/**/
for (i = 0; i < m->row_array->array_len; i++) {
struct sparse_array *row;
ae = &m->row_array->array[i];
/**/
ae->value = offset;
if (ae->index == -1) {
continue;
}
/**/
row = ae->ptr;
sparse_array_make_array(row);
offset += row->array_len;
}
m->array_length = offset;
}
/* API */
struct matrix_image *
anthy_matrix_image_new(struct sparse_matrix *s)
{
struct matrix_image *mi;
int i;
int offset;
/**/
mi = malloc(sizeof(struct matrix_image));
mi->size = 2 + s->row_array->array_len * 2 + s->array_length * 2;
mi->image = malloc(sizeof(int) * mi->size);
mi->image[0] = s->row_array->array_len;
mi->image[1] = s->array_length;
/* row index */
offset = 2;
for (i = 0; i < s->row_array->array_len; i++) {
struct array_elm *ae;
ae = &s->row_array->array[i];
mi->image[offset + i*2] = ae->index;
mi->image[offset + i*2 + 1] = ae->value;
}
/* cells */
offset = 2 + s->row_array->array_len * 2;
for (i = 0; i < s->row_array->array_len; i++) {
struct array_elm *ae;
struct sparse_array *sa;
int j;
ae = &s->row_array->array[i];
if (ae->index == -1) {
continue;
}
sa = ae->ptr;
if (!sa) {
continue;
}
for (j = 0; j < sa->array_len; j++) {
struct array_elm *cell = &sa->array[j];
mi->image[offset] = cell->index;
if (cell->index == -1) {
mi->image[offset + 1] = -1;
} else {
mi->image[offset + 1] = cell->value;
}
offset += 2;
}
}
/**/
return mi;
}
static int
read_int(int *image, int idx, int en)
{
if (en) {
return anthy_dic_ntohl(image[idx]);
}
return image[idx];
}
static int
do_matrix_peek(int *image, int row, int col, int en)
{
int n, h, shift, next_shift;
int row_array_len = read_int(image, 0, en);
int column_array_len;
int cell_offset;
/* find row */
if (row_array_len == 0) {
return 0;
}
for (n = 0; ; n++) {
h = hash(row, row_array_len, n);
if (read_int(image, 2+ h * 2, en) == row) {
shift = read_int(image, 2+h*2+1, en);
break;
}
if (read_int(image, 2+ h * 2, en) == -1) {
return 0;
}
if (n > MAX_FAILURE) {
return 0;
}
}
/* find shift count of next row */
if (h == row_array_len - 1) {
/* last one */
next_shift = read_int(image, 1, en);
} else {
/* not last one */
next_shift = read_int(image, 2+h*2+2+1, en);
}
/* crammed width of this row */
column_array_len = next_shift - shift;
/* cells in this image */
cell_offset = 2 + row_array_len * 2;
for (n = 0; ; n++) {
h = hash(col, column_array_len, n);
if (read_int(image, cell_offset + shift * 2+ h * 2, en) == col) {
return read_int(image, cell_offset + shift * 2 + h*2+1, en);
}
if (read_int(image, cell_offset + shift * 2+ h * 2, en) == -1) {
/* not exist */
return 0;
}
if (n > MAX_FAILURE) {
return 0;
}
}
return 0;
}
/* API */
int
anthy_matrix_image_peek(int *image, int row, int col)
{
if (!image) {
return 0;
}
return do_matrix_peek(image, row, col, 1);
}
#ifdef DEBUG
/* for debug purpose */
static void
sparse_array_dump(struct sparse_array *s)
{
struct list_elm *e;
int i;
printf("list(%d):", s->elm_count);
for (e = s->head.next; e; e = e->next) {
printf(" %d:%d(%x)", e->index, e->value, (unsigned long)e->ptr);
}
printf("\n");
if (!s->array) {
return ;
}
printf("array(%d):", s->array_len);
for (i = 0; i < s->array_len; i ++) {
struct array_elm *ae = &s->array[i];
if (ae->index != -1) {
printf(" %d:%d,%d(%x)", i, ae->index, ae->value, (unsigned long)ae->ptr);
}
}
printf("\n");
return ;
/**/
}
/* for debug purpose */
void
sparse_matrix_dump(struct sparse_matrix *m)
{
struct list_elm *e;
struct array_elm *ae;
int i, offset;
if (!m->row_array) {
for (e = m->row_array->head.next; e; e = e->next) {
sparse_array_dump(e->ptr);
}
return ;
}
printf("\nnumber of row=%d, row array size=%d, cell array size=%d\n\n",
m->nr_rows, m->row_array->array_len, m->array_length);
/* row part */
for (i = 0; i < m->row_array->array_len; i++) {
struct array_elm *ae;
ae = &m->row_array->array[i];
if (ae->index != -1) {
printf(" [%d] row=%d, shift=%d\n", i, ae->index, ae->value);
}
}
printf("\n");
offset = 0;
for (i = 0; i < m->row_array->array_len; i++) {
struct array_elm *ae;
struct sparse_array *sa;
int j;
ae = &m->row_array->array[i];
sa = ae->ptr;
if (!sa) {
continue;
}
for (j = 0; j < sa->array_len; j++) {
struct array_elm *cell = &sa->array[j];
if (cell->index != -1) {
printf(" [%d] column=%d, value=%d\n", offset, cell->index, cell->value);
}
offset ++;
}
}
printf("\n");
}
#endif /* DEBUG */
syntax highlighted by Code2HTML, v. 0.9.1