[dovecot-cvs] dovecot/src/plugins/fts-squat squat-trie.c,1.6,1.7
tss at dovecot.org
tss at dovecot.org
Sun Dec 10 00:27:02 UTC 2006
Update of /var/lib/cvs/dovecot/src/plugins/fts-squat
In directory talvi:/tmp/cvs-serv21372
Modified Files:
squat-trie.c
Log Message:
64bit and big endian fixes
Index: squat-trie.c
===================================================================
RCS file: /var/lib/cvs/dovecot/src/plugins/fts-squat/squat-trie.c,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- squat-trie.c 9 Dec 2006 23:18:58 -0000 1.6
+++ squat-trie.c 10 Dec 2006 00:26:58 -0000 1.7
@@ -146,12 +146,14 @@
(struct trie_node **) \
((char *)((node) + 1) + \
ALIGN(sizeof(uint8_t) * ((node)->chars_8bit_count)))
-#define NODE_CHARS16(node) \
+#define NODE_CHARS16(node, level) \
(uint16_t *)((char *)NODE_CHILDREN8(node) + \
- sizeof(struct trie_node *) * ((node)->chars_8bit_count))
-#define NODE_CHILDREN16(node) \
+ ((node)->chars_8bit_count) * \
+ ((level) == BLOCK_SIZE ? \
+ sizeof(uint32_t) : sizeof(struct trie_node *)))
+#define NODE_CHILDREN16(node, level) \
(struct trie_node **) \
- ((char *)NODE_CHARS16(node) + \
+ ((char *)NODE_CHARS16(node, level) + \
ALIGN(sizeof(uint16_t) * ((node)->chars_16bit_count)))
static void free_node(struct trie_node *node, unsigned int level);
@@ -165,7 +167,8 @@
static int chr_8bit_cmp(const void *_key, const void *_chr)
{
- const uint8_t *key = _key, *chr = _chr;
+ const uint16_t *key = _key;
+ const uint8_t *chr = _chr;
return *key - *chr;
}
@@ -256,29 +259,57 @@
}
static void
+trie_map_node_save_leaf(const uint32_t *src_idx, unsigned int count,
+ uint32_t *children)
+{
+ unsigned int i;
+
+#ifndef ALLOW_UNALIGNED_ACCESS
+ if ((POINTER_CAST_TO(src_idx, size_t) & (sizeof(uint32_t)-1)) == 0) {
+#endif
+ for (i = 0; i < count; i++)
+ children[i] = src_idx[i];
+#ifndef ALLOW_UNALIGNED_ACCESS
+ } else {
+ /* unaligned access */
+ const uint8_t *src_idx8 = (const uint8_t *)src_idx;
+
+ for (i = 0; i < count; i++) {
+ memcpy(&children[i], src_idx8 + i * sizeof(uint32_t),
+ sizeof(children[i]));
+ }
+ }
+#endif
+}
+
+static void
trie_map_node_save_children(unsigned int level, const uint32_t *src_idx,
unsigned int count, struct trie_node **children)
{
- unsigned int i, file_bit;
+ unsigned int i;
- file_bit = level == BLOCK_SIZE ? 0 : 1;
+ if (level == BLOCK_SIZE) {
+ trie_map_node_save_leaf(src_idx, count, (uint32_t *)children);
+ return;
+ }
#ifndef ALLOW_UNALIGNED_ACCESS
if ((POINTER_CAST_TO(src_idx, size_t) & (sizeof(uint32_t)-1)) == 0) {
#endif
for (i = 0; i < count; i++) {
children[i] = src_idx[i] == 0 ? NULL :
- POINTER_CAST(src_idx[i] | file_bit);
+ POINTER_CAST(src_idx[i] | 1);
}
#ifndef ALLOW_UNALIGNED_ACCESS
} else {
/* unaligned access */
+ const uint8_t *src_idx8 = (const uint8_t *)src_idx;
uint32_t idx;
for (i = 0; i < count; i++) {
- memcpy(&idx, &src_idx[i], sizeof(idx));
- children[i] = idx == 0 ? NULL :
- POINTER_CAST(idx | file_bit);
+ memcpy(&idx, src_idx8 + i * sizeof(uint32_t),
+ sizeof(idx));
+ children[i] = idx == 0 ? NULL : POINTER_CAST(idx | 1);
}
}
#endif
@@ -311,6 +342,7 @@
uint32_t num, chars8_count, chars16_count;
unsigned int chars8_offset, chars8_size, chars8_memsize;
unsigned int chars16_offset, chars16_size, chars16_memsize;
+ unsigned int idx_size;
i_assert(trie->fd != -1);
@@ -338,8 +370,11 @@
return -1;
}
+ idx_size = level == BLOCK_SIZE ?
+ sizeof(uint32_t) : sizeof(struct trie_node *);
+
chars8_memsize = ALIGN(chars8_count * sizeof(uint8_t)) +
- chars8_count * sizeof(struct trie_node *);
+ chars8_count * idx_size;
if (trie_map_area(trie, chars8_offset, chars8_size + 8) < 0)
return -1;
@@ -373,7 +408,7 @@
}
chars16_memsize = ALIGN(chars16_count * sizeof(uint16_t)) +
- chars16_count * sizeof(struct trie_node *);
+ chars16_count * idx_size;
}
node = i_malloc(sizeof(*node) + chars8_memsize + chars16_memsize);
@@ -383,9 +418,9 @@
{
uint8_t *chars8 = NODE_CHARS8(node);
- uint16_t *chars16 = NODE_CHARS16(node);
+ uint16_t *chars16 = NODE_CHARS16(node, level);
struct trie_node **children8 = NODE_CHILDREN8(node);
- struct trie_node **children16 = NODE_CHILDREN16(node);
+ struct trie_node **children16 = NODE_CHILDREN16(node, level);
const uint32_t *src_idx;
const void *end_offset;
@@ -434,7 +469,7 @@
{
if (level < BLOCK_SIZE) {
struct trie_node **children8 = NODE_CHILDREN8(node);
- struct trie_node **children16 = NODE_CHILDREN16(node);
+ struct trie_node **children16 = NODE_CHILDREN16(node, level);
free_children(level + 1, children8, node->chars_8bit_count);
free_children(level + 1, children16, node->chars_16bit_count);
@@ -937,7 +972,8 @@
{
struct squat_trie *trie = ctx->trie;
struct trie_node *node = *parent;
- uint32_t char_idx, idx_base_offset;
+ struct trie_node **children;
+ uint32_t char_idx;
bool modified = FALSE;
int ret;
@@ -948,10 +984,9 @@
ctx->node_count++;
node = *parent = node_alloc(*data, level);
char_idx = 0;
- count = 1;
modified = TRUE;
} else {
- uint8_t *chars = PTR_OFFSET(node, sizeof(*node));
+ uint8_t *chars = NODE_CHARS8(node);
uint8_t *pos;
count = node->chars_8bit_count;
@@ -964,10 +999,9 @@
*data, level);
*parent = node;
modified = TRUE;
- count++;
}
}
- idx_base_offset = sizeof(*node) + ALIGN(count);
+ children = NODE_CHILDREN8(node);
} else {
unsigned int offset = sizeof(*node);
unsigned int count;
@@ -976,7 +1010,6 @@
ctx->node_count++;
node = *parent = node_alloc(*data, level);
char_idx = 0;
- count = 1;
modified = TRUE;
} else {
unsigned int idx_size;
@@ -998,15 +1031,13 @@
*data, level);
*parent = node;
modified = TRUE;
- count++;
}
}
- idx_base_offset = offset + ALIGN(sizeof(uint16_t) * count);
+ children = NODE_CHILDREN16(node, level);
}
if (level < BLOCK_SIZE) {
- struct trie_node **children = PTR_OFFSET(node, idx_base_offset);
size_t child_idx = POINTER_CAST_TO(children[char_idx], size_t);
if ((child_idx & 1) != 0) {
@@ -1021,7 +1052,7 @@
if (ret > 0)
node->modified = TRUE;
} else {
- uint32_t *uid_lists = PTR_OFFSET(node, idx_base_offset);
+ uint32_t *uid_lists = (uint32_t *)children;
if (squat_uidlist_add(trie->uidlist, &uid_lists[char_idx],
uid) < 0)
return -1;
@@ -1035,49 +1066,40 @@
trie_lookup_node(struct squat_trie *trie, struct trie_node *node,
const uint16_t *data, unsigned int level)
{
- uint32_t char_idx, idx_base_offset;
+ struct trie_node **children;
+ uint32_t char_idx;
if (*data < 256) {
const uint8_t *chars, *pos;
- unsigned int count;
if (node == NULL)
return 0;
- chars = CONST_PTR_OFFSET(node, sizeof(*node));
- count = node->chars_8bit_count;
- pos = bsearch(data, chars, count, sizeof(chars[0]),
- chr_8bit_cmp);
+ chars = NODE_CHARS8(node);
+ pos = bsearch(data, chars, node->chars_8bit_count,
+ sizeof(chars[0]), chr_8bit_cmp);
if (pos == NULL || *pos != *data)
return 0;
char_idx = pos - chars;
- idx_base_offset = sizeof(*node) + ALIGN(count);
+ children = NODE_CHILDREN8(node);
} else {
const uint16_t *chars, *pos;
- unsigned int count, idx_size, offset;
if (node == NULL)
return 0;
- idx_size = level < BLOCK_SIZE ?
- sizeof(struct trie_node *) : sizeof(uint32_t);
- offset = sizeof(*node) + ALIGN(node->chars_8bit_count) +
- idx_size * node->chars_8bit_count;
- chars = PTR_OFFSET(node, offset);
-
- count = node->chars_16bit_count;
- pos = bsearch(data, chars, count, sizeof(chars[0]),
- chr_16bit_cmp);
+ chars = NODE_CHARS16(node, level);
+ pos = bsearch(data, chars, node->chars_16bit_count,
+ sizeof(chars[0]), chr_16bit_cmp);
if (pos == NULL || *pos != *data)
return 0;
char_idx = pos - chars;
- idx_base_offset = offset + ALIGN(sizeof(uint16_t) * count);
+ children = NODE_CHILDREN16(node, level);
}
if (level < BLOCK_SIZE) {
- struct trie_node **children = PTR_OFFSET(node, idx_base_offset);
size_t child_idx = POINTER_CAST_TO(children[char_idx], size_t);
if ((child_idx & 1) != 0) {
@@ -1090,8 +1112,7 @@
return trie_lookup_node(trie, children[char_idx],
data + 1, level + 1);
} else {
- const uint32_t *uid_lists =
- CONST_PTR_OFFSET(node, idx_base_offset);
+ const uint32_t *uid_lists = (const uint32_t *)children;
return uid_lists[char_idx];
}
@@ -1234,9 +1255,9 @@
static void node_pack(buffer_t *buf, struct trie_node *node)
{
uint8_t *chars8 = NODE_CHARS8(node);
- uint16_t *chars16 = NODE_CHARS16(node);
+ uint16_t *chars16 = NODE_CHARS16(node, 0);
struct trie_node **children8 = NODE_CHILDREN8(node);
- struct trie_node **children16 = NODE_CHILDREN16(node);
+ struct trie_node **children16 = NODE_CHILDREN16(node, 0);
buffer_set_used_size(buf, 0);
_squat_trie_pack_num(buf, (node->chars_8bit_count << 1) |
@@ -1255,7 +1276,7 @@
static int node_leaf_finish(struct squat_trie *trie, struct trie_node *node)
{
uint32_t *idx8 = (uint32_t *)NODE_CHILDREN8(node);
- uint32_t *idx16 = (uint32_t *)NODE_CHILDREN16(node);
+ uint32_t *idx16 = (uint32_t *)NODE_CHILDREN16(node, BLOCK_SIZE);
unsigned int i;
for (i = 0; i < node->chars_8bit_count; i++) {
@@ -1272,9 +1293,9 @@
static void node_pack_leaf(buffer_t *buf, struct trie_node *node)
{
uint8_t *chars8 = NODE_CHARS8(node);
- uint16_t *chars16 = NODE_CHARS16(node);
+ uint16_t *chars16 = NODE_CHARS16(node, BLOCK_SIZE);
uint32_t *idx8 = (uint32_t *)NODE_CHILDREN8(node);
- uint32_t *idx16 = (uint32_t *)NODE_CHILDREN16(node);
+ uint32_t *idx16 = (uint32_t *)NODE_CHILDREN16(node, BLOCK_SIZE);
buffer_set_used_size(buf, 0);
_squat_trie_pack_num(buf, (node->chars_8bit_count << 1) |
@@ -1317,7 +1338,7 @@
if (level < BLOCK_SIZE) {
struct trie_node **children8 = NODE_CHILDREN8(node);
- struct trie_node **children16 = NODE_CHILDREN16(node);
+ struct trie_node **children16 = NODE_CHILDREN16(node, level);
if (trie_write_node_children(ctx, level + 1,
children8,
@@ -1484,8 +1505,8 @@
static void squat_trie_compress_chars16(struct trie_node *node)
{
- uint16_t *chars = NODE_CHARS16(node);
- struct trie_node **child_src = NODE_CHILDREN16(node);
+ uint16_t *chars = NODE_CHARS16(node, 0);
+ struct trie_node **child_src = NODE_CHILDREN16(node, 0);
struct trie_node **child_dest;
unsigned int i, j, old_count;
@@ -1496,7 +1517,7 @@
}
node->chars_16bit_count = j;
- child_dest = NODE_CHILDREN16(node);
+ child_dest = NODE_CHILDREN16(node, 0);
for (i = j = 0; i < old_count; i++) {
if (child_src[i] != NULL)
@@ -1504,6 +1525,50 @@
}
}
+static void squat_trie_compress_leaf_chars8(struct trie_node *node)
+{
+ uint8_t *chars = NODE_CHARS8(node);
+ uint32_t *child_src = (uint32_t *)NODE_CHILDREN8(node);
+ uint32_t *child_dest;
+ unsigned int i, j, old_count;
+
+ old_count = node->chars_8bit_count;
+ for (i = j = 0; i < old_count; i++) {
+ if (child_src[i] != 0)
+ chars[j++] = chars[i];
+ }
+
+ node->chars_8bit_count = j;
+ child_dest = (uint32_t *)NODE_CHILDREN8(node);
+
+ for (i = j = 0; i < old_count; i++) {
+ if (child_src[i] != 0)
+ child_dest[j++] = child_src[i];
+ }
+}
+
+static void squat_trie_compress_leaf_chars16(struct trie_node *node)
+{
+ uint16_t *chars = NODE_CHARS16(node, BLOCK_SIZE);
+ uint32_t *child_src = (uint32_t *)NODE_CHILDREN16(node, BLOCK_SIZE);
+ uint32_t *child_dest;
+ unsigned int i, j, old_count;
+
+ old_count = node->chars_16bit_count;
+ for (i = j = 0; i < old_count; i++) {
+ if (child_src[i] != 0)
+ chars[j++] = chars[i];
+ }
+
+ node->chars_16bit_count = j;
+ child_dest = (uint32_t *)NODE_CHILDREN16(node, BLOCK_SIZE);
+
+ for (i = j = 0; i < old_count; i++) {
+ if (child_src[i] != 0)
+ child_dest[j++] = child_src[i];
+ }
+}
+
static int
squat_trie_compress_children(struct squat_trie_compress_context *ctx,
struct trie_node **children, unsigned int count,
@@ -1543,7 +1608,7 @@
struct trie_node *node)
{
uint32_t *idx8 = (uint32_t *)NODE_CHILDREN8(node);
- uint32_t *idx16 = (uint32_t *)NODE_CHILDREN16(node);
+ uint32_t *idx16 = (uint32_t *)NODE_CHILDREN16(node, BLOCK_SIZE);
unsigned int i;
int ret;
bool compress_chars = FALSE;
@@ -1558,7 +1623,7 @@
}
}
if (compress_chars) {
- squat_trie_compress_chars8(node);
+ squat_trie_compress_leaf_chars8(node);
compress_chars = FALSE;
}
for (i = 0; i < node->chars_16bit_count; i++) {
@@ -1571,7 +1636,7 @@
}
}
if (compress_chars) {
- squat_trie_compress_chars16(node);
+ squat_trie_compress_leaf_chars16(node);
node->chars_16bit_count = i;
}
return 0;
@@ -1598,7 +1663,7 @@
node_pack_leaf(trie->buf, node);
} else {
struct trie_node **children8 = NODE_CHILDREN8(node);
- struct trie_node **children16 = NODE_CHILDREN16(node);
+ struct trie_node **children16 = NODE_CHILDREN16(node, 0);
if ((ret = squat_trie_compress_children(ctx, children8,
node->chars_8bit_count,
More information about the dovecot-cvs
mailing list