+
+
+
+//
+// String ref routines
+//
+static LIST_HEAD(stringhead, string_t) *string_ref_table;
+static u_long string_table_mask;
+static uint32_t max_chain_len=0;
+static struct stringhead *long_chain_head=NULL;
+static uint32_t filled_buckets=0;
+static uint32_t num_dups=0;
+static uint32_t nstrings=0;
+
+typedef struct string_t {
+ LIST_ENTRY(string_t) hash_chain;
+ unsigned char *str;
+ uint32_t refcount;
+} string_t;
+
+
+
+static int
+resize_string_ref_table()
+{
+ struct stringhead *new_table;
+ struct stringhead *old_table;
+ struct stringhead *old_head, *head;
+ string_t *entry, *next;
+ uint32_t i, hashval;
+ u_long new_mask, old_mask;
+
+ new_table = hashinit((string_table_mask + 1) * 2, M_CACHE, &new_mask);
+ if (new_table == NULL) {
+ return ENOMEM;
+ }
+
+ // do the switch!
+ old_table = string_ref_table;
+ string_ref_table = new_table;
+ old_mask = string_table_mask;
+ string_table_mask = new_mask;
+
+ printf("resize: max chain len %d, new table size %d\n",
+ max_chain_len, new_mask + 1);
+ max_chain_len = 0;
+ long_chain_head = NULL;
+ filled_buckets = 0;
+
+ // walk the old table and insert all the entries into
+ // the new table
+ //
+ for(i=0; i <= old_mask; i++) {
+ old_head = &old_table[i];
+ for (entry=old_head->lh_first; entry != NULL; entry=next) {
+ hashval = hash_string(entry->str, 0);
+ head = &string_ref_table[hashval & string_table_mask];
+ if (head->lh_first == NULL) {
+ filled_buckets++;
+ }
+
+ next = entry->hash_chain.le_next;
+ LIST_INSERT_HEAD(head, entry, hash_chain);
+ }
+ }
+
+ FREE(old_table, M_CACHE);
+
+ return 0;
+}
+
+
+static void
+init_string_table(void)
+{
+ string_ref_table = hashinit(4096, M_CACHE, &string_table_mask);
+}
+
+
+char *
+add_name(const char *name, size_t len, u_int hashval, u_int flags)
+{
+ struct stringhead *head;
+ string_t *entry;
+ int chain_len = 0;
+
+ //
+ // If the table gets more than 3/4 full, resize it
+ //
+ if (4*filled_buckets >= ((string_table_mask + 1) * 3)) {
+ if (resize_string_ref_table() != 0) {
+ printf("failed to resize the hash table.\n");
+ }
+ }
+
+ if (hashval == 0) {
+ hashval = hash_string(name, len);
+ }
+
+ head = &string_ref_table[hashval & string_table_mask];
+ for (entry=head->lh_first; entry != NULL; chain_len++, entry=entry->hash_chain.le_next) {
+ if (strncmp(entry->str, name, len) == 0 && entry->str[len] == '\0') {
+ entry->refcount++;
+ num_dups++;
+ break;
+ }
+ }
+
+ if (entry == NULL) {
+ // it wasn't already there so add it.
+ MALLOC(entry, string_t *, sizeof(string_t) + len + 1, M_TEMP, M_WAITOK);
+
+ // have to get "head" again because we could have blocked
+ // in malloc and thus head could have changed.
+ //
+ head = &string_ref_table[hashval & string_table_mask];
+ if (head->lh_first == NULL) {
+ filled_buckets++;
+ }
+
+ LIST_INSERT_HEAD(head, entry, hash_chain);
+ entry->str = (char *)((char *)entry + sizeof(string_t));
+ strncpy(entry->str, name, len);
+ entry->str[len] = '\0';
+ entry->refcount = 1;
+
+ if (chain_len > max_chain_len) {
+ max_chain_len = chain_len;
+ long_chain_head = head;
+ }
+
+ nstrings++;
+ }
+
+ return entry->str;
+}
+
+int
+remove_name(const char *nameref)
+{
+ struct stringhead *head;
+ string_t *entry;
+ uint32_t hashval;
+
+ hashval = hash_string(nameref, 0);
+ head = &string_ref_table[hashval & string_table_mask];
+ for (entry=head->lh_first; entry != NULL; entry=entry->hash_chain.le_next) {
+ if (entry->str == (unsigned char *)nameref) {
+ entry->refcount--;
+ if (entry->refcount == 0) {
+ LIST_REMOVE(entry, hash_chain);
+ if (head->lh_first == NULL) {
+ filled_buckets--;
+ }
+ entry->str = NULL;
+ nstrings--;
+
+ FREE(entry, M_TEMP);
+ } else {
+ num_dups--;
+ }
+
+ return 0;
+ }
+ }
+
+ return ENOENT;
+}
+
+
+void
+dump_string_table(void)
+{
+ struct stringhead *head;
+ string_t *entry;
+ int i;
+
+ for(i=0; i <= string_table_mask; i++) {
+ head = &string_ref_table[i];
+ for (entry=head->lh_first; entry != NULL; entry=entry->hash_chain.le_next) {
+ printf("%6d - %s\n", entry->refcount, entry->str);
+ }
+ }
+}
projects / apple / xnu.git / blobdiff