[前][次][番号順一覧][スレッド一覧]

ruby-changes:22260

From: shyouhei <ko1@a...>
Date: Mon, 16 Jan 2012 00:47:02 +0900 (JST)
Subject: [ruby-changes:22260] shyouhei:r34309 (trunk): st use function instead of macro

shyouhei	2012-01-16 00:46:30 +0900 (Mon, 16 Jan 2012)

  New Revision: 34309

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=34309

  Log:
    st use function instead of macro

  Modified files:
    trunk/st.c

Index: st.c
===================================================================
--- st.c	(revision 34308)
+++ st.c	(revision 34309)
@@ -86,7 +86,7 @@
 Table of prime numbers 2^n+a, 2<=n<=30.
 */
 static const unsigned int primes[] = {
-	8 + 3,
+	ST_DEFAULT_INIT_TABLE_SIZE,
 	16 + 3,
 	32 + 5,
 	64 + 3,
@@ -307,40 +307,48 @@
 #define FOUND_ENTRY
 #endif
 
-#define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
-    (bin_pos) = (hash_val)%(table)->num_bins;\
-    (ptr) = (table)->bins[(bin_pos)];\
-    FOUND_ENTRY;\
-    if (PTR_NOT_EQUAL((table), (ptr), (hash_val), key)) {\
-	COLLISION;\
-	while (PTR_NOT_EQUAL((table), (ptr)->next, (hash_val), key)) {\
-	    (ptr) = (ptr)->next;\
-	}\
-	(ptr) = (ptr)->next;\
-    }\
-} while (0)
+static st_table_entry *
+find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_pos)
+{
+    register st_table_entry *ptr = table->bins[bin_pos];
+    FOUND_ENTRY;
+    if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {
+	COLLISION;
+	while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {
+	    ptr = ptr->next;
+	}
+	ptr = ptr->next;
+    }
+    return ptr;
+}
 
