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