ReactOS  0.4.13-dev-241-g63286c6
hash.c
Go to the documentation of this file.
1 /* hash.c
2 
3  Routines for manipulating hash tables... */
4 
5 /*
6  * Copyright (c) 1995, 1996, 1997, 1998 The Internet Software Consortium.
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  * 3. Neither the name of The Internet Software Consortium nor the names
19  * of its contributors may be used to endorse or promote products derived
20  * from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
23  * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
24  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
25  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
26  * DISCLAIMED. IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
27  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
30  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
31  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
33  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34  * SUCH DAMAGE.
35  *
36  * This software has been written for the Internet Software Consortium
37  * by Ted Lemon <mellon@fugue.com> in cooperation with Vixie
38  * Enterprises. To learn more about the Internet Software Consortium,
39  * see ``http://www.vix.com/isc''. To learn more about Vixie
40  * Enterprises, see ``http://www.vix.com''.
41  */
42 
43 #define lint
44 #ifndef lint
45 static char copyright[] =
46 "$Id: hash.c,v 1.9.2.3 1999/04/09 17:39:41 mellon Exp $ Copyright (c) 1995, 1996, 1997, 1998 The Internet Software Consortium. All rights reserved.\n";
47 #endif /* not lint */
48 
49 #include <rosdhcp.h>
50 
51 static __inline int do_hash PROTO ((unsigned char *, int, int));
52 
53 struct hash_table *new_hash ()
54 {
56  if (!rv)
57  return rv;
58  memset (&rv -> buckets [0], 0,
59  DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *));
60  return rv;
61 }
62 
63 static __inline int do_hash (name, len, size)
64  unsigned char *name;
65  int len;
66  int size;
67 {
68  register int accum = 0;
69  register unsigned char *s = name;
70  int i = len;
71  while (i--) {
72  /* Add the character in... */
73  accum += *s++;
74  /* Add carry back in... */
75  while (accum > 255) {
76  accum = (accum & 255) + (accum >> 8);
77  }
78  }
79  return accum % size;
80 }
81 
83  struct hash_table *table;
84  int len;
85  unsigned char *name;
86  unsigned char *pointer;
87 {
88  int hashno;
89  struct hash_bucket *bp;
90 
91  if (!table)
92  return;
93  if (!len)
94  len = strlen ((char *)name);
95 
96  hashno = do_hash (name, len, table -> hash_count);
97  bp = new_hash_bucket ();
98 
99  if (!bp) {
100  warn ("Can't add %s to hash table.", name);
101  return;
102  }
103  bp -> name = name;
104  bp -> value = pointer;
105  bp -> next = table -> buckets [hashno];
106  bp -> len = len;
107  table -> buckets [hashno] = bp;
108 }
109 
111  struct hash_table *table;
112  int len;
113  unsigned char *name;
114 {
115  int hashno;
116  struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
117 
118  if (!table)
119  return;
120  if (!len)
121  len = strlen ((char *)name);
122 
123  hashno = do_hash (name, len, table -> hash_count);
124 
125  /* Go through the list looking for an entry that matches;
126  if we find it, delete it. */
127  for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
128  if ((!bp -> len &&
129  !strcmp ((char *)bp -> name, (char *)name)) ||
130  (bp -> len == len &&
131  !memcmp (bp -> name, name, len))) {
132  if (pbp) {
133  pbp -> next = bp -> next;
134  } else {
135  table -> buckets [hashno] = bp -> next;
136  }
137  free_hash_bucket (bp, "delete_hash_entry");
138  break;
139  }
140  pbp = bp; /* jwg, 9/6/96 - nice catch! */
141  }
142 }
143 
144 unsigned char *hash_lookup (table, name, len)
145  struct hash_table *table;
146  unsigned char *name;
147  int len;
148 {
149  int hashno;
150  struct hash_bucket *bp;
151 
152  if (!table)
153  return (unsigned char *)0;
154 
155  if (!len)
156  len = strlen ((char *)name);
157 
158  hashno = do_hash (name, len, table -> hash_count);
159 
160  for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
161  if (len == bp -> len && !memcmp (bp -> name, name, len))
162  return bp -> value;
163  }
164  return (unsigned char *)0;
165 }
struct hash_bucket * buckets[DEFAULT_HASH_SIZE]
Definition: dhcpd.h:270
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
#define warn(...)
char copyright[]
Definition: main.c:27
ACPI_SIZE strlen(const char *String)
Definition: utclib.c:269
GLsizei const GLvoid * pointer
Definition: glext.h:5848
void delete_hash_entry(struct hash_table *table, unsigned char *name, int len)
Definition: hash.c:110
struct hash_table * new_hash_table(int count)
Definition: alloc.c:57
struct hash_table * new_hash()
Definition: hash.c:53
GLenum GLsizei GLenum GLenum const GLvoid * table
Definition: glext.h:5644
#define DEFAULT_HASH_SIZE
Definition: dhcpd.h:259
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
unsigned char * hash_lookup(struct hash_table *table, unsigned char *name, int len)
Definition: hash.c:144
GLsizeiptr size
Definition: glext.h:5919
static __inline int do_hash(unsigned char *name, int len, int size)
Definition: hash.c:63
void free_hash_bucket(struct hash_bucket *ptr, char *name)
Definition: alloc.c:89
GLenum GLsizei len
Definition: glext.h:6722
GLdouble s
Definition: gl.h:2039
GLsizei const GLfloat * value
Definition: glext.h:6069
static unsigned __int64 next
Definition: rand_nt.c:6
void add_hash(struct hash_table *table, unsigned char *name, int len, unsigned char *pointer)
Definition: hash.c:82
static __inline int do_hash PROTO((unsigned char *, int, int))
Definition: name.c:36
int strcmp(const char *String1, const char *String2)
Definition: utclib.c:469
struct hash_bucket * new_hash_bucket(void)
Definition: alloc.c:71
#define memset(x, y, z)
Definition: compat.h:39
GLuint const GLchar * name
Definition: glext.h:6031