+static inline st_index_t
+find_packed_index(st_table *table, st_data_t key)
+{
+    st_index_t i = 0;
+    while (i < table->num_entries && (st_data_t)table->bins[i*2] != key) i++;
+    return i;
+}
+
 #define collision_check 0
 
 int
 st_lookup(st_table *table, register st_data_t key, st_data_t *value)
 {
-    st_index_t hash_val, bin_pos;
+    st_index_t hash_val;
     register st_table_entry *ptr;
 
     if (table->entries_packed) {
-        st_index_t i;
-        for (i = 0; i < table->num_entries; i++) {
-            if ((st_data_t)table->bins[i*2] == key) {
-                if (value !=0) *value = (st_data_t)table->bins[i*2+1];
-                return 1;
-            }
-        }
+        st_index_t i = find_packed_index(table, key);
+	if (i < table->num_entries) {
+	    if (value != 0) *value = (st_data_t)table->bins[i*2+1];
+	    return 1;
+	}
         return 0;
     }
 
     hash_val = do_hash(key, table);
-    FIND_ENTRY(table, ptr, hash_val, bin_pos);
+    ptr = find_entry(table, key, hash_val, hash_val % table->num_bins);
 
     if (ptr == 0) {
 	return 0;
@@ -354,22 +362,20 @@
 int
 st_get_key(st_table *table, register st_data_t key, st_data_t *result)
 {
-    st_index_t hash_val, bin_pos;
+    st_index_t hash_val;
     register st_table_entry *ptr;
 
     if (table->entries_packed) {
-        st_index_t i;
-        for (i = 0; i < table->num_entries; i++) {
-            if ((st_data_t)table->bins[i*2] == key) {
-                if (result !=0) *result = (st_data_t)table->bins[i*2];
-                return 1;
-            }
-        }
+        st_index_t i = find_packed_index(table, key);
+	if (i < table->num_entries) {
+	    if (result != 0) *result = (st_data_t)table->bins[i*2];
+	    return 1;
+	}
         return 0;
     }
 
     hash_val = do_hash(key, table);
-    FIND_ENTRY(table, ptr, hash_val, bin_pos);
+    ptr = find_entry(table, key, hash_val, hash_val % table->num_bins);
 
     if (ptr == 0) {
 	return 0;
@@ -387,33 +393,35 @@
     ((st_index_t)((table)->num_entries+1) * 2 <= (table)->num_bins && \
      (table)->num_entries+1 <= MAX_PACKED_NUMHASH)
 
-#define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
-do {\
-    st_table_entry *entry;\
-    if ((table)->num_entries > ST_DEFAULT_MAX_DENSITY * (table)->num_bins) {\
-	rehash(table);\
-        (bin_pos) = (hash_val) % (table)->num_bins;\
-    }\
-    \
-    entry = alloc(st_table_entry);\
-    \
-    entry->hash = (hash_val);\
-    entry->key = (key);\
-    entry->record = (value);\
-    entry->next = (table)->bins[(bin_pos)];\
-    if ((table)->head != 0) {\
-	entry->fore = 0;\
-	(entry->back = (table)->tail)->fore = entry;\
-	(table)->tail = entry;\
-    }\
-    else {\
-	(table)->head = (table)->tail = entry;\
-	entry->fore = entry->back = 0;\
-    }\
-    (table)->bins[(bin_pos)] = entry;\
-    (table)->num_entries++;\
-} while (0)
+static void
+add_direct(st_table * table, st_data_t key, st_data_t value,
+	st_index_t hash_val, st_index_t bin_pos)
+{
+    st_table_entry *entry;
+    if (table->num_entries > ST_DEFAULT_MAX_DENSITY * table->num_bins) {
+	rehash(table);
+        bin_pos = hash_val % table->num_bins;
+    }
 
+    entry = alloc(st_table_entry);
+
+    entry->hash = hash_val;
+    entry->key = key;
+    entry->record = value;
+    entry->next = table->bins[bin_pos];
+    if (table->head != 0) {
+	entry->fore = 0;
+	(entry->back = table->tail)->fore = entry;
+	table->tail = entry;
+    }
+    else {
+	table->head = table->tail = entry;
+	entry->fore = entry->back = 0;
+    }
+    table->bins[bin_pos] = entry;
+    table->num_entries++;
+}
+
 static void
 unpack_entries(register st_table *table)
 {
@@ -432,6 +440,23 @@
     *table = tmp_table;
 }
 
+static int
+add_packed_direct(st_table *table, st_data_t key, st_data_t value)
+{
+    int res = 1;
+    if (MORE_PACKABLE_P(table)) {
+	st_index_t i = table->num_entries++;
+	table->bins[i*2] = (struct st_table_entry*)key;
+	table->bins[i*2+1] = (struct st_table_entry*)value;
+    }
+    else {
+	unpack_entries(table);
+	res = 0;
+    }
+    return res;
+}
+
+
 int
 st_insert(register st_table *table, register st_data_t key, st_data_t value)
 {
@@ -439,29 +464,22 @@
     register st_table_entry *ptr;
 
     if (table->entries_packed) {
-        st_index_t i;
-        for (i = 0; i < table->num_entries; i++) {
-            if ((st_data_t)table->bins[i*2] == key) {
-                table->bins[i*2+1] = (struct st_table_entry*)value;
-                return 1;
-            }
+        st_index_t i = find_packed_index(table, key);
+	if (i < table->num_entries) {
+	    table->bins[i*2+1] = (struct st_table_entry*)value;
+	    return 1;
         }
-        if (MORE_PACKABLE_P(table)) {
-            i = table->num_entries++;
-            table->bins[i*2] = (struct st_table_entry*)key;
-            table->bins[i*2+1] = (struct st_table_entry*)value;
-            return 0;
-        }
-        else {
-            unpack_entries(table);
-        }
+	if (add_packed_direct(table, key, value)) {
+	    return 0;
+	}
     }
 
     hash_val = do_hash(key, table);
-    FIND_ENTRY(table, ptr, hash_val, bin_pos);
+    bin_pos = hash_val % table->num_bins;
+    ptr = find_entry(table, key, hash_val, bin_pos);
 
     if (ptr == 0) {
-	ADD_DIRECT(table, key, value, hash_val, bin_pos);
+	add_direct(table, key, value, hash_val, bin_pos);
 	return 0;
     }
     else {
@@ -478,30 +496,23 @@
     register st_table_entry *ptr;
 
     if (table->entries_packed) {
-        st_index_t i;
-        for (i = 0; i < table->num_entries; i++) {
-            if ((st_data_t)table->bins[i*2] == key) {
-                table->bins[i*2+1] = (struct st_table_entry*)value;
-                return 1;
-            }
+        st_index_t i = find_packed_index(table, key);
+	if (i < table->num_entries) {
+	    table->bins[i*2+1] = (struct st_table_entry*)value;
+	    return 1;
         }
-        if (MORE_PACKABLE_P(table)) {
-            i = table->num_entries++;
-            table->bins[i*2] = (struct st_table_entry*)key;
-            table->bins[i*2+1] = (struct st_table_entry*)value;
-            return 0;
-        }
-        else {
-            unpack_entries(table);
-        }
+	if (add_packed_direct(table, key, value)) {
+	    return 0;
+	}
     }
 
     hash_val = do_hash(key, table);
-    FIND_ENTRY(table, ptr, hash_val, bin_pos);
+    bin_pos = hash_val % table->num_bins;
+    ptr = find_entry(table, key, hash_val, bin_pos);
 
     if (ptr == 0) {
 	key = (*func)(key);
-	ADD_DIRECT(table, key, value, hash_val, bin_pos);
+	add_direct(table, key, value, hash_val, bin_pos);
 	return 0;
     }
     else {
@@ -516,21 +527,14 @@
     st_index_t hash_val, bin_pos;
 
     if (table->entries_packed) {
-        int i;
-        if (MORE_PACKABLE_P(table)) {
-            i = table->num_entries++;
-            table->bins[i*2] = (struct st_table_entry*)key;
-            table->bins[i*2+1] = (struct st_table_entry*)value;
-            return;
-        }
-        else {
-            unpack_entries(table);
-        }
+	if (add_packed_direct(table, key, value)) {
+	    return;
+	}
     }
 
     hash_val = do_hash(key, table);
     bin_pos = hash_val % table->num_bins;
-    ADD_DIRECT(table, key, value, hash_val, bin_pos);
+    add_direct(table, key, value, hash_val, bin_pos);
 }
 
 static void
@@ -605,22 +609,33 @@
     return new_table;
 }
 
-#define REMOVE_ENTRY(table, ptr) do					\
-    {									\
-	if ((ptr)->fore == 0 && (ptr)->back == 0) {			\
-	    (table)->head = 0;						\
-	    (table)->tail = 0;						\
-	}								\
-	else {								\
-	    st_table_entry *fore = (ptr)->fore, *back = (ptr)->back;	\
-	    if (fore) fore->back = back;				\
-	    if (back) back->fore = fore;				\
-	    if ((ptr) == (table)->head) (table)->head = fore;		\
-	    if ((ptr) == (table)->tail) (table)->tail = back;		\
-	}								\
-	(table)->num_entries--;						\
-    } while (0)
+static inline void
+remove_entry(st_table *table, st_table_entry *ptr)
+{
+    if (ptr->fore == 0 && ptr->back == 0) {
+	table->head = 0;
+	table->tail = 0;
+    }
+    else {
+	st_table_entry *fore = ptr->fore, *back = ptr->back;
+	if (fore) fore->back = back;
+	if (back) back->fore = fore;
+	if (ptr == table->head) table->head = fore;
+	if (ptr == table->tail) table->tail = back;
+    }
+    table->num_entries--;
+}
 
+static inline void
+remove_packed_entry(st_table *table, st_index_t pos)
+{
+    table->num_entries--;
+    if (pos < table->num_entries) {
+	memmove(&table->bins[pos*2], &table->bins[(pos+1)*2],
+		sizeof(struct st_table_entry*) * 2*(table->num_entries-pos));
+    }
+}
+
 int
 st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
 {
@@ -629,15 +644,11 @@
     register st_table_entry *ptr;
 
     if (table->entries_packed) {
-        st_index_t i;
-        for (i = 0; i < table->num_entries; i++) {
-            if ((st_data_t)table->bins[i*2] == *key) {
-                if (value != 0) *value = (st_data_t)table->bins[i*2+1];
-                table->num_entries--;
-                memmove(&table->bins[i*2], &table->bins[(i+1)*2],
-                        sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
-                return 1;
-            }
+        st_index_t i = find_packed_index(table, *key);
+	if (i < table->num_entries) {
+	    if (value != 0) *value = (st_data_t)table->bins[i*2+1];
+	    remove_packed_entry(table, i);
+	    return 1;
         }
         if (value != 0) *value = 0;
         return 0;
@@ -648,7 +659,7 @@
     for (prev = &table->bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->next) {
 	if (EQUAL(table, *key, ptr->key)) {
 	    *prev = ptr->next;
-	    REMOVE_ENTRY(table, ptr);
+	    remove_entry(table, ptr);
 	    if (value != 0) *value = ptr->record;
 	    *key = ptr->key;
 	    free(ptr);
@@ -667,13 +678,11 @@
     register st_table_entry *ptr;
 
     if (table->entries_packed) {
-	st_index_t i;
-	for (i = 0; i < table->num_entries; i++) {
-	    if ((st_data_t)table->bins[i*2] == *key) {
-		if (value != 0) *value = (st_data_t)table->bins[i*2+1];
-		table->bins[i*2] = (void *)never;
-		return 1;
-	    }
+        st_index_t i = find_packed_index(table, *key);
+	if (i < table->num_entries) {
+	    if (value != 0) *value = (st_data_t)table->bins[i*2+1];
+	    table->bins[i*2] = (void *)never;
+	    return 1;
 	}
 	if (value != 0) *value = 0;
 	return 0;
@@ -684,7 +693,7 @@
 
     for (; ptr != 0; ptr = ptr->next) {
 	if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
-	    REMOVE_ENTRY(table, ptr);
+	    remove_entry(table, ptr);
 	    *key = ptr->key;
 	    if (value != 0) *value = ptr->record;
 	    ptr->key = ptr->record = never;
@@ -740,27 +749,24 @@
     st_data_t value;
 
     if (table->entries_packed) {
-	st_index_t i;
-	for (i = 0; i < table->num_entries; i++) {
-	    if ((st_data_t)table->bins[i*2] == key) {
-		value = (st_data_t)table->bins[i*2+1];
-		switch ((*func)(key, &value, arg)) {
-		  case ST_CONTINUE:
-		    table->bins[i*2+1] = (struct st_table_entry*)value;
-		    break;
-		  case ST_DELETE:
-		    table->num_entries--;
-		    memmove(&table->bins[i*2], &table->bins[(i+1)*2],
-			    sizeof(struct st_table_entry*) * 2 * (table->num_entries-i));
-		}
-		return 1;
+	st_index_t i = find_packed_index(table, key);
+	if (i < table->num_entries) {
+	    value = (st_data_t)table->bins[i*2+1];
+	    switch ((*func)(key, &value, arg)) {
+	      case ST_CONTINUE:
+		table->bins[i*2+1] = (struct st_table_entry*)value;
+		break;
+	      case ST_DELETE:
+		remove_packed_entry(table, i);
 	    }
+	    return 1;
 	}
 	return 0;
     }
 
     hash_val = do_hash(key, table);
-    FIND_ENTRY(table, ptr, hash_val, bin_pos);
+    bin_pos = hash_val % table->num_bins;
+    ptr = find_entry(table, key, hash_val, bin_pos);
 
     if (ptr == 0) {
 	return 0;
@@ -777,7 +783,7 @@
 		if (ptr == tmp) {
 		    tmp = ptr->fore;
 		    *last = ptr->next;
-		    REMOVE_ENTRY(table, ptr);
+		    remove_entry(table, ptr);
 		    free(ptr);
 		    break;
 		}
@@ -820,9 +826,7 @@
 	      case ST_STOP:
 		return 0;
 	      case ST_DELETE:
-                table->num_entries--;
-                memmove(&table->bins[i*2], &table->bins[(i+1)*2],
-                        sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
+		remove_packed_entry(table, i);
                 i--;
                 break;
             }
@@ -863,7 +867,7 @@
 		    if (ptr == tmp) {
 			tmp = ptr->fore;
 			*last = ptr->next;
-			REMOVE_ENTRY(table, ptr);
+			remove_entry(table, ptr);
 			free(ptr);
 			if (ptr == tmp) return 0;
 			ptr = tmp;
@@ -908,9 +912,7 @@
 	      case ST_STOP:
 		return 0;
 	      case ST_DELETE:
-                table->num_entries--;
-                memmove(&table->bins[i*2], &table->bins[(i+1)*2],
-                        sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
+		remove_packed_entry(table, i);
                 break;
             }
         }
@@ -943,7 +945,7 @@
 		    if (ptr == tmp) {
 			tmp = ptr->back;
 			*last = ptr->next;
-			REMOVE_ENTRY(table, ptr);
+			remove_entry(table, ptr);
 			free(ptr);
 			ptr = tmp;
 			break;

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/

[前][次][番号順一覧][スレッド一覧]