diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/algo.cpp | 5 | ||||
| -rw-r--r-- | src/cube.h | 415 | ||||
| -rw-r--r-- | src/khash.h | 513 |
3 files changed, 933 insertions, 0 deletions
diff --git a/src/algo.cpp b/src/algo.cpp new file mode 100644 index 0000000..56ed646 --- /dev/null +++ b/src/algo.cpp @@ -0,0 +1,5 @@ +#include "cube.h" + +int main() { + printf("Hello, world!"); +} diff --git a/src/cube.h b/src/cube.h new file mode 100644 index 0000000..3ea20eb --- /dev/null +++ b/src/cube.h @@ -0,0 +1,415 @@ +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef _CUBE_H_ +#define _CUBE_H_ + +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> +#include <assert.h> +#include <unistd.h> + +#include "khash.h" + +#define FACE32 +// #define FACE64 + +#ifdef FACE32 +typedef uint32_t face_t; +const uint32_t M012 = 0x00000fff; +const uint32_t M234 = 0x000fff00; +const uint32_t M456 = 0x0fff0000; +const uint32_t M670 = 0xff00000f; +#else +typedef uint64_t face_t; +#endif /* FACE32 */ + +typedef enum { + UP = 0, + LEFT = 1, + FRONT = 2, + RIGHT = 3, + BACK = 4, + DOWN = 5 +} cube_side; + +typedef enum { + WHITE = 0, + ORANGE = 1, + GREEN = 2, + RED = 3, + BLUE = 4, + YELLOW = 5, + EMPTY_COLOR = 6 +} colors; + +typedef struct { + face_t faces[6]; +} cube_t; + +/******************************************************************************/ +/* Macros for generating rotation functions ***********************************/ + +#define ROR(x, y) (face_t)((long)(x) >> (y) | (long)(x) << ((8*sizeof(face_t)) - (y))) +static inline face_t ror(face_t x, face_t y) { + return ROR(x, y); +} + +#define PASTE(to, from, M1, M2) { \ + to = ((to) & ~(M ## M1)) | ((from) & M ## M2); \ +} + +#define PASTE_ROR(to, from, M1, M2, len) { \ + (to) = ((to) & ~(M ## M1)) | ror((from) & M ## M2, len * sizeof(face_t)); \ +} + +#define PASTE_FACE(cube, to, from, M1, M2) { \ + PASTE((cube).faces[to], (cube).faces[from], M1, M2); \ +} + +#define PASTE_FACE_ROR(cube, to, from, M1, M2, len) { \ + PASTE_ROR((cube).faces[to], (cube).faces[from], M1, M2, len); \ +} + +#define ABSTRACT_ROTATION_90(cube, face, len, f0, M0, f1, M1, f2, M2, f3, M3, C0, C1, C2, C3) { \ + (cube).faces[face] = ror((cube).faces[face], len * sizeof(face_t)); \ + face_t temporary_var = (cube).faces[f0]; \ + PASTE_FACE_ROR(cube, f0, f1, M0, M1, C0); \ + PASTE_FACE_ROR(cube, f1, f2, M1, M2, C1); \ + PASTE_FACE_ROR(cube, f2, f3, M2, M3, C2); \ + PASTE_ROR((cube).faces[f3], temporary_var, M3, M0, C3); \ +} + +#define ABSTRACT_ROTATION_180(cube, face, f0, M0, f1, M1, f2, M2, f3, M3, C01, C23) { \ + (cube).faces[face] = ror((cube).faces[face], 4 * sizeof(face_t)); \ + face_t temporary_var = (cube).faces[f0]; \ + PASTE_FACE_ROR(cube, f0, f1, M0, M1, C01); \ + PASTE_ROR((cube).faces[f1], temporary_var, M1, M0, C01); \ + temporary_var = (cube).faces[f2]; \ + PASTE_FACE_ROR(cube, f2, f3, M2, M3, C23); \ + PASTE_ROR((cube).faces[f3], temporary_var, M3, M2, C23); \ +} + +#define DEFINE_ROTATION_90(rotation, face, len, f0, M0, f1, M1, f2, M2, f3, M3, C0, C1, C2, C3) \ +static void rotation_ ## rotation (cube_t *cube) { \ + ABSTRACT_ROTATION_90(*cube, face, len, f0, M0, f1, M1, f2, M2, f3, M3, C0, C1, C2, C3); \ +} + +#define DEFINE_ROTATION_180(rotation, face, f0, M0, f1, M1, f2, M2, f3, M3, C01, C23) \ +static void rotation_ ## rotation (cube_t *cube) { \ + ABSTRACT_ROTATION_180(*cube, face, f0, M0, f1, M1, f2, M2, f3, M3, C01, C23); \ +} + +/* Clockwise rotations */ +DEFINE_ROTATION_90(r, RIGHT, 6, FRONT, 234, DOWN, 234, BACK, 670, UP, 234, 0, 4, 4, 0) +DEFINE_ROTATION_90(l, LEFT, 6, FRONT, 670, UP, 670, BACK, 234, DOWN, 670, 0, 4, 4, 0) +DEFINE_ROTATION_90(u, UP, 6, FRONT, 012, RIGHT, 012, BACK, 012, LEFT, 012, 0, 0, 0, 0) +DEFINE_ROTATION_90(d, DOWN, 6, FRONT, 456, LEFT, 456, BACK, 456, RIGHT, 456, 0, 0, 0, 0) +DEFINE_ROTATION_90(f, FRONT, 6, UP, 456, LEFT, 234, DOWN, 012, RIGHT, 670, 6, 6, 6, 6) +DEFINE_ROTATION_90(b, BACK, 6, UP, 012, RIGHT, 234, DOWN, 456, LEFT, 670, 2, 2, 2, 2) + +/* Counter clockwise rotations */ +DEFINE_ROTATION_90(rp, RIGHT, 2, FRONT, 234, UP, 234, BACK, 670, DOWN, 234, 0, 4, 4, 0) +DEFINE_ROTATION_90(lp, LEFT, 2, FRONT, 670, DOWN, 670, BACK, 234, UP, 670, 0, 4, 4, 0) +DEFINE_ROTATION_90(up, UP, 2, FRONT, 012, LEFT, 012, BACK, 012, RIGHT, 012, 0, 0, 0, 0) +DEFINE_ROTATION_90(dp, DOWN, 2, FRONT, 456, RIGHT, 456, BACK, 456, LEFT, 456, 0, 0, 0, 0) +DEFINE_ROTATION_90(fp, FRONT, 2, UP, 456, RIGHT, 670, DOWN, 012, LEFT, 234, 2, 2, 2, 2) +DEFINE_ROTATION_90(bp, BACK, 2, UP, 012, LEFT, 670, DOWN, 456, RIGHT, 234, 6, 6, 6, 6) + +/* Double clockwise */ +DEFINE_ROTATION_180(r2, RIGHT, FRONT, 234, BACK, 670, UP, 234, DOWN, 234, 4, 0) +DEFINE_ROTATION_180(l2, LEFT, FRONT, 670, BACK, 234, UP, 670, DOWN, 670, 4, 0) +DEFINE_ROTATION_180(u2, UP, FRONT, 012, BACK, 012, RIGHT, 012, LEFT, 012, 0, 0) +DEFINE_ROTATION_180(d2, DOWN, FRONT, 456, BACK, 456, RIGHT, 456, LEFT, 456, 0, 0) +DEFINE_ROTATION_180(f2, FRONT, UP, 456, DOWN, 012, RIGHT, 670, LEFT, 234, 4, 4) +DEFINE_ROTATION_180(b2, BACK, UP, 012, DOWN, 456, RIGHT, 234, LEFT, 670, 4, 4) + +typedef enum { + ROT_R = 0, + ROT_L, + ROT_U, + ROT_D, + ROT_F, + ROT_B, + ROT_RP, + ROT_LP, + ROT_UP, + ROT_DP, + ROT_FP, + ROT_BP, + ROT_R2, + ROT_L2, + ROT_U2, + ROT_D2, + ROT_F2, + ROT_B2, + NULL_ROT +} rotations; + +typedef void (*rot_f)(cube_t *); + +static const rot_f rot_func[] = { + rotation_r, + rotation_l, + rotation_u, + rotation_d, + rotation_f, + rotation_b, + rotation_rp, + rotation_lp, + rotation_up, + rotation_dp, + rotation_fp, + rotation_bp, + rotation_r2, + rotation_l2, + rotation_u2, + rotation_d2, + rotation_f2, + rotation_b2, +}; + +static void perform_rotations(cube_t *cube, rotations rots[]) { + while(*rots != NULL_ROT) { + rot_func[*rots](cube); + rots++; + } +} + +/******************************************************************************/ +/* Parsing rotations from input ***********************************************/ + +#define PRIM_CHAR '\'' + +static int str_to_rot(char *str, rotations *rot) { + ssize_t len = strlen(str); + int i; + + if (len == 0 || len > 2) { + return -1; + } + + const char rots_char[] = { 'R', 'L', 'U', 'D', 'F', 'B' }; + for (i = 0; i < 6; i++) { + if (str[0] == rots_char[i]) { + *rot = (rotations)i; + if (len == 2) { + if (str[1] == PRIM_CHAR) { + *(int*)rot += 6; + } else if (str[1] == '2') { + *(int*)rot += 12; + } + else { + return -1; + } + } + return 0; + } + } + return -1; +} + +static rotations* parse_scramble(char **str) { + ssize_t sz = 0; + ssize_t i = 0; + char *rot_str = str[0]; + while (rot_str) { + printf("token: %s\n", rot_str); + rot_str = str[++sz]; + } + + rotations *rots = (rotations *)calloc(sizeof(rotations), sz+1); + + for (i = 0; i < sz; i++) { + if (str_to_rot(str[i], &rots[i])) { + free(rots); + return NULL; + } + } + + rots[sz] = NULL_ROT; + + return rots; +} + +static char **tokenize_rot_str(char *str) { + const char *delims = " \n\t"; + ssize_t capacity = 20; + char **tokens = (char **)calloc(sizeof(char *), capacity); + int tok_cnt = 0; + + char *tok = strtok(str, delims); + while (tok != NULL) { + tok_cnt++; + if (tok_cnt > capacity) { + capacity *= 2; + tokens = (char **)realloc(tokens, sizeof(char *) * capacity); + } + tokens[tok_cnt - 1] = tok; + tok = strtok(NULL, delims); + } + + tokens = (char **)realloc(tokens, (sizeof(char *) * (1 + tok_cnt))); + tokens[tok_cnt] = NULL; + + return tokens; +} + +static rotations *rot_str_to_rotations(char *str_in) { + char *str = (char *)alloca(strlen(str_in) + 1); + memcpy(str, str_in, strlen(str_in) + 1); + + char **tokens = tokenize_rot_str(str); + rotations *rots = parse_scramble(tokens); + free(tokens); + return rots; +} + +static int rotate_from_str(cube_t *cube, char *str) { + rotations *rot = rot_str_to_rotations(str); + if (!rot) { + return -1; + } + perform_rotations(cube, rot); + free(rot); + return 0; +} + +static void init_cube(cube_t *cube) { + for (int face = 0; face < 6; face++) { + cube->faces[face] = 0; + for (int tile = 0; tile < 8; tile++) { + cube->faces[face] |= (face << (tile * sizeof(face_t))); + } + } +} + +/******************************************************************************/ +/* Printint cube state ********************************************************/ + +static const char letters[] = { 'W', 'O', 'G', 'R', 'B', 'Y' }; +static const char *terminal_letters[] = { + "W", + "\e[35mO\e[0m", + "\e[32mG\e[0m", + "\e[31mR\e[0m", + "\e[34mB\e[0m", + "\e[33mY\e[0m", +}; + +static colors get_tile_color(face_t face, int tile) { + colors color = (colors)((face >> (tile * sizeof(face_t))) & + ((1<<sizeof(face_t)) - 1)); + assert(color <= 5); + return color; +} + +static void dump_face(face_t face, colors buf[3][3]) { + buf[0][0] = get_tile_color(face, 0); + buf[0][1] = get_tile_color(face, 1); + buf[0][2] = get_tile_color(face, 2); + buf[1][0] = get_tile_color(face, 7); + buf[1][2] = get_tile_color(face, 3); + buf[2][0] = get_tile_color(face, 6); + buf[2][1] = get_tile_color(face, 5); + buf[2][2] = get_tile_color(face, 4); + assert(buf[0][0] <= 5); +} + +static void fill_face(cube_t *cube, cube_side face, colors buf[3][3]) { + dump_face(cube->faces[face], buf); + buf[1][1] = (colors)face; +} + +static void dump_cube_grid(cube_t *cube) { + int i, j, row, col; + colors buf[3][4][3][3]; /* XD */ + + memset(buf, -1, 3*4*3*3*sizeof(colors)); + fill_face(cube, UP, buf[0][1]); + fill_face(cube, LEFT, buf[1][0]); + fill_face(cube, FRONT, buf[1][1]); + fill_face(cube, RIGHT, buf[1][2]); + fill_face(cube, BACK, buf[1][3]); + fill_face(cube, DOWN, buf[2][1]); + + for (i = 0; i < 3; i++) { + for (row = 0; row < 3; row++) { + for (j = 0; j < 4; j++) { + for (col = 0; col < 3; col++) { + colors color = buf[i][j][row][col]; + printf("%s", (color == -1 ? " " : terminal_letters[color])); + } + } + printf("\n"); + } + } +} + +/******************************************************************************/ +/* Hash map *******************************************************************/ + +#ifdef FACE32 +#define P1 ((uint64_t)516077606561857057) +#define P2 ((uint64_t)217685325020058187) +#define P3 ((uint64_t)843829397461693519) +#define MOD_M 4200892139 +#define first_64(cube) (*(uint64_t*)((cube).faces)) +#define second_64(cube) (*(uint64_t*)((cube).faces+2)) +#define third_64(cube) (*(uint64_t*)((cube).faces+4)) +#define kh_cube_hash_func(cube) (khint32_t)((first_64(cube)*P1+second_64(cube)*P2+third_64(cube)*P3)%(uint64_t)MOD_M) +#define kh_cube_hash_equal(cube1, cube2) (first_64(cube1) == first_64(cube2) && second_64(cube1) == second_64(cube2) && third_64(cube1) == third_64(cube2)) + + +#endif /* FACE32 */ + +/******************************************************************************/ +/* Algorithm ******************************************************************/ + +typedef uint32_t rot_cnt_t; +#define build_rot_cnt(rot, cnt) (rot_cnt_t)(((uint32_t)rot << 16)|cnt) +#define get_rot(rot_cnt) (((uint32_t)rot_cnt)>>16) +#define get_cnt(rot_cnt) (uint32_t)(rot_cnt & 0xffff) + +KHASH_INIT(cube, cube_t, rot_cnt_t, 1, kh_cube_hash_func, kh_cube_hash_equal) + +khash_t(cube) *generate_pruning_table(int depth) { + khash_t(cube) *h = kh_init(cube); + +} + +/******************************************************************************/ +/* Main ***********************************************************************/ + +void test_scrambling() { + cube_t cube; + int i; + char *buf = NULL; + size_t sz; + + while (getline(&buf, &sz, stdin) != -1) { + init_cube(&cube); + if (sz == 0) break; + printf("> %s\n", buf); + rotations *rots = rot_str_to_rotations(buf); + if (rots) { + perform_rotations(&cube, rots); + free(rots); + dump_cube_grid(&cube); + } else { + printf("Rots == null :o\n"); + } + } + + if (buf) + free(buf); +} + +#endif /* _CUBE_H_ */ + +#ifdef __cplusplus +} +#endif diff --git a/src/khash.h b/src/khash.h new file mode 100644 index 0000000..a50dc80 --- /dev/null +++ b/src/khash.h @@ -0,0 +1,513 @@ +/* The MIT License + + Copyright (c) 2008, 2009 by attractor <attractor@live.co.uk> + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE. +*/ + +/* + An example: + +#include "khash.h" +KHASH_MAP_INIT_INT(32, char) +int main() { + int ret, is_missing; + khiter_t k; + khash_t(32) *h = kh_init(32); + k = kh_put(32, h, 5, &ret); + if (!ret) kh_del(32, h, k); + kh_value(h, k) = 10; + k = kh_get(32, h, 10); + is_missing = (k == kh_end(h)); + k = kh_get(32, h, 5); + kh_del(32, h, k); + for (k = kh_begin(h); k != kh_end(h); ++k) + if (kh_exist(h, k)) kh_value(h, k) = 1; + kh_destroy(32, h); + return 0; +} +*/ + +/* + 2009-09-26 (0.2.4): + + * Improve portability + + 2008-09-19 (0.2.3): + + * Corrected the example + * Improved interfaces + + 2008-09-11 (0.2.2): + + * Improved speed a little in kh_put() + + 2008-09-10 (0.2.1): + + * Added kh_clear() + * Fixed a compiling error + + 2008-09-02 (0.2.0): + + * Changed to token concatenation which increases flexibility. + + 2008-08-31 (0.1.2): + + * Fixed a bug in kh_get(), which has not been tested previously. + + 2008-08-31 (0.1.1): + + * Added destructor +*/ + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef __AC_KHASH_H +#define __AC_KHASH_H + +/*! + @header + + Generic hash table library. + + @copyright Heng Li + */ + +#define AC_VERSION_KHASH_H "0.2.4" + +#include <stdlib.h> +#include <string.h> +#include <limits.h> + +/* compipler specific configuration */ + +#if UINT_MAX == 0xffffffffu +typedef unsigned int khint32_t; +#elif ULONG_MAX == 0xffffffffu +typedef unsigned long khint32_t; +#endif + +#if ULONG_MAX == ULLONG_MAX +typedef unsigned long khint64_t; +#else +typedef unsigned long long khint64_t; +#endif + +#ifdef _MSC_VER +#define inline __inline +#endif + +typedef khint32_t khint_t; +typedef khint_t khiter_t; + +#define __ac_HASH_PRIME_SIZE 32 +static const khint32_t __ac_prime_list[__ac_HASH_PRIME_SIZE] = +{ + 0ul, 3ul, 11ul, 23ul, 53ul, + 97ul, 193ul, 389ul, 769ul, 1543ul, + 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, + 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, + 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, + 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, + 3221225473ul, 4294967291ul +}; + +#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2) +#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1) +#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3) +#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1))) +#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1))) +#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1))) +#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1)) + +static const double __ac_HASH_UPPER = 0.77; + +#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + typedef struct { \ + khint_t n_buckets, size, n_occupied, upper_bound; \ + khint32_t *flags; \ + khkey_t *keys; \ + khval_t *vals; \ + } kh_##name##_t; \ + static inline kh_##name##_t *kh_init_##name() { \ + return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t)); \ + } \ + static inline void kh_destroy_##name(kh_##name##_t *h) \ + { \ + if (h) { \ + free(h->keys); free(h->flags); \ + free(h->vals); \ + free(h); \ + } \ + } \ + static inline void kh_clear_##name(kh_##name##_t *h) \ + { \ + if (h && h->flags) { \ + memset(h->flags, 0xaa, ((h->n_buckets>>4) + 1) * sizeof(khint32_t)); \ + h->size = h->n_occupied = 0; \ + } \ + } \ + static inline khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ + { \ + if (h->n_buckets) { \ + khint_t inc, k, i, last; \ + k = __hash_func(key); i = k % h->n_buckets; \ + inc = 1 + k % (h->n_buckets - 1); last = i; \ + while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ + if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \ + else i += inc; \ + if (i == last) return h->n_buckets; \ + } \ + return __ac_iseither(h->flags, i)? h->n_buckets : i; \ + } else return 0; \ + } \ + static inline void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ + { \ + khint32_t *new_flags = 0; \ + khint_t j = 1; \ + { \ + khint_t t = __ac_HASH_PRIME_SIZE - 1; \ + while (__ac_prime_list[t] > new_n_buckets) --t; \ + new_n_buckets = __ac_prime_list[t+1]; \ + if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; \ + else { \ + new_flags = (khint32_t*)malloc(((new_n_buckets>>4) + 1) * sizeof(khint32_t)); \ + memset(new_flags, 0xaa, ((new_n_buckets>>4) + 1) * sizeof(khint32_t)); \ + if (h->n_buckets < new_n_buckets) { \ + h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \ + if (kh_is_map) \ + h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \ + } \ + } \ + } \ + if (j) { \ + for (j = 0; j != h->n_buckets; ++j) { \ + if (__ac_iseither(h->flags, j) == 0) { \ + khkey_t key = h->keys[j]; \ + khval_t val; \ + if (kh_is_map) val = h->vals[j]; \ + __ac_set_isdel_true(h->flags, j); \ + while (1) { \ + khint_t inc, k, i; \ + k = __hash_func(key); \ + i = k % new_n_buckets; \ + inc = 1 + k % (new_n_buckets - 1); \ + while (!__ac_isempty(new_flags, i)) { \ + if (i + inc >= new_n_buckets) i = i + inc - new_n_buckets; \ + else i += inc; \ + } \ + __ac_set_isempty_false(new_flags, i); \ + if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \ + { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ + if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ + __ac_set_isdel_true(h->flags, i); \ + } else { \ + h->keys[i] = key; \ + if (kh_is_map) h->vals[i] = val; \ + break; \ + } \ + } \ + } \ + } \ + if (h->n_buckets > new_n_buckets) { \ + h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \ + if (kh_is_map) \ + h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \ + } \ + free(h->flags); \ + h->flags = new_flags; \ + h->n_buckets = new_n_buckets; \ + h->n_occupied = h->size; \ + h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + } \ + static inline khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ + { \ + khint_t x; \ + if (h->n_occupied >= h->upper_bound) { \ + if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); \ + else kh_resize_##name(h, h->n_buckets + 1); \ + } \ + { \ + khint_t inc, k, i, site, last; \ + x = site = h->n_buckets; k = __hash_func(key); i = k % h->n_buckets; \ + if (__ac_isempty(h->flags, i)) x = i; \ + else { \ + inc = 1 + k % (h->n_buckets - 1); last = i; \ + while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ + if (__ac_isdel(h->flags, i)) site = i; \ + if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \ + else i += inc; \ + if (i == last) { x = site; break; } \ + } \ + if (x == h->n_buckets) { \ + if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ + else x = i; \ + } \ + } \ + } \ + if (__ac_isempty(h->flags, x)) { \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + ++h->size; ++h->n_occupied; \ + *ret = 1; \ + } else if (__ac_isdel(h->flags, x)) { \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + ++h->size; \ + *ret = 2; \ + } else *ret = 0; \ + return x; \ + } \ + static inline void kh_del_##name(kh_##name##_t *h, khint_t x) \ + { \ + if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ + __ac_set_isdel_true(h->flags, x); \ + --h->size; \ + } \ + } + +/* --- BEGIN OF HASH FUNCTIONS --- */ + +/*! @function + @abstract Integer hash function + @param key The integer [khint32_t] + @return The hash value [khint_t] + */ +#define kh_int_hash_func(key) (khint32_t)(key) +/*! @function + @abstract Integer comparison function + */ +#define kh_int_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract 64-bit integer hash function + @param key The integer [khint64_t] + @return The hash value [khint_t] + */ +#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11) +/*! @function + @abstract 64-bit integer comparison function + */ +#define kh_int64_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract const char* hash function + @param s Pointer to a null terminated string + @return The hash value + */ +static inline khint_t __ac_X31_hash_string(const char *s) +{ + khint_t h = *s; + if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s; + return h; +} +/*! @function + @abstract Another interface to const char* hash function + @param key Pointer to a null terminated string [const char*] + @return The hash value [khint_t] + */ +#define kh_str_hash_func(key) __ac_X31_hash_string(key) +/*! @function + @abstract Const char* comparison function + */ +#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0) + +/* --- END OF HASH FUNCTIONS --- */ + +/* Other necessary macros... */ + +/*! + @abstract Type of the hash table. + @param name Name of the hash table [symbol] + */ +#define khash_t(name) kh_##name##_t + +/*! @function + @abstract Initiate a hash table. + @param name Name of the hash table [symbol] + @return Pointer to the hash table [khash_t(name)*] + */ +#define kh_init(name) kh_init_##name() + +/*! @function + @abstract Destroy a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_destroy(name, h) kh_destroy_##name(h) + +/*! @function + @abstract Reset a hash table without deallocating memory. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_clear(name, h) kh_clear_##name(h) + +/*! @function + @abstract Resize a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param s New size [khint_t] + */ +#define kh_resize(name, h, s) kh_resize_##name(h, s) + +/*! @function + @abstract Insert a key to the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @param r Extra return code: 0 if the key is present in the hash table; + 1 if the bucket is empty (never used); 2 if the element in + the bucket has been deleted [int*] + @return Iterator to the inserted element [khint_t] + */ +#define kh_put(name, h, k, r) kh_put_##name(h, k, r) + +/*! @function + @abstract Retrieve a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @return Iterator to the found element, or kh_end(h) is the element is absent [khint_t] + */ +#define kh_get(name, h, k) kh_get_##name(h, k) + +/*! @function + @abstract Remove a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Iterator to the element to be deleted [khint_t] + */ +#define kh_del(name, h, k) kh_del_##name(h, k) + + +/*! @function + @abstract Test whether a bucket contains data. + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return 1 if containing data; 0 otherwise [int] + */ +#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x))) + +/*! @function + @abstract Get key given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Key [type of keys] + */ +#define kh_key(h, x) ((h)->keys[x]) + +/*! @function + @abstract Get value given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Value [type of values] + @discussion For hash sets, calling this results in segfault. + */ +#define kh_val(h, x) ((h)->vals[x]) + +/*! @function + @abstract Alias of kh_val() + */ +#define kh_value(h, x) ((h)->vals[x]) + +/*! @function + @abstract Get the start iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The start iterator [khint_t] + */ +#define kh_begin(h) (khint_t)(0) + +/*! @function + @abstract Get the end iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The end iterator [khint_t] + */ +#define kh_end(h) ((h)->n_buckets) + +/*! @function + @abstract Get the number of elements in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of elements in the hash table [khint_t] + */ +#define kh_size(h) ((h)->size) + +/*! @function + @abstract Get the number of buckets in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of buckets in the hash table [khint_t] + */ +#define kh_n_buckets(h) ((h)->n_buckets) + +/* More conenient interfaces */ + +/*! @function + @abstract Instantiate a hash set containing integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT(name) \ + KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT(name, khval_t) \ + KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing 64-bit integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT64(name) \ + KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing 64-bit integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT64(name, khval_t) \ + KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal) + +typedef const char *kh_cstr_t; +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_STR(name) \ + KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_STR(name, khval_t) \ + KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) + +#endif /* __AC_KHASH_H */ + +#ifdef __cplusplus +} +#endif |