From d1f78c88faafea7e672c7c45e20f6f040942a92a Mon Sep 17 00:00:00 2001 From: Joshua Haberman Date: Wed, 3 Jun 2009 22:06:24 -0700 Subject: A bunch more work, a fast table for field lookup. --- upb_table.h | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 75 insertions(+) create mode 100644 upb_table.h (limited to 'upb_table.h') diff --git a/upb_table.h b/upb_table.h new file mode 100644 index 0000000..684dbff --- /dev/null +++ b/upb_table.h @@ -0,0 +1,75 @@ +/* + * upb - a minimalist implementation of protocol buffers. + * + * Copyright (c) 2009 Joshua Haberman. See LICENSE for details. + */ + +#ifndef UPB_TABLE_H_ +#define UPB_TABLE_H_ + +#include "upb.h" + +#ifdef __cplusplus +extern "C" { +#endif + +typedef int32_t upb_inttable_key_t; + +#define UPB_END_OF_CHAIN (upb_inttable_key_t)-1 + +struct upb_inttable_entry { + upb_inttable_key_t key; + int32_t next; +}; + +struct upb_inttable { + uint32_t size; /* Is a power of two. */ + void *entries; +}; + +/* Builds an int32_t -> table, optimized for very fast lookup by + * number. table is a pointer to a previously allocated upb_inttable. + * entries points to an array of the desired entries themselves, each of size + * entry_size. The table is allocated in dynamic memory, and does not reference + * the data in entries. Entries may be modified by the function. + * + * The table must be freed with upb_inttable_free. */ +void upb_inttable_init(struct upb_inttable *table, void *entries, + int num_entries, int entry_size); + +inline int32_t upb_inttable_hash(struct upb_inttable * table, + upb_inttable_key_t key) { + return key & (table->size-1); +} + +/* Frees any data that was allocated by upb_inttable_init. */ +void upb_inttable_free(struct upb_inttable *table); + +inline struct upb_inttable_entry *upb_inttable_entry_get( + void *entries, int32_t pos, int entry_size) { + return (struct upb_inttable_entry*)((char*)entries) + pos*entry_size; +} + +inline struct upb_inttable_entry *upb_inttable_get( + struct upb_inttable *table, int32_t pos, int entry_size) { + return upb_inttable_entry_get(table->entries, pos, entry_size); +} + +/* Lookups up key in this table. Inlined because this is in the critical path + * of parsing. */ +inline void *upb_inttable_lookup(struct upb_inttable *table, int32_t key, + int entry_size) { + int32_t pos = upb_inttable_hash(table, key); + do { + struct upb_inttable_entry *e = upb_inttable_get(table, pos, entry_size); + if (key == e->key) return e; + pos = e->next; + } while (pos != UPB_END_OF_CHAIN); + return NULL; /* Not found. */ +} + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* UPB_TABLE_H_ */ -- cgit v1.2.3