src/server/map.c

Fri, 30 Dec 2011 17:50:05 +0100

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Fri, 30 Dec 2011 17:50:05 +0100
changeset 12
34aa8001ea53
parent 1
3c066d52342d
permissions
-rw-r--r--

Added directory index

1
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1 /*
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
3 *
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
4 * Copyright 2011 Olaf Wintermann. All rights reserved.
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
5 *
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
8 *
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
11 *
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
15 *
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
27 */
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
28
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
29 #include <stdio.h>
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
30 #include <stdlib.h>
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
31 #include <string.h>
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
32
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
33 #include "map.h"
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
34
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
35 hashmap_t* hashmap_new(size_t size) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
36 hashmap_t *map = malloc(sizeof(hashmap_t));
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
37 map->map = calloc(size, sizeof(sdlist_t));
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
38 map->len = size;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
39
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
40 return map;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
41 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
42
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
43 void hashmap_free(hashmap_t *map) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
44 for(int i=0;i<map->len;i++) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
45 sdlist_t *list = map->map[0];
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
46 while(list != NULL) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
47 hashmap_elm_t *elm = (hashmap_elm_t*)list->data;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
48 free(elm->key.ptr);
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
49 sdlist_t *l = list;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
50 list = list->next;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
51 free(elm);
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
52 free(l);
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
53 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
54 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
55 free(map->map);
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
56 free(map);
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
57 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
58
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
59
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
60 void hashmap_put(hashmap_t *map, sstr_t key, void *value) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
61 int hash = hashmap_hash(key.ptr, key.length);
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 sdlist_t *list = map->map[hash%map->len];
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
64
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
65 sstr_t k = sstrdub(key);
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
67 hashmap_elm_t *elm = malloc(sizeof(hashmap_elm_t));
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
68 elm->data = value;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
69 elm->hash = hash;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
70 elm->key = k;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
71
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
72 map->map[hash%map->len] = sdlist_add(list, elm);
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
73 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
74
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
75 void* hashmap_get(hashmap_t *map, sstr_t key) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
76 int hash = hashmap_hash(key.ptr, key.length);
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
77 sdlist_t *list = map->map[hash%map->len];
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
78 void *value = NULL;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
79
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
80 while (list != NULL) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
81 hashmap_elm_t *elm = list->data;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
82 if (elm->hash == hash &&
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
83 strncmp(key.ptr, elm->key.ptr, key.length) == 0) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
84 value = elm->data;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
85 break;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
86 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
87 list = list->next;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
88 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
89
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
90 return value;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
91 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
92
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
93
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
94
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
95
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
96 /* hash function */
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
97 int hashmap_hash(char *data, size_t len) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
98 /* murmur hash 2 */
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
99
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
100 int m = 0x5bd1e995;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
101 int r = 24;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
102
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
103 int h = 25 ^ len;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
104
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
105 int i = 0;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
106 while (len >= 4) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
107 int k = data[i + 0] & 0xFF;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
108 k |= (data[i + 1] & 0xFF) << 8;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
109 k |= (data[i + 2] & 0xFF) << 16;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110 k |= (data[i + 3] & 0xFF) << 24;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
112 k *= m;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
113 k ^= k >> r;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
114 k *= m;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
115
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
116 h *= m;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
117 h ^= k;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
118
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
119 i += 4;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
120 len -= 4;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
121 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
122
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
123 switch (len) {
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
124 case 3: h ^= (data[i + 2] & 0xFF) << 16;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
125 case 2: h ^= (data[i + 1] & 0xFF) << 8;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
126 case 1: h ^= (data[i + 0] & 0xFF); h *= m;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
127 }
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
128
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
129 h ^= h >> 13;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
130 h *= m;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131 h ^= h >> 15;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
132
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
133 return h;
3c066d52342d added source
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134 }

mercurial