From 1b1f47c915c69eae40d99727267b147f7c5a44ac Mon Sep 17 00:00:00 2001 From: antirez Date: Wed, 3 Nov 2010 11:23:59 +0100 Subject: [PATCH] command lookup process turned into a much more flexible and probably faster hash table --- src/db.c | 4 +-- src/dict.c | 10 ++++++++ src/dict.h | 1 + src/multi.c | 4 +-- src/redis.c | 73 ++++++++++++++++++++++++++++++++++++++--------------- src/redis.h | 6 ++++- 6 files changed, 70 insertions(+), 28 deletions(-) diff --git a/src/db.c b/src/db.c index f2a0c09e..aa1c14ad 100644 --- a/src/db.c +++ b/src/db.c @@ -435,16 +435,14 @@ time_t getExpire(redisDb *db, robj *key) { * will be consistent even if we allow write operations against expiring * keys. */ void propagateExpire(redisDb *db, robj *key) { - struct redisCommand *cmd; robj *argv[2]; - cmd = lookupCommand("del"); argv[0] = createStringObject("DEL",3); argv[1] = key; incrRefCount(key); if (server.appendonly) - feedAppendOnlyFile(cmd,db->id,argv,2); + feedAppendOnlyFile(server.delCommand,db->id,argv,2); if (listLength(server.slaves)) replicationFeedSlaves(server.slaves,db->id,argv,2); diff --git a/src/dict.c b/src/dict.c index a1060d45..9be7fb16 100644 --- a/src/dict.c +++ b/src/dict.c @@ -42,6 +42,7 @@ #include #include #include +#include #include "dict.h" #include "zmalloc.h" @@ -94,6 +95,15 @@ unsigned int dictGenHashFunction(const unsigned char *buf, int len) { return hash; } +/* And a case insensitive version */ +unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) { + unsigned int hash = 5381; + + while (len--) + hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */ + return hash; +} + /* ----------------------------- API implementation ------------------------- */ /* Reset an hashtable already initialized with ht_init(). diff --git a/src/dict.h b/src/dict.h index 30ace4db..25cce4e5 100644 --- a/src/dict.h +++ b/src/dict.h @@ -137,6 +137,7 @@ void dictReleaseIterator(dictIterator *iter); dictEntry *dictGetRandomKey(dict *d); void dictPrintStats(dict *d); unsigned int dictGenHashFunction(const unsigned char *buf, int len); +unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len); void dictEmpty(dict *d); void dictEnableResize(void); void dictDisableResize(void); diff --git a/src/multi.c b/src/multi.c index 47615eb0..59fc9d9e 100644 --- a/src/multi.c +++ b/src/multi.c @@ -65,12 +65,10 @@ void discardCommand(redisClient *c) { /* Send a MULTI command to all the slaves and AOF file. Check the execCommand * implememntation for more information. */ void execCommandReplicateMulti(redisClient *c) { - struct redisCommand *cmd; robj *multistring = createStringObject("MULTI",5); - cmd = lookupCommand("multi"); if (server.appendonly) - feedAppendOnlyFile(cmd,c->db->id,&multistring,1); + feedAppendOnlyFile(server.multiCommand,c->db->id,&multistring,1); if (listLength(server.slaves)) replicationFeedSlaves(server.slaves,c->db->id,&multistring,1); decrRefCount(multistring); diff --git a/src/redis.c b/src/redis.c index f65901c7..d099551e 100644 --- a/src/redis.c +++ b/src/redis.c @@ -252,6 +252,15 @@ int dictSdsKeyCompare(void *privdata, const void *key1, return memcmp(key1, key2, l1) == 0; } +/* A case insensitive version used for the command lookup table. */ +int dictSdsKeyCaseCompare(void *privdata, const void *key1, + const void *key2) +{ + DICT_NOTUSED(privdata); + + return strcasecmp(key1, key2) == 0; +} + void dictRedisObjectDestructor(void *privdata, void *val) { DICT_NOTUSED(privdata); @@ -283,6 +292,10 @@ unsigned int dictSdsHash(const void *key) { return dictGenHashFunction((unsigned char*)key, sdslen((char*)key)); } +unsigned int dictSdsCaseHash(const void *key) { + return dictGenCaseHashFunction((unsigned char*)key, sdslen((char*)key)); +} + int dictEncObjKeyCompare(void *privdata, const void *key1, const void *key2) { @@ -364,6 +377,16 @@ dictType keyptrDictType = { NULL /* val destructor */ }; +/* Command table. sds string -> command struct pointer. */ +dictType commandTableDictType = { + dictSdsCaseHash, /* hash function */ + NULL, /* key dup */ + NULL, /* val dup */ + dictSdsKeyCaseCompare, /* key compare */ + dictSdsDestructor, /* key destructor */ + NULL /* val destructor */ +}; + /* Hash type hash table (note that small hashes are represented with zimpaps) */ dictType hashDictType = { dictEncObjHash, /* hash function */ @@ -791,6 +814,12 @@ void initServer() { redisLog(REDIS_WARNING, "Can't open /dev/null: %s", server.neterr); exit(1); } + + server.commands = dictCreate(&commandTableDictType,NULL); + populateCommandTable(); + server.delCommand = lookupCommandByCString("del"); + server.multiCommand = lookupCommandByCString("multi"); + server.clients = listCreate(); server.slaves = listCreate(); server.monitors = listCreate(); @@ -860,31 +889,34 @@ void initServer() { if (server.vm_enabled) vmInit(); } -int qsortRedisCommands(const void *r1, const void *r2) { - return strcasecmp( - ((struct redisCommand*)r1)->name, - ((struct redisCommand*)r2)->name); -} +/* Populates the Redis Command Table starting from the hard coded list + * we have on top of redis.c file. */ +void populateCommandTable(void) { + int j; + int numcommands = sizeof(readonlyCommandTable)/sizeof(struct redisCommand); + + for (j = 0; j < numcommands; j++) { + struct redisCommand *c = readonlyCommandTable+j; + int retval; -void sortCommandTable() { - /* Copy and sort the read-only version of the command table */ - commandTable = (struct redisCommand*)zmalloc(sizeof(readonlyCommandTable)); - memcpy(commandTable,readonlyCommandTable,sizeof(readonlyCommandTable)); - qsort(commandTable, - sizeof(readonlyCommandTable)/sizeof(struct redisCommand), - sizeof(struct redisCommand),qsortRedisCommands); + retval = dictAdd(server.commands, sdsnew(c->name), c); + assert(retval == DICT_OK); + } } /* ====================== Commands lookup and execution ===================== */ -struct redisCommand *lookupCommand(char *name) { - struct redisCommand tmp = {name,NULL,0,0,NULL,0,0,0}; - return bsearch( - &tmp, - commandTable, - sizeof(readonlyCommandTable)/sizeof(struct redisCommand), - sizeof(struct redisCommand), - qsortRedisCommands); +struct redisCommand *lookupCommand(sds name) { + return dictFetchValue(server.commands, name); +} + +struct redisCommand *lookupCommandByCString(char *s) { + struct redisCommand *cmd; + sds name = sdsnew(s); + + cmd = dictFetchValue(server.commands, name); + sdsfree(name); + return cmd; } /* Call() is the core of Redis execution of a command */ @@ -1443,7 +1475,6 @@ int main(int argc, char **argv) { time_t start; initServerConfig(); - sortCommandTable(); if (argc == 2) { if (strcmp(argv[1], "-v") == 0 || strcmp(argv[1], "--version") == 0) version(); diff --git a/src/redis.h b/src/redis.h index 6fa3e49f..8818fa05 100644 --- a/src/redis.h +++ b/src/redis.h @@ -360,6 +360,8 @@ struct redisServer { long long dirty; /* changes to DB from the last save */ long long dirty_before_bgsave; /* used to restore dirty on failed BGSAVE */ list *clients; + dict *commands; /* Command table hahs table */ + struct redisCommand *delCommand, *multiCommand; /* often lookedup cmds */ list *slaves, *monitors; char neterr[ANET_ERR_LEN]; aeEventLoop *el; @@ -746,7 +748,8 @@ zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj); void freeMemoryIfNeeded(void); int processCommand(redisClient *c); void setupSigSegvAction(void); -struct redisCommand *lookupCommand(char *name); +struct redisCommand *lookupCommand(sds name); +struct redisCommand *lookupCommandByCString(char *s); void call(redisClient *c, struct redisCommand *cmd); int prepareForShutdown(); void redisLog(int level, const char *fmt, ...); @@ -754,6 +757,7 @@ void usage(); void updateDictResizePolicy(void); int htNeedsResize(dict *dict); void oom(const char *msg); +void populateCommandTable(void); /* Virtual Memory */ void vmInit(void); -- 2.47.2