From f845721828a0000f1c7e30f35360417771788e0a Mon Sep 17 00:00:00 2001 From: Frederic Culot Date: Sat, 8 Nov 2008 19:05:15 +0000 Subject: new files to manage user-definable keybindings --- ChangeLog | 9 ++ src/Makefile.am | 5 +- src/htable.h | 392 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/keys.c | 94 ++++++++++++++ src/keys.h | 91 +++++++++++++ 5 files changed, 589 insertions(+), 2 deletions(-) create mode 100644 src/htable.h create mode 100755 src/keys.c create mode 100755 src/keys.h diff --git a/ChangeLog b/ChangeLog index 47c5ac9..cec77ec 100755 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2008-11-08 Frederic Culot + + * src/keys.[ch]: new files to manage user-definable keybindings + + * src/htable.h: hash table project imported + + * src/Makefile.am: keys.[ch], htable.h added + * po/POTFILES: keys.c added + 2008-10-15 Frederic Culot * === Released 2.3 === diff --git a/src/Makefile.am b/src/Makefile.am index 3f2c1b5..272f3db 100755 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -1,11 +1,11 @@ -# $calcurse: Makefile.am,v 1.6 2007/07/28 15:04:52 culot Exp $ +# $calcurse: Makefile.am,v 1.7 2008/11/08 19:05:15 culot Exp $ AUTOMAKE_OPTIONS= gnu bin_PROGRAMS= calcurse calcurse_SOURCES= \ - calcurse.c i18n.h \ + calcurse.c i18n.h htable.h \ apoint.c apoint.h \ args.c args.h \ calendar.c calendar.h \ @@ -14,6 +14,7 @@ calcurse_SOURCES= \ event.c event.h \ help.c help.h \ io.c io.h \ + keys.c keys.h \ notify.c notify.h \ recur.c recur.h \ sigs.c sigs.h \ diff --git a/src/htable.h b/src/htable.h new file mode 100644 index 0000000..31e9d2f --- /dev/null +++ b/src/htable.h @@ -0,0 +1,392 @@ +/* $Id: htable.h,v 1.1 2008/11/08 19:05:15 culot Exp $ */ + +/* + * Copyright (c) 2008 Frederic Culot + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the + * following disclaimer in the documentation and/or other + * materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef HTABLE_H +#define HTABLE_H + +#include +#include + +/* + * This file defines data structures for hash tables. + * + * Hash tables are ideal for applications with datasets needing lots of adding, + * searching or removal, as those are normally constant-time operations. + * The primary operation it supports efficiently is a lookup: given a key (e.g. + * a person's name), find the corresponding value (e.g. that person's telephone + * number). It works by transforming the key using a hash function into a hash, + * a number that is used as an index in an array to locate the desired location + * ("bucket") where the values should be. + * + * Hash tables support the efficient insertion of new entries, in expected O(1) + * time. The time spent in searching depends on the hash function and the load + * of the hash table; both insertion and search approach O(1) time with well + * chosen values and hashes. + * + * The collision resolution technique used here is direct chaining, implemented + * using singly linked lists (the worst-case time is O(n)). + * + * This was chosen because performance degradation is linear as the table + * fills, so there is almost no need to resize table + * (for example, a chaining hash table containing twice its recommended + * capacity of data would only be about twice as slow on average as the same + * table at its recommended capacity). + */ + +#define HTABLE_HEAD(name, size, type) \ +struct name { \ + uint32_t noitems; /* Number of items stored in hash table. */ \ + uint32_t nosingle; /* Number of items alone in their bucket. */ \ + uint32_t nofreebkts; /* Number of free buckets. */ \ + struct type *bkts[size]; /* Pointers to user-defined data structures. */ \ +} + +#define HTABLE_ENTRY(type) \ +struct { \ + struct type *next; /* To build the bucket chain list. */ \ +} + +#define HTABLE_SIZE(head) \ + (sizeof (*(head)->bkts) ? sizeof ((head)->bkts) / sizeof (*(head)->bkts) : 0) + +#define HTABLE_COUNT(head) \ + ((head)->noitems ? (head)->noitems : 0) + +#define HTABLE_EMPTY(head) \ + (HTABLE_COUNT((head)) == 0 ? 1 : 0) + +#define HTABLE_COLLS(head) \ + ((head)->noitems ? 100.0 - 100 * (head)->nosingle / (head)->noitems : 0) + +#define HTABLE_LOAD(head) \ + (HTABLE_SIZE((head)) ? \ + 100.0 - 100.0 * (head)->nofreebkts / HTABLE_SIZE((head)) : 0) + +#define HTABLE_INITIALIZER(head) \ + { 0, /* noitems */ \ + 0, /* nosingle */ \ + HTABLE_SIZE((head)) /* nofreebkts */ \ + } + +#define HTABLE_INIT(head) do { \ + bzero ((head), sizeof (*(head))); \ + (head)->nofreebkts = HTABLE_SIZE((head)); \ +} while (0) + +/* + * Generate prototypes. + */ +#define HTABLE_PROTOTYPE(name, type) \ +struct type *name##_HTABLE_INSERT(struct name *, struct type *); \ +struct type *name##_HTABLE_REMOVE(struct name *, struct type *); \ +struct type *name##_HTABLE_LOOKUP(struct name *, struct type *); + +/* + * Generate function bodies. + */ +#define HTABLE_GENERATE(name, type, key, cmp) \ +uint32_t \ +name##_HTABLE_FIND_BKT(struct name *head, struct type *elm) \ +{ \ + uint32_t __bkt; \ + char *__key; \ + int __len; \ + \ + (key) (elm, &__key, &__len); \ + HTABLE_HASH(__key, __len, HTABLE_SIZE(head), __bkt); \ + \ + return __bkt; \ +} \ + \ +int \ +name##_HTABLE_CHAIN_LEN(struct name *head, uint32_t bkt) \ +{ \ + struct type *__bktp; \ + int __len; \ + \ + __len = 0; \ + for (__bktp = (head)->bkts[(bkt)]; __bktp != NULL; __bktp = __bktp->next) \ + __len++; \ + \ + return __len; \ +} \ + \ +struct type * \ +name##_HTABLE_INSERT(struct name *head, struct type *elm) \ +{ \ + struct type *__bktp, **__bktpp; \ + uint32_t __bkt, __pos; \ + \ + __pos = 0; \ + __bkt = name##_HTABLE_FIND_BKT(head, elm); \ + __bktpp = &head->bkts[__bkt]; \ + while ((__bktp = *__bktpp)) \ + { \ + if (!(cmp)(elm, __bktp)) \ + return __bktp; \ + else \ + { \ + __pos++; \ + __bktpp = &__bktp->next; \ + } \ + } \ + __bktp = elm; \ + __bktp->next = NULL; \ + *__bktpp = __bktp; \ + head->noitems++; \ + switch (__pos) \ + { \ + case 0: \ + head->nosingle++; \ + head->nofreebkts--; \ + break; \ + case 1: \ + head->nosingle--; \ + break; \ + default: \ + break; \ + } \ + \ + return __bktp; \ +} \ + \ +struct type * \ +name##_HTABLE_REMOVE(struct name *head, struct type *elm) \ +{ \ + struct type *__bktp, **__bktpp; \ + uint32_t __bkt, __pos; \ + \ + __pos = 0; \ + __bkt = name##_HTABLE_FIND_BKT(head, elm); \ + __bktpp = &head->bkts[__bkt]; \ + while ((__bktp = *__bktpp)) \ + { \ + if (!(cmp)(elm, __bktp)) \ + { \ + *__bktpp = __bktp->next; \ + elm = __bktp; \ + head->noitems--; \ + if (__pos <= 1) /* Need to scan list to know if we have */ \ + { /* a free bucket or a single item. */ \ + int __len; \ + \ + __len = name##_HTABLE_CHAIN_LEN(head, __bkt); \ + switch (__len) \ + { \ + case 0: \ + head->nofreebkts++; \ + head->nosingle--; \ + break; \ + case 1: \ + head->nosingle++; \ + break; \ + } \ + } \ + return elm; \ + } \ + __pos++; \ + __bktpp = &__bktp->next; \ + } \ + return NULL; \ +} \ + \ +struct type * \ +name##_HTABLE_LOOKUP(struct name *head, struct type *elm) \ +{ \ + struct type *__bktp, **__bktpp; \ + uint32_t __bkt; \ + \ + __bkt = name##_HTABLE_FIND_BKT(head, elm); \ + __bktpp = &head->bkts[__bkt]; \ + while ((__bktp = *__bktpp)) \ + { \ + if (!(cmp)(elm, __bktp)) \ + return __bktp; \ + else \ + __bktpp = &__bktp->next; \ + } \ + \ + return NULL; \ +} \ + \ +struct type * \ +name##_HTABLE_FIRST_FROM(struct name *head, int bkt) \ +{ \ + struct type *__bktp; \ + \ + while (bkt < HTABLE_SIZE(head)) \ + { \ + if ((__bktp = head->bkts[bkt])) \ + return __bktp; \ + else \ + bkt++; \ + } \ + \ + return NULL; \ +} \ + \ +struct type * \ +name##_HTABLE_NEXT(struct name *head, struct type *elm) \ +{ \ + struct type *__elmp, *__bktp, **__bktpp; \ + uint32_t __bkt; \ + \ + __elmp = NULL; \ + __bkt = name##_HTABLE_FIND_BKT(head, elm); \ + __bktpp = &head->bkts[__bkt]; \ + while ((__bktp = *__bktpp)) \ + { \ + if (!(cmp)(elm, __bktp)) \ + { \ + __elmp = __bktp; \ + break; \ + } \ + else \ + __bktpp = &__bktp->next; \ + } \ + \ + if (!__elmp) \ + return NULL; \ + else if (__elmp->next) \ + return __elmp->next; \ + else \ + return name##_HTABLE_FIRST_FROM(head, ++__bkt); \ +} + +#define FIRST_BKT 0 + +#define HTABLE_INSERT(name, x, y) name##_HTABLE_INSERT(x, y) +#define HTABLE_REMOVE(name, x, y) name##_HTABLE_REMOVE(x, y) +#define HTABLE_LOOKUP(name, x, y) name##_HTABLE_LOOKUP(x, y) +#define HTABLE_FIRST_FROM(name, x, y) (HTABLE_EMPTY(x) ? NULL \ + : name##_HTABLE_FIRST_FROM(x, y)) +#define HTABLE_FIRST(name, x) HTABLE_FIRST_FROM(name, x, FIRST_BKT) +#define HTABLE_NEXT(name, x, y) (HTABLE_EMPTY(x) ? NULL \ + : name##_HTABLE_NEXT(x, y)) + +#define HTABLE_FOREACH(x, name, head) \ + for ((x) = HTABLE_FIRST(name, head); \ + (x) != NULL; \ + (x) = HTABLE_NEXT(name, head, x)) + +/* + * Hash functions. + */ +#ifdef HASH_FUNCTION +#define HTABLE_HASH HASH_FUNCTION +#else +#define HTABLE_HASH HASH_JEN +#endif + +#define HASH_JEN_MIX(a, b, c) do { \ + a -= b; a -= c; a ^= (c >> 13); \ + b -= c; b -= a; b ^= (a << 8); \ + c -= a; c -= b; c ^= (b >> 13); \ + a -= b; a -= c; a ^= (c >> 12); \ + b -= c; b -= a; b ^= (a << 16); \ + c -= a; c -= b; c ^= (b >> 5); \ + a -= b; a -= c; a ^= (c >> 3); \ + b -= c; b -= a; b ^= (a << 10); \ + c -= a; c -= b; c ^= (b >> 15); \ +} while (0) + +#define HASH_JEN(key, keylen, num_bkts, bkt) do { \ + register uint32_t i, j, k, hash; \ + \ + hash = 0xfeedbeef; \ + i = j = 0x9e3779b9; \ + k = keylen; \ + while (k >= 12) \ + { \ + i += (key[0] + ((unsigned)key[1] << 8) \ + + ((unsigned)key[2] << 16) \ + + ((unsigned)key[3] << 24)); \ + j += (key[4] + ((unsigned)key[5] << 8) \ + + ((unsigned)key[6] << 16) \ + + ((unsigned)key[7] << 24 )); \ + hash += (key[8] + ((unsigned)key[9] << 8) \ + + ((unsigned)key[10] << 16) \ + + ((unsigned)key[11] << 24)); \ + \ + HASH_JEN_MIX (i, j, hash); \ + \ + key += 12; \ + k -= 12; \ + } \ + hash += keylen; \ + switch (k) \ + { \ + case 11: \ + hash += ((unsigned)key[10] << 24); \ + case 10: \ + hash += ((unsigned)key[9] << 16); \ + case 9: \ + hash += ((unsigned)key[8] << 8); \ + case 8: \ + j += ((unsigned)key[7] << 24); \ + case 7: \ + j += ((unsigned)key[6] << 16); \ + case 6: \ + j += ((unsigned)key[5] << 8); \ + case 5: \ + j += key[4]; \ + case 4: \ + i += ((unsigned)key[3] << 24); \ + case 3: \ + i += ((unsigned)key[2] << 16); \ + case 2: \ + i += ((unsigned)key[1] << 8); \ + case 1: \ + i += key[0]; \ + } \ + HASH_JEN_MIX (i, j, hash); \ + bkt = hash % (num_bkts); \ +} while (0) + +#define HASH_OAT(key, keylen, num_bkts, bkt) do { \ + register uint32_t hash; \ + int i; \ + \ + hash = 0; \ + for (i = 0; i < keylen; i++) \ + { \ + hash += key[i]; \ + hash += (hash << 10); \ + hash ^= (hash >> 6); \ + } \ + hash += (hash << 3); \ + hash ^= (hash >> 11); \ + hash += (hash << 15); \ + bkt = hash % (num_bkts); \ +} while (0) + +#endif /* !HTABLE_H */ diff --git a/src/keys.c b/src/keys.c new file mode 100755 index 0000000..f024be9 --- /dev/null +++ b/src/keys.c @@ -0,0 +1,94 @@ +/* $calcurse: keys.c,v 1.1 2008/11/08 19:05:15 culot Exp $ */ + +/* + * Calcurse - text-based organizer + * Copyright (c) 2008 Frederic Culot + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + * + * Send your feedback or comments to : calcurse@culot.org + * Calcurse home page : http://culot.org/calcurse + * + */ + +#include "i18n.h" +#include "utils.h" +#include "keys.h" + +const char *keylabel[NOKEYS] = { + "generic-help", + "generic-quit", + "generic-save", + "generic-change-view", + "generic-import", + "generic-export", + + "generic-goto", + "generic-other-cmd", + "generic-config-menu", + "generic-redraw", + + "generic-add-appt", + "generic-add-todo", + "generic-next-ady", + "generic-prev-day", + "generic-next-week", + "generic-prev-week", + "generic-goto-today", + + "cal-next-day", + "cal-prev-day", + "cal-next-week", + "cal-prev-week", + "cal-start-of-week", + "cal-end-of-week", + + "apt-add-item", + "apt-del-item", + "apt-edit-item", + "apt-view-item", + "apt-flag-item", + "apt-repeat", + "apt-move-up", + "apt-move-down", + "apt-edit-note", + "apt-view-note", + + "todo-add-item", + "todo-del-item", + "todo-edit-item", + "todo-view-item", + "todo-raise-priority", + "todo-lower-priority", + "todo-move-up", + "todo-move-down", + "todo-edit-note", + "todo-view-bote", + + "config-quit", + "config-general-menu", + "config-layout-menu", + "config-color-menu", + "config-notify-menu" +}; + +char *keys_get_label (keys_e key) +{ + EXIT_IF (key < 0 || key > NOKEYS, + _("FATAL ERROR in keys_get_label: key value out of bounds")); + + return keylabel (key); +} diff --git a/src/keys.h b/src/keys.h new file mode 100755 index 0000000..4551070 --- /dev/null +++ b/src/keys.h @@ -0,0 +1,91 @@ +/* $calcurse: keys.h,v 1.1 2008/11/08 19:05:15 culot Exp $ */ + +/* + * Calcurse - text-based organizer + * Copyright (c) 2008 Frederic Culot + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + * + * Send your feedback or comments to : calcurse@culot.org + * Calcurse home page : http://culot.org/calcurse + * + */ + +#ifndef CALCURSE_KEYS_H +#define CALCURSE_KEYS_H + +typedef enum + { + KEY_GENERIC_HELP, + KEY_GENERIC_QUIT, + KEY_GENERIC_SAVE, + KEY_GENERIC_CHANGE_VIEW, + KEY_GENERIC_IMPORT, + KEY_GENERIC_EXPORT, + KEY_GENERIC_GOTO, + KEY_GENERIC_OTHER_CMD, + KEY_GENERIC_CONFIG_MENU, + KEY_GENERIC_REDRAW, + KEY_GENERIC_ADD_APPT, + KEY_GENERIC_ADD_TODO, + KEY_GENERIC_NEXT_ADY, + KEY_GENERIC_PREV_DAY, + KEY_GENERIC_NEXT_WEEK, + KEY_GENERIC_PREV_WEEK, + KEY_GENERIC_GOTO_TODAY, + + KEY_CAL_NEXT_DAY, + KEY_CAL_PREV_DAY, + KEY_CAL_NEXT_WEEK, + KEY_CAL_PREV_WEEK, + KEY_CAL_START_OF_WEEK, + KEY_CAL_END_OF_WEEK, + + KEY_APT_ADD_ITEM, + KEY_APT_DEL_ITEM, + KEY_APT_EDIT_ITEM, + KEY_APT_VIEW_ITEM, + KEY_APT_FLAG_ITEM, + KEY_APT_REPEAT, + KEY_APT_MOVE_UP, + KEY_APT_MOVE_DOWN, + KEY_APT_EDIT_NOTE, + KEY_APT_VIEW_NOTE, + + KEY_TODO_ADD_ITEM, + KEY_TODO_DEL_ITEM, + KEY_TODO_EDIT_ITEM, + KEY_TODO_VIEW_ITEM, + KEY_TODO_RAISE_PRIORITY, + KEY_TODO_LOWER_PRIORITY, + KEY_TODO_MOVE_UP, + KEY_TODO_MOVE_DOWN, + KEY_TODO_EDIT_NOTE, + KEY_TODO_VIEW_BOTE, + + KEY_CONFIG_QUIT, + KEY_CONFIG_GENERAL_MENU, + KEY_CONFIG_LAYOUT_MENU, + KEY_CONFIG_COLOR_MENU, + KEY_CONFIG_NOTIFY_MENU, + + NOKEYS + } +keys_e; + +char *keys_get_label (keys_e); + +#endif /* CALCURSE_KEYS_H */ -- cgit v1.2.3-54-g00ecf