fork download 
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include <stdio.h>
  4. typedef unsigned long long type_key;
  5. typedef struct value {
  6.   unsigned int values[10];
  7. } type_value;
  8. typedef struct entry {
  9.   type_key key;
  10.   type_value value;
  11. } type_entry;
  12. typedef unsigned int type_index;
  13. typedef struct table {
  14.   type_index bin_power, entry_power, n_entries, *bins;
  15.   type_entry *entries;
  16. } type_table;
  17. static inline type_index value_cap(type_value *value) {
  18.   return sizeof value->values / sizeof *value->values;
  19. }
  20. static inline type_index value_size(type_value *value) {
  21.   type_index i, size = value_cap(value);
  22.   for (i = 0; i < size && value->values[i]; i++);
  23.   return i;
  24. }
  25. void value_inspect_values(type_value *value) {
  26.   type_index i, cap = value_cap(value);
  27.   putchar('[');
  28.   for (i = 0; i < cap; i += 2) {
  29.     if (0 < i) printf(", ");
  30.     printf("[%u, %u]", value->values[i], value->values[i + 1]);
  31.   }
  32.   putchar(']');
  33. }
  34. void value_inspect(type_value *value) {
  35.   printf("value {cap: %u, size: %u, values: ", value_cap(value), value_size(value));
  36.   value_inspect_values(value);
  37.   puts("}");
  38. }
  39. static inline void value_append(type_value *value, unsigned int a, unsigned int b) {
  40.   type_index i, cap = value_cap(value), size = value_size(value);
  41.   if (size < cap)
  42.     value->values[size] = a, value->values[size + 1] = b;
  43.   else
  44.     fprintf(stderr, "value cap: %u, required: %u\n", cap, cap + 2), exit(EXIT_FAILURE);
  45. }
  46. static inline type_index bins_cap(type_table *table) {
  47.   return (type_index)1 << table->bin_power;
  48. }
  49. static inline type_index entries_cap(type_table *table) {
  50.   return (type_index)1 << table->entry_power;
  51. }
  52. static inline size_t bins_n_bytes(type_table *table) {
  53.   return sizeof *table->bins * bins_cap(table);
  54. }
  55. static inline size_t entries_n_bytes(type_table *table) {
  56.   return sizeof *table->entries * entries_cap(table);
  57. }
  58. void inspect_bins(type_table *table) {
  59.   for (size_t i = 0; i < bins_cap(table); i++)
  60.     printf("bs[%d]: %u\n", i, table->bins[i]);
  61. }
  62. void table_inspect(type_table *table) {
  63.   printf("table: %p\n", table);
  64.   printf("bin_power: %u\n", table->bin_power);
  65.   printf("entry_power: %u\n", table->entry_power);
  66.   printf("n_entries: %u\n", table->n_entries);
  67.   printf("bins: %p\n", table->bins);
  68.   printf("entries: %p\n", table->entries);
  69.   printf("bins_cap: %p %d\n", bins_cap(table), bins_cap(table));
  70.   printf("entries_cap: %p %d\n", entries_cap(table), entries_cap(table));
  71. }
  72. type_table *table_new(type_index bin_power, type_index entry_power) {
  73.   type_table *table = malloc(sizeof (type_table));
  74.   table->bin_power = bin_power;
  75.   table->entry_power = entry_power;
  76.   table->n_entries = 0;
  77.   table->bins = malloc(bins_n_bytes(table));
  78.   table->entries = malloc(entries_n_bytes(table));
  79.   memset(table->bins, 0, bins_n_bytes(table));
  80.   if (!table || !table->bins || !table->entries)
  81.     fprintf(stderr, "table_new: out of memory\n"), exit(EXIT_FAILURE);
  82.   return table;
  83. }
  84. void table_free(type_table *table) {
  85.   free(table->bins), free(table->entries), free(table);
  86. }
  87. static inline type_index calc_bin_index(type_table *table, type_key key) {
  88.   return (bins_cap(table) - 1) & key;
  89. }
  90. static inline type_index find_bin_index(type_table *table, type_key key) {
  91.   type_index found = calc_bin_index(table, key);
  92.   type_index collision = 0;
  93.   type_index borderline = bins_cap(table) - 1;
  94.   type_index *bins = table->bins;
  95.   type_entry *entries = table->entries;
  96.   while (bins[found] && entries[bins[found]].key != key) {
  97.     collision++;
  98.     if (borderline < collision)
  99.       fprintf(stderr, "borderline: %u, collision: %u\n", borderline, collision), exit(EXIT_FAILURE);
  100.     else
  101.       found = calc_bin_index(table, found + 1);
  102.   }
  103.   return found;
  104. }
  105. static inline void table_put_at(type_table *table, type_key key, type_value value, type_index bin_index) {
  106.   type_index borderline = entries_cap(table) - 1;
  107.   type_index *bins = table->bins;
  108.   type_entry *entries = table->entries;
  109.   if (!bins[bin_index]) {
  110.     // bins[x] == 0はビンが未使用という表現。そのため entries[0] は欠番。最初のデータは entries[1] に入る。
  111.     if (borderline < table->n_entries + 1)
  112.       fprintf(stderr, "borderline: %u, (table->n_entries + 1): %u\n", borderline, table->n_entries + 1), exit(EXIT_FAILURE);
  113.     table->n_entries++;
  114.     bins[bin_index] = table->n_entries;
  115.     entries[bins[bin_index]].key = key;
  116.     entries[bins[bin_index]].value = value;
  117.   } else {
  118.     // 既存のエントリに上書き。
  119.     entries[bins[bin_index]].key = key;
  120.     entries[bins[bin_index]].value = value;
  121.   }
  122. }
  123. void table_put(type_table *table, type_key key, type_value value) {
  124.   return table_put_at(table, key, value, find_bin_index(table, key));
  125. }
  126. static inline type_value *table_get_at(type_table *table, type_index bin_index) {
  127.   type_index *bins = table->bins;
  128.   type_entry *entries = table->entries;
  129.   return !bins[bin_index] ? 0 : &entries[bins[bin_index]].value;
  130. }
  131. type_value *table_get(type_table *table, type_key key) {
  132.   return table_get_at(table, find_bin_index(table, key));
  133. }
  134. int table_contains_key(type_table *table, type_key key) {
  135.   return !!table_get(table, key);
  136. }
  137. type_index table_size(type_table *table) {
  138.   return table->n_entries;
  139. }
  140. type_value f(unsigned m) {
  141.   type_table *table = table_new(27, 24);
  142.   type_value *value = 0, found;
  143.   type_index index;
  144.   type_key a, b, c;
  145.   for (a = 1; ; a++) {
  146.     for (b = 1; b < a; b++) {
  147.       c = a * a * a - b * b * b;
  148.       index = find_bin_index(table, c);
  149.       value = table_get_at(table, index);
  150.       if (value) 
  151.         value_append(value, a, b);
  152.       else 
  153.         table_put_at(table, c, (type_value){a, b}, index);
  154.  
  155.       if (value && value_size(value) == m * 2) 
  156.         goto finally;
  157.     }
  158.   }
  159.  finally:
  160.   found = *value;
  161.   table_free(table);
  162.   return found;
  163. }
  164. int main() {
  165.   type_value value = f(5);
  166.   value_inspect_values(&value);
  167.   return 0;
  168. }
  169.  
Success #stdin #stdout 0.49s 1054084KB
comments (?)
stdin 
Standard input is empty
stdout 
[[1134, 357], [1155, 504], [1246, 805], [2115, 2004], [4746, 4725]]
https://ideone.com/eM18H1
language:
C (clang 8.0)
created:
83 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!