// 3508. Implement Router #include "leetcode.h" /* * design a data structure that can efficiently manage data packets in a network * router. each data packet consists of the following attributes: 'source', * 'destination', 'timestamp'. note that the queries for 'routerAddPacket' will * be made in increasing order of timestamp */ #define HASH_SIZE 200925 struct packet { int source; int destination; int timestamp; struct packet *next; }; struct key_node { char *key; struct key_node *next; }; struct destination_info { int *timestamps; int size; int capacity; }; typedef struct { int memoryLimit; int size; struct packet *head; struct packet *tail; struct key_node *packet_set[HASH_SIZE]; struct destination_info *dest_map[HASH_SIZE]; } Router; unsigned int hash_str(const char *s) { unsigned int res = 0; while (*s) res = res * 31 + (unsigned char)(*s++); return res % HASH_SIZE; } unsigned int hash_int(int x) { return ((unsigned int)x) % HASH_SIZE; } char *make_key(int src, int dst, int ts) { char *res = (char *)malloc(32 * sizeof(char)); sprintf(res, "%d-%d-%d", src, dst, ts); return res; } bool key_exists(Router *obj, const char *key) { unsigned int hash = hash_str(key); struct key_node *curr = obj->packet_set[hash]; while (curr) { if (!strcmp(curr->key, key)) return true; curr = curr->next; } return false; } void key_insert(Router *obj, char *key) { unsigned int hash = hash_str(key); struct key_node *node = (struct key_node *)malloc(sizeof(struct key_node)); node->key = key; node->next = obj->packet_set[hash]; obj->packet_set[hash] = node; } void key_remove(Router *obj, const char *key) { unsigned int hash = hash_str(key); struct key_node *curr = obj->packet_set[hash], *prev = NULL; while (curr) { if (!strcmp(curr->key, key)) { if (prev) prev->next = curr->next; else obj->packet_set[hash] = curr->next; free(curr->key); free(curr); return; } prev = curr; curr = curr->next; } } struct destination_info *get_dest(Router *obj, int dst) { unsigned int hash = hash_int(dst); return obj->dest_map[hash]; } struct destination_info *create_dest(void) { struct destination_info *obj = (struct destination_info *)malloc(sizeof(struct destination_info)); obj->timestamps = (int *)malloc(8 * sizeof(int)); obj->size = 0; obj->capacity = 0; return obj; } void add_dest_timestamp(Router *obj, int dst, int ts) { unsigned int hash = hash_int(dst); struct destination_info *d = obj->dest_map[hash]; if (!d) { d = create_dest(); obj->dest_map[hash] = d; } if (d->size == d->capacity) { d->capacity *= 2; d->timestamps = (int *)realloc(d->timestamps, d->capacity * sizeof(int)); } d->timestamps[d->size++] = ts; } void remove_dest_timestamp(Router *obj, int dst, int ts) { unsigned int hash = hash_int(dst); struct destination_info *d = obj->dest_map[hash]; if (!d) return; int i; for (int i = 0; i < d->size; i++) if (d->timestamps[i] == ts) break; if (i == d->size) return; for (int j = i; j < d->size; j++) d->timestamps[j] = d->timestamps[j + 1]; d->size--; if (!d->size) { free(d->timestamps); free(d); obj->dest_map[hash] = NULL; } } int lower_bound(int *arr, int n, int target) { int l = 0, r = n; while (l < r) { int m = l + (r - l) / 2; if (arr[m] < target) l = m + 1; else r = m; } return l; } int upper_bound(int *arr, int n, int target) { int l = 0, r = n; while (l < r) { int m = l + (r - l) / 2; if (arr[m] <= target) l = m + 1; else r = m; } return l; } Router *routerCreate(int memoryLimit) { Router *obj = (Router *)malloc(sizeof(Router)); obj->memoryLimit = memoryLimit; obj->size = 0; obj->head = obj->tail = NULL; memset(obj->packet_set, 0, sizeof(obj->packet_set)); memset(obj->dest_map, 0, sizeof(obj->dest_map)); return obj; } bool routerAddPacket(Router *obj, int source, int destination, int timestamp) { char *key = make_key(source, destination, timestamp); if (key_exists(obj, key)) { free(key); return false; } if (obj->size == obj->memoryLimit) { struct packet *old = obj->head; obj->head = old->next; if (!obj->head) obj->tail = NULL; obj->size--; char *prev_key = make_key(old->source, old->destination, old->timestamp); key_remove(obj, prev_key); free(prev_key); remove_dest_timestamp(obj, old->destination, old->timestamp); free(old); } struct packet *p = (struct packet *)malloc(sizeof(struct packet)); p->source = source; p->destination = destination; p->timestamp = timestamp; p->next = NULL; if (!obj->tail) obj->head = obj->tail = p; else { obj->tail->next = p; obj->tail = p; } obj->size++; key_insert(obj, key); add_dest_timestamp(obj, destination, timestamp); return true; } int *routerForwardPacket(Router *obj, int *retSize) { if (!obj->head) { *retSize = 0; return NULL; } struct packet *p = obj->head; obj->head = p->next; if (!obj->head) obj->tail = NULL; obj->size--; char *key = make_key(p->source, p->destination, p->timestamp); key_remove(obj, key); free(key); remove_dest_timestamp(obj, p->destination, p->timestamp); int *res = (int *)malloc(3 * sizeof(int)); res[0] = p->source; res[1] = p->destination; res[2] = p->timestamp; *retSize = 3; free(p); return res; } int routerGetCount(Router *obj, int destination, int startTime, int endTime) { unsigned int hash = hash_int(destination); struct destination_info *d = obj->dest_map[hash]; if (!d) return 0; int l = lower_bound(d->timestamps, d->size, startTime); int r = upper_bound(d->timestamps, d->size, endTime); return r - l; } void routerFree(Router *obj) { while (obj->head) { struct packet *tmp = obj->head; obj->head = obj->head->next; free(tmp); for (int i = 0; i < HASH_SIZE; i++) { struct key_node *key = obj->packet_set[i]; while (key) { struct key_node *t = key; key = key->next; free(t->key); free(t); } struct destination_info *d = obj->dest_map[i]; if (d) { free(d->timestamps); free(d); } } } free(obj); } int main() { Router *obj = routerCreate(3); printf("%d\n", routerAddPacket(obj, 1, 4, 90)); // expect: 1 printf("%d\n", routerAddPacket(obj, 2, 5, 90)); // expect: 1 printf("%d\n", routerAddPacket(obj, 1, 4, 90)); // expect: 0 printf("%d\n", routerAddPacket(obj, 3, 5, 95)); // expect: 1 printf("%d\n", routerAddPacket(obj, 4, 5, 105)); // expect: 1 int rs, *rfp = routerForwardPacket(obj, &rs); for (int i = 0; i < rs; i++) printf("%d ", rfp[i]); // expect: 2 5 90 free(rfp); printf("%d\n", routerAddPacket(obj, 5, 2, 110)); // expect: 1 printf("%d\n", routerGetCount(obj, 5, 100, 110)); // expect: routerFree(obj); }