File indexing completed on 2024-03-24 15:17:31
0001 /* 0002 ** Author: Eric Veach, July 1994. 0003 ** 0004 */ 0005 0006 #ifndef __dict_list_h_ 0007 #define __dict_list_h_ 0008 0009 /* Use #define's so that another heap implementation can use this one */ 0010 0011 #define DictKey DictListKey 0012 #define Dict DictList 0013 #define DictNode DictListNode 0014 0015 #define dictNewDict(frame, leq) __gl_dictListNewDict(frame, leq) 0016 #define dictDeleteDict(dict) __gl_dictListDeleteDict(dict) 0017 0018 #define dictSearch(dict, key) __gl_dictListSearch(dict, key) 0019 #define dictInsert(dict, key) __gl_dictListInsert(dict, key) 0020 #define dictInsertBefore(dict, node, key) __gl_dictListInsertBefore(dict, node, key) 0021 #define dictDelete(dict, node) __gl_dictListDelete(dict, node) 0022 0023 #define dictKey(n) __gl_dictListKey(n) 0024 #define dictSucc(n) __gl_dictListSucc(n) 0025 #define dictPred(n) __gl_dictListPred(n) 0026 #define dictMin(d) __gl_dictListMin(d) 0027 #define dictMax(d) __gl_dictListMax(d) 0028 0029 typedef void *DictKey; 0030 typedef struct Dict Dict; 0031 typedef struct DictNode DictNode; 0032 0033 Dict *dictNewDict(void *frame, int (*leq)(void *frame, DictKey key1, DictKey key2)); 0034 0035 void dictDeleteDict(Dict *dict); 0036 0037 /* Search returns the node with the smallest key greater than or equal 0038 * to the given key. If there is no such key, returns a node whose 0039 * key is NULL. Similarly, Succ(Max(d)) has a NULL key, etc. 0040 */ 0041 DictNode *dictSearch(Dict *dict, DictKey key); 0042 DictNode *dictInsertBefore(Dict *dict, DictNode *node, DictKey key); 0043 void dictDelete(Dict *dict, DictNode *node); 0044 0045 #define __gl_dictListKey(n) ((n)->key) 0046 #define __gl_dictListSucc(n) ((n)->next) 0047 #define __gl_dictListPred(n) ((n)->prev) 0048 #define __gl_dictListMin(d) ((d)->head.next) 0049 #define __gl_dictListMax(d) ((d)->head.prev) 0050 #define __gl_dictListInsert(d, k) (dictInsertBefore((d), &(d)->head, (k))) 0051 0052 /*** Private data structures ***/ 0053 0054 struct DictNode 0055 { 0056 DictKey key; 0057 DictNode *next; 0058 DictNode *prev; 0059 }; 0060 0061 struct Dict 0062 { 0063 DictNode head; 0064 void *frame; 0065 int (*leq)(void *frame, DictKey key1, DictKey key2); 0066 }; 0067 0068 #endif