1 files changed, 75 insertions, 0 deletions
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 -> <entry> 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_ */