Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
URL shortner implementation in C. This is just an example how it could be implemented. Ideally the lookup table should be pre-generated and not hardcoded.
/**
* Author: Felipe Ferreri Tonello <eu@felipetonello.com>
*
* This url-shortner it only works with ASCII characters. It encodes and
* decodes ids.
* You can change base_x as you wish.
*
* It runs at least 20 times faster then a Python implementation.
*
* $ time python url-shortner.py -s I7
* 1123
*
* real 0m0.020s
* user 0m0.015s
* sys 0m0.001s
* $ time ./url-shortner -d I7
* 1123
*
* real 0m0.001s
* user 0m0.000s
* sys 0m0.000s
*
* But this gain it's not really useful.
*
* TODO: use big numbers instead of unsigned long long
* Compile instructions: gcc url-shortner.c -o url-shortner -lm
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#define BUFFER_SIZE 50
#define BASE_NUM (sizeof(base_x) / sizeof(*(base_x)))
#define HASH_BASE_X_SIZE (sizeof(char) * (0xff + 1))
/* NOTE: Ideally you want to generate the lookup table
and not hard code it. */
/* Base X lookup table */
static char base_x[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
/* Inverted base X lookup table */
static size_t base_x_to_dec[HASH_BASE_X_SIZE];
/* This is a work around. You should use
a pre generated lookup table */
static void init_hash_base_x()
{
size_t i, j;
for (i = 0; i < HASH_BASE_X_SIZE; ++i)
for (j = 0; j < BASE_NUM; ++j)
if (i == (size_t) base_x[j]) {
base_x_to_dec[i] = j;
break;
}
}
inline static swap(char *a, char *b)
{
char tmp = *a;
*a = *b;
*b = tmp;
}
static void strrev(char *str, size_t len)
{
size_t i, mid = len / 2;
for (i = 0; i < mid; ++i)
swap(&str[i], &str[len - i - 1]);
}
unsigned long long decode(char *str)
{
unsigned long long sum = 0;
size_t i = 0;
strrev(str, strlen(str));
while (*str) {
sum += base_x_to_dec[(size_t)*str] * pow(BASE_NUM, i);
str++, i++;
}
return sum;
}
char * encode(unsigned long long id)
{
char *buf = malloc(sizeof(char) * BUFFER_SIZE);
size_t i = 0;
while (id > 0) {
int mod = id % BASE_NUM;
buf[i] = base_x[mod];
id /= BASE_NUM;
++i;
}
buf[i] = '\0';
strrev(buf, i);
return buf;
}
void print_usage_and_exit(char *argv0)
{
fprintf(stderr, "usage: %s option value\n"
"Options:\n"
" -e\tEnconde\n"
" -d\tDecode\n"
" -h\tDisplay this information\n", argv0);
exit(-1);
}
int main(int argc, char *argv[])
{
if (argc != 3)
print_usage_and_exit(argv[0]);
if(strcmp(argv[1], "-e") == 0) {
char *buf = encode(strtoull(argv[2], NULL, 10));
printf("%s\n", buf);
free(buf);
} else if(strcmp(argv[1], "-d") == 0) {
unsigned long long dec;
init_hash_base_x();
dec = decode(argv[2]);
printf("%llu\n", dec);
} else {
print_usage_and_exit(argv[0]);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.