User:Ledrug/bits: Difference between revisions
mNo edit summary |
mNo edit summary |
||
Line 1: | Line 1: | ||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
#include <stdlib.h> |
|||
#include <stdint.h> |
|||
#include <string.h> |
#include <string.h> |
||
typedef uint32_t hash_t; |
|||
int b = 99, u = 1; |
|||
char *d[16], y[] = "#:ottle/ of:eer_ a_Go<o5st>y some6_Take8;do" |
|||
"wn4pa=1rou7_17 _<h;_ m?_nd_ on_085wall_ b_e _" |
|||
" t_ss it_?4bu_ore_9, 0.@, 9$"; |
|||
#define eq == |
|||
#define ne =! |
|||
#define xor ^= |
|||
#define nz(x) !(x=0) |
|||
#define or(x, z) else if (c eq x && nz(c) &&(c ne z)); |
|||
int p(char *x) |
|||
{ |
|||
char *s = x; |
|||
unsigned char c; |
|||
for (d[c=0]=y; !x && (d[c+1] = strchr(s=d[c], '_')); *(d[++c]++)=0); |
|||
typedef struct hash_value_t { |
|||
for (x = s?:x; (c = *s++); c?putchar(c):0) { |
|||
void *data; |
|||
if (!(((c xor 48) & ~0xf) &&(c xor 48))) p(d[c]), c = 0; |
|||
char *key; |
|||
or('$', p(b-99 ? ".\n":".") && p(b-99 ? x : "")) |
|||
struct hash_value_t *chain; |
|||
or('@', c && p(d[!!b--+2])) |
|||
} hash_value_t; |
|||
or('/', c && p(b^1?"s":"")) |
|||
or('#', b++ ? p("So6"+--b): !printf("%d", b?--b:(b += 99))) |
|||
typedef struct hash_table_t { |
|||
or('S', !(++u%3)*32 + 78) |
|||
hash_value_t **v, *pool; |
|||
or('.', puts(".")) |
|||
size_t n, cap; |
|||
} hash_table_t, *htbl; |
|||
inline hash_t hash(char *s) |
|||
{ |
|||
hash_t hash; |
|||
for (hash = 0; *s; s++) { |
|||
hash += *s; |
|||
hash += (hash << 10); |
|||
hash ^= (hash >> 6); |
|||
} |
} |
||
hash += hash << 3; |
|||
return c; |
|||
hash ^= hash >> 11; |
|||
hash += hash << 15; |
|||
return hash; |
|||
} |
} |
||
htbl hash_new(size_t size) |
|||
int main() |
|||
{ |
{ |
||
htbl h = calloc(1, sizeof(hash_table_t)); |
|||
return p(0); |
|||
if (!size) size = 4; |
|||
}</lang> |
|||
<lang c>#include <stdio.h> |
|||
#include <stdlib.h> |
|||
for (h->cap = 1; h->cap < size; h->cap <<= 1); |
|||
#define S 10 |
|||
typedef struct { double v; int fixed; } node; |
|||
h->v = calloc(h->cap, sizeof(hash_value_t*)); |
|||
h->pool = 0; |
|||
return h; |
|||
} |
|||
hash_value_t *hash_get_storage(htbl t) |
|||
#define each(i, x) for(i = 0; i < x; i++) |
|||
node **alloc2(int w, int h) |
|||
{ |
{ |
||
size_t len; |
|||
hash_value_t *p = t->pool; |
|||
node **a = calloc(1, sizeof(node*)*h + sizeof(node)*w*h); |
|||
if (!p) { |
|||
len = 1024; |
|||
each(i, h) if (i) a[i] = a[i-1] + w; |
|||
if (len > t->cap) len = t->cap; |
|||
return a; |
|||
t->pool = calloc(len, sizeof(hash_value_t)); |
|||
for (p = t->pool; len > 1; len --) |
|||
p->chain = p + 1; |
|||
p = t->pool; |
|||
} |
|||
t->pool = p->chain; |
|||
return p; |
|||
} |
} |
||
void hash_insert_node(htbl t, hash_value_t *p) |
|||
void set_boundary(node **m) |
|||
{ |
{ |
||
size_t idx = hash(p->key) % t->cap; |
|||
m[1][1].fixed = 1; m[1][1].v = 1; |
|||
p->chain = t->v[idx]; |
|||
t->v[idx] = p; |
|||
} |
} |
||
void hash_expand(htbl t) |
|||
double calc_diff(node **m, node **d, int w, int h) |
|||
{ |
{ |
||
size_t i, c = t->cap; |
|||
hash_value_t *p, *tmp; |
|||
double v, total = 0; |
|||
each(i, h) each(j, w) { |
|||
v = 0; n = 0; |
|||
if (i) v += m[i-1][j].v, n++; |
|||
if (j) v += m[i][j-1].v, n++; |
|||
if (i+1 < h) v += m[i+1][j].v, n++; |
|||
if (j+1 < w) v += m[i][j+1].v, n++; |
|||
t->v = realloc(t->v, sizeof(hash_value_t*) * c * 2); |
|||
v = m[i][j].v - v / n; |
|||
memset(t->v + c, 0, c * sizeof(hash_table_t*)); |
|||
d[i][j].v = v; |
|||
if (!m[i][j].fixed) total += v * v; |
|||
t->cap *= 2; |
|||
for (i = 0; i < c; i++) { |
|||
p = t->v[i]; |
|||
if (!p) continue; |
|||
t->v[i] = 0; |
|||
while (p) { |
|||
tmp = p->chain; |
|||
p->chain = 0; |
|||
hash_insert_node(t, p); |
|||
p = tmp; |
|||
} |
|||
} |
} |
||
return total; |
|||
} |
} |
||
void hash_insert(htbl t, char *s, void *data) |
|||
{ |
{ |
||
hash_value_t *p = hash_get_storage(t); |
|||
if (t->n * 5 >= t->cap * 4) hash_expand(t); |
|||
int i, j; |
|||
p->key = strdup(s); |
|||
double diff = 1e10; |
|||
p->data = data; |
|||
while (diff > 1e-24) { |
|||
hash_insert_node(t, p); |
|||
set_boundary(m); |
|||
t->n ++; |
|||
diff = calc_diff(m, d, w, h); |
|||
} |
|||
each(i,h) each(j, w) m[i][j].v -= d[i][j].v; |
|||
void* hash_remove(htbl t, char *s) |
|||
{ |
|||
size_t idx = hash(s) % t->cap; |
|||
hash_value_t *head = 0, *p = t->v[idx]; |
|||
while (p) { |
|||
if (!strcmp(p->key, s)) break; |
|||
head = p; |
|||
p = p->chain; |
|||
} |
} |
||
if (!p) return 0; |
|||
free(p->key); |
|||
double cur[] = {0, 0, 0}; |
|||
each(i, h) each(j, w) |
|||
cur[ m[i][j].fixed + 1 ] += d[i][j].v * |
|||
(!!i + !!j + (i < h-1) + (j < w -1)); |
|||
if (head) head->chain = p->chain; |
|||
//char *name = "+g-"; |
|||
else t->v[idx] = p->chain; |
|||
//each(i, 3) printf("I%c = %g\n", name[i], current[i]); |
|||
free(d); |
|||
p->chain = t->pool; |
|||
return (cur[2] - cur[0])/2; |
|||
t->pool = p; |
|||
t->n--; |
|||
return p->data; |
|||
} |
} |
||
void* hash_lookup(htbl t, char *s) |
|||
int main() |
|||
{ |
{ |
||
size_t idx = hash(s) % t->cap; |
|||
hash_value_t *p; |
|||
printf("R = %g\n", 2 / iter(mesh, S, S)); |
|||
p = t->v[idx]; |
|||
// free(mesh); |
|||
while (p) { |
|||
return 0; |
|||
if (!strcmp(p->key, s)) return p->data; |
|||
p = p->chain; |
|||
} |
|||
return (void*)-1; |
|||
}</lang> |
}</lang> |
Revision as of 03:56, 31 August 2011
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <stdint.h>
- include <string.h>
typedef uint32_t hash_t;
typedef struct hash_value_t { void *data; char *key; struct hash_value_t *chain; } hash_value_t;
typedef struct hash_table_t { hash_value_t **v, *pool; size_t n, cap; } hash_table_t, *htbl;
inline hash_t hash(char *s) { hash_t hash; for (hash = 0; *s; s++) { hash += *s; hash += (hash << 10); hash ^= (hash >> 6); } hash += hash << 3; hash ^= hash >> 11; hash += hash << 15; return hash; }
htbl hash_new(size_t size) { htbl h = calloc(1, sizeof(hash_table_t)); if (!size) size = 4;
for (h->cap = 1; h->cap < size; h->cap <<= 1);
h->v = calloc(h->cap, sizeof(hash_value_t*)); h->pool = 0; return h; }
hash_value_t *hash_get_storage(htbl t) { size_t len; hash_value_t *p = t->pool; if (!p) { len = 1024; if (len > t->cap) len = t->cap; t->pool = calloc(len, sizeof(hash_value_t)); for (p = t->pool; len > 1; len --) p->chain = p + 1; p = t->pool; } t->pool = p->chain; return p; }
void hash_insert_node(htbl t, hash_value_t *p) { size_t idx = hash(p->key) % t->cap; p->chain = t->v[idx]; t->v[idx] = p; }
void hash_expand(htbl t) { size_t i, c = t->cap; hash_value_t *p, *tmp;
t->v = realloc(t->v, sizeof(hash_value_t*) * c * 2); memset(t->v + c, 0, c * sizeof(hash_table_t*));
t->cap *= 2; for (i = 0; i < c; i++) { p = t->v[i]; if (!p) continue;
t->v[i] = 0; while (p) { tmp = p->chain; p->chain = 0; hash_insert_node(t, p); p = tmp; } } }
void hash_insert(htbl t, char *s, void *data) { hash_value_t *p = hash_get_storage(t); if (t->n * 5 >= t->cap * 4) hash_expand(t); p->key = strdup(s); p->data = data; hash_insert_node(t, p); t->n ++; }
void* hash_remove(htbl t, char *s) { size_t idx = hash(s) % t->cap; hash_value_t *head = 0, *p = t->v[idx];
while (p) { if (!strcmp(p->key, s)) break; head = p; p = p->chain; } if (!p) return 0;
free(p->key);
if (head) head->chain = p->chain; else t->v[idx] = p->chain;
p->chain = t->pool; t->pool = p; t->n--; return p->data; }
void* hash_lookup(htbl t, char *s) { size_t idx = hash(s) % t->cap; hash_value_t *p; p = t->v[idx]; while (p) { if (!strcmp(p->key, s)) return p->data; p = p->chain; } return (void*)-1; }</lang>